Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

   
 
 

 

Tug-of-war and the infinity Laplacian


Authors: Yuval Peres, Oded Schramm, Scott Sheffield and David B. Wilson
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
Published electronically: July 28, 2008
MathSciNet review: 2449057
Full-text PDF Free Access
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle \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.


References [Enhancements On Off] (What's this?)

  • 1. Gunnar Aronsson, Extension of functions satisfying Lipschitz conditions, Ark. Mat. 6 (1967), 551-561. MR 0217665 (36:754)
  • 2. -, 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. MR 0237962 (38:239)
  • 3. -, 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 (87j:35070)
  • 4. 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 (electronic). MR 2083637 (2005k:35159)
  • 5. 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, 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 C.I.M.E. [C.I.M.E. Foundation]. MR 1462698 (98b:35005)
  • 6. 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 (2002k:35078)
  • 7. T. Bhattacharya, E. DiBenedetto, and J. Manfredi, Limits as $ p\to\infty$ of $ \Delta\sb pu\sb p=f$ and related extremal problems, Rend. Sem. Mat. Univ. Politec. Torino 1989 (1991). Special issue on topics in nonlinear PDEs, 15-68. MR 1155453 (93a:35049)
  • 8. 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
  • 9. 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 (2002h:49048)
  • 10. 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) (San Marcos, TX), Electron. J. Differ. Equ. Conf., vol. 6, Southwest Texas State Univ., 2001, pp. 123-129 (electronic). MR 1804769 (2001j:35076)
  • 11. 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 (85g:35029)
  • 12. 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 (2006g:35062)
  • 13. 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 (94g:35063)
  • 14. Petri Juutinen, Absolutely minimizing Lipschitz extensions on a metric space, Ann. Acad. Sci. Fenn. Math. 27 (2002), no. 1, 57-67. MR 1884349 (2002m:54020)
  • 15. 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 (2001f:91023)
  • 16. Andrew J. Lazarus, Daniel E. Loeb, James G. Propp, and Daniel Ullman, Richman games, Games of No Chance (Richard J. Nowakowski, ed.), MSRI Publications, vol. 29, Cambridge Univ. Press, Cambridge, 1996, pp. 439-449. MR 1427981 (97j:90101)
  • 17. Donald A. Martin, The determinacy of Blackwell games, J. Symbolic Logic 63 (1998), no. 4, 1565-1581. MR 1665779 (2000d:03118)
  • 18. E. J. McShane, Extension of range of functions, Bull. Amer. Math. Soc. 40 (1934), no. 12, 837-842. MR 1562984
  • 19. V. A. Mil$ '$man, Absolutely minimal extensions of functions on metric spaces, Mat. Sb. 190 (1999), no. 6, 83-110. MR 1719573 (2000j:41041)
  • 20. Abraham Neyman and Sylvain Sorin (eds.), Stochastic games and applications, NATO Science Series C: Mathematical and Physical Sciences, vol. 570, Dordrecht, Kluwer Academic Publishers, 2003. MR 2032421 (2004h:91004)
  • 21. 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 (electronic). MR 2137000 (2006h:65165)
  • 22. 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 (2008a:91039)
  • 23. Ovidiu Savin, $ C\sp 1$ regularity for infinity harmonic functions in two dimensions, Arch. Ration. Mech. Anal. 176 (2005), no. 3, 351-361. MR 2185662 (2006i:35108)
  • 24. Hassler Whitney, Analytic extensions of differentiable functions defined in closed sets, Trans. Amer. Math. Soc. 36 (1934), no. 1, 63-89. MR 1501735
  • 25. 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.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 91A15, 91A24, 35J70, 54E35, 49N70

Retrieve articles in all journals with MSC (2000): 91A15, 91A24, 35J70, 54E35, 49N70


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

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

DOI: https://doi.org/10.1090/S0894-0347-08-00606-1
Keywords: Infinity Laplacian, absolutely minimal Lipschitz extension, tug-of-war
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.
Article copyright: © Copyright 2008 by the authors. This paper or any part thereof may be reproduced for non-commercial purposes.

American Mathematical Society