Probabilistic memory-one strategies for the iterated prisoner's dilemma

Probabilistic memory-one strategies for the iterated prisoner's dilemma

Jean-Paul Delahaye Philippe Mathieu  

Univ. Lille, CNRS, Centrale Lille, UMR 9189 – CRIStAL (équipe SMAC) Centre de Recherche en Informatique Signal et Automatique de Lille F-59000 Lille, France

Corresponding Author Email: 
prenom.nom@univ-lille.fr
Page: 
141-167
|
DOI: 
https://doi.org/10.3166/RIA.32.141-167
Received: 
|
Accepted: 
|
Published: 
30 April 2018
| Citation
Abstract: 

We conduct a thorough experimental study of probabilistic strategies to the prisoner’s dilemma. To do this, we use the complete class method associated with an evolutionary approach. The results we obtain are therefore objective in nature and depend as little as possible on the sets of strategies put in competition. The studied sets are large (several thousand strategies), homogeneous, and systematic. We test the robustness of our results by various methods. The best strategies identified are for some of them new in the sense that they have never been clearly identified by previous studies, despite their simplicity. We propose a criterion that leads to a good anticipation of their behavior in various contexts. We compare the results of this study with those obtained by the mathematical approaches of Press and Dyson. We also confront the new strategies with the best known strategies.  

Keywords: 

game theory, iterated prisoner’s dilemma, mixted strategies, behaviour

1. Introduction
2. Définitions et rappels
3. Les résultats de Press et Dyson
4. Stratégies probabilistes à mémoire de un coup
5. Conclusion
Annexe
  References

Adami C., Hintze A. (2013). Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything. Nature communications, vol. 4. 

Adami C., Hintze A. (2014). Corrigendum: Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything. Nature communications, vol. 5. Axelrod R. M. (2006). The evolution of cooperation. Basic books. 

Beaufils B., Delahaye J.-P., Mathieu P. (1997). Our meeting with gradual, a good strategy for the iterated prisoner’s dilemma. In Proceedings of the fifth international workshop on the synthesis and simulation of living systems, alife v, p. 202–209. The MIT Press/Bradford Books. 

Beaufils B., Delahaye J.-P., Mathieu P. (1998). Complete classes of strategies for the classical iterated prisoner’s dilemma. In International conference on evolutionary programming, ep7, vol1447, p. 33–41. Springer. 

Beaufils B., Mathieu P. (2006). Cheating is not playing: Methodological issues of computational game theory. In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI’06), vol. 141, p. 185-189. 

Boerlijst M. C., Nowak M. A., Sigmund K. (1997). Equal pay for all prisoners. The American mathematical monthly, vol. 104, no 4, p. 303–305. 

Delahaye J.-P., Mathieu P. (2016). Méta-stratégies pour le dilemme itéré du prisonnier. In 24e journées francophones sur les systèmes multi-agents (jfsma’16), p. 13–22.

Delahaye J.-P., Mathieu P., Beaufils B. (2000). The iterated lift dilemma. In Computational conflicts, p. 202–223. Springer. 

Dong H., Zhi-Hai R., Tao Z. (2014). Zero-determinant strategy: An underway revolution in game theory. Chinese Physics B, vol. 23, no 7, p. 078905. 

Hilbe C., Nowak M. A., Sigmund K. (2013). Evolution of extortion in iterated prisoner’s dilemma games. Proceedings of the National Academy of Sciences, vol. 110, no 17, p. 6913– 6918. 

Hilbe C., Nowak M. A., Traulsen A. (2013). Adaptive dynamics of extortion and compliance. PloS one, vol. 8, no 11, p. e77886. 

Hilbe C., Röhl T., Milinski M. (2014). Extortion subdues human players but is finally punished in the prisoner’s dilemma. Nature communications, vol. 5. 

Kendall G., Yao X., Chong S. Y. (2007). The iterated prisoners’ dilemma: 20 years on. World Scientific Publishing Co., Inc. 

Li J., Hingston P., Kendall G. (2011). Engineering design of strategies for winning iterated prisoner’s dilemma competitions. IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, no 4, p. 348–360. 

Li J., Kendall G. (2014). The effect of memory size on the evolutionary stability of strategies in iterated prisoner’s dilemma. IEEE Transactions on Evolutionary Computation, vol. 18, no 6, p. 819–826. 

Liu J., Li Y., Xu C., Hui P. (2015). Evolutionary behavior of generalized zero-determinant strategies in iterated prisoner’s dilemma. Physica A: Statistical Mechanics and its Applications, vol. 430, p. 81–92. 

Mathieu P., Beaufils B., Delahaye J.-P. (1999). Studies on dynamics in the classical iterated prisoner’s dilemma with few strategies. In European conference on artificial evolution, p. 177–190. 

Mathieu P., Delahaye J.-P. (2015). New winning strategies for the iterated prisoner’s dilemma. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems, p. 1665–1666. 

Milinski M., Hilbe C., Semmann D., Sommerfeld R., Marotzke J. (2016). Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature communications, vol. 7. 

O’Riordan C. et al. (2000). A forgiving strategy for the iterated prisoner’s dilemma. Journal of Artificial Societies and Social Simulation, vol. 3, no 4, p. 56–58. 

Press W. H., Dyson F. J. (2012). Iterated prisoner’s dilemma contains strategies that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences, vol. 109, no 26, p. 10409–10413. 

Rapoport A., Chammah A. M. (1965). Prisoner’s dilemma: A study in conflict and cooperation (vol. 165). University of Michigan press. 

Sigmund K. (2010). The calculus of selfishness. Princeton University Press. 

Stewart A. J., Plotkin J. B. (2013). From extortion to generosity, evolution in the iterated prisoner’s dilemma. Proceedings of the National Academy of Sciences, vol. 110, no 38, p. 15348–15353. 

Szolnoki A., Perc M. (2014a). Defection and extortion as unexpected catalysts of unconditional cooperation in structured populations. Scientific reports, vol. 4. 

Szolnoki A., Perc M. (2014b). Evolution of extortion in structured populations. Physical  Review E, vol. 89, no 2, p. 022804. 

Tzafestas E. (2000). Toward adaptive cooperative behavior. In Proceedings of the simulation of adaptive behavior conference, paris. 

Wedekind C., Milinski M. (1996). Human cooperation in the simultaneous and the alternating prisoner’s dilemma: Pavlov versus generous tit-for-tat. Proceedings of the National Academy of Sciences, vol. 93, no 7, p. 2686–2689.