Tug-of-war and the infinity Laplacian

Peres, Yuval¹ ; Schramm, Oded² ; Sheffield, Scott^1, 3 ; Wilson, David²

¹ Microsoft Research, One Microsoft Way, Redmond, Washington 98052, and Department of Statistics, 367 Evans Hall, University of California, Berkeley, California 94720
² Microsoft Research, One Microsoft Way, Redmond, Washington 98052
³ Courant Institute, 251 Mercer Street, New York, New York 10012

Journal of the American Mathematical Society, Tome 22 (2009) no. 1, pp. 167-210

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-08-00606-1

Bibliographie

[1] Aronsson, Gunnar Extension of functions satisfying Lipschitz conditions Ark. Mat. 1967

[2] Aronsson, Gunnar On the partial differential equation 𝑢ₓ²𝑢ₓₓ+2𝑢ₓ𝑢_{𝑦}𝑢_{𝑥𝑦}+𝑢_{𝑦}²𝑢_{𝑦𝑦} Ark. Mat. 1968

[3] Aronsson, Gunnar Construction of singular solutions to the 𝑝-harmonic equation and its limit equation for 𝑝 Manuscripta Math. 1986 135 158

[4] Aronsson, Gunnar, Crandall, Michael G., Juutinen, Petri A tour of the theory of absolutely minimizing functions Bull. Amer. Math. Soc. (N.S.) 2004 439 505

[5] Bardi, M., Crandall, M. G., Evans, L. C., Soner, H. M., Souganidis, P. E. Viscosity solutions and applications 1997

[6] Barles, G., Busca, Jã©Rã´Me Existence and comparison results for fully nonlinear degenerate elliptic equations without zeroth-order term Comm. Partial Differential Equations 2001 2323 2337

[7] Bhattacharya, T., Dibenedetto, E., Manfredi, J. Limits as 𝑝→∞ of Δ_{𝑝}𝑢_{𝑝} Rend. Sem. Mat. Univ. Politec. Torino 1989

[8] Champion, Thierry, De Pascale, Luigi Principles of comparison with distance functions for absolute minimizers J. Convex Anal. 2007 515 541

[9] Crandall, M. G., Evans, L. C., Gariepy, R. F. Optimal Lipschitz extensions and the infinity Laplacian Calc. Var. Partial Differential Equations 2001 123 139

[10] Crandall, Michael G., Evans, L. C. A remark on infinity harmonic functions 2001 123 129

[11] Crandall, Michael G., Lions, Pierre-Louis Viscosity solutions of Hamilton-Jacobi equations Trans. Amer. Math. Soc. 1983 1 42

[12] Evans, Lawrence C., Yu, Yifeng Various properties of solutions of the infinity-Laplacian equation Comm. Partial Differential Equations 2005 1401 1428

[13] Jensen, Robert Uniqueness of Lipschitz extensions: minimizing the sup norm of the gradient Arch. Rational Mech. Anal. 1993 51 74

[14] Juutinen, Petri Absolutely minimizing Lipschitz extensions on a metric space Ann. Acad. Sci. Fenn. Math. 2002 57 67

[15] Lazarus, Andrew J., Loeb, Daniel E., Propp, James G., Stromquist, Walter R., Ullman, Daniel H. Combinatorial games under auction play Games Econom. Behav. 1999 229 264

[16] Lazarus, Andrew J., Loeb, Daniel E., Propp, James G., Ullman, Daniel Richman games 1996 439 449

[17] Martin, Donald A. The determinacy of Blackwell games J. Symbolic Logic 1998 1565 1581

[18] Mcshane, E. J. Extension of range of functions Bull. Amer. Math. Soc. 1934 837 842

[19] Mil′Man, V. A. Absolutely minimal extensions of functions on metric spaces Mat. Sb. 1999 83 110

[20] Stochastic games and applications 2003

[21] Oberman, Adam M. A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions Math. Comp. 2005 1217 1230

[22] Peres, Yuval, Schramm, Oded, Sheffield, Scott, Wilson, David B. Random-turn hex and other selection games Amer. Math. Monthly 2007 373 387

[23] Savin, Ovidiu 𝐶¹ regularity for infinity harmonic functions in two dimensions Arch. Ration. Mech. Anal. 2005 351 361

[24] Whitney, Hassler Analytic extensions of differentiable functions defined in closed sets Trans. Amer. Math. Soc. 1934 63 89