Tug-of-war and the infinity Laplacian

We prove that every bounded Lipschitz function $F$ on a subset $Y$ of a length space $X$ admits a tautest extension to $X$, i.e., a unique Lipschitz extension $u:X \rightarrow \mathbb{R}$ for which $\operatorname{Lip}_U u =\operatorname{Lip}_{\partial U} u$ for all open $U \subset X\smallsetminus Y$. This was previously known only for bounded domains in $\mathbb{R}^n$, in which case $u$ is infinity harmonic; that is, a viscosity solution to $\Delta_\infty u = 0$, where

$$\Delta_\infty u = \vert\nabla u\vert^{-2} \sum_{i,j} u_{x_i} u_{x_ix_j} u_{x_j}.$$

We also prove the first general uniqueness results for $\Delta_{\infty} u = g$ on bounded subsets of $\mathbb{R}^n$ (when $g$ is uniformly continuous and bounded away from 0) and analogous results for bounded length spaces. The proofs rely on a new game-theoretic description of $u$. Let $u^\varepsilon(x)$ be the value of the following two-player zero-sum game, called tug-of-war: fix $x_0=x\in X \smallsetminus Y$. At the $k\ensuremath{^{\text{th}}}$ turn, the players toss a coin and the winner chooses an $x_k$ with $d(x_k, x_{k-1})< \varepsilon$. The game ends when $x_k \in Y$, and player I's payoff is $F(x_k) - \frac{\varepsilon^2}{2}\sum_{i=0}^{k-1} g(x_i)$. We show that $\Vert u^\varepsilon- u\Vert _{\infty} \to 0$. Even for bounded domains in $\mathbb{R}^n$, the game theoretic description of infinity harmonic functions yields new intuition and estimates; for instance, we prove power law bounds for infinity harmonic functions in the unit disk with boundary values supported in a $\delta$-neighborhood of a Cantor set on the unit circle.