American Institute of Mathematical Sciences

Advanced
July  2014, 1(3): 507-535. doi: 10.3934/jdg.2014.1.507

Strong approachability

Barak Shani 1, and  Eilon Solan 1,

1. 

School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel, Israel

Received  February 2013 Revised  October 2013 Published  July 2014

We introduce the concept of strongly approachable sets in two-player repeated games with vector payoffs. A set in the payoff space is strongly approachable by a player if the player can guarantee that from a certain stage on the average payoff will be inside that set, regardless of the strategy that the other player implements. We provide sufficient conditions that ensure that a closed convex approachable set is also strongly approachable in the expected deterministic version of the game.
Keywords: vector payoffs, strong approachability., Approachability, repeated games.
Mathematics Subject Classification: Primary: 91A05, 91A10, 91A2.
Citation: Barak Shani, Eilon Solan. Strong approachability. Journal of Dynamics & Games, 2014, 1 (3) : 507-535. doi: 10.3934/jdg.2014.1.507
References:
[1]

R. J. Aumann and M. Maschler, Repeated games of incomplete information: A survey of recent results,, in Reports of the U.S. Arms Control and Disarmament Agency ST-116, (1967), 287. Google Scholar

[2]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information,, MIT Press, (1995). Google Scholar

[3]

D. Blackwell, An analog of the minmax theorem for vector payoffs,, Pacific Journal of Mathematics, 6 (1956), 1. doi: 10.2140/pjm.1956.6.1. Google Scholar

[4]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning and Games,, Cambridge University Press, (2006). doi: 10.1017/CBO9780511546921. Google Scholar

[5]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium,, Games Economics Behavior, 21 (1997), 40. doi: 10.1006/game.1997.0595. Google Scholar

[6]

M. A. Goberna, E. Gonzalez, J. E. Martinez-Legaz and M. I. Todorov, Motzkin decomposition of closed convex sets,, Journal of Mathematical Analysis and Applications, 364 (2010), 209. doi: 10.1016/j.jmaa.2009.10.015. Google Scholar

[7]

S. Hart and A. Mas-Colell, A simple adaptive procedure leading to correlated equilibrium,, Econometrica, 68 (2000), 1127. doi: 10.1111/1468-0262.00153. Google Scholar

[8]

T. F. Hou, Approachability in a two-person game,, The Annals of Mathematical Statistics, 42 (1971), 735. doi: 10.1214/aoms/1177693422. Google Scholar

[9]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, International Journal of Game Theory, 4 (1975), 7. doi: 10.1007/BF01766399. Google Scholar

[10]

E. Lehrer, Approachability in infinitely dimensional spaces,, International Journal of Game Theory, 31 (2002), 253. doi: 10.1007/s001820200115. Google Scholar

[11]

E. Lehrer, The game of normal numbers,, Mathematics of Operations Research, 29 (2004), 259. doi: 10.1287/moor.1030.0087. Google Scholar

[12]

S. Mannor and V. Perchet, Approachability, Fast and slow,, JMLR Workshop and Conference Proceedings, 30 (2013), 474. Google Scholar

[13]

M. Maschler, E. Solan and S. Zamir, Game Theory,, Cambridge University Press, (2013). doi: 10.1017/CBO9780511794216. Google Scholar

[14]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970). Google Scholar

[15]

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. doi: 10.1137/S0363012902407107. Google Scholar

[16]

S. Sorin, Zero-sum repeated games: recent advances and new links with differential games,, Dynamic Games and Applications, 1 (2011), 172. doi: 10.1007/s13235-010-0006-z. Google Scholar

[17]

X. Spinat, A necessary and sufficient condition for approachability,, Mathematics of Operations Research, 27 (2002), 31. doi: 10.1287/moor.27.1.31.333. Google Scholar

show all references

References:
[1]

R. J. Aumann and M. Maschler, Repeated games of incomplete information: A survey of recent results,, in Reports of the U.S. Arms Control and Disarmament Agency ST-116, (1967), 287. Google Scholar

[2]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information,, MIT Press, (1995). Google Scholar

[3]

D. Blackwell, An analog of the minmax theorem for vector payoffs,, Pacific Journal of Mathematics, 6 (1956), 1. doi: 10.2140/pjm.1956.6.1. Google Scholar

[4]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning and Games,, Cambridge University Press, (2006). doi: 10.1017/CBO9780511546921. Google Scholar

[5]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium,, Games Economics Behavior, 21 (1997), 40. doi: 10.1006/game.1997.0595. Google Scholar

[6]

M. A. Goberna, E. Gonzalez, J. E. Martinez-Legaz and M. I. Todorov, Motzkin decomposition of closed convex sets,, Journal of Mathematical Analysis and Applications, 364 (2010), 209. doi: 10.1016/j.jmaa.2009.10.015. Google Scholar

[7]

S. Hart and A. Mas-Colell, A simple adaptive procedure leading to correlated equilibrium,, Econometrica, 68 (2000), 1127. doi: 10.1111/1468-0262.00153. Google Scholar

[8]

T. F. Hou, Approachability in a two-person game,, The Annals of Mathematical Statistics, 42 (1971), 735. doi: 10.1214/aoms/1177693422. Google Scholar

[9]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, International Journal of Game Theory, 4 (1975), 7. doi: 10.1007/BF01766399. Google Scholar

[10]

E. Lehrer, Approachability in infinitely dimensional spaces,, International Journal of Game Theory, 31 (2002), 253. doi: 10.1007/s001820200115. Google Scholar

[11]

E. Lehrer, The game of normal numbers,, Mathematics of Operations Research, 29 (2004), 259. doi: 10.1287/moor.1030.0087. Google Scholar

[12]

S. Mannor and V. Perchet, Approachability, Fast and slow,, JMLR Workshop and Conference Proceedings, 30 (2013), 474. Google Scholar

[13]

M. Maschler, E. Solan and S. Zamir, Game Theory,, Cambridge University Press, (2013). doi: 10.1017/CBO9780511794216. Google Scholar

[14]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970). Google Scholar

[15]

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. doi: 10.1137/S0363012902407107. Google Scholar

[16]

S. Sorin, Zero-sum repeated games: recent advances and new links with differential games,, Dynamic Games and Applications, 1 (2011), 172. doi: 10.1007/s13235-010-0006-z. Google Scholar

[17]

X. Spinat, A necessary and sufficient condition for approachability,, Mathematics of Operations Research, 27 (2002), 31. doi: 10.1287/moor.27.1.31.333. Google Scholar

[1]

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
[2]

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
[3]

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
[4]

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
[5]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics & Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008
[6]

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

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
[8]

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
[9]

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
[10]

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
[11]

Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial & Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563
[12]

Kenji Kimura, Jen-Chih Yao. Semicontinuity of solution mappings of parametric generalized strong vector equilibrium problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 167-181. doi: 10.3934/jimo.2008.4.167
[13]

Nguyen Ba Minh, Pham Huu Sach. Strong vector equilibrium problems with LSC approximate solution mappings. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2018165
[14]

Lam Quoc Anh, Nguyen Van Hung. Gap functions and Hausdorff continuity of solution mappings to parametric strong vector quasiequilibrium problems. Journal of Industrial & Management Optimization, 2018, 14 (1) : 65-79. doi: 10.3934/jimo.2017037
[15]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[16]

Yan Liu, Minjia Shi, Hai Q. Dinh, Songsak Sriboonchitta. Repeated-root constacyclic codes of length $ 3\ell^mp^s $. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020025
[17]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117
[18]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016
[19]

Hassan Najafi Alishah, Pedro Duarte. Hamiltonian evolutionary games. Journal of Dynamics & Games, 2015, 2 (1) : 33-49. doi: 10.3934/jdg.2015.2.33
[20]

Yonghui Zhou, Jian Yu, Long Wang. Topological essentiality in infinite games. Journal of Industrial & Management Optimization, 2012, 8 (1) : 179-187. doi: 10.3934/jimo.2012.8.179

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences