American Mathematical Society

Tug-of-war and the infinity Laplacian

By Yuval Peres, Oded Schramm, Scott Sheffield, David B. Wilson

Abstract

We prove that every bounded Lipschitz function upper F on a subset upper Y of a length space upper X admits a tautest extension to upper X , i.e., a unique Lipschitz extension u colon upper X right-arrow double-struck upper R for which upper L i p Subscript upper U Baseline u equals upper L i p Subscript partial-differential upper U Baseline u for all open upper U subset-of upper X minus upper Y . This was previously known only for bounded domains in double-struck upper R Superscript n , in which case u is infinity harmonic; that is, a viscosity solution to normal upper Delta Subscript normal infinity Baseline u equals 0 , where

normal upper Delta Subscript normal infinity Baseline u equals StartAbsoluteValue nabla u EndAbsoluteValue Superscript negative 2 Baseline sigma-summation Underscript i comma j Endscripts u Subscript x Sub Subscript i Subscript Baseline u Subscript x Sub Subscript i Subscript x Sub Subscript j Subscript Baseline u Subscript x Sub Subscript j Subscript Baseline period

We also prove the first general uniqueness results for normal upper Delta Subscript normal infinity Baseline u equals g on bounded subsets of double-struck upper R Superscript n (when g is uniformly continuous and bounded away from 0 ) and analogous results for bounded length spaces. The proofs rely on a new game-theoretic description of u . Let u Superscript epsilon Baseline left-parenthesis x right-parenthesis be the value of the following two-player zero-sum game, called tug-of-war: fix x 0 equals x element-of upper X minus upper Y . At the k Superscript th turn, the players toss a coin and the winner chooses an x Subscript k with d left-parenthesis x Subscript k Baseline comma x Subscript k minus 1 Baseline right-parenthesis less-than epsilon . The game ends when x Subscript k Baseline element-of upper Y , and player I’s payoff is upper F left-parenthesis x Subscript k Baseline right-parenthesis minus StartFraction epsilon squared Over 2 EndFraction sigma-summation Underscript i equals 0 Overscript k minus 1 Endscripts g left-parenthesis x Subscript i Baseline right-parenthesis . We show that double-vertical-bar u Superscript epsilon Baseline minus u double-vertical-bar Subscript normal infinity Baseline right-arrow 0 . Even for bounded domains in double-struck upper R Superscript 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.

1. Introduction and preliminaries

1.1. Overview

We consider a class of zero-sum two-player stochastic games called tug-of-war and use them to prove that every bounded real-valued Lipschitz function upper F on a subset upper Y of a length space upper X admits a unique absolutely minimal (AM) extension to upper X , i.e., a unique Lipschitz extension u colon upper X right-arrow double-struck upper R for which upper L i p Subscript upper U Baseline u equals upper L i p Subscript partial-differential upper U Baseline u for all open upper U subset-of upper X minus upper Y . We present an example that shows this is not generally true when upper F is merely Lipschitz and positive. (Recall that a metric space left-parenthesis upper X comma d right-parenthesis is a length space if for all x comma y element-of upper X , the distance d left-parenthesis x comma y right-parenthesis is the infimum of the lengths of continuous paths in upper X that connect x to y . Length spaces are more general than geodesic spaces, where the infima need to be achieved.)

When upper X is the closure of a bounded domain upper U subset-of double-struck upper R Superscript n and upper Y is its boundary, a Lipschitz extension u of upper F is AM if and only it is infinity harmonic in the interior of upper X minus upper Y ; i.e., it is a viscosity solution (defined below) to normal upper Delta Subscript normal infinity Baseline u equals 0 , where normal upper Delta Subscript normal infinity is the so-called infinity Laplacian

StartLayout 1st Row with Label left-parenthesis 1.1 right-parenthesis EndLabel normal upper Delta Subscript normal infinity Baseline u equals StartAbsoluteValue nabla u EndAbsoluteValue Superscript negative 2 Baseline sigma-summation Underscript i comma j Endscripts u Subscript x Sub Subscript i Baseline u Subscript x Sub Subscript i Subscript x Sub Subscript j Baseline u Subscript x Sub Subscript j EndLayout

(informally, this is the second derivative of u in the direction of the gradient of u ). Aronsson proved this equivalence for smooth u in 1967, and Jensen proved the general statement in 1993 Reference1Reference13. Our analysis of tug-of-war also shows that in this setting normal upper Delta Subscript normal infinity Baseline u equals g has a unique viscosity solution (extending upper F ) when g colon upper U overbar right-arrow double-struck upper R is continuous and inf g greater-than 0 or sup g less-than 0 , but not necessarily when g assumes values of both signs. We note that in the study of the homogenous equation normal upper Delta Subscript normal infinity Baseline u equals 0 , the normalizing factor StartAbsoluteValue nabla u EndAbsoluteValue Superscript negative 2 in (Equation1.1) is sometimes omitted; however, it is important to include it in the non-homogenous equation. Observe that with the normalization, normal upper Delta Subscript normal infinity coincides with the ordinary Laplacian normal upper Delta in the one-dimensional case.

Unlike the ordinary Laplacian or the p -Laplacian for p less-than normal infinity , the infinity Laplacian can be defined on any length space with no additional structure (such as a measure or a canonical Markov semigroup)—that is, we will see that viscosity solutions to normal upper Delta Subscript normal infinity Baseline u equals g are well defined in this generality. We will establish the above stated uniqueness of solutions u to normal upper Delta Subscript normal infinity Baseline u equals g in the setting of length spaces.

Originally, we were motivated not by the infinity Laplacian but by random turn Hex Reference22 and its generalizations, which led us to consider the tug-of-war game. As we later learned, tug-of-war games have been considered by Lazarus, Loeb, Propp and Ullman in Reference16 (see also Reference15).

Tug-of-war on a metric space is very natural and conceivably applicable (like differential game theory) to economic and political modeling.

The intuition provided by thinking of strategies for tug-of-war yields new results even in the classical setting of domains in double-struck upper R Superscript n . For instance, in Section 4 we show that if u is infinity harmonic in the unit disk and its boundary values are in left-bracket 0 comma 1 right-bracket and supported on a delta -neighborhood of the ternary Cantor set on the unit circle, then u left-parenthesis 0 right-parenthesis less-than delta Superscript beta for some beta greater-than 0 .

Before precisely stating our main results, we need several definitions.

1.2. Random turn games and values

We consider two-player, zero-sum random-turn games, which are defined by the following parameters: a set upper X of states of the game, two directed transition graphs upper E Subscript normal upper I Baseline comma upper E Subscript normal upper I normal upper I Baseline with vertex set upper X , a non-empty set upper Y subset-of upper X of terminal states (a.k.a. absorbing states), a terminal payoff function upper F colon upper Y right-arrow double-struck upper R , a running payoff function f colon upper X minus upper Y right-arrow double-struck upper R , and an initial state x 0 element-of upper X .

The game play is as follows: a token is initially placed at position x 0 . At the k Superscript th step of the game, a fair coin is tossed, and the player who wins the toss may move the token to any x Subscript k for which left-parenthesis x Subscript k minus 1 Baseline comma x Subscript k Baseline right-parenthesis is a directed edge in her transition graph. The game ends the first time x Subscript k Baseline element-of upper Y , and player I’s payoff is upper F left-parenthesis x Subscript k Baseline right-parenthesis plus sigma-summation Underscript i equals 0 Overscript k minus 1 Endscripts f left-parenthesis x Subscript i Baseline right-parenthesis . Player I seeks to maximize this payoff, and since the game is zero-sum, player II seeks to minimize it.

We will use the term tug-of-war (on the graph with edges upper E ) to describe the game in which upper E colon equals upper E Subscript normal upper I Baseline equals upper E Subscript normal upper I normal upper I (i.e., players have identical move options) and upper E is undirected (i.e., all moves are reversible). Generally, our results pertain only to the undirected setting. Occasionally, we will also mention some counterexamples showing that the corresponding results do not hold in the directed case.

In the most conventional version of tug-of-war on a graph, upper Y is a union of “target sets” upper Y Superscript normal upper I and upper Y Superscript normal upper I normal upper I , there is no running payoff ( f equals 0 ), and upper F is identically 1 on upper Y Superscript normal upper I and identically 0 on upper Y Superscript normal upper I normal upper I . Players then try to “tug” the game token to their respective targets (and away from their opponent’s targets), and the game ends when a target is reached.

A strategy for a player is a way of choosing the player’s next move as a function of all previously played moves and all previous coin tosses. It is a map from the set of partially played games to moves (or in the case of a random strategy, a probability distribution on moves). Normally, one would think of a good strategy as being Markovian, i.e., as a map from the current state to the next move, but it is useful to allow more general strategies that take into account the history.

Given two strategies script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline , let upper F Subscript minus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis and upper F Subscript plus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis be the expected total payoff (including the running payoffs received) at the termination of the game, if the game terminates with probability one and this expectation exists in left-bracket negative normal infinity comma normal infinity right-bracket ; otherwise, let upper F Subscript minus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis equals negative normal infinity and upper F Subscript plus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis equals plus normal infinity .

The value of the game for player I is defined as sup Underscript script upper S Subscript normal upper I Endscripts inf Underscript script upper S Subscript normal upper I normal upper I Endscripts upper F Subscript minus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis . The value for player II is inf Underscript script upper S Subscript normal upper I normal upper I Endscripts sup Underscript script upper S Subscript normal upper I Endscripts upper F Subscript plus Baseline left-parenthesis script upper S Subscript normal upper I Baseline comma script upper S Subscript normal upper I normal upper I Baseline right-parenthesis . We use the expressions u Subscript normal upper I Baseline left-parenthesis x right-parenthesis and u Subscript normal upper I normal upper I Baseline left-parenthesis x right-parenthesis to denote the values for players I and II, respectively, as a function of the starting state x of the game.

Note that if player I cannot force the game to end almost surely, then u Subscript normal upper I Baseline equals negative normal infinity , and if player II cannot force the game to end almost surely, then u Subscript normal upper I normal upper I Baseline equals normal infinity . Clearly, u Subscript normal upper I Baseline left-parenthesis x right-parenthesis less-than-or-equal-to u Subscript normal upper I normal upper I Baseline left-parenthesis x right-parenthesis . When u Subscript normal upper I Baseline left-parenthesis x right-parenthesis equals u Subscript normal upper I normal upper I Baseline left-parenthesis x right-parenthesis , we say that the game has a value, given by u left-parenthesis x right-parenthesis colon equals u Subscript normal upper I Baseline left-parenthesis x right-parenthesis equals u Subscript normal upper I normal upper I Baseline left-parenthesis x right-parenthesis .

Our definition of value for player I penalizes player I severely for not forcing the game to terminate with probability one, awarding negative normal infinity in this case.

(As an alternative definition, one could define upper F Subscript minus , and hence player I’s value, by assigning payoffs to all of the non-terminating sequences x 0 comma x 1 comma x 2 comma period period period . If the payoff function for the non-terminating games is a zero-sum Borel-measurable function of the infinite sequence, then player I’s value is equal to player II’s value in great generality Reference17; see also Reference20 for more on stochastic games. The existence of a value by our strong definition implies the existence and equality of the values defined by these alternative definitions.)

Considering the two possibilities for the first coin toss yields the following lemma, a variant of which appears in Reference16.

Lemma 1.1

The function u equals u Subscript normal upper I satisfies the equation

StartLayout 1st Row with Label left-parenthesis 1.2 right-parenthesis EndLabel u left-parenthesis x right-parenthesis equals one-half left-parenthesis sup Underscript y colon left-parenthesis x comma y right-parenthesis element-of upper E 1 Endscripts u left-parenthesis y right-parenthesis plus inf Underscript y colon left-parenthesis x comma y right-parenthesis element-of upper E 2 Endscripts u left-parenthesis y right-parenthesis right-parenthesis plus f left-parenthesis x right-parenthesis EndLayout

for every non-terminal state x element-of upper X minus upper Y for which the right-hand side is well defined, and u Subscript normal upper I Baseline left-parenthesis x right-parenthesis equals negative normal infinity when the right-hand side is of the form one-half left-parenthesis normal infinity plus left-parenthesis negative normal infinity right-parenthesis right-parenthesis plus f left-parenthesis x right-parenthesis . The analogous statement holds for u Subscript normal upper I normal upper I , except that u Subscript normal upper I normal upper I Baseline left-parenthesis x right-parenthesis equals plus normal infinity when the right-hand side of Equation1.2 is of the form one-half left-parenthesis normal infinity plus left-parenthesis negative normal infinity right-parenthesis right-parenthesis plus f left-parenthesis x right-parenthesis .

When upper E equals upper E 1 equals upper E 2 , the operator

normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis colon equals sup Underscript y colon left-parenthesis x comma y right-parenthesis element-of upper E Endscripts u left-parenthesis y right-parenthesis plus inf Underscript y colon left-parenthesis x comma y right-parenthesis element-of upper E Endscripts u left-parenthesis y right-parenthesis minus 2 u left-parenthesis x right-parenthesis

is called the (discrete) infinity Laplacian. A function u is infinity harmonic if Equation1.2 holds and f left-parenthesis x right-parenthesis equals 0 at all non-terminal x element-of upper X minus upper Y . When u is finite, this is equivalent to normal upper Delta Subscript normal infinity Baseline u equals 0 . However, it will be convenient to adopt the convention that u is infinity harmonic at x if u left-parenthesis x right-parenthesis equals plus normal infinity (resp. negative normal infinity ) and the right-hand side in Equation1.2 is also plus normal infinity (resp. negative normal infinity ). Similarly, it will be convenient to say “ u is a solution to normal upper Delta Subscript normal infinity Baseline u equals minus 2 f at x if u left-parenthesis x right-parenthesis equals plus normal infinity (resp. negative normal infinity ) and the right-hand side in Equation1.2 is also plus normal infinity (resp. negative normal infinity ).

In a tug-of-war game, it is natural to guess that the value u equals u Subscript normal upper I Baseline equals u Subscript normal upper I normal upper I exists and is the unique solution to

normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis equals minus 2 f comma

and also that (at least when upper E is locally finite) player I’s optimal strategy will be to always move to the vertex that maximizes u left-parenthesis x right-parenthesis and that player II’s optimal strategy will be to always move to the vertex that minimizes u left-parenthesis x right-parenthesis . This is easy to prove when upper E is undirected and finite and f is everywhere positive or everywhere negative. Subtleties arise in more general cases ( upper X infinite, upper E directed, upper F unbounded, f having values of both signs, etc.).

Our first theorem addresses the question of the existence of a value.

Theorem 1.2

A tug-of-war game with parameters upper X comma upper E comma upper Y comma upper F comma f has a value whenever the following hold:

(1)

Either f equals 0 everywhere or inf f greater-than 0 .

(2)

inf upper F greater-than negative normal infinity .

(3)

upper E is undirected.

Counterexamples exist when any one of the three criteria is removed. In Section 5 (a section devoted to counterexamples) we give an example of a tug-of-war game without a value, where upper E is undirected, upper F equals 0 , and the running payoff satisfies f greater-than 0 but inf f equals 0 .

The case where f equals 0 , upper F is bounded, and left-parenthesis upper X comma upper E right-parenthesis is locally finite was proved earlier in Reference15. That paper discusses an (essentially non-random) game in which the two players bid for the right to choose the next move. That game, called the Richman game, has the same value as tug-of-war with f equals 0 , where upper F takes the values 0 and 1 . Additionally, a simple and efficient algorithm for calculating the value when f equals 0 and left-parenthesis upper X comma upper E right-parenthesis is finite is presented there.

1.3. Tug-of-war on a metric space

Now consider the special case where left-parenthesis upper X comma d right-parenthesis is a metric space, upper Y subset-of upper X , and Lipschitz functions upper F colon upper Y right-arrow double-struck upper R and f colon upper X minus upper Y right-arrow double-struck upper R are given. Let upper E Subscript epsilon be the edge-set in which x tilde y if and only if d left-parenthesis x comma y right-parenthesis less-than epsilon , and let u Superscript epsilon be the value (if it exists) of the game played on upper E Subscript epsilon with terminal payoff upper F and running payoff normalized to be epsilon squared f .

In other words, u Superscript epsilon Baseline left-parenthesis x right-parenthesis is the value of the following two-player zero-sum game, called epsilon -tug-of-war: fix x 0 equals x element-of upper X minus upper Y . At the k Superscript th turn, the players toss a coin and the winner chooses an x Subscript k with d left-parenthesis x Subscript k Baseline comma x Subscript k minus 1 Baseline right-parenthesis less-than epsilon . The game ends when x Subscript k Baseline element-of upper Y , and player I’s payoff is upper F left-parenthesis x Subscript k Baseline right-parenthesis plus epsilon squared sigma-summation Underscript i equals 0 Overscript k minus 1 Endscripts f left-parenthesis x Subscript i Baseline right-parenthesis .

When the limit u colon equals limit Underscript epsilon right-arrow 0 Endscripts u Superscript epsilon exists pointwise, we call u the continuum value (or just “value”) of the quintuple left-parenthesis upper X comma d comma upper Y comma upper F comma f right-parenthesis . We define the continuum value for player I (or II) analogously.

The reader may wonder why we have chosen not to put an edge in upper E Subscript epsilon between x and y when d left-parenthesis x comma y right-parenthesis equals epsilon exactly. This choice has some technical implications. Specifically, we will compare the epsilon -game with the 2 epsilon -game. If x comma z are such that d left-parenthesis x comma z right-parenthesis less-than-or-equal-to 2 epsilon , then in a length space it does not follow that there is a y such that d left-parenthesis x comma y right-parenthesis less-than-or-equal-to epsilon and d left-parenthesis y comma z right-parenthesis less-than-or-equal-to epsilon . However, it does follow if you replace the weak inequalities with strong inequalities throughout.

We prove the following:

Theorem 1.3

Suppose upper X is a length space, upper Y subset-of upper X is non-empty, upper F colon upper Y right-arrow double-struck upper R is bounded below and has an extension to a uniformly continuous function on upper X , and either f colon upper X minus upper Y right-arrow double-struck upper R satisfies f equals 0 or all three of the following hold: inf StartAbsoluteValue f EndAbsoluteValue greater-than 0 , f is uniformly continuous, and upper X has finite diameter. Then the continuum value u exists and is a uniformly continuous function extending upper F . Furthermore, double-vertical-bar u minus u Superscript epsilon Baseline double-vertical-bar Subscript normal infinity Baseline right-arrow 0 as epsilon down right-arrow 0 . If upper F is Lipschitz, then so is u . If upper F and f are Lipschitz, then double-vertical-bar u minus u Superscript epsilon Baseline double-vertical-bar Subscript normal infinity Baseline equals upper O left-parenthesis epsilon right-parenthesis .

The above condition that upper F colon upper Y right-arrow double-struck upper R extends to a uniformly continuous function on upper X is equivalent to having upper F uniformly continuous on upper Y and “Lipschitz on large scales,” as we prove in Lemma 3.9 below.

We will see in Section 5.1 that this fails in general when f greater-than 0 but inf f equals 0 . When f assumes values of both signs, it fails even when upper X is a closed disk in double-struck upper R squared , upper Y is its boundary and upper F equals 0 . In Section 5.3 we show by means of an example that in such circumstances it may happen that u Subscript normal upper I Baseline Superscript epsilon Baseline not-equals u Subscript normal upper I normal upper I Baseline Superscript epsilon and moreover, limit inf double-vertical-bar u Subscript normal upper I Baseline Superscript epsilon Baseline minus u Subscript normal upper I normal upper I Baseline Superscript epsilon Baseline double-vertical-bar Subscript normal infinity Baseline greater-than 0 .

1.4. Absolutely minimal Lipschitz extensions

Given a metric space left-parenthesis upper X comma d right-parenthesis , a subset upper Y subset-of upper X and a function u colon upper X right-arrow double-struck upper R , we write

upper L i p Subscript upper Y Baseline u equals sup Underscript x comma y element-of upper Y Endscripts StartAbsoluteValue u left-parenthesis y right-parenthesis minus u left-parenthesis x right-parenthesis EndAbsoluteValue slash d left-parenthesis x comma y right-parenthesis

and upper L i p u equals upper L i p Subscript upper X Baseline u . Thus u is Lipschitz iff upper L i p u less-than normal infinity . Given upper F colon upper Y right-arrow double-struck upper R , we say that u colon upper X right-arrow double-struck upper R is a minimal extension of upper F if upper L i p Subscript upper X Baseline u equals upper L i p Subscript upper Y Baseline upper F and u left-parenthesis y right-parenthesis equals upper F left-parenthesis y right-parenthesis for all y element-of upper Y .

It is well known that for any metric space upper X , any Lipschitz upper F on a subset upper Y of upper X admits a minimal extension. The largest and smallest minimal extensions (introduced by McShane Reference18 and Whitney Reference24 in the 1930’s) are respectively

inf Underscript y element-of upper Y Endscripts left-bracket upper F left-parenthesis y right-parenthesis plus upper L i p Subscript upper Y Baseline upper F d left-parenthesis x comma y right-parenthesis right-bracket and sup Underscript y element-of upper Y Endscripts left-bracket upper F left-parenthesis y right-parenthesis minus upper L i p Subscript upper Y Baseline upper F d left-parenthesis x comma y right-parenthesis right-bracket period

We say u is an absolutely minimal (AM) extension of upper F if upper L i p u less-than normal infinity and upper L i p Subscript upper U Baseline u equals upper L i p Subscript partial-differential upper U Baseline u for every open set upper U subset-of upper X minus upper Y . We say that u is AM on upper U if it is defined on upper U overbar and is an AM extension of its restriction to partial-differential upper U . AM extensions were first introduced by Aronsson in 1967 Reference1 and have applications in engineering and image processing (see Reference4 for a recent survey).

We prove the following:

Theorem 1.4

Let upper X be a length space and let upper F colon upper Y right-arrow double-struck upper R be Lipschitz, where normal empty-set not-equals upper Y subset-of upper X . If inf upper F greater-than negative normal infinity , then the continuum value function u described in Theorem 1.3 (with f equals 0 ) is an AM extension of upper F . If upper F is also bounded, then u is the unique AM extension of upper F .

We present in the counterexample section, Section 5, an example in which upper F is Lipschitz, non-negative, and unbounded, and although the continuum value is an AM extension, it is not the only AM extension.

Prior to our work, the existence of AM extensions in the above settings was known only for separable length spaces Reference14 (see also Reference19). The uniqueness in Theorem 1.4 was known only in the case that upper X is the closure of a bounded domain upper U subset-of double-struck upper R Superscript n and upper Y equals partial-differential upper U . (To deduce this case from Theorem 1.4, one needs to replace upper X by the smallest closed ball containing upper U overbar , say.) Three uniqueness proofs in this setting have been published, by Jensen Reference13, by Barles and Busca Reference6, and by Aronsson, Crandall, and Juutinen Reference4. The third proof generalizes from the Euclidean norm to uniformly convex norms.

Our proof applies to more general spaces because it invokes no outside theorems from analysis (which assume existence of a local Euclidean geometry, a measure, a notion of twice differentiability, etc.), and relies only on the structure of upper X as a length space.

As noted in Reference4, AM extensions do not generally exist on metric spaces that are not length spaces. (For example, if upper X is the upper L -shaped region StartSet 0 EndSet times left-bracket 0 comma 1 right-bracket union left-bracket 0 comma 1 right-bracket times StartSet 0 EndSet subset-of double-struck upper R squared with the Euclidean metric, and upper Y equals StartSet left-parenthesis 0 comma 1 right-parenthesis comma left-parenthesis 1 comma 0 right-parenthesis EndSet , then no non-constant upper F colon upper Y right-arrow double-struck upper R has an AM extension. Indeed, suppose that u colon upper X right-arrow double-struck upper R is an AM extension of upper F colon upper Y right-arrow double-struck upper R . Let a colon equals u left-parenthesis 0 comma 0 right-parenthesis , b colon equals u left-parenthesis 0 comma 1 right-parenthesis and c colon equals u left-parenthesis 1 comma 0 right-parenthesis . Then, considering upper U equals StartSet 0 EndSet times left-parenthesis 0 comma 1 right-parenthesis , it follows that u left-parenthesis 0 comma s right-parenthesis equals a plus s left-parenthesis b minus a right-parenthesis . Likewise, u left-parenthesis s comma 0 right-parenthesis equals a plus s left-parenthesis c minus a right-parenthesis . Now taking upper U Subscript epsilon Baseline colon equals StartSet 0 EndSet times left-bracket 0 comma 1 right-parenthesis union left-bracket 0 comma epsilon right-parenthesis times StartSet 0 EndSet , we see that limit Underscript epsilon down right-arrow 0 Endscripts upper L i p Subscript upper U Sub Subscript epsilon Baseline u equals StartAbsoluteValue b minus a EndAbsoluteValue . Hence StartAbsoluteValue c minus a EndAbsoluteValue less-than-or-equal-to StartAbsoluteValue b minus a EndAbsoluteValue . By symmetry, StartAbsoluteValue c minus a EndAbsoluteValue equals StartAbsoluteValue b minus a EndAbsoluteValue . Since upper F is assumed to be non-constant, b not-equals c , and hence c minus a equals a minus b . Then StartAbsoluteValue u left-parenthesis 0 comma s right-parenthesis minus u left-parenthesis s comma 0 right-parenthesis EndAbsoluteValue slash left-parenthesis StartRoot 2 EndRoot s right-parenthesis equals StartRoot 2 EndRoot StartAbsoluteValue b minus a EndAbsoluteValue , which contradicts limit Underscript epsilon down right-arrow 0 Endscripts upper L i p Subscript upper U Sub Subscript epsilon Baseline u equals StartAbsoluteValue b minus a EndAbsoluteValue .)

One property that makes length spaces special is the fact that the Lipschitz norm is determined locally. More precisely, if upper W subset-of upper X is closed, then either upper L i p Subscript upper W Baseline u equals upper L i p Subscript partial-differential upper W Baseline u or for every delta greater-than 0

sup left-brace StartFraction StartAbsoluteValue u left-parenthesis x right-parenthesis minus u left-parenthesis y right-parenthesis EndAbsoluteValue Over d left-parenthesis x comma y right-parenthesis EndFraction colon x comma y element-of upper W comma 0 less-than d left-parenthesis x comma y right-parenthesis less-than delta right-brace equals upper L i p Subscript upper W Baseline u period

The definition of AM was inspired by the notion that if u is the “tautest possible” Lipschitz extension of upper F , it should be tautest possible on any open upper V subset-of upper X minus upper Y , given the values of u on partial-differential upper V and ignoring the rest of the metric space. Without locality, the rest of the metric space cannot be ignored (since long-distance effects may change the global Lipschitz constant), and the definition of AM is less natural. Another important property of length spaces is the fact that the graph distance metric on upper E Subscript epsilon scaled by epsilon approximates the original metric, namely, it is within epsilon of d left-parenthesis dot comma dot right-parenthesis .

1.5. Infinity Laplacian on double-struck upper R Superscript n

The continuum version of the infinity Laplacian is defined for upper C squared functions u on domains upper U subset-of double-struck upper R Superscript n by

normal upper Delta Subscript normal infinity Baseline u equals StartAbsoluteValue nabla u EndAbsoluteValue Superscript negative 2 Baseline sigma-summation Underscript i comma j Endscripts u Subscript x Sub Subscript i Subscript Baseline u Subscript x Sub Subscript i Subscript x Sub Subscript j Subscript Baseline u Subscript x Sub Subscript j Subscript Baseline period

This is the same as eta Superscript upper T Baseline upper H eta , where upper H is the Hessian of u and eta equals nabla u slash StartAbsoluteValue nabla u EndAbsoluteValue . Informally, normal upper Delta Subscript normal infinity Baseline u is the second derivative of u in the direction of the gradient of u . If nabla u left-parenthesis x right-parenthesis equals 0 , then normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis is undefined; however, we adopt the convention that if the second derivative of u left-parenthesis x right-parenthesis happens to be the same in every direction (i.e., the matrix StartSet u Subscript x Sub Subscript i Subscript x Sub Subscript j Subscript Baseline EndSet is lamda times the identity), then normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis equals lamda , which is the second derivative in any direction. (As mentioned above, some texts on infinity harmonic functions define normal upper Delta Subscript normal infinity without the normalizing factor StartAbsoluteValue nabla u EndAbsoluteValue Superscript negative 2 . When discussing viscosity solutions to normal upper Delta Subscript normal infinity Baseline u equals 0 , the two definitions are equivalent. The fact that the normalized version is sometimes undefined when nabla u equals 0 does not matter because it is always well defined at x when phi is a cone function, i.e., when phi left-parenthesis z right-parenthesis has the form a StartAbsoluteValue x minus z EndAbsoluteValue plus b for a comma b element-of double-struck upper R and z element-of double-struck upper R Superscript n with z not-equals x , and viscosity solutions can be defined via comparison with cones; see Section 1.6.) As in the discrete setting, u is infinity harmonic if normal upper Delta Subscript normal infinity Baseline u equals 0 .

While discrete infinity harmonic functions are a recent concept, introduced in finite-difference schemes for approximating continuous infinity harmonic functions Reference21, related notions of value for stochastic games are of course much older. The continuous infinity Laplacian first appeared in the work of Aronsson Reference1 and has been very thoroughly studied Reference4. Key motivations for studying this operator are the following:

(1)

AM extensions: Aronsson proved that upper C squared extensions u on domains upper U subset-of double-struck upper R Superscript n (of functions upper F on partial-differential upper U ) are infinity harmonic if and only if they are AM.

(2)

p -harmonic functions: As noted by Aronsson Reference1, the infinity Laplacian is the formal limit, as p right-arrow normal infinity of the (properly normalized) p -Laplacians. Recall that p -harmonic functions, i.e., minimizers u of integral StartAbsoluteValue nabla u left-parenthesis x right-parenthesis EndAbsoluteValue Superscript p Baseline d x subject to boundary conditions, solve the Euler-Lagrange equation nabla dot left-parenthesis StartAbsoluteValue nabla u EndAbsoluteValue Superscript p minus 2 Baseline nabla u right-parenthesis equals 0 comma

which can be rewritten StartAbsoluteValue nabla u EndAbsoluteValue Superscript p minus 2 Baseline left-parenthesis normal upper Delta u plus left-parenthesis p minus 2 right-parenthesis normal upper Delta Subscript normal infinity Baseline u right-parenthesis equals 0 comma

where normal upper Delta is the ordinary Laplacian. Dividing by StartAbsoluteValue nabla u EndAbsoluteValue Superscript p minus 2 , we see that (at least when StartAbsoluteValue nabla u EndAbsoluteValue not-equals 0 ) p -harmonic functions satisfy normal upper Delta Subscript p Baseline u equals 0 , where normal upper Delta Subscript p Baseline colon equals normal upper Delta Subscript normal infinity plus left-parenthesis p minus 2 right-parenthesis Superscript negative 1 Baseline normal upper Delta ; the second term vanishes in the large p limit. It is not too hard to see that as p tends to infinity, the Lipschitz norm of any limit of the p -harmonic functions extending upper F will be upper L i p Subscript partial-differential upper U Baseline upper F . So it is natural to guess (and was proved in Reference7) that as p tends to infinity the p -harmonic extensions of upper F converge to a limit that is both absolutely minimal and a viscosity solution to normal upper Delta Subscript normal infinity Baseline u equals 0 .

In the above setting, Aronsson also proved that there always exists an AM extension, and that in the planar case upper U subset-of double-struck upper R squared , there exists at most one upper C squared infinity harmonic extension; however upper C squared infinity harmonic extensions do not always exist Reference2.

To define the infinity Laplacian in the non- upper C squared setting requires us to consider weak solutions; the right notion here is that of viscosity solution, as introduced by Crandall and Lions (1983) Reference11. Start by observing that if u and v are upper C squared functions, u left-parenthesis x right-parenthesis equals v left-parenthesis x right-parenthesis , and v greater-than-or-equal-to u in a neighborhood of x , then v minus u has a local minimum at x , whence normal upper Delta Subscript normal infinity Baseline v left-parenthesis x right-parenthesis greater-than-or-equal-to normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis (if both sides of this inequality are defined). This comparison principle (which has analogs for more general degenerate elliptic PDEs Reference5) suggests that if u is not upper C squared , in order to define normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis we want to compare it to upper C squared functions phi for which normal upper Delta Subscript normal infinity Baseline phi left-parenthesis x right-parenthesis is defined. Let upper S left-parenthesis x right-parenthesis be the set of real valued functions phi defined and upper C squared in a neighborhood of x for which normal upper Delta Subscript normal infinity Baseline phi left-parenthesis x right-parenthesis has been defined; that is, either nabla phi left-parenthesis x right-parenthesis not-equals 0 , or nabla phi left-parenthesis x right-parenthesis equals 0 and the limit normal upper Delta Subscript normal infinity Baseline phi left-parenthesis x right-parenthesis colon equals limit Underscript x prime right-arrow x Endscripts 2 StartFraction phi left-parenthesis x prime right-parenthesis minus phi left-parenthesis x right-parenthesis Over StartAbsoluteValue x prime minus x EndAbsoluteValue squared EndFraction exists.

Definition

Let upper X be a domain in double-struck upper R Superscript n and let u colon upper X right-arrow double-struck upper R be continuous. Set

StartLayout 1st Row with Label left-parenthesis 1.3 right-parenthesis EndLabel normal upper Delta Subscript normal infinity Superscript plus Baseline u left-parenthesis x right-parenthesis equals inf left-brace normal upper Delta Subscript normal infinity Baseline phi left-parenthesis x right-parenthesis colon phi element-of upper S left-parenthesis x right-parenthesis and x is a local minimum of phi minus u right-brace period EndLayout

Thus u satisfies normal upper Delta Subscript normal infinity Superscript plus Baseline left-parenthesis u right-parenthesis greater-than-or-equal-to g in a domain upper X , iff every phi element-of upper C squared such that phi minus u has a local minimum at some x element-of upper X satisfies normal upper Delta Subscript normal infinity Superscript plus Baseline phi left-parenthesis x right-parenthesis greater-than-or-equal-to g left-parenthesis x right-parenthesis . In this case u is called a viscosity subsolution of normal upper Delta Subscript normal infinity Baseline left-parenthesis dot right-parenthesis equals g . Note that if phi element-of upper C squared , then normal upper Delta Subscript normal infinity Superscript plus Baseline phi equals normal upper Delta Subscript normal infinity Baseline phi wherever nabla phi not-equals 0 .

Similarly, let

StartLayout 1st Row with Label left-parenthesis 1.4 right-parenthesis EndLabel normal upper Delta Subscript normal infinity Superscript minus Baseline u left-parenthesis x right-parenthesis equals sup left-brace normal upper Delta Subscript normal infinity Baseline phi left-parenthesis x right-parenthesis colon phi element-of upper S left-parenthesis x right-parenthesis and x is a local maximum of phi minus u right-brace comma EndLayout

and call u a viscosity supersolution of normal upper Delta Subscript normal infinity Baseline left-parenthesis dot right-parenthesis equals g iff normal upper Delta Subscript normal infinity Superscript minus Baseline u less-than-or-equal-to g in upper X .

Finally, u is a viscosity solution of normal upper Delta Subscript normal infinity Baseline left-parenthesis dot right-parenthesis equals g if normal upper Delta Subscript normal infinity Superscript minus Baseline u less-than-or-equal-to g less-than-or-equal-to normal upper Delta Subscript normal infinity Superscript plus Baseline u in upper X (i.e., u is both a supersolution and a subsolution).

Here is a little caveat. At present, we do not know how to show that normal upper Delta Subscript normal infinity Baseline u equals g in the viscosity sense determines g . For example, if u is Lipschitz, g 1 and g 2 are continuous, and normal upper Delta Subscript normal infinity Baseline u equals g Subscript j holds for j equals 1 comma 2 (in the viscosity sense), how does one prove that g 1 equals g 2 ?

The following result of Jensen (alluded to above) is now well known Reference1Reference13Reference4: if upper X is a domain in double-struck upper R Superscript n and u colon upper X right-arrow double-struck upper R is continuous, then upper L i p Subscript upper U Baseline u equals upper L i p Subscript partial-differential upper U Baseline u less-than normal infinity for every bounded open set upper U subset-of upper U overbar subset-of upper X (i.e., u is AM) if and only if u is a viscosity solution to normal upper Delta Subscript normal infinity Baseline u equals 0 in upper X .

Let upper A subset-of upper Y subset-of upper X , where upper A is closed, upper Y not-equals normal empty-set and upper X is a length space. If x element-of upper X , one can define the normal infinity -harmonic measure of upper A from x as the infimum of u left-parenthesis x right-parenthesis over all functions u colon upper X right-arrow left-bracket 0 comma normal infinity right-parenthesis that are Lipschitz on upper X , AM in upper X minus upper Y and satisfy u greater-than-or-equal-to 1 on upper A . This quantity will be denoted by omega Subscript normal infinity Baseline left-parenthesis upper A right-parenthesis equals omega Subscript normal infinity Superscript left-parenthesis x comma upper Y comma upper X right-parenthesis Baseline left-parenthesis upper A right-parenthesis . In Section 4 we prove

Theorem 1.5

Let upper X be the unit ball in double-struck upper R Superscript n , n greater-than 1 , let upper Y equals partial-differential upper X , let x be the center of the ball, and for each delta greater-than 0 let upper A Subscript delta Baseline subset-of upper Y be a spherical cap of radius delta (of dimension n minus 1 ). Then

c delta Superscript 1 slash 3 Baseline less-than-or-equal-to omega Subscript normal infinity Baseline left-parenthesis upper A Subscript delta Baseline right-parenthesis less-than-or-equal-to upper C delta Superscript 1 slash 3 Baseline comma

where c comma upper C greater-than 0 are absolute constants (which do not depend on n ).

Numerical calculations Reference21 had suggested that in the setting of the theorem omega Subscript normal infinity Baseline left-parenthesis upper A Subscript delta Baseline right-parenthesis tends to 0 as delta right-arrow 0 , but this was only recently proved Reference12, and the proof did not yield any quantitative information on the rate of decay. In contrast to our other theorems in the paper, the proof of this theorem does not use tug-of-war. The primary tool is the comparison of a specific AM function in double-struck upper R squared minus StartSet 0 EndSet with decay r Superscript negative 1 slash 3 discovered by Aronsson Reference3.

1.6. Quadratic comparison on length spaces

To motivate the next definition, observe that for continuous functions u colon double-struck upper R right-arrow double-struck upper R , the inequality normal upper Delta Subscript normal infinity Superscript plus Baseline u greater-than-or-equal-to 0 reduces to convexity. The definition of convexity requiring a function to lie below its chords has an analog, comparison with cones, which characterizes infinity harmonic functions. Call the function phi left-parenthesis y right-parenthesis equals b StartAbsoluteValue y minus z EndAbsoluteValue plus c a cone based at z element-of double-struck upper R Superscript n . For an open upper U subset-of double-struck upper R Superscript n , say that a continuous u colon upper U right-arrow double-struck upper R satisfies comparison with cones from above on upper U if for every open upper W subset-of upper W overbar subset-of upper U for every z element-of double-struck upper R Superscript n minus upper W , and for every cone phi based at z such that the inequality u less-than-or-equal-to phi holds on partial-differential upper W , the same inequality is valid throughout upper W . Comparison with cones from below is defined similarly using the inequality u greater-than-or-equal-to phi .

Jensen Reference13 proved that viscosity solutions to normal upper Delta Subscript normal infinity Baseline u equals 0 for domains in double-struck upper R Superscript n satisfy comparison with cones (from above and below), and Crandall, Evans, and Gariepy Reference9 proved that a function on double-struck upper R Superscript n is absolutely minimal in a bounded domain upper U if and only if it satisfies comparison with cones in upper U .

Champion and De Pascale Reference8 adapted this definition to length spaces, where cones are replaced by functions of the form phi left-parenthesis x right-parenthesis equals b d left-parenthesis x comma z right-parenthesis plus c , where b greater-than 0 . Their precise definition is as follows. Let upper U be an open subset of a length-space upper X and let u colon upper U overbar right-arrow double-struck upper R be continuous. Then u is said to satisfy comparison with distance functions from above on upper U if for every open upper W subset-of upper U , for every z element-of upper X minus upper W , for every b greater-than-or-equal-to 0 and for every c element-of double-struck upper R , if u left-parenthesis x right-parenthesis less-than-or-equal-to b d left-parenthesis x comma z right-parenthesis plus c holds on partial-differential upper W , then it also holds in upper W . The function u is said to satisfy comparison with distance functions from below if negative u satisfies comparison with distance functions from above. Finally, u satisfies comparison with distance functions if it satisfies comparison with distance functions from above and from below.

The following result from Reference8 will be used in the proof of Theorem 1.4:

Lemma 1.6 (Reference8).

Let upper U be an open subset of a length space. A continuous u colon upper U overbar right-arrow double-struck upper R satisfies comparison with distance functions in upper U if and only if it is AM in upper U .

To study the inhomogenous equation normal upper Delta Subscript normal infinity Baseline u equals g , because u will in general have a non-zero second derivative (in its gradient direction), it is natural to extend these definitions to comparison with functions that have a quadratic term.

Definitions

Let upper Q left-parenthesis r right-parenthesis equals a r squared plus b r plus c with r comma a comma b comma c element-of double-struck upper R and let upper X be a length space.

Let z element-of upper X . We call the function phi left-parenthesis x right-parenthesis equals upper Q left-parenthesis d left-parenthesis x comma z right-parenthesis right-parenthesis a quadratic distance function (centered at z ).

We say that a quadratic distance function phi left-parenthesis x right-parenthesis equals upper Q left-parenthesis d left-parenthesis x comma z right-parenthesis right-parenthesis is star -increasing (in distance from z ) on an open set upper V subset-of upper X if either (1) z not-an-element-of upper V and for every x element-of upper V , we have upper Q prime left-parenthesis d left-parenthesis x comma z right-parenthesis right-parenthesis greater-than 0 , or (2) z element-of upper V and b equals 0 and a greater-than 0 . Similarly, we say that a quadratic distance function phi is star -decreasing on upper V if negative phi is star -increasing  on upper V .

If u colon upper U right-arrow double-struck upper R is a continuous function defined on an open set upper U in a length space upper X , we say that u satisfies g -quadratic comparison on upper U if the following two conditions hold:

(1)

g -quadratic comparison from above: For every open upper V subset-of upper V overbar subset-of upper U and star -increasing  quadratic distance function phi on upper V with quadratic term a less-than-or-equal-to inf Underscript y element-of upper V Endscripts StartFraction g left-parenthesis y right-parenthesis Over 2 EndFraction , the inequality phi greater-than-or-equal-to u on partial-differential upper V implies phi greater-than-or-equal-to u on upper V .

(2)

g -quadratic comparison from below: For every open upper V subset-of upper V overbar subset-of upper U and star -decreasing  quadratic distance function phi on upper V with quadratic term a greater-than-or-equal-to sup Underscript y element-of upper V Endscripts StartFraction g left-parenthesis y right-parenthesis Over 2 EndFraction , the inequality phi less-than-or-equal-to u on partial-differential upper V implies phi less-than-or-equal-to u on upper V .

The following theorem is proved in Section 6.

Theorem 1.7

Let u be a real-valued continuous function on a bounded domain upper U in double-struck upper R Superscript n , and suppose that g is a continuous function on upper U . Then u satisfies g -quadratic comparison on upper U if and only if u is a viscosity solution to normal upper Delta Subscript normal infinity Baseline u equals g in upper U .

This equivalence motivates the study of functions satisfying quadratic comparison. Note that satisfying normal upper Delta Subscript normal infinity Baseline u left-parenthesis x right-parenthesis equals g left-parenthesis x right-parenthesis in the viscosity sense depends only on the local behavior of u near x . We may use Theorem 1.7 to extend the definition of normal upper Delta Subscript normal infinity to length spaces, saying that normal upper Delta Subscript normal infinity Baseline u equals g on an open subset upper U of a length space if and only if every x element-of upper U has a neighborhood upper V subset-of upper U on which u satisfies g -quadratic comparison. We warn the reader, however, that even for length spaces upper X contained within double-struck upper R , there can be solutions to normal upper Delta Subscript normal infinity Baseline u equals 0 that do not satisfy comparison with distance functions (or 0 -quadratic comparison, for that matter): for example, upper X equals upper U equals left-parenthesis 0 comma 1 right-parenthesis and u left-parenthesis x right-parenthesis equals x . The point here is that when we take upper V subset-of left-parenthesis 0 comma 1 right-parenthesis and compare u with some function phi on partial-differential upper V , the “appropriate” notion of the boundary partial-differential upper V is the boundary in double-struck upper R , not in upper X .

The continuum value of the tug-of-war game sometimes gives a construction of a function satisfying g -quadratic comparison. We prove:

Theorem 1.8

Suppose upper X is a length space, upper Y subset-of upper X is non-empty, upper F colon upper Y right-arrow double-struck upper R is uniformly continuous and bounded, and either f colon upper X minus upper Y right-arrow double-struck upper R satisfies f equals 0 or all three of the following hold: inf StartAbsoluteValue f EndAbsoluteValue greater-than 0 , f is uniformly continuous, and upper X has finite diameter. Then the continuum value u is the unique continuous function satisfying left-parenthesis minus 2 f right-parenthesis -quadratic comparison on upper X minus upper Y and u equals upper F on upper Y . Moreover, if u overTilde colon upper X right-arrow double-struck upper R is continuous, satisfies u overTilde greater-than-or-equal-to upper F on upper Y and left-parenthesis minus 2 f right-parenthesis -quadratic comparison from below on upper X minus upper Y , then u overTilde greater-than-or-equal-to u 1 throughout upper X .

Putting these last two theorems together, we obtain

Corollary 1.9

Suppose upper U subset-of double-struck upper R Superscript n is a bounded open set, upper F colon partial-differential upper U right-arrow double-struck upper R is uniformly continuous, and f colon upper U right-arrow double-struck upper R satisfies either f equals 0 or inf f greater-than 0 and f is uniformly continuous. Then there is a unique continuous function u colon upper U overbar right-arrow double-struck upper R that is a viscosity solution to normal upper Delta Subscript normal infinity Baseline u equals minus 2 f on upper U and satisfies u equals upper F on partial-differential upper U . This unique solution is the continuum value of tug-of-war on left-parenthesis upper U overbar comma d comma partial-differential upper U comma upper F comma f right-parenthesis .

It is easy to verify that upper F indeed satisfies the assumptions in Theorem 1.8. In order to deduce the corollary, we may take the length space upper X as a ball in double-struck upper R Superscript n which contains upper U and extend upper F to upper X minus upper U , say. Alternatively, we may consider upper U with its intrinsic metric and lift upper F to the completion of upper U .

We present in Section 5 an example showing that the corollary may fail if f is permitted to take values of both signs. Specifically, the example describes two functions u 1 comma u 2 defined in the closed unit disk in double-struck upper R squared and having boundary values identically zero on the unit circle such that with some Lipschitz function g we have normal upper Delta Subscript normal infinity Baseline u Subscript j Baseline equals g for j equals 1 comma 2 (in the viscosity sense), while u 1 not-equals u 2 .

The plan of the paper is as follows. Section 2 discusses the discrete tug-of-war on graphs and proves Theorem 1.2, and Section 3 deals with tug-of-war on length spaces and proves Theorems 1.3, 1.4 and 1.8. Section 4 is devoted to estimates of normal infinity -harmonic measure. In Section 5, we present a few counterexamples showing that some of the assumptions in the theorems we prove are necessary. Section 6 is devoted to the proof of Theorem 1.7. Section 7 presents some heuristic arguments describing what the limiting trajectories of some epsilon -tug-of-war games on domains in double-struck upper R Superscript n may look like and states a question regarding the length of the game. We conclude with additional open problems in Section 8.

2. Discrete game value existence

2.1. Tug-of-war on graphs without running payoffs

In this section, we will generally assume that upper E equals upper E Subscript normal upper I Baseline equals upper E Subscript normal upper I normal upper I is undirected and connected and that f equals 0 .

Though we will not use this fact, it is interesting to point out that in the case where upper E is finite, there is a simple algorithm from Reference15 which calculates the value u of the game and proceeds as follows. Assuming the value u left-parenthesis v right-parenthesis is already calculated at some set upper V prime superset-of upper Y of vertices, find a path v 0 comma v 1 comma ellipsis comma v Subscript k Baseline , k greater-than 1 , with interior vertices v 1 comma ellipsis comma v Subscript k minus 1 Baseline element-of upper X minus upper V prime and endpoints v 0 comma v Subscript k Baseline element-of upper V prime which maximizes left-parenthesis u left-parenthesis v Subscript k Baseline right-parenthesis minus u left-parenthesis v 0 right-parenthesis right-parenthesis slash k and set u left-parenthesis v Subscript i Baseline right-parenthesis equals u left-parenthesis v 0 right-parenthesis plus i left-parenthesis u left-parenthesis v Subscript k Baseline right-parenthesis minus u left-parenthesis v 0 right-parenthesis right-parenthesis slash k for i equals 1 comma 2 comma ellipsis comma k minus 1 . Repeat this as long as upper V prime not-equals upper X .

Recall that u Subscript normal upper I is the value function for player I.

Lemma 2.1

Suppose that inf Underscript upper Y Endscripts upper F greater-than negative normal infinity and f equals 0 . Then u Subscript normal upper I is the smallest normal infinity -harmonic function bounded from below on upper X that extends upper F . More generally, if v is an normal infinity -harmonic function which is bounded from below on upper X and v greater-than-or-equal-to upper F on upper Y , then v greater-than-or-equal-to u Subscript normal upper I on upper X .

Similarly, if upper F is bounded from above on upper Y , then u Subscript normal upper I normal upper I is the largest normal infinity -harmonic function bounded from above on upper X that extends upper F .

Proof.

Player I could always try to move closer to some specific point y element-of upper Y . Since in almost every infinite sequence of fair coin tosses there will be a time when the number of tails exceeds the number of heads by d left-parenthesis x 0 comma y right-parenthesis , this ensures that the game terminates a.s., and we have u Subscript normal upper I Baseline greater-than-or-equal-to inf Underscript upper Y Endscripts upper F greater-than negative normal infinity . Suppose that v greater-than-or-equal-to upper F on upper Y and v is normal infinity -harmonic on upper X . Given delta greater-than 0 , consider an arbitrary strategy for player I and let II play a strategy that at step k (if II wins the coin toss) II selects a state where v left-parenthesis dot right-parenthesis is within delta 2 Superscript negative k of its infimum among the states to which II could move. We will show that the expected payoff for player I is at most v left-parenthesis x 0 right-parenthesis plus delta . We may assume the game terminates a.s. at a time tau less-than normal infinity . Let StartSet x Subscript j Baseline EndSet Subscript j greater-than-or-equal-to 0 denote the random sequence of states encountered in the game. Since v is normal infinity -harmonic, the sequence upper M Subscript k Baseline equals v left-parenthesis x Subscript k logical-and tau Baseline right-parenthesis plus delta 2 Superscript negative k is a supermartingale. Optional sampling and Fatou’s lemma imply that v left-parenthesis x 0 right-parenthesis plus delta equals upper M 0 greater-than-or-equal-to double-struck upper E left-bracket upper M Subscript tau Baseline right-bracket greater-than-or-equal-to double-struck upper E left-bracket upper F left-parenthesis x Subscript tau Baseline right-parenthesis right-bracket . Thus u Subscript normal upper I Baseline less-than-or-equal-to v . By Lemma Equation1.1, this completes the proof.

Now, we prove the first part of Theorem 1.2. When the graph left-parenthesis upper X comma upper E right-parenthesis is locally finite and upper Y is finite, this was proven in Reference15, Thm. 17.

Theorem 2.2

Suppose that left-parenthesis upper X comma upper E right-parenthesis is connected, and upper Y not-equals normal empty-set . If upper F is bounded below (or above) on upper Y and f equals 0 , then u Subscript normal upper I Baseline equals u Subscript normal upper I normal upper I , so the game has a value.

Before we prove this, we discuss several counterexamples that occur when the conditions of the theorem are not met. First, this theorem can fail if upper E is directed. A trivial counterexample is when upper X is finite and there is no directed path from the initial state to upper Y .

If upper X is infinite and upper E is directed, then there are counterexamples to Theorem 2.2, even when every vertex lies on a directed path towards a terminal state. For example, suppose upper X equals double-struck upper N and upper Y equals StartSet 0 EndSet , with upper F left-parenthesis 0 right-parenthesis equals 0 . If upper E consists of directed edges of the form left-parenthesis n comma n minus 1 right-parenthesis and left-parenthesis n comma n plus 2 right-parenthesis , then II may play so that with positive probability the game never terminates, and hence the value for player I is by definition negative normal infinity .

Even in the undirected case, a game may not have a value if upper F is not bounded either from above or below. The reader may check that if upper X is the integer lattice double-struck upper Z squared and the terminal states are the x -axis with upper F left-parenthesis left-parenthesis x comma 0 right-parenthesis right-parenthesis equals x , then the players’ value functions are given by u Subscript normal upper I Baseline left-parenthesis left-parenthesis x comma y right-parenthesis right-parenthesis equals x minus StartAbsoluteValue y EndAbsoluteValue and u Subscript normal upper I normal upper I Baseline left-parenthesis left-parenthesis x comma y right-parenthesis right-parenthesis equals x plus StartAbsoluteValue y EndAbsoluteValue . (Roughly speaking, this is because, in order to force the game to end in a finite amount of time, player I has to “give up” StartAbsoluteValue y EndAbsoluteValue opportunities to move to the right.) Observe also that in this case any linear function which agrees with upper F on the x -axis is normal infinity -harmonic.

As a final remark before proving this theorem, let us consider the obvious strategy for the two players, namely for player I to always maximize u on her turn and for II to always minimize u on her turn. Even when upper E is (undirected and) locally finite and the payoff function satisfies 0 less-than-or-equal-to upper F less-than-or-equal-to 1 , these obvious strategies need not be optimal. Consider, e.g., the game shown in Figure 1, where upper X subset-of double-struck upper R squared is given by upper X equals StartSet v left-parenthesis k comma j right-parenthesis colon j equals 1 comma 2 comma period period period semicolon k equals 0 comma 1 comma ellipsis comma 2 Superscript j Baseline EndSet , v left-parenthesis k comma j right-parenthesis equals left-parenthesis 2 Superscript negative j Baseline k comma 1 minus 2 Superscript negative j plus 1 Baseline right-parenthesis , and upper E consists of edges of the form StartSet v left-parenthesis k comma j right-parenthesis comma v left-parenthesis k plus 1 comma j right-parenthesis EndSet and StartSet v left-parenthesis k comma j right-parenthesis comma v left-parenthesis 2 k comma j plus 1 right-parenthesis EndSet . The terminal states are on the left and right edges of the square, and the payoff is 1 on the left and 0 on the right. Clearly the function u left-parenthesis v left-parenthesis k comma j right-parenthesis right-parenthesis equals 1 minus k slash 2 Superscript j (the Euclidean distance from the right edge of the square) is infinity harmonic, and by Corollary 2.3 below, we have u Subscript normal upper I Baseline equals u equals u Subscript normal upper I normal upper I . The obvious strategy for player I is to always move left, and for II it is to always move right. Suppose however that player I always pulls left and player II always pulls up. It is easy to check that the probability that the game ever terminates when starting from v left-parenthesis k comma j right-parenthesis is at most 2 slash left-parenthesis k plus 2 right-parenthesis (this function is a supermartingale under the corresponding Markov chain). Therefore the game continues forever with positive probability, resulting in a payoff of negative normal infinity to player I. Thus, a near-optimal strategy for player I must be able to force the game to end, and must be prepared to make moves which do not maximize u . (This is a well-known phenomenon, not particular to tug-of-war.)

Proof of Theorem 2.2.

If upper F is bounded above but not below, then we may exchange the roles of players normal upper I and normal upper I normal upper I and negate upper F to reduce to the case where upper F is bounded from below. Since u Subscript normal upper I Baseline less-than-or-equal-to u Subscript normal upper I normal upper I always holds, we just need to show that u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u Subscript normal upper I . Since player I could always pull towards a point in upper Y and thereby ensure that the game terminates, we have u Subscript normal upper I Baseline greater-than-or-equal-to inf Underscript upper Y Endscripts upper F greater-than negative normal infinity . Let u equals u Subscript normal upper I and write delta left-parenthesis x right-parenthesis equals sup Underscript y colon y tilde x Endscripts StartAbsoluteValue u left-parenthesis y right-parenthesis minus u left-parenthesis x right-parenthesis EndAbsoluteValue . Let x 0 comma x 1 comma period period period be the sequence of positions of the game. For ease of exposition, we begin by assuming that upper E is locally finite (so that the suprema and infima in the definition of the normal infinity -Laplacian definition are achieved) and that delta left-parenthesis x 0 right-parenthesis greater-than 0 ; later we will remove these assumptions.

To motivate the following argument, we make a few observations. In order to prove that u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u Subscript normal upper I , we need to show that player II can guarantee that the game terminates while also making sure that the expected payoff is not much larger than u left-parenthesis x 0 right-parenthesis . These are two different goals, and it is not a priori clear how to combine them. To resolve this difficulty, observe that delta left-parenthesis x Subscript j Baseline right-parenthesis is non-decreasing in j if players I and II adopt the strategies of maximizing (respectively, minimizing) u at every step. As we will later see, this implies that the game terminates a.s. under these strategies. On the other hand, if player I deviates from this strategy and thereby reduces delta left-parenthesis x Subscript j Baseline right-parenthesis , then perhaps player II can spend some turns playing suboptimally with respect to u in order to increase delta . Let upper X 0 colon equals StartSet x element-of upper X colon delta left-parenthesis x right-parenthesis greater-than-or-equal-to delta left-parenthesis x 0 right-parenthesis EndSet union upper Y . For n equals 0 comma 1 comma 2 comma period period period let j Subscript n Baseline equals max left-brace j less-than-or-equal-to n colon x Subscript j Baseline element-of upper X 0 right-brace and v Subscript n Baseline equals x Subscript j Sub Subscript n , which is the last position in upper X 0 up to time n . We will shortly describe a strategy for II based on the idea of backtracking to upper X 0 when not in upper X 0 . If v Subscript n Baseline not-equals x Subscript n , we may define a backtracking move from x Subscript n as any move to a neighbor y Subscript n of x Subscript n that is closer to v Subscript n than x Subscript n in the subgraph upper G Subscript n Baseline subset-of left-parenthesis upper X comma upper E right-parenthesis spanned by the vertices x Subscript j Sub Subscript n Subscript Baseline comma x Subscript j Sub Subscript n Subscript plus 1 Baseline comma ellipsis comma x Subscript n Baseline . Here, “closer” refers to the graph metric of upper G Subscript n . When II plays the backtracking strategy, she backtracks whenever not in upper X 0 and plays to a neighbor minimizing u Subscript normal upper I when in upper X 0 .

Now consider the game evolving under any strategy for player I and the backtracking strategy for II. Let d Subscript n be the distance from x Subscript n to v Subscript n in the subgraph upper G Subscript n . Set

m Subscript n Baseline colon equals u left-parenthesis v Subscript n Baseline right-parenthesis plus delta left-parenthesis x 0 right-parenthesis d Subscript n Baseline period

It is clear that u left-parenthesis x Subscript n Baseline right-parenthesis less-than-or-equal-to m Subscript n , because there is a path of length d Subscript n from x Subscript n to v Subscript n in upper G Subscript n and the change in u across any edge in this path is less than delta left-parenthesis x 0 right-parenthesis , by the definition of upper X 0 . It is easy to verify that m Subscript n is a supermartingale, as follows. If x Subscript n Baseline element-of upper X 0 , and player I plays, then m Subscript n plus 1 Baseline less-than-or-equal-to u left-parenthesis x Subscript n Baseline right-parenthesis plus delta left-parenthesis x Subscript n Baseline right-parenthesis equals m Subscript n Baseline plus delta left-parenthesis x Subscript n Baseline right-parenthesis , while if II gets the turn, then m Subscript n plus 1 Baseline equals u left-parenthesis x Subscript n Baseline right-parenthesis minus delta left-parenthesis x Subscript n Baseline right-parenthesis . If x Subscript n Baseline not-an-element-of upper X 0 and II plays, then m Subscript n plus 1 Baseline equals m Subscript n Baseline minus delta left-parenthesis x 0 right-parenthesis . If x Subscript n Baseline not-an-element-of upper X 0 and player I does not play into upper X 0 , then m Subscript n plus 1 Baseline less-than-or-equal-to m Subscript n Baseline plus delta left-parenthesis x 0 right-parenthesis . The last case to consider is that x Subscript n Baseline not-an-element-of upper X 0 and player I plays into a vertex in upper X 0 . In such a situation,

m Subscript n plus 1 Baseline equals u left-parenthesis x Subscript n plus 1 Baseline right-parenthesis less-than-or-equal-to u left-parenthesis x Subscript n Baseline right-parenthesis plus delta left-parenthesis x Subscript n Baseline right-parenthesis less-than-or-equal-to m Subscript n Baseline plus delta left-parenthesis x 0 right-parenthesis period

Thus, indeed, m Subscript n is a supermartingale (bounded from below). Let tau denote the first time a terminal state is reached (so tau equals normal infinity if the game does not terminate). By the martingale convergence theorem, the limit limit Underscript n right-arrow normal infinity Endscripts m Subscript n logical-and tau exists. But when player II plays we have m Subscript n plus 1 Baseline less-than-or-equal-to m Subscript n Baseline minus delta left-parenthesis x 0 right-parenthesis . Therefore, the game must terminate with probability 1 . The expected outcome of the game thus played is at most m 0 equals u left-parenthesis x 0 right-parenthesis . Consequently, u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u , which completes the proof in the case where upper E is locally finite and delta left-parenthesis x 0 right-parenthesis greater-than 0 .

Next, what if upper E is not locally finite, so that suprema and infima might not be achieved? In this case, we fix a small eta greater-than 0 , and use the same strategy as above, except that if x Subscript n Baseline element-of upper X 0 and II gets the turn, she moves to a neighbor at which u is at most eta 2 Superscript negative n minus 1 larger than its infimum value among neighbors of x Subscript n . In this case, m Subscript n Baseline plus eta 2 Superscript negative n is a supermartingale, and hence the expected payoff is at most u left-parenthesis x 0 right-parenthesis plus eta . Since this can be done for any eta greater-than 0 , we again have that u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u .

Finally, suppose that delta left-parenthesis x 0 right-parenthesis equals 0 . Let y element-of upper Y , and let player II pull toward y until the first time a vertex x 0 Superscript asterisk with delta left-parenthesis x 0 Superscript asterisk Baseline right-parenthesis greater-than 0 or x 0 Superscript asterisk Baseline element-of upper Y is reached. After that, II continues as above. Since u left-parenthesis x 0 right-parenthesis equals u left-parenthesis x 0 Superscript asterisk Baseline right-parenthesis , this completes the proof.

Corollary 2.3

If upper E is connected, upper Y not-equals normal empty-set and sup StartAbsoluteValue upper F EndAbsoluteValue less-than normal infinity , then u equals u Subscript normal upper I Baseline equals u Subscript normal upper I normal upper I is the unique bounded normal infinity -harmonic function agreeing with upper F on upper Y .

Proof.

This is an immediate consequence of Lemma 2.1, the remark that follows it, and Theorem 2.2.

If upper E equals StartSet left-parenthesis n comma n plus 1 right-parenthesis colon n equals 0 comma 1 comma 2 comma period period period EndSet , upper Y equals StartSet 0 EndSet and upper F left-parenthesis 0 right-parenthesis equals 0 , then ModifyingAbove u With tilde left-parenthesis n right-parenthesis equals n is an example of an (unbounded) normal infinity -harmonic function that is different from u .

2.2. Tug-of-war on graphs with running payoffs

Suppose now that f not-equals 0 . Then the analog of Theorem 2.2 does not hold without additional assumptions. For a simple counterexample, suppose that upper E is a triangle with self-loops at its vertices (i.e., a player may opt to remain in the same position), that the vertex v 0 is a terminal vertex with final payoff upper F left-parenthesis v 0 right-parenthesis equals 0 , and the running payoff is given by f left-parenthesis v 1 right-parenthesis equals negative 1 and f left-parenthesis v 2 right-parenthesis equals 1 . Then the function given by u left-parenthesis v 0 right-parenthesis equals 0 , u left-parenthesis v 1 right-parenthesis equals a minus 1 , u left-parenthesis v 2 right-parenthesis equals a plus 1 is a solution to normal upper Delta Subscript normal infinity Baseline u equals minus 2 f , provided negative 1 less-than-or-equal-to a less-than-or-equal-to 1 . The reader may check that u Subscript normal upper I is the smallest of these functions and u Subscript normal upper I normal upper I is the largest. The gap of 2 between u Subscript normal upper I and u Subscript normal upper I normal upper I appears because a player would have to give up a move (sacrificing one) in order to force the game to end. This is analogous to the double-struck upper Z squared example given in Section 2.1. Both players are earning payoffs in the interior of the game, and moving to a terminal vertex costs a player a turn.

One way around this is to assume that f is either uniformly positive or uniformly negative, as in the following analog of Theorem 2.2. We now prove the second half of Theorem 1.2:

Theorem 2.4

Suppose that upper E is connected and upper Y not-equals normal empty-set . Assume that upper F is bounded from below and inf f greater-than 0 . Then u Subscript normal upper I Baseline equals u Subscript normal upper I normal upper I . If, additionally, f and upper F are bounded from above, then any bounded solution u overTilde to normal upper Delta Subscript normal infinity Baseline u overTilde equals minus 2 f with the given boundary conditions is equal to u .

Proof.

By considering a strategy for player I that always pulls toward a specific terminal state y , we see that inf Underscript upper X Endscripts u Subscript normal upper I Baseline greater-than-or-equal-to inf Underscript upper Y Endscripts upper F . By Lemma Equation1.1, normal upper Delta Subscript normal infinity Baseline u Subscript normal upper I Baseline equals minus 2 f on upper X minus upper Y . Let u overTilde be any solution to normal upper Delta Subscript normal infinity Baseline u overTilde equals minus 2 f on upper X minus upper Y that is bounded from below on upper X and has the given boundary values on upper Y .

Claim

u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u overTilde . In proving this, we may assume without loss of generality that upper G minus upper Y is connected, where upper G is the graph left-parenthesis upper X comma upper E right-parenthesis . Then if u overTilde equals normal infinity at some vertex in upper X minus upper Y , we also have u overTilde equals normal infinity throughout upper X minus upper Y , in which case the Claim is obvious. Thus, assume that u overTilde is finite on upper X minus upper Y . Fix delta element-of left-parenthesis 0 comma inf f right-parenthesis and let II use the strategy that at step k , if the current state is x Subscript k minus 1 and II wins the coin toss, selects a state x Subscript k with ModifyingAbove u With tilde left-parenthesis x Subscript k Baseline right-parenthesis less-than inf Underscript z colon z tilde x Subscript k minus 1 Baseline Endscripts ModifyingAbove u With tilde left-parenthesis z right-parenthesis plus 2 Superscript negative k Baseline delta period Then for any strategy chosen by player I, the sequence upper M Subscript k Baseline equals ModifyingAbove u With tilde left-parenthesis x Subscript k Baseline right-parenthesis plus 2 Superscript negative k Baseline delta plus sigma-summation Underscript j equals 0 Overscript k minus 1 Endscripts f left-parenthesis x Subscript j Baseline right-parenthesis is a supermartingale bounded from below, which must converge a.s. to a finite limit. Since inf f greater-than 0 , this also forces the game to terminate a.s. Let tau denote the termination time. Then

ModifyingAbove u With tilde left-parenthesis x 0 right-parenthesis plus delta equals upper M 0 greater-than-or-equal-to double-struck upper E left-parenthesis upper M Subscript tau Baseline right-parenthesis greater-than-or-equal-to double-struck upper E left-parenthesis ModifyingAbove u With tilde left-parenthesis x Subscript tau Baseline right-parenthesis plus sigma-summation Underscript j equals 0 Overscript tau minus 1 Endscripts f left-parenthesis x Subscript j Baseline right-parenthesis right-parenthesis period

Thus this strategy for II shows that u Subscript normal upper I normal upper I Baseline left-parenthesis x 0 right-parenthesis less-than-or-equal-to ModifyingAbove u With tilde left-parenthesis x 0 right-parenthesis plus delta . Since delta greater-than 0 is arbitrary, this verifies the claim. In particular, u Subscript normal upper I normal upper I Baseline less-than-or-equal-to u Subscript upper I in upper X , so u Subscript normal upper I normal upper I Baseline equals u Subscript normal upper I .

Now suppose that sup upper F less-than normal infinity and sup f less-than normal infinity , and u overTilde is a bounded solution to normal upper Delta Subscript normal infinity Baseline u overTilde equals minus 2 f with the given boundary values. By the claim above, u overTilde greater-than-or-equal-to u Subscript normal upper I normal upper I Baseline equals u Subscript normal upper I . On the other hand, player I can play to maximize or nearly maximize u overTilde in every move. Under such a strategy, she guarantees that by turn k the expected payoff is at least ModifyingAbove u With tilde left-parenthesis x 0 right-parenthesis minus double-struck upper E left-bracket upper Q left-parenthesis k right-parenthesis right-bracket minus epsilon , where upper Q left-parenthesis k right-parenthesis is 0 if the game has terminated by time k , and ModifyingAbove u With tilde left-parenthesis x Subscript k Baseline right-parenthesis otherwise. If the expected number of moves played is infinite, the expected payoff is infinite. Otherwise, limit Underscript k Endscripts double-struck upper E left-bracket upper Q left-parenthesis k right-parenthesis right-bracket equals 0 , since u overTilde is bounded. Thus, u Subscript normal upper I normal upper I Baseline equals u Subscript normal upper I Baseline greater-than-or-equal-to u overTilde in any case.

3. Continuum value of tug-of-war on a length space

3.1. Preliminaries and outline

In this section, we will prove Theorem 1.3, Theorem 1.8 and Theorem 1.4. Throughout this section, we assume left-parenthesis upper X comma d comma upper Y comma upper F comma f right-parenthesis denotes a tug-of-war game, i.e., upper X is a length space with distance function d , upper Y subset-of upper X is a non-empty set of terminal states, upper F colon upper Y right-arrow double-struck upper R is the final payoff function, and f colon upper X minus upper Y right-arrow double-struck upper R is the running payoff function. We let x Subscript k denote the game state at time k in epsilon -tug-of-war.

It is natural to ask for a continuous-time version of tug-of-war on a length space. Precisely and rigorously defining such a game (which would presumably involve replacing coin tosses with white noise, making sense of what a continuum no-look-ahead strategy means, etc.) is a technical challenge we will not undertake in this paper (though we include some discussion of the small-