Tug-of-war with noise: A game-theoretic view of the $p$-Laplacian

By Yuval Peres, Scott Sheffield. 2006

267 citations recorded by the source corpus.

Fix a bounded domain Ω ⊂ Rd, a continuous function F : ∂Ω → R, and constants ǫ > 0 and 1 < p, q < ∞ with p−1 + q−1 = 1. For each x ∈ Ω, let uǫ(x) be the value for player I of the following two-player, zero-sum game. The initial game position is x. At each stage, a fair coin is tossed and the player who wins the toss chooses a vector v ∈ B(0, ǫ) to add to the game position, after which a random “noise vector” with mean zero and variance q p |v| 2 in each orthogonal direction is also added. The game ends when the game position reaches some y ∈ ∂Ω, and player I’s payoff is F (y). We show that (for sufficiently regular Ω) as ǫ tends to zero the functions uǫ converge uniformly to the unique p-harmonic extension of F . Using a modified game (in which ǫ gets smaller as the game position approaches ∂Ω), we prove similar statements for general bounded domains Ω and resolutive functions F . These games and their variants interpolate between the tug of war games studied by Peres, Schramm, Sheffield, and Wilson (p = ∞) and the motion-by-curvature games introduced by Spencer and studied by Kohn and Serfaty (p = 1). They generalize the relationship between Brownian motion and the ordinary Laplacian and yield new results about p-capacity and p-harmonic measure.

Subfields: Applied Mathematics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/50372d387400b8d3b4df402548dd7d5767521b22

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 Computational Theory and Mathematics

Citations in the corpus

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 [39] (see also [1, 2, 8, 22, 34, 40, 46, 47] for related work including extensions to evolution problems and the p-Laplacian).”
Solutions of nonlinear PDEs in the sense of averages (2012, background): “It appears to be more complicated, but in the context of the tug-of-war game similar to that in [PS08] it turns out to be quite natural.”
Harnack's Inequality for p-Harmonic Functions via Stochastic Games (2012, methodology): “uniform positive probability before exiting a larger ball. This result is based on the use of the fundamental solution to the p-Laplace equation and an iteration argument, see Proposition 1.1 (ii) in [PS08]. The proof can be modiﬁed for the version of the game considered in this paper, and thus we h”
Dynamic Programming Principle for tug-of-war games with noise (2012, background): “This game was studied in a slightly different form by Peres and Sheffield in [9], and the tug-of-war game by Peres, Schramm, Sheffield, and Wilson in [8].”
A New Proof for the Equivalence of Weak and Viscosity Solutions for the p-Laplace Equation (2011, methodology): “The equivalence has turned out to be a very useful tool in certain removability questions, see [7, 13], as well as in the analysis of various approximations of the p-Laplace equation see [4, 11, 12].”
An asymptotic mean value characterization for p-harmonic functions (2010, methodology): “This formal expansion was used by Peres and Sheffield in [13] (see also Peres et al.”
On the definition and properties of p-harmonious functions (2012, methodology): “The proof utilizes some ideas from [9] but does not explicitly employ probabilistic tools.”