October  2019, 6(4): 259-275. doi: 10.3934/jdg.2019018

Asymptotically optimal strategies in repeated games with incomplete information and vanishing weights

Université Paris-Dauphine, PSL Research University, CNRS, CEREMADE, 75016 Paris, France

Received  November 2018 Revised  September 2019 Published  October 2019

We construct asymptotically optimal strategies in two-player zero-sum repeated games with incomplete information on both sides in which stages have vanishing weights. Our construction, inspired in Heuer (IJGT 1992), proves the convergence of the values for these games, thus extending the results established by Mertens and Zamir (IJGT 1971) for $ n $-stage games and discounted games to the case of arbitrary vanishing weights.

Citation: 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
References:
[1]

R. Aumann and M. Maschler, Repeated Games with Incomplete Information, With the collaboration of Richard E. Stearns. MIT Press, Cambridge, MA, 1995.  Google Scholar

[2]

P. CardaliaguetR. Laraki and S. Sorin, A continuous time approach for the asymptotic value in two-person zero-sum repeated games, SIAM Journal on Control and Optimization, 50 (2012), 1573-1596.  doi: 10.1137/110839473.  Google Scholar

[3]

B. De Meyer, Repeated games and partial differential equations, Mathematics of Operations Research, 21 (1996), 209-236.  doi: 10.1287/moor.21.1.209.  Google Scholar

[4]

B. De Meyer, Repeated games, duality and the Central Limit theorem, Mathematics of Operations Research, 21 (1996), 237-251.  doi: 10.1287/moor.21.1.237.  Google Scholar

[5]

B. De Meyer and A. Marino, Duality and optimal strategies in the finitely repeated zero-sum games with incomplete information on both sides, Cahiers de la MSE, 27. Google Scholar

[6]

F. Gensbittel and M. Oliu-Barton, Optimal strategies in repeated games with incomplete information, In revison. Google Scholar

[7]

M. Heuer, Asymptotically optimal strategies in repeated games with incomplete information, International Journal of Game Theory, 20 (1992), 377-392.  doi: 10.1007/BF01271132.  Google Scholar

[8]

N. Krasovskii and A. Subbotin, Game Theoretical Control Problems, Springer Verlag, 1988.  Google Scholar

[9]

R. Laraki, Variational inequalities, system of functional equations and incomplete information repeated games, SIAM Journal on Control and Optimization, 40 (2001), 516-524.  doi: 10.1137/S0363012900366601.  Google Scholar

[10]

R. Laraki and J. Renault, Acyclic gambling games, 2017. Google Scholar

[11]

P. Maldonado and M. Oliu-Barton, A strategy-based proof of the existence of the value in zero-sum differential games, Morfismos, 18 (2014), 31-44.   Google Scholar

[12]

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

[13]

J.-F. Mertens and S. Zamir, Incomplete information games with transcendental values, Mathematics of Operations Research, 6 (1981), 313-318.  doi: 10.1287/moor.6.2.313.  Google Scholar

[14]

M. Oliu-Barton, Differential games with asymmetric and correlated information, Dynamic Games and Applications, 5 (2015), 378-396.  doi: 10.1007/s13235-014-0131-1.  Google Scholar

[15]

M. Oliu-Barton, Splitting game: Uniform value and optimal strategies, Dynamic Games and Applications, 8 (2018), 157-179.  doi: 10.1007/s13235-017-0216-8.  Google Scholar

[16]

R. Rockafellar, Convex Analysis, Princeton University Press, 1997.  Google Scholar

[17]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel Journal of Mathematics, 121 (2001), 221-246.  doi: 10.1007/BF02802505.  Google Scholar

[18]

S. Sorin, A First Course on Zero-Sum Repeated Games, Springer, 2002.  Google Scholar

[19]

N. Vieille, Weak approachability, Mathematics of Operations Research, 17 (1992), 781-791.  doi: 10.1287/moor.17.4.781.  Google Scholar

show all references

References:
[1]

R. Aumann and M. Maschler, Repeated Games with Incomplete Information, With the collaboration of Richard E. Stearns. MIT Press, Cambridge, MA, 1995.  Google Scholar

[2]

P. CardaliaguetR. Laraki and S. Sorin, A continuous time approach for the asymptotic value in two-person zero-sum repeated games, SIAM Journal on Control and Optimization, 50 (2012), 1573-1596.  doi: 10.1137/110839473.  Google Scholar

[3]

B. De Meyer, Repeated games and partial differential equations, Mathematics of Operations Research, 21 (1996), 209-236.  doi: 10.1287/moor.21.1.209.  Google Scholar

[4]

B. De Meyer, Repeated games, duality and the Central Limit theorem, Mathematics of Operations Research, 21 (1996), 237-251.  doi: 10.1287/moor.21.1.237.  Google Scholar

[5]

B. De Meyer and A. Marino, Duality and optimal strategies in the finitely repeated zero-sum games with incomplete information on both sides, Cahiers de la MSE, 27. Google Scholar

[6]

F. Gensbittel and M. Oliu-Barton, Optimal strategies in repeated games with incomplete information, In revison. Google Scholar

[7]

M. Heuer, Asymptotically optimal strategies in repeated games with incomplete information, International Journal of Game Theory, 20 (1992), 377-392.  doi: 10.1007/BF01271132.  Google Scholar

[8]

N. Krasovskii and A. Subbotin, Game Theoretical Control Problems, Springer Verlag, 1988.  Google Scholar

[9]

R. Laraki, Variational inequalities, system of functional equations and incomplete information repeated games, SIAM Journal on Control and Optimization, 40 (2001), 516-524.  doi: 10.1137/S0363012900366601.  Google Scholar

[10]

R. Laraki and J. Renault, Acyclic gambling games, 2017. Google Scholar

[11]

P. Maldonado and M. Oliu-Barton, A strategy-based proof of the existence of the value in zero-sum differential games, Morfismos, 18 (2014), 31-44.   Google Scholar

[12]

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

[13]

J.-F. Mertens and S. Zamir, Incomplete information games with transcendental values, Mathematics of Operations Research, 6 (1981), 313-318.  doi: 10.1287/moor.6.2.313.  Google Scholar

[14]

M. Oliu-Barton, Differential games with asymmetric and correlated information, Dynamic Games and Applications, 5 (2015), 378-396.  doi: 10.1007/s13235-014-0131-1.  Google Scholar

[15]

M. Oliu-Barton, Splitting game: Uniform value and optimal strategies, Dynamic Games and Applications, 8 (2018), 157-179.  doi: 10.1007/s13235-017-0216-8.  Google Scholar

[16]

R. Rockafellar, Convex Analysis, Princeton University Press, 1997.  Google Scholar

[17]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel Journal of Mathematics, 121 (2001), 221-246.  doi: 10.1007/BF02802505.  Google Scholar

[18]

S. Sorin, A First Course on Zero-Sum Repeated Games, Springer, 2002.  Google Scholar

[19]

N. Vieille, Weak approachability, Mathematics of Operations Research, 17 (1992), 781-791.  doi: 10.1287/moor.17.4.781.  Google Scholar

Figure 1.  Duality between the hyperplanes above $ v_1(\, \cdot \, , Q) $ (resp. supporting $ v_1(\, \cdot \, , Q) $ at $ p\in \Delta(K) $) and the set $ B(Q) $ (resp. $ B(p, Q) $). Here, $ z \in B(Q) $ corresponds to the hyperplane $ p'\mapsto \langle z, p'\rangle $ and $ x\in B(p, Q) $ corresponds to $ p'\mapsto \langle x, p'\rangle $
Figure 2.  Illustration of the strategy at stage $ m $, in the case $ v(\pi_m)<u(\pi_m) $ where player $ 2 $ needs to use his private information. In the figure, $ R = \{r, r'\} $ and $ \alpha_m = ( \alpha, \alpha')\in \Delta(R) $. The vectors $ z_m(r) $ and $ z_m(r') $ belong, respectively, to $ B(p_m(r), Q_m(r)) $ and $ B(p_m(r), Q_m(r')) $. The construction is trivial in the case $ v(\pi_m)\geq u(\pi_m) $, for it is enough to take $ z_m(r) = z_m(r') = z_m $
[1]

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

[2]

Cyril Imbert, Sylvia Serfaty. Repeated games for non-linear parabolic integro-differential equations and integral curvature flows. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1517-1552. doi: 10.3934/dcds.2011.29.1517

[3]

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

[4]

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

[5]

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

[6]

Barak Shani, Eilon Solan. Strong approachability. Journal of Dynamics & Games, 2014, 1 (3) : 507-535. doi: 10.3934/jdg.2014.1.507

[7]

Matthew Bourque, T. E. S. Raghavan. Policy improvement for perfect information additive reward and additive transition stochastic games with discounted and average payoffs. Journal of Dynamics & Games, 2014, 1 (3) : 347-361. doi: 10.3934/jdg.2014.1.347

[8]

Vianney Perchet. Approachability, regret and calibration: Implications and equivalences. Journal of Dynamics & Games, 2014, 1 (2) : 181-254. doi: 10.3934/jdg.2014.1.181

[9]

Shie Mannor, Vianney Perchet, Gilles Stoltz. A primal condition for approachability with partial monitoring. Journal of Dynamics & Games, 2014, 1 (3) : 447-469. doi: 10.3934/jdg.2014.1.447

[10]

Maxime Breden. Applications of improved duality lemmas to the discrete coagulation-fragmentation equations with diffusion. Kinetic & Related Models, 2018, 11 (2) : 279-301. doi: 10.3934/krm.2018014

[11]

Ricardo J. Alonso, Véronique Bagland, Bertrand Lods. Uniform estimates on the Fisher information for solutions to Boltzmann and Landau equations. Kinetic & Related Models, 2019, 12 (5) : 1163-1183. doi: 10.3934/krm.2019044

[12]

Alain Bensoussan, Jens Frehse, Jens Vogelgesang. Systems of Bellman equations to stochastic differential games with non-compact coupling. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1375-1389. doi: 10.3934/dcds.2010.27.1375

[13]

François James, Nicolas Vauchelet. Equivalence between duality and gradient flow solutions for one-dimensional aggregation equations. Discrete & Continuous Dynamical Systems - A, 2016, 36 (3) : 1355-1382. doi: 10.3934/dcds.2016.36.1355

[14]

Yanju Zhou, Zhen Shen, Renren Ying, Xuanhua Xu. A loss-averse two-product ordering model with information updating in two-echelon inventory system. Journal of Industrial & Management Optimization, 2018, 14 (2) : 687-705. doi: 10.3934/jimo.2017069

[15]

Pierre Cardaliaguet, Chloé Jimenez, Marc Quincampoix. Pure and Random strategies in differential game with incomplete informations. Journal of Dynamics & Games, 2014, 1 (3) : 363-375. doi: 10.3934/jdg.2014.1.363

[16]

Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems & Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661

[17]

Frank Natterer. Incomplete data problems in wave equation imaging. Inverse Problems & Imaging, 2010, 4 (4) : 685-691. doi: 10.3934/ipi.2010.4.685

[18]

Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics & Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005

[19]

Regina S. Burachik, Xiaoqi Yang. Asymptotic strong duality. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 539-548. doi: 10.3934/naco.2011.1.539

[20]

Shiri Artstein-Avidan and Vitali Milman. A characterization of the concept of duality. Electronic Research Announcements, 2007, 14: 42-59. doi: 10.3934/era.2007.14.42

 Impact Factor: 

Metrics

  • PDF downloads (22)
  • HTML views (46)
  • Cited by (0)

Other articles
by authors

[Back to Top]