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

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.**Scott N. Armstrong and Charles K. Smart,*An easy proof of Jensen’s theorem on the uniqueness of infinity harmonic functions*, Calc. Var. Partial Differential Equations**37**(2010), no. 3-4, 381–384. MR**2592977**, 10.1007/s00526-009-0267-9**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. MR**2083637**, 10.1090/S0273-0979-04-01035-3**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**, 10.1081/PDE-100107824**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. MR**2341994**, 10.1090/S0002-9947-07-04338-3**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**, 10.1007/s00526-008-0185-2**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****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**, 10.1007/978-3-540-75914-0_3**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**, 10.1080/03605300601088807**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**, 10.1090/S0273-0979-1992-00266-5**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**, 10.1017/S0308210500018631**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**, 10.1007/BF00386368**12.**E. Le Gruyer,*On absolutely minimizing Lipschitz extensions and PDE Δ_{∞}(𝑢)=0*, NoDEA Nonlinear Differential Equations Appl.**14**(2007), no. 1-2, 29–55. MR**2346452**, 10.1007/s00030-006-4030-z**13.**Guozhen Lu and Peiyong Wang,*Infinity Laplace equation with non-trivial right-hand side*, preprint.**14.**Guozhen Lu and Peiyong Wang,*A PDE perspective of the normalized infinity Laplacian*, Comm. Partial Differential Equations**33**(2008), no. 10-12, 1788–1817. MR**2475319**, 10.1080/03605300802289253**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**, 10.1090/S0025-5718-04-01688-6**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**, 10.1090/S0894-0347-08-00606-1**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), no. 4, 1299–1308. MR**2542726**, 10.1016/j.anihpc.2008.11.001

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:
http://dx.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.