IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v123y2020icp182-206.html
   My bibliography  Save this article

Fictitious play in networks

Author

Listed:
  • Ewerhart, Christian
  • Valkanova, Kremena

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/τ, 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

  • Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    • Handle: RePEc:eee:gamebe:v:123:y:2020:i:c:p:182-206
    DOI: 10.1016/j.geb.2020.06.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825620300919
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2020.06.006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    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. Bramoulle, Yann & Galeotti, Andrea & Rogers, Brian (ed.), 2016. "The Oxford Handbook of the Economics of Networks," OUP Catalogue, Oxford University Press, number 9780199948277.
    3. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July.
    4. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    5. 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.
    6. 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.
    7. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    8. Matthew O. Jackson & Stephen Nei, 2014. "Networks of Military Alliances, Wars, and International Trade," Working Papers 2014.46, Fondazione Eni Enrico Mattei.
    9. 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..
    10. Renaud Bourlès & Yann Bramoullé & Eduardo Perez‐Richet, 2017. "Altruism in Networks," Econometrica, Econometric Society, vol. 85, pages 675-689, March.
    11. Monderer, Dov & Sela, Aner, 1997. "Fictitious play and no-cycling conditions," Papers 97-12, Sonderforschungsbreich 504.
    12. 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.
    13. Yann Bramoullé & Andrea Galeotti & Brian Rogers, 2016. "The Oxford Handbook of the Economics of Networks," Post-Print hal-01447842, HAL.
    14. 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.
    15. Michael R. Baye & Dan Kovenock & Casper G. Vries, 1996. "The all-pay auction with complete information," Springer Books, in: Roger D. Congleton & Arye L. Hillman & Kai A. Konrad (ed.), 40 Years of Research on Rent Seeking 1, pages 209-223, Springer.
    16. Zenou, Yves & Xu, Jin & Zhou, Junjie, 2019. "Networks in Conflict: A Variational Inequality Approach," CEPR Discussion Papers 13647, C.E.P.R. Discussion Papers.
    17. Blume Lawrence E., 1993. "The Statistical Mechanics of Strategic Interaction," Games and Economic Behavior, Elsevier, vol. 5(3), pages 387-424, July.
    18. 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.
    19. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    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. Josef Hofbauer & William H. Sandholm, 2002. "On the Global Convergence of Stochastic Fictitious Play," Econometrica, Econometric Society, vol. 70(6), pages 2265-2294, November.
    22. 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.
    23. 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).
    24. Yann Bramoullé & Andrea Galeotti & Brian Rogers, 2016. "The Oxford Handbook of the Economics of Networks," Post-Print hal-03572533, HAL.
    25. 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.
    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. Yann Bramoullé & Rachel Kranton, 2015. "Games Played on Networks," Working Papers halshs-01180657, HAL.
    28. Morris, Stephen & Ui, Takashi, 2004. "Best response equivalence," Games and Economic Behavior, Elsevier, vol. 49(2), pages 260-287, November.
    29. 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.
    30. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, April.
    31. Monderer, Dov & Samet, Dov & Sela, Aner, 1997. "Belief Affirming in Learning Processes," Journal of Economic Theory, Elsevier, vol. 73(2), pages 438-452, April.
    32. 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.
    33. Gilboa, Itzhak & Matsui, Akihiko, 1991. "Social Stability and Equilibrium," Econometrica, Econometric Society, vol. 59(3), pages 859-867, May.
    34. Jack Hirshleifer, 1989. "Conflict and rent-seeking success functions: Ratio vs. difference models of relative success," Springer Books, in: Roger D. Congleton & Arye L. Hillman & Kai A. Konrad (ed.), 40 Years of Research on Rent Seeking 1, pages 251-262, Springer.
    35. 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.
    36. Daron Acemoglu & Asuman Ozdaglar, 2011. "Opinion Dynamics and Learning in Social Networks," Dynamic Games and Applications, Springer, vol. 1(1), pages 3-49, March.
    37. 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.
    38. 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.
    39. Berger, Ulrich, 2008. "Learning in games with strategic complementarities revisited," Journal of Economic Theory, Elsevier, vol. 143(1), pages 292-301, November.
    40. 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.
    41. 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).
    42. Bozbay, Irem & Vesperoni, Alberto, 2018. "A contest success function for networks," Journal of Economic Behavior & Organization, Elsevier, vol. 150(C), pages 404-422.
    43. Ulrich Berger, 2012. "Non-algebraic Convergence Proofs for Continuous-Time Fictitious Play," Dynamic Games and Applications, Springer, vol. 2(1), pages 4-17, March.
    44. Hofbauer, Josef & Sandholm, William H., 2009. "Stable games and their dynamics," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1665-1693.4, July.
    45. 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.
    46. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August.
    47. 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.
    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. Abheek Ghosh & Paul W. Goldberg, 2023. "Best-Response Dynamics in Lottery Contests," Papers 2305.10881, arXiv.org.
    2. 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. Sandholm,W.H., 2003. "Excess payoff dynamics, potential dynamics, and stable games," Working papers 5, Wisconsin Madison - Social Systems.
    5. Hofbauer,J. & Sandholm,W.H., 2001. "Evolution and learning in games with randomly disturbed payoffs," Working papers 5, Wisconsin Madison - Social Systems.
    6. Hofbauer,J. & Sandholm,W.H., 2001. "Evolution and learning in games with randomly disturbed payoffs," Working papers 5, Wisconsin Madison - Social Systems.
    7. Cortes-Corrales, Sebastián & Gorny, Paul M., 2018. "Generalising Conflict Networks," MPRA Paper 90001, University Library of Munich, Germany.
    8. Zenou, Yves & Bochet, Olivier & Faure, Mathieu & Long, Yan, 2020. "Perceived Competition in Networks," CEPR Discussion Papers 15582, C.E.P.R. Discussion Papers.
    9. Berger, Ulrich, 2008. "Learning in games with strategic complementarities revisited," Journal of Economic Theory, Elsevier, vol. 143(1), pages 292-301, November.
    10. Sandholm,W.H., 2002. "Potential dynamics and stable games," Working papers 21, Wisconsin Madison - Social Systems.
    11. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    12. Bochet, Olivier & Faure, Mathieu & Long, Yan & Zenou, Yves, 2020. "Perceived Competition in Networks," CEPR Discussion Papers 15582, C.E.P.R. Discussion Papers.
    13. 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.
    14. Ulrich Berger, 2004. "Some Notes on Learning in Games with Strategic Complementarities," Game Theory and Information 0409001, University Library of Munich, Germany.
    15. 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.
    16. 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.
    17. Ulrich Berger, 2003. "Fictitious play in 2xn games," Game Theory and Information 0303009, University Library of Munich, Germany.
    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

    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:eee:gamebe:v:123:y:2020:i:c:p:182-206. See general information about how to correct material in RePEc.

    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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.