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
• 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
• \(p(x)\)-harmonic functions with unbounded exponent in a subdomain
• A game theoretical approximation for solutions to nonlinear systems with obstacle-type equations
• Phragmén-Lindelöf theorems and \(p\)-harmonic measures for sets near low-dimensional hyperplanes
• General existence of solutions to dynamic programming equations
• Mean value properties and unique continuation
• Analysis on an HDG method for the \(p\)-Laplacian equations
• On the horizontal mean curvature flow for axisymmetric surfaces in the Heisenberg group
• The behaviour of the \(p(x)\)-Laplacian eigenvalue problem as \(p(x)\rightarrow \infty \)
• The behavior of solutions to an elliptic equation involving a \(p\)-Laplacian and a \(q\)-Laplacian for large \(p\)
• Non-convex Hamilton-Jacobi equations with gradient constraints
• A mixed problem for the infinity Laplacian via tug-of-war games
• \(C^{1,\alpha}\) regularity for the normalized \(p\)-Poisson problem
• Hölder gradient estimates for a class of singular or degenerate parabolic equations
• \(p\)-harmonic functions by way of intrinsic mean value properties
• A semi-Lagrangian scheme for the game \(p\)-Laplacian via \(p\)-averaging
• The Cauchy problem for the fast \(p\)-Laplacian evolution equation. Characterization of the global Harnack principle and fine asymptotic behaviour
• Regularity for nonlinear stochastic games
• A finite difference approach to the infinity Laplace equation and tug-of-war games
• A hybridizable discontinuous Galerkin method for the \(p\)-Laplacian
• An inhomogeneous evolution equation involving the normalized infinity Laplacian with a transport term
• Statistical exponential formulas for homogeneous diffusion
• A New Proof for the Equivalence of Weak and Viscosity Solutions for thep-Laplace Equation
• Finite difference methods for the infinity Laplace and \(p\)-Laplace equations
• Dynamic programming principle for tug-of-war games with noise
• An Anisotropic infinity Laplacian obtained as the limit of the anisotropic \((p, q)\)-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)