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

Abstract

top
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 ( x ) = α 2 sup y ∈ B ( x ) u ( y ) + inf y ∈ B ( x ) u ( y ) + β B ( x ) u ( y ) y , for x ∈ Ω with u(y) = F(y) when y ∉ Ω. This principle implies the existence of quasioptimal Markovian strategies.

How to cite

top

Manfredi, 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
  1. E. Le Gruyer, On absolutely minimizing Lipschitz extensions and PDE Δ∞(u) = 0. NoDEA14 (2007) 29–55.  
  2. E. Le Gruyer and J.C. Archer, Harmonious extensions. SIAM J. Math. Anal.29 (1998) 279–292.  
  3. A.P. Maitra and W.D. Sudderth, Borel stochastic games with limsup payoff. Ann. Probab.21 (1993) 861–885.  
  4. A.P. Maitra and W.D. Sudderth, Discrete gambling and stochastic games, Applications of Mathematics32. Springer-Verlag (1996).  
  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.  
  6. J.J. Manfredi, M. Parviainen and J.D. Rossi, On the definition and properties ofp-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.  
  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.  
  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.  
  10. S.R.S. Varadhan, Probability theory, Courant Lecture Notes in Mathematics7. Courant Institute of Mathematical Sciences, New York University/AMS (2001).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.