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

Strong approachability

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.
Citation: Barak Shani, Eilon Solan. Strong approachability. Journal of Dynamics and 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, Washingtom, D.C., Chapter III, 1967, 287-403.

[2]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information, MIT Press, Cambridge, 1995.

[3]

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

[4]

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

[5]

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

[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-221. doi: 10.1016/j.jmaa.2009.10.015.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

[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-110. doi: 10.1137/S0363012902407107.

[16]

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

[17]

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

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, Washingtom, D.C., Chapter III, 1967, 287-403.

[2]

R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information, MIT Press, Cambridge, 1995.

[3]

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

[4]

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

[5]

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

[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-221. doi: 10.1016/j.jmaa.2009.10.015.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

[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-110. doi: 10.1137/S0363012902407107.

[16]

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

[17]

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

[1]

Dario Bauso, Thomas W. L. Norman. Approachability in population games. Journal of Dynamics and Games, 2020, 7 (4) : 269-289. doi: 10.3934/jdg.2020019

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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 and Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008

[7]

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

[8]

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

[9]

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

[10]

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 and Games, 2014, 1 (3) : 347-361. doi: 10.3934/jdg.2014.1.347

[11]

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

[12]

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 and Games, 2014, 1 (3) : 411-445. doi: 10.3934/jdg.2014.1.411

[13]

Aradhana Narang, A. J. Shaiju. Neighborhood strong superiority and evolutionary stability of polymorphic profiles in asymmetric games. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022012

[14]

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

[15]

Nguyen Ba Minh, Pham Huu Sach. Strong vector equilibrium problems with LSC approximate solution mappings. Journal of Industrial and Management Optimization, 2020, 16 (2) : 511-529. doi: 10.3934/jimo.2018165

[16]

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

[17]

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

[18]

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

[19]

Yan Liu, Minjia Shi, Hai Q. Dinh, Songsak Sriboonchitta. Repeated-root constacyclic codes of length $ 3\ell^mp^s $. Advances in Mathematics of Communications, 2020, 14 (2) : 359-378. doi: 10.3934/amc.2020025

[20]

Tingting Wu, Shixin Zhu, Li Liu, Lanqiang Li. Repeated-root constacyclic codes of length 6lmpn. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021044

 Impact Factor: 

Metrics

  • PDF downloads (83)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]