{
  "id": "math/0605002",
  "version": "v2",
  "published": "2006-04-28T21:42:00.000Z",
  "updated": "2008-03-31T22:06:42.000Z",
  "title": "Tug-of-war and the infinity Laplacian",
  "authors": [
    "Yuval Peres",
    "Oded Schramm",
    "Scott Sheffield",
    "David B. Wilson"
  ],
  "comment": "44 pages, 4 figures",
  "journal": "Journal of the American Mathematical Society 22(1):167--210, 2009",
  "doi": "10.1090/S0894-0347-08-00606-1",
  "categories": [
    "math.AP",
    "math.MG",
    "math.OC",
    "math.PR"
  ],
  "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^\\epsilon 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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-03-31T22:06:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A15",
      "91A24",
      "35J70",
      "54E35",
      "49N70"
    ],
    "keywords": [
      "infinity laplacian",
      "tug-of-war",
      "first general uniqueness results",
      "length space",
      "two-player zero-sum game"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "AMS",
      "journal": "Journal of the American Mathematical Society",
      "year": 2009,
      "month": "Jan",
      "volume": 22,
      "number": 1,
      "pages": 167
    },
    "note": {
      "typesetting": "TeX",
      "pages": 44,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "inspire": 738889,
      "adsabs": "2009JAMS...22..167P"
    }
  }
}