American Institute of Mathematical Sciences

Advanced
October  2014, 1(4): 621-638. doi: 10.3934/jdg.2014.1.621

Payoff performance of fictitious play

Georg Ostrovski 1, and  Sebastian van Strien 2,

1. 

Mathematics Institute, Zeeman Building, University of Warwick, Coventry CV4 7AL, United Kingdom
2. 

Department of Mathematics, Imperial College London, London SW7 2AZ, United Kingdom

Received  August 2013 Revised  November 2014 Published  November 2014

We investigate how well continuous-time fictitious play in two-player games performs in terms of average payoff, particularly compared to Nash equilibrium payoff. We show that in many games, fictitious play outperforms Nash equilibrium on average or even at all times, and moreover that any game is linearly equivalent to one in which this is the case. Conversely, we provide conditions under which Nash equilibrium payoff dominates fictitious play payoff. A key step in our analysis is to show that fictitious play dynamics asymptotically converges to the set of coarse correlated equilibria (a fact which is implicit in the literature).
Keywords: Nash equilibrium, Fictitious play, payoff performance, coarse correlated equilibrium., learning algorithms.
Mathematics Subject Classification: Primary: 91A20, 91A26; Secondary: 91A05, 34A6.
Citation: Georg Ostrovski, Sebastian van Strien. Payoff performance of fictitious play. Journal of Dynamics & Games, 2014, 1 (4) : 621-638. doi: 10.3934/jdg.2014.1.621
References:
[1]

R. J. Aumann, Subjectivity and correlation in randomized strategies, J. Math. Econom., 1 (1974), 67-96. doi: 10.1016/0304-4068(74)90037-8.  Google Scholar

[2]

R. J. Aumann, Correlated equilibrium as an expression of Bayesian rationality, Econometrica, 55 (1987), 1-18. doi: 10.2307/1911154.  Google Scholar

[3]

U. Berger, Fictitious play in $2 \times n$ games, J. Econ. Theory, 120 (2005), 139-154. doi: 10.1016/j.jet.2004.02.003.  Google Scholar

[4]

U. Berger, Two more classes of games with the continuous-time fictitious play property, Game. Econ. Behav., 60 (2007), 247-261. doi: 10.1016/j.geb.2006.10.008.  Google Scholar

[5]

U. Berger, Learning in games with strategic complementarities revisited, J. Econ. Theory, 143 (2008), 292-301. doi: 10.1016/j.jet.2008.01.007.  Google Scholar

[6]

D. Blackwell, Controlled random walks, In Proceedings of the International Congress of Mathematicians, 3 (1954), 336-338.  Google Scholar

[7]

G. W. Brown, Some notes on computation of games solutions, Technical report, Report P-78, The Rand Corporation, 1949. Google Scholar

[8]

G. W. Brown, Iterative solution of games by fictitious play, In Activity Analysis of Production and Allocation, volume 13, pages 374-376. John Wiley & Sons, New York, 1951.  Google Scholar

[9]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium, Game. Econ. Behav., 21 (1997), 40-55. doi: 10.1006/game.1997.0595.  Google Scholar

[10]

D. Fudenberg and D. K. Levine, Consistency and cautious fictitious play, J. Econ. Dyn. Control, 19 (1995), 1065-1089. doi: 10.1016/0165-1889(94)00819-4.  Google Scholar

[11]

D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press Series on Economic Learning and Social Evolution, 2. MIT Press, Cambridge, MA, 1998.  Google Scholar

[12]

A. Gaunersdorfer and J. Hofbauer, Fictitious play, Shapley polygons, and the replicator equation, Game. Econ. Behav., 11 (1995), 279-303. doi: 10.1006/game.1995.1052.  Google Scholar

[13]

I. Gilboa and A. Matsui, Social stability and equilibrium, Econometrica, 59 (1991), 859-867. doi: 10.2307/2938230.  Google Scholar

[14]

J. Hannan, Approximation to Bayes risk in repeated play, Contributions to the Theory of Games, 3 (1957), 97-139.  Google Scholar

[15]

C. Harris, On the rate of convergence of continuous-time fictitious play, Game. Econ. Behav., 22 (1998), 238-259. doi: 10.1006/game.1997.0582.  Google Scholar

[16]

S. Hart, Adaptive heuristics, Econometrica, 73 (2005), 1401-1430. doi: 10.1111/j.1468-0262.2005.00625.x.  Google Scholar

[17]

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.  Google Scholar

[18]

S. Hart and A. Mas-Colell, A general class of adaptive strategies, J. Econ. Theory, 98 (2001), 26-54. doi: 10.1006/jeth.2000.2746.  Google Scholar

[19]

J. Hofbauer, Stability for the Best Response Dynamics, Mimeo, 1995. Google Scholar

[20]

V. Krishna and T. Sjöström, On the convergence of fictitious play, Math. Oper. Res., 23 (1998), 479-511. doi: 10.1287/moor.23.2.479.  Google Scholar

[21]

A. Matsui, Best response dynamics and socially stable strategies, J. Econ. Theory, 57 (1992), 343-362. doi: 10.1016/0022-0531(92)90040-O.  Google Scholar

[22]

D. Monderer, D. Samet and A. Sela, Belief affirming in learning processes, J. Econ. Theory, 73 (1997), 438-452. doi: 10.1006/jeth.1996.2245.  Google Scholar

[23]

S. Morris and T. Ui, Best response equivalence, Game. Econ. Behav., 49 (2004), 260-287. doi: 10.1016/j.geb.2003.12.004.  Google Scholar

[24]

H. J. Moulin and J.-P. Vial, Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon, Internat. J. Game Theory, 7 (1978), 201-221. doi: 10.1007/BF01769190.  Google Scholar

[25]

G. Ostrovski and S. van Strien, Piecewise linear Hamiltonian flows associated to zero-sum games: Transition combinatorics and questions on ergodicity, Regul. Chaotic Dyn., 16 (2011), 128-153. doi: 10.1134/S1560354711010059.  Google Scholar

[26]

J. Rosenmüller, Über Periodizitätseigenschaften spieltheoretischer Lernprozesse, Z. Wahrscheinlichkeit., 17 (1971), 259-308. doi: 10.1007/BF00536300.  Google Scholar

[27]

L. S. Shapley, Some topics in two-person games, Advances in Game Theory, 52 (1964), 1-28.  Google Scholar

[28]

C. Sparrow, S. van Strien and C. Harris, Fictitious play in $3\times 3$ games: The transition between periodic and chaotic behaviour, Game. Econ. Behav., 63 (2008), 259-291. doi: 10.1016/j.geb.2007.08.005.  Google Scholar

[29]

K. Sydsaeter and P. Hammond, Essential Mathematics for Economic Analysis, Prentice Hall, 3rd edition, 2008. Google Scholar

[30]

S. van Strien and C. Sparrow, Fictitious play in $3 \times 3$ games: Chaos and dithering behaviour, Game. Econ. Behav., 73 (2011), 262-286. doi: 10.1016/j.geb.2010.12.004.  Google Scholar

[31]

S. van Strien, A new class of Hamiltonian flows with random-walk behavior originating from zero-sum games and Fictitious Play, Nonlinearity, 24 (2011), 1715-1742. doi: 10.1088/0951-7715/24/6/002.  Google Scholar

[32]

H. P. Young, Strategic Learning and Its Limits (Arne Ryde Memorial Lectures Series), Oxford University Press, USA, 2005. Google Scholar

show all references

References:
[1]

R. J. Aumann, Subjectivity and correlation in randomized strategies, J. Math. Econom., 1 (1974), 67-96. doi: 10.1016/0304-4068(74)90037-8.  Google Scholar

[2]

R. J. Aumann, Correlated equilibrium as an expression of Bayesian rationality, Econometrica, 55 (1987), 1-18. doi: 10.2307/1911154.  Google Scholar

[3]

U. Berger, Fictitious play in $2 \times n$ games, J. Econ. Theory, 120 (2005), 139-154. doi: 10.1016/j.jet.2004.02.003.  Google Scholar

[4]

U. Berger, Two more classes of games with the continuous-time fictitious play property, Game. Econ. Behav., 60 (2007), 247-261. doi: 10.1016/j.geb.2006.10.008.  Google Scholar

[5]

U. Berger, Learning in games with strategic complementarities revisited, J. Econ. Theory, 143 (2008), 292-301. doi: 10.1016/j.jet.2008.01.007.  Google Scholar

[6]

D. Blackwell, Controlled random walks, In Proceedings of the International Congress of Mathematicians, 3 (1954), 336-338.  Google Scholar

[7]

G. W. Brown, Some notes on computation of games solutions, Technical report, Report P-78, The Rand Corporation, 1949. Google Scholar

[8]

G. W. Brown, Iterative solution of games by fictitious play, In Activity Analysis of Production and Allocation, volume 13, pages 374-376. John Wiley & Sons, New York, 1951.  Google Scholar

[9]

D. P. Foster and R. V. Vohra, Calibrated learning and correlated equilibrium, Game. Econ. Behav., 21 (1997), 40-55. doi: 10.1006/game.1997.0595.  Google Scholar

[10]

D. Fudenberg and D. K. Levine, Consistency and cautious fictitious play, J. Econ. Dyn. Control, 19 (1995), 1065-1089. doi: 10.1016/0165-1889(94)00819-4.  Google Scholar

[11]

D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press Series on Economic Learning and Social Evolution, 2. MIT Press, Cambridge, MA, 1998.  Google Scholar

[12]

A. Gaunersdorfer and J. Hofbauer, Fictitious play, Shapley polygons, and the replicator equation, Game. Econ. Behav., 11 (1995), 279-303. doi: 10.1006/game.1995.1052.  Google Scholar

[13]

I. Gilboa and A. Matsui, Social stability and equilibrium, Econometrica, 59 (1991), 859-867. doi: 10.2307/2938230.  Google Scholar

[14]

J. Hannan, Approximation to Bayes risk in repeated play, Contributions to the Theory of Games, 3 (1957), 97-139.  Google Scholar

[15]

C. Harris, On the rate of convergence of continuous-time fictitious play, Game. Econ. Behav., 22 (1998), 238-259. doi: 10.1006/game.1997.0582.  Google Scholar

[16]

S. Hart, Adaptive heuristics, Econometrica, 73 (2005), 1401-1430. doi: 10.1111/j.1468-0262.2005.00625.x.  Google Scholar

[17]

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.  Google Scholar

[18]

S. Hart and A. Mas-Colell, A general class of adaptive strategies, J. Econ. Theory, 98 (2001), 26-54. doi: 10.1006/jeth.2000.2746.  Google Scholar

[19]

J. Hofbauer, Stability for the Best Response Dynamics, Mimeo, 1995. Google Scholar

[20]

V. Krishna and T. Sjöström, On the convergence of fictitious play, Math. Oper. Res., 23 (1998), 479-511. doi: 10.1287/moor.23.2.479.  Google Scholar

[21]

A. Matsui, Best response dynamics and socially stable strategies, J. Econ. Theory, 57 (1992), 343-362. doi: 10.1016/0022-0531(92)90040-O.  Google Scholar

[22]

D. Monderer, D. Samet and A. Sela, Belief affirming in learning processes, J. Econ. Theory, 73 (1997), 438-452. doi: 10.1006/jeth.1996.2245.  Google Scholar

[23]

S. Morris and T. Ui, Best response equivalence, Game. Econ. Behav., 49 (2004), 260-287. doi: 10.1016/j.geb.2003.12.004.  Google Scholar

[24]

H. J. Moulin and J.-P. Vial, Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon, Internat. J. Game Theory, 7 (1978), 201-221. doi: 10.1007/BF01769190.  Google Scholar

[25]

G. Ostrovski and S. van Strien, Piecewise linear Hamiltonian flows associated to zero-sum games: Transition combinatorics and questions on ergodicity, Regul. Chaotic Dyn., 16 (2011), 128-153. doi: 10.1134/S1560354711010059.  Google Scholar

[26]

J. Rosenmüller, Über Periodizitätseigenschaften spieltheoretischer Lernprozesse, Z. Wahrscheinlichkeit., 17 (1971), 259-308. doi: 10.1007/BF00536300.  Google Scholar

[27]

L. S. Shapley, Some topics in two-person games, Advances in Game Theory, 52 (1964), 1-28.  Google Scholar

[28]

C. Sparrow, S. van Strien and C. Harris, Fictitious play in $3\times 3$ games: The transition between periodic and chaotic behaviour, Game. Econ. Behav., 63 (2008), 259-291. doi: 10.1016/j.geb.2007.08.005.  Google Scholar

[29]

K. Sydsaeter and P. Hammond, Essential Mathematics for Economic Analysis, Prentice Hall, 3rd edition, 2008. Google Scholar

[30]

S. van Strien and C. Sparrow, Fictitious play in $3 \times 3$ games: Chaos and dithering behaviour, Game. Econ. Behav., 73 (2011), 262-286. doi: 10.1016/j.geb.2010.12.004.  Google Scholar

[31]

S. van Strien, A new class of Hamiltonian flows with random-walk behavior originating from zero-sum games and Fictitious Play, Nonlinearity, 24 (2011), 1715-1742. doi: 10.1088/0951-7715/24/6/002.  Google Scholar

[32]

H. P. Young, Strategic Learning and Its Limits (Arne Ryde Memorial Lectures Series), Oxford University Press, USA, 2005. Google Scholar

[1]

Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[2]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[3]

Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[4]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[5]

Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1
[6]

Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153
[7]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[8]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[9]

Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843
[10]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010
[11]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
[12]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[13]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049
[14]

Dmitry Pozharskiy, Noah J. Wichrowski, Andrew B. Duncan, Grigorios A. Pavliotis, Ioannis G. Kevrekidis. Manifold learning for accelerating coarse-grained optimization. Journal of Computational Dynamics, 2020, 7 (2) : 511-536. doi: 10.3934/jcd.2020021
[15]

Zaki Chbani, Hassan Riahi. Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 353-366. doi: 10.3934/naco.2013.3.353
[16]

Sin-Man Choi, Ximin Huang, Wai-Ki Ching. Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment. Journal of Industrial & Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299
[17]

Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. Performance analysis of buffers with train arrivals and correlated output interruptions. Journal of Industrial & Management Optimization, 2015, 11 (3) : 829-848. doi: 10.3934/jimo.2015.11.829
[18]

Hongyu He, Naohiro Kato. Equilibrium submanifold for a biological system. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1429-1441. doi: 10.3934/dcdss.2011.4.1429
[19]

Alain Chenciner. The angular momentum of a relative equilibrium. Discrete & Continuous Dynamical Systems, 2013, 33 (3) : 1033-1047. doi: 10.3934/dcds.2013.33.1033
[20]

Manuel Friedrich, Martin Kružík, Ulisse Stefanelli. Equilibrium of immersed hyperelastic solids. Discrete & Continuous Dynamical Systems - S, 2021, 14 (11) : 4141-4157. doi: 10.3934/dcdss.2021003

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy