Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A finite difference approach to the infinity Laplace equation and tug-of-war games

Authors: Scott N. Armstrong and Charles K. Smart
Journal: Trans. Amer. Math. Soc. 364 (2012), 595-636
MSC (2000): Primary 35J70, 91A15
Published electronically: September 14, 2011
MathSciNet review: 2846345
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a modified version of the two-player ``tug-of-war'' game introduced by Peres, Schramm, Sheffield, and Wilson (2009). This new tug-of-war game is identical to the original except near the boundary of the domain $ \partial \Omega$, but its associated value functions are more regular. The dynamic programming principle implies that the value functions satisfy a certain finite difference equation. By studying this difference equation directly and adapting techniques from viscosity solution theory, we prove a number of new results.

We show that the finite difference equation has unique maximal and minimal solutions, which are identified as the value functions for the two tug-of-war players. We demonstrate uniqueness, and hence the existence of a value for the game, in the case that the running payoff function is nonnegative. We also show that uniqueness holds in certain cases for sign-changing running payoff functions which are sufficiently small. In the limit $ \varepsilon \to 0$, we obtain the convergence of the value functions to a viscosity solution of the normalized infinity Laplace equation.

We also obtain several new results for the normalized infinity Laplace equation $ -\Delta_\infty u = f$. In particular, we demonstrate the existence of solutions to the Dirichlet problem for any bounded continuous $ f$, and continuous boundary data, as well as the uniqueness of solutions to this problem in the generic case. We present a new elementary proof of uniqueness in the case that $ f>0$, $ f< 0$, or $ f\equiv 0$. The stability of the solutions with respect to $ f$ is also studied, and an explicit continuous dependence estimate from $ f\equiv 0$ is obtained.

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

  • 1. S. N. Armstrong and C. K. Smart, An easy proof of Jensen's theorem on the uniqueness of infinity harmonic functions, Calc. Var. Partial Differential Equations 37 (2010), 381-384. MR 2592977 (2011b:35144)
  • 2. 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)
  • 3. 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)
  • 4. E. N. Barron, L. C. Evans, and R. Jensen, The infinity Laplacian, Aronsson's equation and their generalizations, Trans. Amer. Math. Soc. 360 (2008), no. 1, 77-101 (electronic). MR 2341994
  • 5. Fernando Charro, Jesus García Azorero, and Julio D. Rossi, A mixed problem for the infinity Laplacian via tug-of-war games, Calc. Var. Partial Differential Equations 34 (2009), no. 3, 307-320. MR 2471139
  • 6. 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)
  • 7. Michael G. Crandall, A visit with the $ \infty$-Laplace equation, Calculus of variations and nonlinear partial differential equations, Lecture Notes in Math., vol. 1927, Springer, Berlin, 2008, pp. 75-122. MR 2408259
  • 8. Michael G. Crandall, Gunnar Gunnarsson, and Peiyong Wang, Uniqueness of $ \infty$-harmonic functions and the eikonal equation, Comm. Partial Differential Equations 32 (2007), no. 10-12, 1587-1615. MR 2372480
  • 9. Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 1-67. MR 1118699 (92j:35050)
  • 10. Lawrence C. Evans, The perturbed test function method for viscosity solutions of nonlinear PDE, Proc. Roy. Soc. Edinburgh Sect. A 111 (1989), no. 3-4, 359-375. MR 1007533 (91c:35017)
  • 11. 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)
  • 12. E. Le Gruyer, On absolutely minimizing Lipschitz extensions and PDE $ \Delta\sb \infty(u)=0$, NoDEA Nonlinear Differential Equations Appl. 14 (2007), no. 1-2, 29-55. MR 2346452 (2008k:35159)
  • 13. Guozhen Lu and Peiyong Wang, Infinity Laplace equation with non-trivial right-hand side, preprint.
  • 14. -, A PDE perspective of the normalized infinity Laplacian, Comm. Partial Differential Equations 33 (2008), no. 10-12, 1788-1817. MR 2475319
  • 15. 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)
  • 16. Yuval Peres, Gábor Pete, and Stephanie Somersille, Biased tug-of-war, the biased infinity Laplacian, and comparison with exponential cones, preprint.
  • 17. Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson, Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc. 22 (2009), no. 1, 167-210. MR 2449057
  • 18. Yifeng Yu, Uniqueness of values of Aronsson operators and running costs in ``tug-of-war'' games, Ann. Inst. H. Poincaré Anal. Non Linéaire 26 (2009), 1299-1308. MR 2542726

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 35J70, 91A15

Retrieve articles in all journals with MSC (2000): 35J70, 91A15

Additional Information

Scott N. Armstrong
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720

Charles K. Smart
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720

Keywords: Infinity Laplace equation, tug-of-war, finite difference approximations
Received by editor(s): July 8, 2009
Published electronically: September 14, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society