IDEAS home Printed from https://ideas.repec.org/p/cla/levarc/506439000000000070.html
   My bibliography  Save this paper

Learning to play approximate Nash equilibria in games with many players

Author

Listed:
  • Edward Cartwright

Abstract

We illustrate one way in which a population of boundedly rational individuals can learn to play an approximate Nash equilibrium. Players are assumed to make strategy choices using a combination of imitation and innovation. We begin by looking at an imitation dynamic and provide conditions under which play evolves to an imitation equilibrium; convergence is conditional on the network of social interaction. We then illustrate, through example, how imitation and innovation can complement each other; in particular, we demonstrate how imitation can .help. a population to learn to play a Nash equilibrium where more rational methods do not. This leads to our main result in which we provide a general class of large game for which the imitation with innovation dynamic almost surely converges to an approximate Nash, imitation equilibrium.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • Edward Cartwright, 2002. "Learning to play approximate Nash equilibria in games with many players," Levine's Working Paper Archive 506439000000000070, David K. Levine.
  • Handle: RePEc:cla:levarc:506439000000000070
    as

    Download full text from publisher

    File URL: http://www.dklevine.com/archive/refs4506439000000000070.pdf
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Levine, David K. & Pesendorfer, Wolfgang, 2007. "The evolution of cooperation through imitation," Games and Economic Behavior, Elsevier, vol. 58(2), pages 293-315, February.
    2. Schlag, Karl H., 1999. "Which one should I imitate?," Journal of Mathematical Economics, Elsevier, vol. 31(4), pages 493-522, May.
    3. Theo Offerman & Jan Potters & Joep Sonnemans, 2002. "Imitation and Belief Learning in an Oligopoly Experiment," Review of Economic Studies, Oxford University Press, vol. 69(4), pages 973-997.
    4. Blume Lawrence E., 1995. "The Statistical Mechanics of Best-Response Strategy Revision," Games and Economic Behavior, Elsevier, vol. 11(2), pages 111-145, November.
    5. Ellison, Glenn & Fudenberg, Drew, 1993. "Rules of Thumb for Social Learning," Journal of Political Economy, University of Chicago Press, vol. 101(4), pages 612-643, August.
    6. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    7. Clark, Andrew E. & Oswald, Andrew J., 1996. "Satisfaction and comparison income," Journal of Public Economics, Elsevier, vol. 61(3), pages 359-381, September.
    8. Ellison, Glenn, 1993. "Learning, Local Interaction, and Coordination," Econometrica, Econometric Society, vol. 61(5), pages 1047-1071, September.
    9. Alos-Ferrer, Carlos & Ania, Ana B. & Schenk-Hoppe, Klaus Reiner, 2000. "An Evolutionary Model of Bertrand Oligopoly," Games and Economic Behavior, Elsevier, vol. 33(1), pages 1-19, October.
    10. Glenn Ellison & Drew Fudenberg, 1995. "Word-of-Mouth Communication and Social Learning," The Quarterly Journal of Economics, Oxford University Press, vol. 110(1), pages 93-125.
    11. Kalai, Ehud & Lehrer, Ehud, 1993. "Rational Learning Leads to Nash Equilibrium," Econometrica, Econometric Society, vol. 61(5), pages 1019-1045, September.
    12. Robson, Arthur J. & Vega-Redondo, Fernando, 1996. "Efficient Equilibrium Selection in Evolutionary Games with Random Matching," Journal of Economic Theory, Elsevier, vol. 70(1), pages 65-92, July.
    13. Gale, Douglas & Rosenthal, Robert W., 1999. "Experimentation, Imitation, and Stochastic Stability," Journal of Economic Theory, Elsevier, vol. 84(1), pages 1-40, January.
    14. Schlag, Karl H., 1998. "Why Imitate, and If So, How?, : A Boundedly Rational Approach to Multi-armed Bandits," Journal of Economic Theory, Elsevier, vol. 78(1), pages 130-156, January.
    15. Watts, Alison, 2001. "A Dynamic Model of Network Formation," Games and Economic Behavior, Elsevier, vol. 34(2), pages 331-341, February.
    16. Fernando Vega-Redondo, 1997. "The Evolution of Walrasian Behavior," Econometrica, Econometric Society, vol. 65(2), pages 375-384, March.
    17. Alan Kirman, 1993. "Ants, Rationality, and Recruitment," The Quarterly Journal of Economics, Oxford University Press, vol. 108(1), pages 137-156.
    18. David K Levine & Wolfgang Pesendorfer, 2000. "Evolution Through Imitation in a Single Population," Levine's Working Paper Archive 2122, David K. Levine.
    19. Wooders, Myrna & Edward Cartwright & Selten, Reinhard, 2002. "Social Conformity And Equilibrium In Pure Strategies In Games With Many Players," The Warwick Economics Research Paper Series (TWERPS) 636, University of Warwick, Department of Economics.
    20. Bernheim, B Douglas, 1994. "A Theory of Conformity," Journal of Political Economy, University of Chicago Press, vol. 102(5), pages 841-877, October.
    21. Jackson, Matthew O. & Wolinsky, Asher, 1996. "A Strategic Model of Social and Economic Networks," Journal of Economic Theory, Elsevier, vol. 71(1), pages 44-74, October.
    22. Kandori, Michihiro & Mailath, George J & Rob, Rafael, 1993. "Learning, Mutation, and Long Run Equilibria in Games," Econometrica, Econometric Society, vol. 61(1), pages 29-56, January.
    23. Venkatesh Bala & Sanjeev Goyal, 2000. "A Noncooperative Model of Network Formation," Econometrica, Econometric Society, vol. 68(5), pages 1181-1230, September.
    24. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, January.
    25. Blume Lawrence E., 1993. "The Statistical Mechanics of Strategic Interaction," Games and Economic Behavior, Elsevier, vol. 5(3), pages 387-424, July.
    26. SCHMEIDLER, David, 1973. "Equilibrium points of nonatomic games," CORE Discussion Papers RP 146, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    27. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    28. Rapoport, Amnon & Seale, Darryl A. & Winter, Eyal, 2002. "Coordination and Learning Behavior in Large Groups with Asymmetric Players," Games and Economic Behavior, Elsevier, vol. 39(1), pages 111-136, April.
    29. Selten, Reinhard, 1998. "Features of experimentally observed bounded rationality," European Economic Review, Elsevier, vol. 42(3-5), pages 413-436, May.
    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. Edward Cartwright, 2004. "Contagion and the Emergence of Convention in Small Worlds," Studies in Economics 0414, School of Economics, University of Kent.
    2. Cartwright, Edward, 2003. "Imitation and the emergence of Nash equilibrium play in games with many players," Economic Research Papers 269568, University of Warwick - Department of Economics.
    3. Cartwright, Edward & Wooders, Myrna, 2004. "Correlated equilibrium and behavioral conformity," Economic Research Papers 269625, University of Warwick - Department of Economics.
    4. Wooders, Myrna & Cartwright, Edward & Selten, Reinhard, 2003. "Social Conformity in Games with Many Players," The Warwick Economics Research Paper Series (TWERPS) 682, University of Warwick, Department of Economics.
    5. Wooders, Myrna & Cartwright, Edward & Selten, Reinhard, 2006. "Behavioral conformity in games with many players," Games and Economic Behavior, Elsevier, vol. 57(2), pages 347-360, November.

    More about this item

    JEL classification:

    • C70 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - General
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games

    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:cla:levarc:506439000000000070. 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: (David K. Levine). General contact details of provider: http://www.dklevine.com/ .

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

    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.