  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.
