×

Finite automata play repeated prisoner’s dilemma with information processing costs. (English) Zbl 0875.90347

Summary: We study the finitely repeated Prisoner’s Dilemma game. Our players are modeled as finite automata. A population of boundedly rational players compete in a ‘survival of the fittest’ evolution contest simulated using Holland’s genetic algorithm. Starting from a hostile population which plays defection frequently, our simulation results show that players converge to play cooperatively. This emergence of cooperative behavior breaks down when we penalize a complex strategy based on the size of the machine. On the other hand, a penalty cost that increases with the frequency an automaton switches states will not hurt the development of cooperative behavior.

MSC:

91A20 Multistage and repeated games
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abreu, D.; Rubinstein, A., The structure of Nash equilibrium in repeated games with finite automata, Econometrica, 56, 1259-1281 (1988) · Zbl 0664.90103
[2] Anderlini, L., Communication, computability, and common interest games, (Working paper (1989), Santa Fé Institute: Santa Fé Institute Santa Fé, NM) · Zbl 0926.91001
[3] Aumann, R., Survey of repeated games, (Aumann, R. J.; etal., Essays in game theory and mathematical economics in honor of Oscar Morgenstern (1981)), 11-42
[4] Aumann, R., Perspectives on bounded rationality, (Working paper (1989), Stanford Graduate School of Business: Stanford Graduate School of Business Stanford, CA)
[5] Axelrod, R., The evolution of cooperation (1984), Basic Books: Basic Books New York, NY
[6] Axelrod, R., The evolution of strategies in the iterated prisoner’s dilemma, (Davis, Lawrence, Genetic algorithms and simulated annealing (1987), Morgan Kaufman: Morgan Kaufman Los Altos, CA) · Zbl 0904.90182
[7] Banks, J.; Sundaram, R., Repeated games, finite automata, and complexity, (Games and Economic Behavior (1990)), 97-117 · Zbl 0755.90099
[8] Binmore, K., Modeling rational players: Part I, Economics and Philosophy, 3, 179-214 (1987)
[9] Binmore, K., Modeling rational players: Part II, Economics and Philosophy, 4, 9-55 (1988)
[10] Binmore, K.; Samuelson, L., Evolutionary stability in repeated games played by finite automata, (Working paper (1990), University of Wisconsin: University of Wisconsin Madison, WI) · Zbl 0767.90095
[11] Brown, G. W., Iterative solution of games by fictitious play, (Activity analysis of production and allocation (1951), Wiley: Wiley New York, NY) · Zbl 0045.09902
[12] Friedman, D., Evolutionary games in economics, Econometrica, 59, 637-666 (1991) · Zbl 0745.90012
[13] Fudenberg, D.; Kreps, D., A theory of learning, experimentation, and equilibrium in games (1988), Stanford Graduate School of Business: Stanford Graduate School of Business Stanford, CA, Memo
[14] Fudenberg, D.; Maskin, E., The Folk theorem in repeated games with discounting or with incomplete information, Econometrica, 54, 533-554 (1986) · Zbl 0615.90099
[15] Fudenberg, D.; Maskin, E., Evolution and cooperation in noisy repeated games, American Economic Review, 80, 274-279 (1990)
[16] Gilboa, I., The complexity of computing best-response automata in repeated games, Journal of Economic Theory, 45, 342-352 (1988) · Zbl 0649.90105
[17] Goldberg, D., Genetic algorithms in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley New York, NY · Zbl 0721.68056
[18] Harrison, M., Introduction to switching and automata theory (1965), McGraw-Hill: McGraw-Hill New York, NY · Zbl 0196.51702
[19] Ho, T.-H.; Weigelt, K., Task complexity, equilibrium selection, and learning: An experimental study, Management Science (1993), forthcoming
[20] Holland, J. H., Adaptation in natural and artificial systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[21] Holland, J. H.; Miller, J., Artificially adaptive agents in economic theory, American Economic Review, 81, 365-370 (1991)
[22] Holland, J. H.; Holyoak, K. J.; Nisbett, R. E.; Thagard, P. R., Induction: Processes of inference, learning, and discovery (1986), MIT Press: MIT Press Cambridge, MA
[23] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[24] Kalai, E.; Stanford, W., Finite rationality and interpersonal complexity in repeated games, Econometrica, 56, 397-410 (1988) · Zbl 0647.90104
[25] Kreps, D., Game theory and economic modeling (1990), Oxford University Press: Oxford University Press Oxford
[26] Kreps, D.; Milgrom, P.; Roberts, J.; Wilson, R., Rational cooperation in the finitely repeated prisoner’s dilemma, Journal of Economic Theory, 27, 245-252 (1982) · Zbl 0485.90092
[27] Linster, B., Evolutionary stability in the infinitely repeated prisoners’ dilemma played by two-state Moore machines, Southern Economic Journal, 880-903 (1992)
[28] Marimon, R.; Miller, J., Money as a medium of exchange in an economy with genetically reproduced decision rules, (Working paper (1989), Santa Fé Institute: Santa Fé Institute Santa Fé, NM)
[29] Marimon, R.; McGrattan, E.; Sargent, T., Money as a medium of exchange in an economy with artificial intelligent agents, Journal of Economic Dynamics and Control, 14, 329-374 (1990) · Zbl 0698.90014
[30] Milgrom, P.; Roberts, J., Adaptive and sophisticated learning in repeated normal form games, Games and Economic Behavior, 3, 82-100 (1991) · Zbl 0751.90093
[31] Miller, J., The coevolution of automata in the repeated prisoner’s dilemma, (Working paper (1989), Santa Fé Institute: Santa Fé Institute Santa Fé, NM)
[32] Minsky, M., Computation: Finite and infinite machines (1967), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0195.02402
[33] Neyman, A., Bounded rationality justifies cooperation in the finitely repeated prisoner’s dilemma, Economics Letters, 19, 227-229 (1985) · Zbl 1273.91022
[34] Radner, R., Can bounded rationality resolve the prisoner’s dilemma?, (Essays in honor of Gerard Debreu (1986), North-Holland: North-Holland Amsterdam) · Zbl 0662.90101
[35] Rapoport, A., A note on the index of cooperation for prisoner’s dilemma, Journal of Conflict Resolution, 100-103 (1966)
[36] Rapoport, A.; Chammah, A. M., Prisoner’s dilemma (1965), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[37] Ross, M.; Sicoly, F., Egocentric biases in availability and attribution, Journal of Personality and Social Psychology, 37, 322-336 (1979)
[38] Rubinstein, A., Finite automata play the repeated prisoner’s dilemma, Journal of Economic Theory, 39, 83-96 (1986) · Zbl 0606.68050
[39] Selten, R., Evolutionary stability in extensive two-person games, Mathematical Social Sciences, 5, 269-363 (1983) · Zbl 0534.90095
[40] Selten, R., Evolution, learning and economic behavior, Games and Economic Behavior, 3, 3-24 (1991) · Zbl 0825.90320
[41] Selten, R.; Stoecker, R., End behavior in sequences of finitely repeated prisoner’s dilemma supergames — A learning theory approach, Journal of Economic Behavior and Organization, 7, 47-70 (1986)
[42] Simon, H., (Models of bounded rationality (1982), MIT Press: MIT Press Cambridge, MA), 2 vols.
[43] Smith, J., Evolution and the theory of games (1982), Cambridge University Press: Cambridge University Press Cambridge
[44] Zemel, E., Small talk and cooperation: A note on bounded rationality, Journal of Economic Theory, 49, 1-9 (1989) · Zbl 0679.90101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.