Dynamic Programming Principle for tug-of-war games with noise
ESAIM: Control, Optimisation and Calculus of Variations, Volume 18 (2012) no. 1, p. 81-90

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.

DOI : https://doi.org/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
@article{COCV_2012__18_1_81_0,
author = {Manfredi, Juan J. and Parviainen, Mikko and Rossi, Julio D.},
title = {Dynamic Programming Principle for tug-of-war games with noise},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {18},
number = {1},
year = {2012},
pages = {81-90},
doi = {10.1051/cocv/2010046},
zbl = {1233.91042},
mrnumber = {2887928},
language = {en},
url = {http://www.numdam.org/item/COCV_2012__18_1_81_0}
}

Manfredi, Juan J.; Parviainen, Mikko; Rossi, Julio D. Dynamic Programming Principle for tug-of-war games with noise. ESAIM: Control, Optimisation and Calculus of Variations, Volume 18 (2012) no. 1, pp. 81-90. doi : 10.1051/cocv/2010046. http://www.numdam.org/item/COCV_2012__18_1_81_0/

[1] E. Le Gruyer, On absolutely minimizing Lipschitz extensions and PDE Δ∞(u) = 0. NoDEA 14 (2007) 29-55. | MR 2346452 | Zbl 1154.35055

[2] E. Le Gruyer and J.C. Archer, Harmonious extensions. SIAM J. Math. Anal. 29 (1998) 279-292. | MR 1617186 | Zbl 0915.46002

[3] A.P. Maitra and W.D. Sudderth, Borel stochastic games with limsup payoff. Ann. Probab. 21 (1993) 861-885. | MR 1217569 | Zbl 0803.90142

[4] A.P. Maitra and W.D. Sudderth, Discrete gambling and stochastic games, Applications of Mathematics 32. Springer-Verlag (1996). | MR 1382657 | Zbl 0864.90148

[5] J.J. Manfredi, M. Parviainen and J.D. Rossi, An asymptotic mean value property characterization of p-harmonic functions. Proc. Am. Math. Soc. 138 (2010) 881-889. | MR 2566554 | Zbl 1187.35115

[6] J.J. Manfredi, M. Parviainen and J.D. Rossi, On the definition and properties of p-harmonious functions. Preprint (2009). | MR 3011990 | Zbl 1252.91014

[7] A. Oberman, A convergent difference scheme for the infinity Laplacian : construction of absolutely minimizing Lipschitz extensions. Math. Comp. 74 (2005) 1217-1230. | MR 2137000 | Zbl 1094.65110

[8] Y. Peres and S. Sheffield, Tug-of-war with noise : a game theoretic view of the p-Laplacian. Duke Math. J. 145 (2008) 91-120. | MR 2451291 | Zbl 1206.35112

[9] Y. Peres, O. Schramm, S. Sheffield and D. Wilson, Tug-of-war and the infinity Laplacian. J. Am. Math. Soc. 22 (2009) 167-210. | MR 2449057 | Zbl 1206.91002

[10] S.R.S. Varadhan, Probability theory, Courant Lecture Notes in Mathematics 7. Courant Institute of Mathematical Sciences, New York University/AMS (2001). | MR 1852999 | Zbl 0980.60002