IDEAS home Printed from https://ideas.repec.org/p/zur/econwp/239.html
   My bibliography  Save this paper

Fictitious play in networks

Author

Listed:
  • Christian Ewerhart
  • Kremena Valkanova

Abstract

This paper studies fictitious play in networks of noncooperative two-person games. We show that continuous-time fictitious play converges to the set of Nash equilibria if the overall n-person game is zero-sum. Moreover, the rate of convergence is 1/T, regardless of the size of the network. In contrast, arbitrary n-person zero-sum games with bilinear payoff functions do not possess the continuous-time fictitious-play property. As extensions, we consider networks in which each bilateral game is either strategically zero-sum, a weighted potential game, or a two-by-two game. In those cases, convergence requires a condition on bilateral payoffs or, alternatively, that the network is acyclic. Our results hold also for the discrete-time variant of fictitious play, which implies, in particular, a generalization of Robinson's theorem to arbitrary zero-sum networks. Applications include security games, conflict networks, and decentralized wireless channel selection.

Suggested Citation

  • Christian Ewerhart & Kremena Valkanova, 2016. "Fictitious play in networks," ECON - Working Papers 239, Department of Economics - University of Zurich, revised Jun 2019.
  • Handle: RePEc:zur:econwp:239
    as

    Download full text from publisher

    File URL: http://www.econ.uzh.ch/static/wp/econwp239.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Lazear, Edward P & Rosen, Sherwin, 1981. "Rank-Order Tournaments as Optimum Labor Contracts," Journal of Political Economy, University of Chicago Press, vol. 89(5), pages 841-864, October.
    2. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    3. Dan Kovenock & Sudipta Sarangi & Matt Wiser, 2015. "All-pay 2 $$\times $$ × 2 Hex: a multibattle contest with complementarities," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 571-597, August.
    4. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    5. Yann Bramoullé & Andrea Galeotti & Brian Rogers, 2016. "The Oxford Handbook of the Economics of Networks," Post-Print hal-01447842, HAL.
    6. Dan Kovenock & Michael R. Baye & Casper G. de Vries, 1996. "The all-pay auction with complete information (*)," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(2), pages 291-305.
    7. Xu, Jin & Zenou, Yves & Zhou, Junjie, 2019. "Networks in Conflict: A Variational Inequality Approach," CEPR Discussion Papers 13647, C.E.P.R. Discussion Papers.
    8. Gaunersdorfer Andrea & Hofbauer Josef, 1995. "Fictitious Play, Shapley Polygons, and the Replicator Equation," Games and Economic Behavior, Elsevier, vol. 11(2), pages 279-303, November.
    9. Michael D. König & Dominic Rohner & Mathias Thoenig & Fabrizio Zilibotti, 2017. "Networks in Conflict: Theory and Evidence From the Great War of Africa," Econometrica, Econometric Society, vol. 85, pages 1093-1132, July.
    10. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    11. Sergiu Hart & Andreu Mas-Colell, 2013. "A General Class Of Adaptive Strategies," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 3, pages 47-76, World Scientific Publishing Co. Pte. Ltd..
    12. Blume Lawrence E., 1993. "The Statistical Mechanics of Strategic Interaction," Games and Economic Behavior, Elsevier, vol. 5(3), pages 387-424, July.
    13. Ulrich Berger, 2006. "A Generalized Model Of Best Response Adaptation," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 8(01), pages 45-66.
    14. MOULIN, Hervé & VIAL, Jean-Philippe, 1978. "Strategically zero-sum games: the class of games whose completely mixed equilibria connot be improved upon," LIDAM Reprints CORE 359, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Yann Bramoullé & Andrea Galeotti & Brian Rogers, 2016. "The Oxford Handbook of the Economics of Networks," Post-Print hal-03572533, HAL.
    16. Jackson, Matthew O. & Nei, Stephen, 2014. "Networks of Military Alliances, Wars, and International Trade," Climate Change and Sustainable Development 172702, Fondazione Eni Enrico Mattei (FEEM).
    17. Gjerstad, Steven, 1996. "The Rate of Convergence of Continuous Fictitious Play," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 161-177, January.
    18. Yann Bramoullé & Rachel Kranton, 2015. "Games Played on Networks," Working Papers halshs-01180657, HAL.
    19. Yang Cai & Ozan Candogan & Constantinos Daskalakis & Christos Papadimitriou, 2016. "Zero-Sum Polymatrix Games: A Generalization of Minmax," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 648-655, May.
    20. Yann Bramoull? & Rachel Kranton & Martin D'Amours, 2014. "Strategic Interaction and Networks," American Economic Review, American Economic Association, vol. 104(3), pages 898-930, March.
    21. Daron Acemoglu & Asuman Ozdaglar, 2011. "Opinion Dynamics and Learning in Social Networks," Dynamic Games and Applications, Springer, vol. 1(1), pages 3-49, March.
    22. Brian Roberson, 2006. "The Colonel Blotto game," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 1-24, September.
    23. Metrick, Andrew & Polak, Ben, 1994. "Fictitious Play in 2 x 2 Games: A Geometric Proof of Convergence," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 4(6), pages 923-933, October.
    24. Berger, Ulrich, 2008. "Learning in games with strategic complementarities revisited," Journal of Economic Theory, Elsevier, vol. 143(1), pages 292-301, November.
    25. Gilboa, Itzhak & Matsui, Akihiko, 1991. "Social Stability and Equilibrium," Econometrica, Econometric Society, vol. 59(3), pages 859-867, May.
    26. Harris, Christopher, 1998. "On the Rate of Convergence of Continuous-Time Fictitious Play," Games and Economic Behavior, Elsevier, vol. 22(2), pages 238-259, February.
    27. Kenan Huremovic, 2014. "Rent Seeking and Power Hierarchies: A Noncooperative Model of Network Formation with Antagonistic Links," Working Papers 2014.45, Fondazione Eni Enrico Mattei.
    28. Dan Kovenock & Brian Roberson, 2018. "The Optimal Defense Of Networks Of Targets," Economic Inquiry, Western Economic Association International, vol. 56(4), pages 2195-2211, October.
    29. Renaud Bourlès & Yann Bramoullé & Eduardo Perez‐Richet, 2017. "Altruism in Networks," Econometrica, Econometric Society, vol. 85, pages 675-689, March.
    30. Ulrich Berger, 2012. "Non-algebraic Convergence Proofs for Continuous-Time Fictitious Play," Dynamic Games and Applications, Springer, vol. 2(1), pages 4-17, March.
    31. Hofbauer, Josef & Sandholm, William H., 2009. "Stable games and their dynamics," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1665-1693.4, July.
    32. Monderer, Dov & Shapley, Lloyd S., 1996. "Fictitious Play Property for Games with Identical Interests," Journal of Economic Theory, Elsevier, vol. 68(1), pages 258-265, January.
    33. Bramoulle, Yann & Galeotti, Andrea & Rogers, Brian (ed.), 2016. "The Oxford Handbook of the Economics of Networks," OUP Catalogue, Oxford University Press, number 9780199948277.
    34. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July.
    35. Alberto Vesperoni, 2016. "A contest success function for rankings," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(4), pages 905-937, December.
    36. Monderer, Dov & Sela, Aner, 1997. "Fictitious play and- no-cycling conditions," Sonderforschungsbereich 504 Publications 97-12, Sonderforschungsbereich 504, Universität Mannheim;Sonderforschungsbereich 504, University of Mannheim.
    37. Josef Hofbauer & William H. Sandholm, 2002. "On the Global Convergence of Stochastic Fictitious Play," Econometrica, Econometric Society, vol. 70(6), pages 2265-2294, November.
    38. Morris, Stephen & Ui, Takashi, 2004. "Best response equivalence," Games and Economic Behavior, Elsevier, vol. 49(2), pages 260-287, November.
    39. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945.
    40. Monderer, Dov & Samet, Dov & Sela, Aner, 1997. "Belief Affirming in Learning Processes," Journal of Economic Theory, Elsevier, vol. 73(2), pages 438-452, April.
    41. Monderer, Dov & Sela, Aner, 1996. "A2 x 2Game without the Fictitious Play Property," Games and Economic Behavior, Elsevier, vol. 14(1), pages 144-148, May.
    42. Jack Hirshleifer, 1989. "Conflict and rent-seeking success functions: Ratio vs. difference models of relative success," Public Choice, Springer, vol. 63(2), pages 101-112, November.
    43. Milgrom, Paul & Roberts, John, 1991. "Adaptive and sophisticated learning in normal form games," Games and Economic Behavior, Elsevier, vol. 3(1), pages 82-100, February.
    44. Driesen, B.W.I., 2009. "Continuous fictitious play in zero-sum games," Research Memorandum 049, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    45. Bozbay, Irem & Vesperoni, Alberto, 2018. "A contest success function for networks," Journal of Economic Behavior & Organization, Elsevier, vol. 150(C), pages 404-422.
    46. Monderer, Dov & Sela, Aner, 1997. "Fictitious play and no-cycling conditions," Papers 97-12, Sonderforschungsbreich 504.
    47. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    48. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ewerhart, Christian, 2017. "The lottery contest is a best-response potential game," Economics Letters, Elsevier, vol. 155(C), pages 168-171.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ulrich Berger, 2004. "Two More Classes of Games with the Fictitious Play Property," Game Theory and Information 0408003, University Library of Munich, Germany.
    2. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    3. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    4. Ulrich Berger, 2004. "Some Notes on Learning in Games with Strategic Complementarities," Game Theory and Information 0409001, University Library of Munich, Germany.
    5. Berger, Ulrich, 2007. "Two more classes of games with the continuous-time fictitious play property," Games and Economic Behavior, Elsevier, vol. 60(2), pages 247-261, August.
    6. Ulrich Berger, 2003. "Fictitious play in 2xn games," Game Theory and Information 0303009, University Library of Munich, Germany.
    7. Sandholm,W.H., 2003. "Excess payoff dynamics, potential dynamics, and stable games," Working papers 5, Wisconsin Madison - Social Systems.
    8. Hofbauer,J. & Sandholm,W.H., 2001. "Evolution and learning in games with randomly disturbed payoffs," Working papers 5, Wisconsin Madison - Social Systems.
    9. Cortes-Corrales, Sebastián & Gorny, Paul M., 2018. "Generalising Conflict Networks," MPRA Paper 90001, University Library of Munich, Germany.
    10. Bochet, Olivier & Faure, Mathieu & Long, Yan & Zenou, Yves, 2020. "Perceived Competition in Networks," CEPR Discussion Papers 15582, C.E.P.R. Discussion Papers.
    11. Berger, Ulrich, 2008. "Learning in games with strategic complementarities revisited," Journal of Economic Theory, Elsevier, vol. 143(1), pages 292-301, November.
    12. Sandholm,W.H., 2002. "Potential dynamics and stable games," Working papers 21, Wisconsin Madison - Social Systems.
    13. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    14. Bochet, Olivier & Faure, Mathieu & Long, Yan & Zenou, Yves, 2020. "Perceived Competition in Networks," CEPR Discussion Papers 15582, C.E.P.R. Discussion Papers.
    15. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2012. "Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory," Dynamic Games and Applications, Springer, vol. 2(2), pages 195-205, June.
    16. van Strien, Sebastian & Sparrow, Colin, 2011. "Fictitious play in 3x3 games: Chaos and dithering behaviour," Games and Economic Behavior, Elsevier, vol. 73(1), pages 262-286, September.
    17. Berger, Ulrich, 2007. "Brown's original fictitious play," Journal of Economic Theory, Elsevier, vol. 135(1), pages 572-578, July.
    18. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    19. Berger, Ulrich, 2005. "Fictitious play in 2 x n games," Journal of Economic Theory, Elsevier, vol. 120(2), pages 139-154, February.
    20. Ulrich Berger, 2012. "Non-algebraic Convergence Proofs for Continuous-Time Fictitious Play," Dynamic Games and Applications, Springer, vol. 2(1), pages 4-17, March.

    More about this item

    Keywords

    Fictitious play; networks; zero-sum games; conflicts; potential games; Miyasawa's theorem; Robinson's theorem;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness
    • D85 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Network Formation

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:zur:econwp:239. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Severin Oswald (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.