## Tug-of-war and the infinity Laplacian

HTML articles powered by AMS MathViewer

- by
Yuval Peres, Oded Schramm, Scott Sheffield and David B. Wilson
**HTML**| PDF - J. Amer. Math. Soc.
**22**(2009), 167-210

## 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.

## References

- Gunnar Aronsson,
*Extension of functions satisfying Lipschitz conditions*, Ark. Mat.**6**(1967), 551β561 (1967). MR**217665**, DOI 10.1007/BF02591928 - Gunnar Aronsson,
*On the partial differential equation $u_{x}{}^{2}\!u_{xx} +2u_{x}u_{y}u_{xy}+u_{y}{}^{2}\!u_{yy}=0$*, Ark. Mat.**7**(1968), 395β425 (1968). MR**237962**, DOI 10.1007/BF02590989 - Gunnar Aronsson,
*Construction of singular solutions to the $p$-harmonic equation and its limit equation for $p=\infty$*, Manuscripta Math.**56**(1986), no.Β 2, 135β158. MR**850366**, DOI 10.1007/BF01172152 - Gunnar Aronsson, Michael G. Crandall, and Petri Juutinen,
*A tour of the theory of absolutely minimizing functions*, Bull. Amer. Math. Soc. (N.S.)**41**(2004), no.Β 4, 439β505. MR**2083637**, DOI 10.1090/S0273-0979-04-01035-3 - M. Bardi, M. G. Crandall, L. C. Evans, H. M. Soner, and P. E. Souganidis,
*Viscosity solutions and applications*, Lecture Notes in Mathematics, vol. 1660, Springer-Verlag, Berlin; Centro Internazionale Matematico Estivo (C.I.M.E.), Florence, 1997. Lectures given at the 2nd C.I.M.E. Session held in Montecatini Terme, June 12β20, 1995; Edited by I. Capuzzo Dolcetta and P. L. Lions; Fondazione CIME/CIME Foundation Subseries. MR**1462698**, DOI 10.1007/BFb0094293 - G. Barles and JΓ©rΓ΄me Busca,
*Existence and comparison results for fully nonlinear degenerate elliptic equations without zeroth-order term*, Comm. Partial Differential Equations**26**(2001), no.Β 11-12, 2323β2337. MR**1876420**, DOI 10.1081/PDE-100107824 - T. Bhattacharya, E. DiBenedetto, and J. Manfredi,
*Limits as $p\to \infty$ of $\Delta _pu_p=f$ and related extremal problems*, Rend. Sem. Mat. Univ. Politec. Torino**Special Issue**(1989), 15β68 (1991). Some topics in nonlinear PDEs (Turin, 1989). MR**1155453** - Thierry Champion and Luigi De Pascale,
*Principles of comparison with distance functions for absolute minimizers*, J. Convex Anal.**14**(2007), no.Β 3, 515β541. MR**2341302** - M. G. Crandall, L. C. Evans, and R. F. Gariepy,
*Optimal Lipschitz extensions and the infinity Laplacian*, Calc. Var. Partial Differential Equations**13**(2001), no.Β 2, 123β139. MR**1861094**, DOI 10.1007/s005260000065 - Michael G. Crandall and L. C. Evans,
*A remark on infinity harmonic functions*, Proceedings of the USA-Chile Workshop on Nonlinear Analysis (ViΓ±a del Mar-Valparaiso, 2000) Electron. J. Differ. Equ. Conf., vol. 6, Southwest Texas State Univ., San Marcos, TX, 2001, pp.Β 123β129. MR**1804769** - Michael G. Crandall and Pierre-Louis Lions,
*Viscosity solutions of Hamilton-Jacobi equations*, Trans. Amer. Math. Soc.**277**(1983), no.Β 1, 1β42. MR**690039**, DOI 10.1090/S0002-9947-1983-0690039-8 - Lawrence C. Evans and Yifeng Yu,
*Various properties of solutions of the infinity-Laplacian equation*, Comm. Partial Differential Equations**30**(2005), no.Β 7-9, 1401β1428. MR**2180310**, DOI 10.1080/03605300500258956 - Robert Jensen,
*Uniqueness of Lipschitz extensions: minimizing the sup norm of the gradient*, Arch. Rational Mech. Anal.**123**(1993), no.Β 1, 51β74. MR**1218686**, DOI 10.1007/BF00386368 - Petri Juutinen,
*Absolutely minimizing Lipschitz extensions on a metric space*, Ann. Acad. Sci. Fenn. Math.**27**(2002), no.Β 1, 57β67. MR**1884349** - Andrew J. Lazarus, Daniel E. Loeb, James G. Propp, Walter R. Stromquist, and Daniel H. Ullman,
*Combinatorial games under auction play*, Games Econom. Behav.**27**(1999), no.Β 2, 229β264. MR**1685133**, DOI 10.1006/game.1998.0676 - Andrew J. Lazarus, Daniel E. Loeb, James G. Propp, and Daniel Ullman,
*Richman games*, Games of no chance (Berkeley, CA, 1994) Math. Sci. Res. Inst. Publ., vol. 29, Cambridge Univ. Press, Cambridge, 1996, pp.Β 439β449. MR**1427981**, DOI 10.2977/prims/1195167051 - Donald A. Martin,
*The determinacy of Blackwell games*, J. Symbolic Logic**63**(1998), no.Β 4, 1565β1581. MR**1665779**, DOI 10.2307/2586667 - E. J. McShane,
*Extension of range of functions*, Bull. Amer. Math. Soc.**40**(1934), no.Β 12, 837β842. MR**1562984**, DOI 10.1090/S0002-9904-1934-05978-0 - V. A. Milβ²man,
*Absolutely minimal extensions of functions on metric spaces*, Mat. Sb.**190**(1999), no.Β 6, 83β110 (Russian, with Russian summary); English transl., Sb. Math.**190**(1999), no.Β 5-6, 859β885. MR**1719573**, DOI 10.1070/SM1999v190n06ABEH000409 - Abraham Neyman and Sylvain Sorin (eds.),
*Stochastic games and applications*, NATO Science Series C: Mathematical and Physical Sciences, vol. 570, Kluwer Academic Publishers, Dordrecht, 2003. MR**2032421**, DOI 10.1007/978-94-010-0189-2 - Adam M. Oberman,
*A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions*, Math. Comp.**74**(2005), no.Β 251, 1217β1230. MR**2137000**, DOI 10.1090/S0025-5718-04-01688-6 - Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson,
*Random-turn hex and other selection games*, Amer. Math. Monthly**114**(2007), no.Β 5, 373β387. MR**2309980**, DOI 10.1080/00029890.2007.11920428 - Ovidiu Savin,
*$C^1$ regularity for infinity harmonic functions in two dimensions*, Arch. Ration. Mech. Anal.**176**(2005), no.Β 3, 351β361. MR**2185662**, DOI 10.1007/s00205-005-0355-8 - Hassler Whitney,
*Analytic extensions of differentiable functions defined in closed sets*, Trans. Amer. Math. Soc.**36**(1934), no.Β 1, 63β89. MR**1501735**, DOI 10.1090/S0002-9947-1934-1501735-3
YifengYu Yifeng Yu,

*Uniqueness of values of Aronsson operators and applications to βtug-of-warβ game theory*, 2007, http://www.ma.utexas.edu/$^{\sim }$yifengyu/uofa2d.pdf.

## Additional Information

**Yuval Peres**- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052, and Department of Statistics, 367 Evans Hall, University of California, Berkeley, California 94720
- MR Author ID: 137920
**Oded Schramm**- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
**Scott Sheffield**- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052, and Department of Statistics, 367 Evans Hall, University of California, Berkeley, California 94720
- Address at time of publication: Courant Institute, 251 Mercer Street, New York, New York 10012
**David B. Wilson**- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
- Received by editor(s): July 11, 2006
- Published electronically: July 28, 2008
- Additional Notes: Research of the first and third authors was supported in part by NSF grants DMS-0244479 and DMS-0104073.
- © Copyright 2008 by the authors. This paper or any part thereof may be reproduced for non-commercial purposes.
- Journal: J. Amer. Math. Soc.
**22**(2009), 167-210 - MSC (2000): Primary 91A15, 91A24, 35J70, 54E35, 49N70
- DOI: https://doi.org/10.1090/S0894-0347-08-00606-1
- MathSciNet review: 2449057