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 and 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.

[2]

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

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

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

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

[6]

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

[7]

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

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

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

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

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

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

[13]

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

[14]

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

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

[16]

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

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

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

[19]

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

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

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

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

[23]

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

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

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

[26]

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

[27]

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

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

[29]

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

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

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

[32]

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

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.

[2]

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

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

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

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

[6]

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

[7]

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

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

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

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

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

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

[13]

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

[14]

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

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

[16]

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

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

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

[19]

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

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

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

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

[23]

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

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

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

[26]

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

[27]

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

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

[29]

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

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

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

[32]

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

[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 and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[2]

Jiequn Han, Ruimeng Hu, Jihao Long. Convergence of deep fictitious play for stochastic differential games. Frontiers of Mathematical Finance, 2022, 1 (2) : 287-319. doi: 10.3934/fmf.2021011
[3]

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

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

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

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

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

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

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

Zhi Lin, Zaiyun Peng. Algorithms for the Pareto solution of the multicriteria traffic equilibrium problem with capacity constraints of arcs. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022104
[11]

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

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

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

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

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

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

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

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 and Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299
[19]

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

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy