Tug-of-war and the infinity Laplacian
HTML articles powered by AMS MathViewer
- by Yuval Peres, Oded Schramm, Scott Sheffield and David B. Wilson;
- J. Amer. Math. Soc. 22 (2009), 167-210
- DOI: https://doi.org/10.1090/S0894-0347-08-00606-1
- Published electronically: July 28, 2008
- HTML | PDF
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.
Bibliographic 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