Payoff performance of fictitious play

Georg Ostrovski; Sebastian van Strien

doi:10.3934/jdg.2014.1.621

Article Contents

2014, Volume 1, Issue 4: 621-638. Doi: 10.3934/jdg.2014.1.621

This issue Previous Article A game theoretic analysis of the cops and robber game Next Article A limit theorem for Markov decision processes

Payoff performance of fictitious play

Georg Ostrovski^1, and
Sebastian van Strien^2,

1.
Mathematics Institute, Zeeman Building, University of Warwick, Coventry CV4 7AL
2.
Department of Mathematics, Imperial College London, London SW7 2AZ

Received: August 2013

Revised: November 2014

Published: October 2014

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 91A20, 91A26; Secondary: 91A05, 34A60.

Citation:

Related Papers

Cited by

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.