Tug-of-war and the infinity Laplacian

Abstract:

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 = |\nabla u|^{-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^{\mathrm {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 $\|u^\varepsilon - u\|_{\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.