American Institute of Mathematical Sciences

Advanced
July  2014, 1(3): 411-445. doi: 10.3934/jdg.2014.1.411

Existence of the uniform value in zero-sum repeated games with a more informed controller

Fabien Gensbittel 1, , Miquel Oliu-Barton 2, and  Xavier Venel 3,

1. 

TSE (GREMAQ, Université Toulouse 1 Capitole), Manufacture des Tabacs, 21, Allée de Brienne, 31015 Toulouse Cedex 6, France
2. 

Université de Neuchâtel, Institut de Mathématiques, Emilie-Argand 11, 2000 Neuchatel, Switzerland
3. 

Department of Statistics and Operations Research, Tel-Aviv University, Ramat-Aviv, 69978 Tel-Aviv, Israel

Received  November 2012 Revised  September 2013 Published  July 2014

We prove that in a two-player zero-sum repeated game where one of the players, say player $1$, is more informed than his opponent and controls the evolution of information on the state, the uniform value exists. This result extends previous results on Markov decision processes with partial observation (Rosenberg, Solan, Vieille [15]), and repeated games with an informed controller (Renault [14]). Our formal definition of a more informed player is more general than the inclusion of signals, allowing therefore for imperfect monitoring of actions. We construct an auxiliary stochastic game whose state space is the set of second order beliefs of player $2$ (beliefs about beliefs of player $1$ on the state variable of the original game) with perfect monitoring and we prove it has a value by using a result of Renault [14]. A key element in this work is to prove that player $1$ can use strategies of the auxiliary game in the original game in our general framework, from which we deduce that the value of the auxiliary game is also the value of our original game by using classical arguments.
Keywords: repeated games, Zero-sum games, uniform value., incomplete information, stochastic games.
Mathematics Subject Classification: Primary: 91A20; Secondary: 91A26, 91A1.
Citation: Fabien Gensbittel, Miquel Oliu-Barton, Xavier Venel. Existence of the uniform value in zero-sum repeated games with a more informed controller. Journal of Dynamics & Games, 2014, 1 (3) : 411-445. doi: 10.3934/jdg.2014.1.411
References:
[1]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information, with the collaboration of R. Stearns, MIT Press, 1995.  Google Scholar

[2]

D. Blackwell and T. S. Fergusson, The big match, The Annals of Mathematical Statistics, 39 (1968), 159-163. doi: 10.1214/aoms/1177698513.  Google Scholar

[3]

D. Blackwell and L. E. Dubins, An extension of Skorohod's almost sure representation theorem, Proceedings of the American Mathematical Society, 89 (1983), 691-692. doi: 10.2307/2044607.  Google Scholar

[4]

K. Fan, Minimax theorems, Proceedings of the National Academy of Sciences of the United States of America, 39 (1953), 42-47. doi: 10.1073/pnas.39.1.42.  Google Scholar

[5]

L. Kantorovich and G. S. Rubinstein, On a space of totally additive functions, Vestnik Leningrad. Univ, 13 (1958), 52-59.  Google Scholar

[6]

J. F. Mertens, Repeated games, in Proceedings of the International Congress of Mathematicians, Vol. 1 (Berkeley, Calif., 1986), Amer. Math. Soc., Providence, RI, 1986, 1528-1577.  Google Scholar

[7]

J. F. Mertens and A. Neyman, Stochastic games, International Journal of Game Theory, 10 (1981), 53-66. doi: 10.1007/BF01769259.  Google Scholar

[8]

J. F. Mertens, S. Sorin and S. Zamir, Repeated Games, CORE Discussion Papers 9420, 9421 and 9422, Université Catholique De Louvain, Belgium, 1994. Google Scholar

[9]

J. F. Mertens and S. Zamir, The value of two-person zero-sum repeated games with lack of information on both sides, International Journal of Game Theory, 1 (1971), 39-64. doi: 10.1007/BF01753433.  Google Scholar

[10]

A. Neyman and S. Sorin, Repeated games with public uncertain duration process, International Journal of Game Theory 39 (2010), 29-52. doi: 10.1007/s00182-009-0197-y.  Google Scholar

[11]

A. Neyman, Existence of optimal strategies in Markov games with incomplete information, International Journal of Game Theory, 37 (2008), 581-596. doi: 10.1007/s00182-008-0134-5.  Google Scholar

[12]

J. Renault, The value of Markov chain games with lack of information on one side, Mathematics of Operations Research, 31 (2006), 490-512. doi: 10.1287/moor.1060.0199.  Google Scholar

[13]

J. Renault, Uniform value in Dynamic Programming, Journal of the European Mathematical Society, 13 (2011), 309-330. doi: 10.4171/JEMS/254.  Google Scholar

[14]

J. Renault, The value of repeated games with an informed controller, Mathematics of Operations Research, 37 (2012), 154-179. doi: 10.1287/moor.1110.0518.  Google Scholar

[15]

D. Rosenberg, E. Solan and N. Vieille, Blackwell optimality in Markov decision processes with partial observation, Annals of Statistics, 30 (2002), 1178-1193. doi: 10.1214/aos/1031689022.  Google Scholar

[16]

D. Rosenberg, E. Solan and N. Vieille, Stochastic games with a single controller and incomplete information, SIAM Journal on Control and Optimization, 43 (2004), 86-110. doi: 10.1137/S0363012902407107.  Google Scholar

[17]

S. Sorin, "Big Match'' with lack of information on one side (part I), International Journal of Game Theory, 13 (1984), 201-255. doi: 10.1007/BF01769463.  Google Scholar

[18]

S. Sorin, A First Course on Zero-Sum Repeated games, Mathématiques & Applications, Springer, 2002.  Google Scholar

show all references

References:
[1]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information, with the collaboration of R. Stearns, MIT Press, 1995.  Google Scholar

[2]

D. Blackwell and T. S. Fergusson, The big match, The Annals of Mathematical Statistics, 39 (1968), 159-163. doi: 10.1214/aoms/1177698513.  Google Scholar

[3]

D. Blackwell and L. E. Dubins, An extension of Skorohod's almost sure representation theorem, Proceedings of the American Mathematical Society, 89 (1983), 691-692. doi: 10.2307/2044607.  Google Scholar

[4]

K. Fan, Minimax theorems, Proceedings of the National Academy of Sciences of the United States of America, 39 (1953), 42-47. doi: 10.1073/pnas.39.1.42.  Google Scholar

[5]

L. Kantorovich and G. S. Rubinstein, On a space of totally additive functions, Vestnik Leningrad. Univ, 13 (1958), 52-59.  Google Scholar

[6]

J. F. Mertens, Repeated games, in Proceedings of the International Congress of Mathematicians, Vol. 1 (Berkeley, Calif., 1986), Amer. Math. Soc., Providence, RI, 1986, 1528-1577.  Google Scholar

[7]

J. F. Mertens and A. Neyman, Stochastic games, International Journal of Game Theory, 10 (1981), 53-66. doi: 10.1007/BF01769259.  Google Scholar

[8]

J. F. Mertens, S. Sorin and S. Zamir, Repeated Games, CORE Discussion Papers 9420, 9421 and 9422, Université Catholique De Louvain, Belgium, 1994. Google Scholar

[9]

J. F. Mertens and S. Zamir, The value of two-person zero-sum repeated games with lack of information on both sides, International Journal of Game Theory, 1 (1971), 39-64. doi: 10.1007/BF01753433.  Google Scholar

[10]

A. Neyman and S. Sorin, Repeated games with public uncertain duration process, International Journal of Game Theory 39 (2010), 29-52. doi: 10.1007/s00182-009-0197-y.  Google Scholar

[11]

A. Neyman, Existence of optimal strategies in Markov games with incomplete information, International Journal of Game Theory, 37 (2008), 581-596. doi: 10.1007/s00182-008-0134-5.  Google Scholar

[12]

J. Renault, The value of Markov chain games with lack of information on one side, Mathematics of Operations Research, 31 (2006), 490-512. doi: 10.1287/moor.1060.0199.  Google Scholar

[13]

J. Renault, Uniform value in Dynamic Programming, Journal of the European Mathematical Society, 13 (2011), 309-330. doi: 10.4171/JEMS/254.  Google Scholar

[14]

J. Renault, The value of repeated games with an informed controller, Mathematics of Operations Research, 37 (2012), 154-179. doi: 10.1287/moor.1110.0518.  Google Scholar

[15]

D. Rosenberg, E. Solan and N. Vieille, Blackwell optimality in Markov decision processes with partial observation, Annals of Statistics, 30 (2002), 1178-1193. doi: 10.1214/aos/1031689022.  Google Scholar

[16]

D. Rosenberg, E. Solan and N. Vieille, Stochastic games with a single controller and incomplete information, SIAM Journal on Control and Optimization, 43 (2004), 86-110. doi: 10.1137/S0363012902407107.  Google Scholar

[17]

S. Sorin, "Big Match'' with lack of information on one side (part I), International Journal of Game Theory, 13 (1984), 201-255. doi: 10.1007/BF01769463.  Google Scholar

[18]

S. Sorin, A First Course on Zero-Sum Repeated games, Mathématiques & Applications, Springer, 2002.  Google Scholar

[1]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020
[2]

Sylvain Sorin, Guillaume Vigeral. Reversibility and oscillations in zero-sum discounted stochastic games. Journal of Dynamics & Games, 2015, 2 (1) : 103-115. doi: 10.3934/jdg.2015.2.103
[3]

Antoine Hochart. An accretive operator approach to ergodic zero-sum stochastic games. Journal of Dynamics & Games, 2019, 6 (1) : 27-51. doi: 10.3934/jdg.2019003
[4]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045
[5]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics & Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002
[6]

Marianne Akian, Stéphane Gaubert, Antoine Hochart. Ergodicity conditions for zero-sum games. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 3901-3931. doi: 10.3934/dcds.2015.35.3901
[7]

Miquel Oliu-Barton. Asymptotically optimal strategies in repeated games with incomplete information and vanishing weights. Journal of Dynamics & Games, 2019, 6 (4) : 259-275. doi: 10.3934/jdg.2019018
[8]

Alexander J. Zaslavski. Structure of approximate solutions of dynamic continuous time zero-sum games. Journal of Dynamics & Games, 2014, 1 (1) : 153-179. doi: 10.3934/jdg.2014.1.153
[9]

Libin Mou, Jiongmin Yong. Two-person zero-sum linear quadratic stochastic differential games by a Hilbert space method. Journal of Industrial & Management Optimization, 2006, 2 (1) : 95-117. doi: 10.3934/jimo.2006.2.95
[10]

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa. Average optimal strategies for zero-sum Markov games with poorly known payoff function on one side. Journal of Dynamics & Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105
[11]

Alexander J. Zaslavski. Turnpike properties of approximate solutions of dynamic discrete time zero-sum games. Journal of Dynamics & Games, 2014, 1 (2) : 299-330. doi: 10.3934/jdg.2014.1.299
[12]

Salah Eddine Choutri, Boualem Djehiche, Hamidou Tembine. Optimal control and zero-sum games for Markov chains of mean-field type. Mathematical Control & Related Fields, 2019, 9 (3) : 571-605. doi: 10.3934/mcrf.2019026
[13]

Chandan Pal, Somnath Pradhan. Zero-sum games for pure jump processes with risk-sensitive discounted cost criteria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021020
[14]

René Carmona, Kenza Hamidouche, Mathieu Laurière, Zongjun Tan. Linear-quadratic zero-sum mean-field type games: Optimality conditions and policy optimization. Journal of Dynamics & Games, 2021, 8 (4) : 403-443. doi: 10.3934/jdg.2021023
[15]

Feimin Zhong, Jinxing Xie, Jing Jiao. Solutions for bargaining games with incomplete information: General type space and action space. Journal of Industrial & Management Optimization, 2018, 14 (3) : 953-966. doi: 10.3934/jimo.2017084
[16]

Dejian Chang, Zhen Wu. Stochastic maximum principle for non-zero sum differential games of FBSDEs with impulse controls and its application to finance. Journal of Industrial & Management Optimization, 2015, 11 (1) : 27-40. doi: 10.3934/jimo.2015.11.27
[17]

Josef Hofbauer, Sylvain Sorin. Best response dynamics for continuous zero--sum games. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 215-224. doi: 10.3934/dcdsb.2006.6.215
[18]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555
[19]

Christian Hofer, Georg Jäger, Manfred Füllsack. Critical transitions and Early Warning Signals in repeated Cooperation Games. Journal of Dynamics & Games, 2018, 5 (3) : 223-230. doi: 10.3934/jdg.2018014
[20]

Mathias Staudigl, Jan-Henrik Steg. On repeated games with imperfect public monitoring: From discrete to continuous time. Journal of Dynamics & Games, 2017, 4 (1) : 1-23. doi: 10.3934/jdg.2017001

 Impact Factor: 

Tools

Metrics

  • PDF downloads (56)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences