Dynamic Programming Principle for tug-of-war games with noise

Manfredi, Juan J. ; Parviainen, Mikko ; Rossi, Julio D.

ESAIM: Control, Optimisation and Calculus of Variations, Tome 18 (2012) no. 1, pp. 81-90

Résumé

We consider a two-player zero-sum-game in a bounded open domain Ω described as follows: at a point x ∈ Ω, Players I and II play an ε-step tug-of-war game with probability α, and with probability β (α + β = 1), a random point in the ball of radius ε centered at x is chosen. Once the game position reaches the boundary, Player II pays Player I the amount given by a fixed payoff function F. We give a detailed proof of the fact that the value functions of this game satisfy the Dynamic Programming Principle

$$u\left(x\right)=\frac{\alpha }{2}\left\{\underset{y\in {\overline{B}}_{ϵ}\left(x\right)}{sup}u\left(y\right)+\underset{y\in {\overline{B}}_{ϵ}\left(x\right)}{inf}u\left(y\right)\right\}+{\beta }_{B_{}\left(x\right)}u\left(y\right)dy,$$

for $x\in \Omega$ with $u\left(y\right)=F\left(y\right)$ when $y\notin \Omega$. This principle implies the existence of quasioptimal Markovian strategies.

Détail

DOI : 10.1051/cocv/2010046

Classification : 35J70, 49N70, 91A15, 91A24
Keywords: Dirichlet boundary conditions, dynamic programming principle, p-laplacian, stochastic games, two-player zero-sum games