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

DOI10.1215/00127094-2008-048MaRDI QIDQ953967zbMATH OpenOpenAlexFDO

Authors Yuval Peres, Scott Sheffield

Publication date 7 November 2008

Published in Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0607761

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Nonlinear elliptic equations (35J60) Combinatorial games (91A46) Probabilistic games; gambling (91A60)

Abstract: Fix a bounded domain Omega in R^d, a continuous function F on the boundary of Omega, and constants epsilon>0, p>1, and q>1 with p^{-1} + q^{-1} = 1. For each x in Omega, let u^epsilon(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 of length at most epsilon 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 on the boundary of Omega, and player I's payoff is F(y). We show that (for sufficiently regular Omega) as epsilon tends to zero the functions u^epsilon converge uniformly to the unique p-harmonic extension of F. Using a modified game (in which epsilon gets smaller as the game position approaches the boundary), we prove similar statements for general bounded domains Omega and resolutive functions F. These games and their variants interpolate between the tug of war games studied by Peres, Schramm, Sheffield, and Wilson (p=infinity) 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.

Recommendations

• Noisy tug of war games for the $p$-Laplacian: 1 < p < $\infty$
• Tug-of-war games with varying probabilities and the normalized \(p(x)\)-Laplacian
• Game theoretical methods in PDEs
• Gradient walks and \(p\)-harmonic functions
• Tug-of-war and the infinity Laplacian

Cites work

• scientific article; zbMATH DE number 988850 (Why is no real title available?)
• scientific article; zbMATH DE number 3875656 (Why is no real title available?)
• scientific article; zbMATH DE number 201036 (Why is no real title available?)
• scientific article; zbMATH DE number 902750 (Why is no real title available?)
• scientific article; zbMATH DE number 233055 (Why is no real title available?)
• A deterministic‐control‐based approach motion by curvature
• A tour of the theory of absolutely minimizing functions
• Balancing games
• C1 + α local regularity of weak solutions of degenerate elliptic equations
• Finitely additive stochastic games with Borel measurable payoffs
• On the equivalence of viscosity solutions and weak solutions for a quasi-linear equation
• Random-Turn Hex and Other Selection Games
• Regularity for a more general class of quasilinear equations
• The determinacy of Blackwell games
• The infinity Laplacian, Aronsson's equation and their generalizations
• Tug-of-war and the infinity Laplacian
• Two-dimensional Brownian motion and harmonic functions
• \(p\)-harmonic measure is not additive on null sets

Cited in

(only showing first 100 items - show all)

• The sublinear problem for the 1-homogeneous 𝑝-Laplacian
• Tug-of-war with Kolmogorov
• The behavior at infinity of \(p\)-harmonic measure in an infinite slab
• Limits as \(p(x)\rightarrow \infty \) of \(p(x)\)-harmonic functions
• Asymptotics for the resolvent equation associated to the game-theoretic \(p\)-Laplacian
• Obstacle problems for integro-differential operators with partially vanishing kernels
• Asymptotic \(C^{1,\gamma}\)-regularity for value functions to uniformly elliptic dynamic programming principles
• Estimates for nonlinear harmonic measures on trees
• The expected time to end the tug-of-war in a wedge
• Asymptotically optimal strategies for online prediction with history-dependent experts
• Asymptotic Lipschitz regularity for tug-of-war games with varying probabilities
• A scheme for the game \(p\)-Laplacian and its application to image inpainting
• Nonlocal PDEs on graphs: from tug-of-war games to unified interpolation on images and point clouds
• Short-time behavior for game-theoretic \(p\)-caloric functions
• A deterministic-control-based approach to fully nonlinear parabolic and elliptic equations
• p-hyperbolicity of ends and families of paths in metric spaces
• A basic homogenization problem for the \(p\)-Laplacian in \(\mathbb{R}^d\) perforated along a sphere: \(L^\infty\) estimates
• A deterministic game interpretation for fully nonlinear parabolic equations with dynamic boundary conditions
• A game theoretical approximation for a parabolic/elliptic system with different operators
• On the definition and properties of \(p\)-harmonious functions
• Asymptotic mean value formulas for parabolic nonlinear equations
• How I met the normalized \(p\)-Laplacian \(\Delta_p^N\) and what we know now about mean values and concavity properties
• A new \(p\)-harmonic map flow with Struwe monotonicity
• Prediction with expert advice: a PDE perspective
• Discrete approximations to the double-obstacle problem and optimal stopping of tug-of-war games
• The obstacle problem for the \(p\)-Laplacian via optimal stopping of tug-of-war games
• Equivalence of viscosity and weak solutions for the normalized \(p(x)\)-Laplacian
• The Gelfand problem for the 1-homogeneous \(p\)-Laplacian
• On the first eigenvalue of the normalized \(p\)-Laplacian
• A control problem related to the parabolic dominative \(p\)-Laplace equation
• Introduction to random tug-of-war games and PDEs
• Monotone iterations of two obstacle problems with different operators
• Local regularity estimates for general discrete dynamic programming equations
• On a new singular and degenerate extension of the \(p\)-Laplace operator
• Tug-of-war games with varying probabilities and the normalized \(p(x)\)-Laplacian
• On the \(p\)-Laplacian and \(\infty\)-Laplacian on graphs with applications in image and data processing
• Solutions of nonlinear PDEs in the sense of averages
• Hessian estimates for equations involving \(p\)-Laplacian via a fundamental inequality
• Gradient and Lipschitz estimates for tug-of-war-type games
• Regularity for quasi-linear parabolic equations with nonhomogeneous degeneracy or singularity
• Local Lipschitz regularity for functions satisfying a time-dependent dynamic programming principle
• The limit as p for the eigenvalue problem of the 1-homogeneous p-Laplacian
• Hölder regularity for the gradient of the inhomogeneous parabolic normalized \(p\)-Laplacian
• A nonlinear mean value property for the Monge-Ampère operator
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
• Mean value property for \(p\)-harmonic functions
• Noisy tug of war games for the $p$-Laplacian: 1 < p < $\infty$
• Introduction: Big data and partial differential equations
• The boundary Harnack inequality for variable exponent p-Laplacian, Carleson estimates, barrier functions and p()-harmonic measures
• Hölder gradient regularity for the inhomogeneous normalized \(p(x)\)-Laplace equation
• Gradient walks and \(p\)-harmonic functions
• Mean value properties for p-harmonic functions for higher dimensions
• Game-theoretic p-Laplace operator involving the gradient
• Hölder regularity for stochastic processes with bounded and measurable increments
• An obstacle problem arising in large exponent limit of power mean curvature flow equation
• Non-local gradient dependent operators
• Equivalence between radial solutions of different parabolic gradient-diffusion equations and applications
• Waiting time effect for motion by positive second derivatives and applications
• Superposition operators between Sobolev spaces and a non-existence result of higher-order regular solutions for the \(p\)-Laplacian
• Jacobian determinants for nonlinear gradient of planar \(\infty \)-harmonic functions and applications
• The first nontrivial eigenvalue for a system of \(p\)-Laplacians with Neumann and Dirichlet boundary conditions
• scientific article; zbMATH DE number 7487854 (Why is no real title available?)
• Game-theoretic approach to Hölder regularity for PDEs involving eigenvalues of the Hessian
• The Robin mean value equation. II: Asymptotic Hölder regularity
• The limit as \({p\to\infty}\) in the eigenvalue problem for a system of \(p\)-Laplacians
• On mild solutions of the p-Laplacian fractional Langevin equations with anti-periodic type boundary conditions
• Geometric gradient estimates for fully nonlinear models with non-homogeneous degeneracy and applications
• The tug-of-war without noise and the infinity Laplacian in a wedge
• Gradient Hölder regularity for parabolic normalized \(p(x,t)\)-Laplace equation
• A game-theoretic approach to dynamic boundary problems for level-set curvature flow equations and applications
• Hölder gradient estimates for parabolic homogeneous \(p\)-Laplacian equations
• Gradient continuity estimates for the normalized p-Poisson equation
• Obstacle problems and maximal operators
• Local regularity for time-dependent tug-of-war games with varying probabilities
• A priori Hölder and Lipschitz regularity for generalized \(p\)-harmonious functions in metric measure spaces
• Random walks and random tug of war in the Heisenberg group
• A weighted eigenvalue problem of the biased infinity Laplacian
• A game theoretical approach for a nonlinear system driven by elliptic operators
• On the Aleksandrov-Bakelman-Pucci estimate for the infinity Laplacian
• \(p\)-harmonic functions with boundary data having jump discontinuities and Baernstein's problem
• Asymptotic mean-value formulas for solutions of general second-order elliptic equations
• The eigenvalue problem for a class of degenerate operators related to the normalized \(p\)-Laplacian
• Maximal operators for the \(p\)-Laplacian family
• The limit as \(p(x)\rightarrow \infty \) of solutions to the inhomogeneous Dirichlet problem of the \(p(x)\)-Laplacian
• Time-dependent tug-of-war games and normalized parabolic p-Laplace equations
• An obstacle problem for tug-of-war games
• Asymptotic mean value properties for the \(p\)-Laplacian
• p(x)-harmonic functions with unbounded exponent in a subdomain
• Phragmén-Lindelöf theorems and p-harmonic measures for sets near low-dimensional hyperplanes
• Parabolic biased infinity Laplacian equation related to the biased tug-of-war
• An asymptotic mean value characterization for \(p\)-harmonic functions
• Harnack's Inequality forp-Harmonic Functions via Stochastic Games
• A game theoretical approximation for solutions to nonlinear systems with obstacle-type equations
• General existence of solutions to dynamic programming equations
• Mean value properties and unique continuation
• Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History‐Dependent Experts
• Improved regularity for the parabolic normalized \(p\)-Laplace equation
• Analysis on an HDG method for the p-Laplacian equations
• Game theoretical methods in PDEs

This page was built for publication: Tug-of-war with noise: a game-theoretic view of the \(p\)-Laplacian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q953967)