A Course on Tug-of-War Games with Random Noise

Marta Lewicka

Publisher:

Springer

Publication Date:

2020

Number of Pages:

263

Format:

Paperback

Price:

29.99

ISBN:

978-3-030-46208-6

Category:

Textbook

MAA Review
Table of Contents

[Reviewed by

Bill Satzer

, on

04/4/2021

]

Tug-of-War games with random noise are part of an emerging field that uses probabilistic methods to explore questions in linear and nonlinear potential theory. The author says that she wants to explore the subject as an analyst an area that lies at the intersection of differential game theory, partial differential equations and stochastic processes, and leads to both questions of significance and new techniques for practitioners of partial differential equations. Her interests are primarily in the area on nonlinear potential theory.

Linear potential theory has a strong connection with Brownian motions and random walks. That connection, developed by Itô, Doob, Lévy and others depends on the observation that harmonic functions and martingales have a common cancellation property that is expressed in their mean value properties. In nonlinear potential theory a similar observation and approach apply. The game-theoretical approach to nonlinear potential theory allows replacing analytical techniques with suitable strategies of competing players.

A simple discrete version of two-player zero-sum tug-of-war game with random noise is as follows. Game play begins when a token is placed at a position \( x_{0} \) on a domain \( \mathcal{D} \) in \( R^{n} \) with boundary \( \partial \mathcal{D} \) and with a function \( F \) defined on the boundary. At each step it moved according to a rule: either one of two players (each acting with probability \( \frac{1}{2}\)) updates the current position \( x_{n} \) with a chosen vector \( y \) of length at most \( \epsilon \) to a new position \( x_{n+1} \), uniformly distributed within an ellipsoid centered at \( z = x_{n} + y \). The game ends whenever the token reaches the \( \epsilon \)-neighborhood of the boundary of \( \mathcal{D} \). The game value \( u^{\epsilon}(x_{0}) \) is defined as the value of \( F \) at the stopping position \( x_{\tau} \), subject to both players playing optimally.

The optimality condition gets to the tug-of-war idea. Player 2 pays to Player 1 the value \( F(x_{\tau}) \). So Player 1 has the incentive to maximize his gain by pulling the token to portions of \( \partial \mathcal{D} \) with high values of \( F \), whereas Player 2 tries to minimize the loss by pulling toward lower values of \( F \).

It turns out that the game value \( u_{\epsilon} \) with \( \epsilon \rightarrow 0 \) converges pointwise to the unique Perron solution \( u \) of an associated p-Laplace-Dirichlet problem defined by

\( \Delta_{p}(u) = \mbox{div} (|\nabla{u})|^{p-2} \nabla{u})=0 \)

with \( u=F \) on \( \partial \mathcal{D} \) and \( p \geq 2 \).

The second-order differential operator \( \Delta_{p}(u) \) is called the \( p \)-Laplacian, the differential equation the \( p \)-harmonic equation, and its solutions \( p \)-harmonic equations. These and the role they play in nonlinear potential theory are the primary subjects of this book. The focus of this book is how game-theoretic notions from tug-of-war games can be applied to develop new results in nonlinear potential theory. The author begins with classical linear potential theory and random walks. This leads to questions that involve the ordinary (\( p = 2 \)) Laplacian. With some modifications the basic ideas in the linear case can be applied in the nonlinear case. A treatment of the linear case is intended to guide the reader more easily to the increasingly complicated constructions that follow.

Prerequisites for the book include multivariable calculus and basic measure theory together with rigorous courses in probability and differential equations. Probably the book is best suited for advanced graduate students and specialists in nonlinear potential theory. The author provides background appendices for probability, Brownian motion and PDEs.

Bill Satzer (bsatzer@gmail.com), now retired from 3M Company, spent most of his career as a mathematician working in industry on a variety of applications ranging from speech recognition and network modeling to optical films, material science and the odd bit of high performance computing. He did his PhD work in dynamical systems and celestial mechanics.

See the publisher's website.

Tags:

Game Theory