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.

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.

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

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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