Tug-of-war and the infinity Laplacian

Abstract

We prove that every bounded Lipschitz function F on a subset Y of a length space X admits a tautest extension to X, i.e., a unique Lipschitz extension u for which Lip_U u = Lip_{boundary of U} u for all open subsets U of X that do not intersect Y. This was previously known only for bounded domains R^n, in which case u is infinity harmonic, that is, a viscosity solution to Delta_infty u = 0. We also prove the first general uniqueness results for Delta_infty u = g on bounded subsets of R^n (when g is uniformly continuous and bounded away from zero), and analogous results for bounded length spaces. The proofs rely on a new game-theoretic description of u. Let u^epsilon(x) be the value of the following two-player zero-sum game, called tug-of-war: fix x_0=x \in X minus Y. At the kth turn, the players toss a coin and the winner chooses an x_k with d(x_k, x_{k-1})< epsilon. The game ends when x_k is in Y, and player one's payoff is F(x_k) - (epsilon^2/2) sum_{i=0}^{k-1} g(x_i) We show that the u^εconverge uniformly to u as epsilon tends to zero. Even for bounded domains in R^n, the game theoretic description of infinity-harmonic functions yields new intuition and estimates; for instance, we prove power law bounds for infinity-harmonic functions in the unit disk with boundary values supported in a delta-neighborhood of a Cantor set on the unit circle.

44 pages, 4 figures

References in corpus (1)

• Uniqueness of values of Aronsson operators and running costs in "tug-of-war" games

Cited by in corpus (61)

• An easy proof of Jensen's theorem on the uniqueness of infinity harmonic functions
• Parabolic theory of the discrete p-Laplace operator
• Tug-of-war games with varying probabilities and the normalized $p(x)$-Laplacian
• Equivalence of Viscosity and Weak Solutions for the $p(x)$-Laplacian
• p(x)-Harmonic functions with unbounded exponent in a subdomain
• Convergence Properties for the Physarum Solver
• A Neumann problem involving the $p(x)$-Laplacian with $p=\infty$ in a subdomain
• On the Dirichlet and Serrin problems for the inhomogeneous infinity Laplacian in convex domains: Regularity and geometric results
• The evolution problem associated with eigenvalues of the Hessian
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Convexity criteria and uniqueness of absolutely minimizing functions
• Prediction with Expert Advice: a PDE Perspective
• Infinity Laplacian equation with strong absorptions
• Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
• A semi-Lagrangian scheme for the game $p$-Laplacian via $p$-averaging
• On the horizontal Mean Curvature Flow for Axisymmetric surfaces in the Heisenberg Group
• The unique continuation property for a nonlinear equation on trees
• A general theorem of existence of quasi absolutely minimal Lipschitz extensions
• A $C^1$ regularity result for the inhomogeneous normalized infinity Laplacian
• A stochastic differential game for the inhomogeneous $\infty$-Laplace equation
• Uniqueness of values of Aronsson operators and running costs in "tug-of-war" games
• Uniqueness of absolute minimizers for $L^\fz$-functionals involving Hamiltonians $H(x,p)$
• Characterization of stadium-like domains via boundary value problems for the infinity Laplacian
• A game interpretation of the Neumann problem for fully nonlinear parabolic and elliptic equations
• Detecting the completeness of a Finsler manifold via potential theory for its infinity Laplacian
• Infinity Laplacian equations with singular absorptions
• Tug-of-War games and parabolic problems with spatial and time dependence
• Evolution Driven by the Infinity Fractional Laplacian
• Determinacy in Discrete-Bidding Infinite-Duration Games
• Local Lipschitz regularity for functions satisfying a time-dependent dynamic programming principle
• Head and tail speeds of mean curvature flow with forcing
• On a class of quasilinear operators on smooth metric measure spaces
• The Infinity Laplacian eigenvalue problem: reformulation and a numerical scheme
• On the viscosity solutions to a degenerate parabolic differential equation
• The first nontrivial eigenvalue for a system of $p-$Laplacians with Neumann and Dirichlet boundary conditions
• Functions with average smoothness: structure, algorithms, and learning
• On asymptotic expansions for the fractional infinity Laplacian
• Regularity of absolute minimizers for continuous convex Hamiltonians
• An existence result for the infinity laplacian with non-homogeneous Neumann boundary conditions using Tug-of-War games
• Uniform measure density condition and game regularity for tug-of-war games
• A continuous time tug-of-war game for parabolic $p(x,t)$-Laplace type equations
• A quantative Sobolev regularity for absolute minimizers involving Hamiltonian $H(p)\in C^0({\mathbb{R}}^2)$ in plane
• Lipschitz continuity and convexity preserving for solutions of semilinear evolution equations in the Heisenberg group
• Biased infinity Laplacian Boundary Problem on finite graphs
• Systems involving mean value formulas on trees
• Regularity for quasi-linear parabolic equations with nonhomogeneous degeneracy or singularity
• Infinity-Harmonic Potentials and Their Streamlines
• The two membranes problem in a regular tree
• Numerical solution of a PDE arising from prediction with expert advice
• The streamlines of $\infty$-harmonic functions obey the inverse mean curvature flow
• Time-dependent tug-of-war games and normalized parabolic $p$-Laplace equations
• Gradient Holder regularity for parabolic normalized p(x,t)-Laplace equation
• A game theoretical approach for an elliptic system with two different operators (the Laplacian and the infinity Laplacian)
• Totalitarian random Tug-of-War games in graphs
• Non-local tug-of-war with noise for the geometric fractional $p$-Laplacian
• Tug-of-war with noise and an invariance of p-harmonic functions under boundary perturbations
• Boosting with Lexicographic Programming: Addressing Class Imbalance without Cost Tuning
• A control problem related to the parabolic dominative $p$-Laplace equation
• Principal eigenvalue problem for infinity Laplacian in metric spaces
• Some results of the Lipschitz constant of 1-Field on ${\mathbb{R}}^n$
• On $p$-Harmonic Measures in Half Spaces