Tug-of-war and the infinity Laplacian

By Yuval Peres, Oded Schramm, Scott Sheffield, David Bruce Wilson. 2006

475 citations recorded by the source corpus.

We consider a class of zero-sum two-player stochastic games called tug-of-war and use them to prove that every bounded real-valued Lipschitz function F on a subset Y of a length space X admits a unique absolutely minimal (AM) extension to X, i.e., a unique Lipschitz extension u : X → ℝ for which Lip U u = Lip ∂u u for all open U ⊂ X \ Y.

Subfields: Applied Mathematics, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/d43b5794103774753cadd1329810049b2d9a315c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Control and Systems Engineering

Citations in the corpus

A finite difference approach to the infinity Laplace equation and tug-of-war games (2009, methodology): “This is indeed the case for certain running payoff functions f , as was shown in [18].”
Dynamic Programming Principle for tug-of-war games with noise (2012, unknown): “To be more precise, Le Gruyer proved in [1], see also [9], that a uniform limit of a sequence of harmonious functions when ε → 0 is a solution to Δ∞u = 0, where Δ∞u = |∇u|−2 ∑ ij uxiuxixj uxj = |∇u|−2 〈D2u∇u,∇u〉”
Vector‐valued optimal Lipschitz extensions (2010, methodology): “It was shown in [17] that if G is finite then every g : Y → R has a unique extension u : X → R that is discrete infinity harmonic on X \ Y .”
Solutions of nonlinear PDEs in the sense of averages (2012, background): “There are several ways in the literature, see for example [6], [9], and [23], to resolve this difficulty.”
Inhomogeneous infinity Laplace equation (2008, background): “Assuming the uniqueness of solutions of the Dirichlet problem which is proved in Section 3, we can see that no classical solution to the Dirichlet problem with the same continuous boundary data exists.”
The infinity Laplacian, Aronsson’s equation and their generalizations (2008, background): “Within the last year Peres, Schramm, Sheffield and Wilson in [P-S-S-W], [S] have shown that the infinity Laplace equation is solved by the value function for a random turn “tug–of–war” game, in which the two players at each step flip a fair coin to determine the order of play.”
An asymptotic mean value characterization for p-harmonic functions (2010, methodology): “[12]) to find p-harmonic functions as limits of values of Tug-of-War games.”
A mixed problem for the infinity Laplacian via Tug-of-War games (2007, methodology): “However, when ΓD 6= ∂Ω the PDE problem (1) is incomplete, since there is a missing boundary condition on ΓN = ∂Ω \ ΓD.”
On the evolution governed by the infinity Laplacian (2006, background): “Moreover, a time dependent version of the tug-of-war game of Peres, Schramm, Sheffield and Wilson [28] leads to the backward-in-time version of (1.”
Nonlocal Tug‐of‐War and the Infinity Fractional Laplacian (2010, background): “, [12], introduced and studied a class of two-player differential games called “tug-of-war”.”
Harnack's Inequality for p-Harmonic Functions via Stochastic Games (2012, methodology): “In the nonlinear case, a connection of the tug-of-war game to so called infinity harmonic functions was established by Peres, Schramm, Sheffield and Wilson in [PSSW09], see also [LA98], [Obe05], and [LeG07].”
A deterministic‐control‐based approach to fully nonlinear parabolic and elliptic equations (2010, methodology): “(d) For the infinity-Laplacian, the Dirichlet problem can be solved using a rather simple two-person stochastic game [32] (see also [6, 17, 26, 33, 37, 38] for related work including extensions to evolution problems and the p-Laplacian).”
On the definition and properties of p-harmonious functions (2012, methodology): “By adapting the martingale methods used in [8], we prove a comparison principle.”
Everywhere differentiability of infinity harmonic functions (2011, unknown): “[10]).”