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

DOI10.1215/00127094-2008-048zbMATH Open1206.35112arXivmath/0607761OpenAlexW1987642543MaRDI QIDQ953967FDOQ953967

Authors: Yuval Peres, Scott Sheffield 

Publication date: 7 November 2008

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

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.

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

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

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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• A nonlinear mean value property for the Monge-Ampère operator
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
• Introduction: Big data and partial differential equations
• Mean value properties for p-harmonic functions for higher dimensions
• Gradient walks and \(p\)-harmonic functions
• Hölder gradient regularity for the inhomogeneous normalized \(p(x)\)-Laplace equation
• An obstacle problem arising in large exponent limit of power mean curvature flow equation
• Hölder regularity for stochastic processes with bounded and measurable increments
• Equivalence between radial solutions of different parabolic gradient-diffusion equations and applications
• Title not available (Why is that?)
• 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
• Gradient continuity estimates for the normalized p-Poisson equation
• A weighted eigenvalue problem of the biased infinity Laplacian
• 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
• Asymptotics for the resolvent equation associated to the game-theoretic p-laplacian
• Time-dependent tug-of-war games and normalized parabolic \(p\)-Laplace equations
• Parabolic biased infinity Laplacian equation related to the biased tug-of-war
• Improved regularity for the parabolic normalized \(p\)-Laplace equation
• Game theoretical methods in PDEs
• Convergence of dynamic programming principles for the \(p\)-Laplacian
• Variational approach to the asymptotic mean-value property for the \(p\)-Laplacian on Carnot groups
• The evolution problem associated with eigenvalues of the Hessian
• A continuous time tug-of-war game for parabolic \(p(x,t)\)-Laplace-type equations
• Convergence of natural \(p\)-means for the \(p\)-Laplacian in the Heisenberg group
• Convergence of the natural \(p\)-means for the \(p\)-Laplacian
• The \(p\)-harmonic measure of small axially symmetric sets
• Eigenvalues for systems of fractional \(p\)-Laplacians
• Variational \(p\)-harmonious functions: existence and convergence to \(p\)-harmonic functions
• A \(hk\) mortar spectral element method for the \(p\)-Laplacian equation
• On the game p-Laplacian on weighted graphs with applications in image processing and data clustering
• Asymptotic Hölder regularity for the ellipsoid process
• Non-local Tug-of-War with noise for the geometric fractional \(p\)-Laplacian
• The behavior at infinity of \(p\)-harmonic measure in an infinite slab
• Tug-of-war with Kolmogorov
• The expected time to end the tug-of-war in a wedge
• Asymptotically optimal strategies for online prediction with history-dependent experts
• 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 game interpretation for fully nonlinear parabolic equations with dynamic boundary conditions
• A game theoretical approximation for a parabolic/elliptic system with different operators
• How I met the normalized \(p\)-Laplacian \(\Delta_p^N\) and what we know now about mean values and concavity properties
• Prediction with expert advice: a PDE perspective
• On the first eigenvalue of the normalized \(p\)-Laplacian
• The Gelfand problem for the 1-homogeneous \(p\)-Laplacian
• A control problem related to the parabolic dominative \(p\)-Laplace equation
• Local regularity estimates for general discrete dynamic programming equations
• Hessian estimates for equations involving \(p\)-Laplacian via a fundamental inequality
• Regularity for quasi-linear parabolic equations with nonhomogeneous degeneracy or singularity
• Local Lipschitz regularity for functions satisfying a time-dependent dynamic programming principle
• Noisy tug of war games for the $p$-Laplacian: 1 < p < $\infty$
• Game-theoretic p-Laplace operator involving the gradient
• Jacobian determinants for nonlinear gradient of planar \(\infty \)-harmonic functions and applications
• Game-theoretic approach to Hölder regularity for PDEs involving eigenvalues of the Hessian
• The Robin mean value equation. II: Asymptotic Hölder regularity
• On mild solutions of the p-Laplacian fractional Langevin equations with anti-periodic type boundary conditions
• 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
• Semiconvexity of viscosity solutions to fully nonlinear evolution equations via discrete games
• Borderline gradient continuity for the normalized \(p\)-parabolic operator
• The Robin mean value equation. I: A random walk approach to the third boundary value problem
• \(C^{1, \alpha}\)-regularity for functions in solution classes and its application to parabolic normalized \(p\)-Laplace equations
• Asymptotic mean value properties for the elliptic and parabolic double phase equations
• NONLINEAR MEAN-VALUE FORMULAS ON FRACTAL SETS
• Games associated with products of eigenvalues of the Hessian
• Short-time asymptotics for game-theoretic \(p\)-Laplacian and Pucci operators
• Games for the two membranes problem
• Obstacle problems for integro-differential operators with partially vanishing kernels
• Asymptotic \(C^{1,\gamma}\)-regularity for value functions to uniformly elliptic dynamic programming principles
• A scheme for the game \(p\)-Laplacian and its application to image inpainting
• A basic homogenization problem for the \(p\)-Laplacian in \(\mathbb{R}^d\) perforated along a sphere: \(L^\infty\) estimates
• Asymptotic mean value formulas for parabolic nonlinear equations
• A new \(p\)-harmonic map flow with Struwe monotonicity
• Monotone iterations of two obstacle problems with different operators
• On a new singular and degenerate extension of the \(p\)-Laplace operator
• The limit as \(p\rightarrow \infty \) for the eigenvalue problem of the 1-homogeneous \(p\)-Laplacian
• Mean value property for \(p\)-harmonic functions
• The boundary Harnack inequality for variable exponent \(p\)-Laplacian, Carleson estimates, barrier functions and \(p(\cdot)\)-harmonic measures
• Non-local gradient dependent operators
• 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
• The first nontrivial eigenvalue for a system of \(p\)-Laplacians with Neumann and Dirichlet boundary conditions
• The limit as \({p\to\infty}\) in the eigenvalue problem for a system of \(p\)-Laplacians
• 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
• Random walks and random tug of war in the Heisenberg group
• Obstacle problems and maximal operators
• Local regularity for time-dependent tug-of-war games with varying probabilities
• A game theoretical approach for a nonlinear system driven by elliptic operators
• A priori Hölder and Lipschitz regularity for generalized \(p\)-harmonious functions in metric measure spaces
• On the Aleksandrov-Bakelman-Pucci estimate for the infinity Laplacian
• \(p\)-harmonic functions with boundary data having jump discontinuities and Baernstein's problem
• Maximal operators for the \(p\)-Laplacian family
• An obstacle problem for tug-of-war games
• Harnack's Inequality forp-Harmonic Functions via Stochastic Games
• The limit as \(p(x)\rightarrow \infty \) of solutions to the inhomogeneous Dirichlet problem of the \(p(x)\)-Laplacian
• An asymptotic mean value characterization for \(p\)-harmonic functions
• Asymptotic mean value properties for the \(p\)-Laplacian

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)