Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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
Published electronically: July 28, 2008
MathSciNet review: 2449057
Full-text PDF

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?)


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: http://dx.doi.org/10.1090/S0894-0347-08-00606-1
PII: S 0894-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.