Networks preserving evolutionary equilibria and the power of randomization

ABSTRACT

We study a natural extension of classical evolutionary game theory to a setting in which pairwise interactions are restricted to the edges of an undirected graph or network. We generalize the definition of an evolutionary stable strategy (ESS), and show a pair of complementary results that exhibit the power of randomization in our setting: subject to degree or edge density conditions, the classical ESS of any game are preserved when the graph is chosen randomly and the mutation set is chosen adversarially, or when the graph is chosen adversarially and the mutation set is chosen randomly. We examine natural strengthenings of our generalized ESS definition, and show that similarly strong resultsnare not possible for them.

REFERENCES

• 1: Elwyn R. Berlekamp, John Horton Conway, and Richard K. Guy. Winning Ways for Your Mathematical Plays, volume 4. AK Peters, Ltd, March 2004.
• 2: Jonas Björnerstedt and Karl H. Schlag. On the evolution of imitative behavior. Discussion Paper B-378, University of Bonn, 1996.
• 3: L. E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387--424, 1993.
• 4: L. E. Blume. The statistical mechanics of best-response strategy revision. Games and Economic Behavior, 11(2):111--145, November 1995.
• 5: B. Bollobás. Random Graphs. Cambridge University Press, 2001.
• 6: Michael Suk-Young Chwe. Communication and coordination in social networks. Review of Economic Studies, 67:1--16, 2000.
• 7: Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047{1071, Sept. 1993.
• 8: I. Eshel, L. Samuelson, and A. Shaked. Altruists, egoists, and hooligans in a local interaction model. The American Economic Review, 88(1), 1998.
• 9: Geofrey R. Grimmett and David R. Stirzaker. Probability and Random Processes. Oxford University Press, 3rd edition, 2001.
• 10: M. Jackson. A survey of models of network formation: Stability and efficiency. In Group Formation in Economics; Networks, Clubs and Coalitions. Cambridge University Press, 2004.
• 11: Sham Kakade , Michael Kearns , John Langford , Luis Ortiz, Correlated equilibria in graphical games, Proceedings of the 4th ACM conference on Electronic commerce, p.42-47, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779934]
• 12: S. Kakade, M. Kearns, L. Ortiz, R. Pemantle, and S. Suri. Economic properties of social networks. Neural Information Processing Systems, 2004.
• 13: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 14: E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433:312--316, 2005.
• 15: S. Morris. Contagion. Review of Economic Studies, 67(1):57--78, 2000.
• 16: Karl H. Schlag. Why imitate and if so, how? Journal of Economic Theory, 78:130--156, 1998.
• 17: J. M. Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.
• 18: William L. Vickery. How to cheat against a simple mixed strategy ESS. Journal of Theoretical Biology, 127:133--139, 1987.
• 19: Jörgen W. Weibull. Evolutionary Game Theory. The MIT Press, 1995.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Theory

Keywords:
evolutionary stable strategy, game theory, networks