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

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

ESAIM: Control, Optimisation and Calculus of Variations (2012)

- Volume: 18, Issue: 1, page 81-90
- ISSN: 1292-8119

## Access Full Article

top## Abstract

top## How to cite

topManfredi, Juan J., Parviainen, Mikko, and Rossi, Julio D.. "Dynamic Programming Principle for tug-of-war games with noise." ESAIM: Control, Optimisation and Calculus of Variations 18.1 (2012): 81-90. <http://eudml.org/doc/277814>.

@article{Manfredi2012,

abstract = {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\begin\{equation*\} u(x) = \frac\{\alpha\}\{2\} \left\\{ \sup\_\{y\in
\ol B\_\{\eps\}(x)\} u (y) + \inf\_\{ y \in \ol B\_\{\eps\}(x)\} u (y) \right\\} + \beta
\kint\_\{ B\_\{\eps\}(x)\} u(y) \ud y, \end\{equation*\} for x ∈ Ω with
u(y) = F(y) when
y ∉ Ω. This principle implies the existence of
quasioptimal Markovian strategies. },

author = {Manfredi, Juan J., Parviainen, Mikko, Rossi, Julio D.},

journal = {ESAIM: Control, Optimisation and Calculus of Variations},

keywords = {Dirichlet boundary conditions; Dynamic Programming Principle; p-Laplacian; stochastic games; two-player zero-sum games; zero sum game; tug-of-war game; dynamic programming; quasioptimal strategies; Markovian strategies},

language = {eng},

month = {2},

number = {1},

pages = {81-90},

publisher = {EDP Sciences},

title = {Dynamic Programming Principle for tug-of-war games with noise},

url = {http://eudml.org/doc/277814},

volume = {18},

year = {2012},

}

TY - JOUR

AU - Manfredi, Juan J.

AU - Parviainen, Mikko

AU - Rossi, Julio D.

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

JO - ESAIM: Control, Optimisation and Calculus of Variations

DA - 2012/2//

PB - EDP Sciences

VL - 18

IS - 1

SP - 81

EP - 90

AB - 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\begin{equation*} u(x) = \frac{\alpha}{2} \left\{ \sup_{y\in
\ol B_{\eps}(x)} u (y) + \inf_{ y \in \ol B_{\eps}(x)} u (y) \right\} + \beta
\kint_{ B_{\eps}(x)} u(y) \ud y, \end{equation*} for x ∈ Ω with
u(y) = F(y) when
y ∉ Ω. This principle implies the existence of
quasioptimal Markovian strategies.

LA - eng

KW - Dirichlet boundary conditions; Dynamic Programming Principle; p-Laplacian; stochastic games; two-player zero-sum games; zero sum game; tug-of-war game; dynamic programming; quasioptimal strategies; Markovian strategies

UR - http://eudml.org/doc/277814

ER -

## References

top- E. Le Gruyer, On absolutely minimizing Lipschitz extensions and PDE Δ∞(u) = 0. NoDEA14 (2007) 29–55.
- E. Le Gruyer and J.C. Archer, Harmonious extensions. SIAM J. Math. Anal.29 (1998) 279–292.
- A.P. Maitra and W.D. Sudderth, Borel stochastic games with limsup payoff. Ann. Probab.21 (1993) 861–885.
- A.P. Maitra and W.D. Sudderth, Discrete gambling and stochastic games, Applications of Mathematics32. Springer-Verlag (1996).
- 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.
- J.J. Manfredi, M. Parviainen and J.D. Rossi, On the definition and properties ofp-harmonious functions. Preprint (2009).
- A. Oberman, A convergent difference scheme for the infinity Laplacian : construction of absolutely minimizing Lipschitz extensions. Math. Comp.74 (2005) 1217–1230.
- 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.
- Y. Peres, O. Schramm, S. Sheffield and D. Wilson, Tug-of-war and the infinity Laplacian. J. Am. Math. Soc.22 (2009) 167–210.
- S.R.S. Varadhan, Probability theory, Courant Lecture Notes in Mathematics7. Courant Institute of Mathematical Sciences, New York University/AMS (2001).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.