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

DOI:
https://doi.org/10.1090/S0002-9947-2011-05289-X

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 , 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 , 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 . In particular, we demonstrate the existence of solutions to the Dirichlet problem for any bounded continuous , 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 , , or . The stability of the solutions with respect to is also studied, and an explicit continuous dependence estimate from is obtained.

**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 -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 -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*, 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**

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

Email:
sarm@math.berkeley.edu

**Charles K. Smart**

Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720

Email:
smart@math.berkeley.edu

DOI:
https://doi.org/10.1090/S0002-9947-2011-05289-X

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.