Evolutionary game dynamics in populations with different learners. (English) Zbl 1397.91062

Chatterjee, Krishnendu; Zufferey, Damien; Nowak, Martin A.

J. Theor. Biol. 301, 161-173 (2012).

Summary: We study evolutionary game theory in a setting where individuals learn from each other. We extend the traditional approach by assuming that a population contains individuals with different learning abilities. In particular, we explore the situation where individuals have different search spaces, when attempting to learn the strategies of others. The search space of an individual specifies the set of strategies learnable by that individual. The search space is genetically given and does not change under social evolutionary dynamics. We introduce a general framework and study a specific example in the context of direct reciprocity. For this example, we obtain the counter intuitive result that cooperation can only evolve for intermediate benefit-to-cost ratios, while small and large benefit-to-cost ratios favor defection. Our paper is a step toward making a connection between computational learning theory and evolutionary game dynamics.

MSC:

91A22	Evolutionary games
91A26	Rationality and learning in game theory

Keywords:

evolutionary game theory; direct reciprocity (prisoner’s dilemma); learning theory

References:

[1]	Axelrod, R.M., The evolution of cooperation, (1984), Basic Books New York, NY, (reprinted 1989. Penguin, Harmondsworth UK)
[2]	Benaim, M.; Hofbauer, J.; Hopkins, Ed., Learning in games and unstable equilibria, J. econ. theory, 144, 1694-1709, (2009) · Zbl 1175.91031
[3]	Boyd, R., Mistakes allow evolutionary stability in the repeated Prisoner’s dilemma game, J. theor. biol., 136, 47-56, (1989)
[4]	Boyd, R.; Richerson, P.J., Culture and the evolutionary process, (1985), University of Chicago Press
[5]	Cavalli-Sforza, L.L.; Feldman, M.W., Cultural transmission and evolution: A quantitative approach, (1981), Princeton University Press Princeton, NJ · Zbl 0479.92011
[6]	Chomsky, N., Aspects of the theory of syntax, (1965), MIT Press
[7]	Chomsky, N., Principles and parameters in syntactic theory explanation, (), 123-146
[8]	Cressman, R., Evolutionary dynamics and extensive form games, (2003), MIT Press Cambridge, MA · Zbl 1067.91001
[9]	Fudenberg, D.; Levine, K.D., The theory of learning in games, (1995), MIT Press Cambridge, MA
[10]	Fudenberg, D.; Maskin, E., The folk theorem in repeated games with discounting or with incomplete information, Econometrica, 50, 533-554, (1986) · Zbl 0615.90099
[11]	Fudenberg, D.; Maskin, E., Evolution and cooperation in noisy repeated games, Am. econ. rev., 80, 274-279, (1990) · Zbl 0721.90090
[12]	Fudenberg, D.; Tirole, J., Game theory, (1991), MIT Press Cambridge, MA · Zbl 1339.91001
[13]	Gintis, H., Game theory evolving, (2000), Princeton University Press Princeton, NJ · Zbl 1159.91300
[14]	Gold, E.M., Language identification in the limit, Inform. control, 10, 447-474, (1967) · Zbl 0259.68032
[15]	Hauert, Ch., Replicator dynamics of reward & reputation in public goods games, J. theor. biol., 267, 22-28, (2010) · Zbl 1410.91073
[16]	Helbing, D., Interrelations between stochastic equations for systems with pair interactions, Phys. A: stat. mech. appl., 181, 29-52, (1992)
[17]	Hofbauer, J.; Schlag, K.H., Sophisticated imitation in cyclic games, J. evol. econ., 10, 523-543, (2000)
[18]	Hofbauer, J.; Schuster, P.; Sigmund, K., A note on evolutionary stable strategies and game dynamics, J. theor. biol., 81, 609-612, (1979)
[19]	Hofbauer, J.; Sigmund, K., The theory of evolution and dynamical systems, (1988), Cambridge University Press Cambridge, UK · Zbl 0716.92024
[20]	Hofbauer, J.; Sigmund, K., Evolutionary games and population dynamics, (1998), Cambridge University Press Cambridge, UK · Zbl 0914.90287
[21]	Hofbauer, J.; Sigmund, K., Evolutionary game dynamics, Bull. am. math. soc., 40, 479-519, (2003) · Zbl 1049.91025
[22]	Imhof, L.A.; Fudenberg, D.; Nowak, M.A., Evolutionary cycles of cooperation and defection, Proc. natl. acad. sci. USA, 102, 10797-10800, (2005)
[23]	Kandori, M.; Mailath, G.J.; Rob, R., Learning, mutation and long run equilibria in games, Econometrica, 61, 29-56, (1993) · Zbl 0776.90095
[24]	Komarova, N.L., Replicator-mutator equation, universality property and population dynamics of learning, J. theor. biol., 230, 2, 227-239, (2004)
[25]	Komarova, N.L.; Niyogi, P., Optimizing the mutual intelligibility of linguistic agents in a shared world, J. artif. intell., 54, 1-2, 1-42, (2004) · Zbl 1085.68720
[26]	Komarova, N.L.; Levin, S.A., Eavesdropping and language dynamics, J. theor. biol., 264, 1, 104-118, (2010) · Zbl 1406.91067
[27]	May, R.M., More evolution of cooperation, Nature, 327, 15-17, (1987)
[28]	Maynard Smith, J., Evolution and the theory of games, (1982), Cambridge University Press Cambridge, UK · Zbl 0526.90102
[29]	Maynard Smith, J.; Price, G.R., The logic of animal conflict, Nature, 246, 15-18, (1973) · Zbl 1369.92134
[30]	McNamara, J.M.; Barta, Z.; Houston, A.I., Variation in behaviour promotes cooperation in the Prisoner’s dilemma game, Nature, 428, 745-748, (2004)
[31]	McNamara, J.M.; Leimar, O., Variation and the response to variation as a basis for successful cooperation, Phil. trans. R. soc. B, 365, 2627-2633, (2010)
[32]	Milinski, M., Tit for tat in sticklebacks and the evolution of cooperation, Nature, 325, 433-435, (1987)
[33]	Mitchener, W.G.; Nowak, M.A., Competitive exclusion and coexistence of universal grammars, Bull. math. biol., 65, 67-93, (2003) · Zbl 1334.91065
[34]	Mitchener, W.G., Game dynamics with learning and evolution of universal grammar, Bull. math. biol., 69, 3, 1093-1118, (2007) · Zbl 1298.92073
[35]	Niyogi, P., The computational nature of language learning and evolution, (2006), MIT Press
[36]	Nowak, M.A.; Komarova, N.L.; Niyogi, P., Evolution of universal grammar, Science, 291, 114-118, (2001) · Zbl 1226.91060
[37]	Nowak, M.A.; Komarova, N.L.; Niyogi, P., Computational and evolutionary aspects of language, Nature, 417, 611-617, (2002)
[38]	Nowak, M.A.; Sigmund, K., Oscillations in the evolution of reciprocity, J. theor. biol., 137, 21-26, (1989)
[39]	Nowak, M.A.; Sigmund, K., Tit for tat in heterogeneous populations, Nature, 355, 250-253, (1992)
[40]	Nowak, M.A.; Sigmund, K., A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s dilemma game, Nature, 364, 56-58, (1993)
[41]	Nowak, M.A.; Sigmund, K., Chaos and the evolution of cooperation, Proc. natl. acad. sci. USA, 90, 5091-5094, (1993)
[42]	Nowak, M.A.; Sigmund, K., Evolutionary dynamics of biological games, Science, 303, 793-799, (2004)
[43]	Osherson, D.N.; Stob, M.; Weinstein, S., Systems that learn: an introduction to learning theory for cognitive and computer scientists, (1986), MIT Press Cambridge
[44]	Panait, L.; Tuyls, K.; Luke, S., Theoretical advantages of lenient learners: an evolutionary game theoretic perspective, J. Mach. learn. res., 9, 423-457, (2008) · Zbl 1225.68204
[45]	Rapoport, A.; Chammah, A.M., Prisoner’s dilemma, (1965), University of Michigan Press Ann Arbor, MI
[46]	Riechmann, T., Genetic algorithm learning and evolutionary games, J. econ. dyn. control, 25, 1019-1037, (2001) · Zbl 0979.91007
[47]	Samuelson, L., Evolutionary games and equilibrium selection, (1997), MIT Press Cambridge, MA · Zbl 0953.91500
[48]	Sandholm, W.H., Population games and evolutionary dynamics, (2010), MIT Press Cambridge, MA · Zbl 1208.91003
[49]	Schlag, K.H., 1993. Dynamic stability in the repeated prisoners’ dilemma played by finite automata. Discussion Paper Serie B 243, University of Bonn, Germany.
[50]	Schlag, K.H., Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits, J. econ. theory, 78, 130-156, (1998) · Zbl 0895.90003
[51]	Sigmund, K., The calculus of selfishness. Princeton series in theoretical and computational biology, (2010), Princeton University Press
[52]	Sigmund, K.; De Silva, H.; Traulsen, A.; Hauert, C., Social learning promotes institutions for governing commons, Nature, 466, 861-863, (2010)
[53]	Skyrms, B., Evolution of the social contract, (1996), Cambridge University Press Cambridge, UK
[54]	Tarnita, C.E.; Antal, T.; Ohtsuki, H.; Nowak, M.A., Evolutionary dynamics in set structured populations, Proc. natl. acad. sci. USA, 106, 21, 8601-8604, (2009)
[55]	Taylor, P.D.; Jonker, L.B., Evolutionary stable strategies and game dynamics, Math. biosci., 40, 145-156, (1978) · Zbl 0395.90118
[56]	Traulsen, A.; Hauert, C.; De Silva, H.; Nowak, M.A.; Sigmund, K., Exploration dynamics in evolutionary games, Proc. natl. acad. sci., 106, 709-712, (2009) · Zbl 1202.91029
[57]	Trivers, R.L., The evolution of reciprocal altruism, Q. rev. biol., 46, 35-57, (1971)
[58]	Valiant, L.G., A theory of learnable, Commun. ACM, 27, 436-445, (1984) · Zbl 0587.68077
[59]	Vapnik, V.N., Statistical learning theory, (1998), John Wiley Hoboken, NJ · Zbl 0935.62007
[60]	Weibull, J.W., Evolutionary game theory, (1995), MIT Press Cambridge, MA · Zbl 0879.90206
[61]	Zeeman, E.C., Population dynamics from game theory, () · Zbl 0448.92015