IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2007.01896.html
   My bibliography  Save this paper

Spatial Iterated Prisoner's Dilemma as a Transformation Semigroup

Author

Listed:
  • Isaiah Farahbakhsh
  • Chrystopher L. Nehaniv

Abstract

The prisoner's dilemma (PD) is a game-theoretic model studied in a wide array of fields to understand the emergence of cooperation between rational self-interested agents. In this work, we formulate a spatial iterated PD as a discrete-event dynamical system where agents play the game in each time-step and analyse it algebraically using Krohn-Rhodes algebraic automata theory using a computational implementation of the holonomy decomposition of transformation semigroups. In each iteration all players adopt the most profitable strategy in their immediate neighbourhood. Perturbations resetting the strategy of a given player provide additional generating events for the dynamics. Our initial study shows that the algebraic structure, including how natural subsystems comprising permutation groups acting on the spatial distributions of strategies, arise in certain parameter regimes for the pay-off matrix, and are absent for other parameter regimes. Differences in the number of group levels in the holonomy decomposition (an upper bound for Krohn-Rhodes complexity) are revealed as more pools of reversibility appear when the temptation to defect is at an intermediate level. Algebraic structure uncovered by this analysis can be interpreted to shed light on the dynamics of the spatial iterated PD.

Suggested Citation

  • Isaiah Farahbakhsh & Chrystopher L. Nehaniv, 2020. "Spatial Iterated Prisoner's Dilemma as a Transformation Semigroup," Papers 2007.01896, arXiv.org, revised Jul 2020.
    • Handle: RePEc:arx:papers:2007.01896
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2007.01896
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Clark, Kenneth & Sefton, Martin, 2001. "The Sequential Prisoner's Dilemma: Evidence on Reciprocation," Economic Journal, Royal Economic Society, vol. 111(468), pages 51-68, January.
    2. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Becchetti, Leonardo & Degli Antoni, Giacomo & Ottone, Stefania & Solferino, Nazaria, 2013. "Allocation criteria under task performance: The gendered preference for protection," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 45(C), pages 96-111.
    2. Zvonimir Bašić & Parampreet C. Bindra & Daniela Glätzle-Rützler & Angelo Romano & Matthias Sutter & Claudia Zoller, 2021. "The Roots of Cooperation," ECONtribute Discussion Papers Series 097, University of Bonn and University of Cologne, Germany.
    3. Ghidoni, Riccardo & Suetens, Sigrid, 2019. "Empirical Evidence on Repeated Sequential Games," Other publications TiSEM ff3a441f-e196-4e45-ba59-c, Tilburg University, School of Economics and Management.
    4. David Baron & Ehud Kalai, 1990. "Dividing a Cake by Majority: The Simplest Equilibria," Discussion Papers 919, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    5. Siegfried Berninghaus & Hans Haller & Alexander Outkin, 2006. "Neural networks and contagion," Revue d'économie industrielle, De Boeck Université, vol. 0(2), pages 11-11.
    6. Rudolf Vetschera, 2003. "Experimentation and Learning in Repeated Cooperation," Computational and Mathematical Organization Theory, Springer, vol. 9(1), pages 37-60, May.
    7. Philippe Jehiel, 2022. "Analogy-Based Expectation Equilibrium and Related Concepts:Theory, Applications, and Beyond," Working Papers halshs-03735680, HAL.
    8. Gilboa Itzhak & Schmeidler David, 1994. "Infinite Histories and Steady Orbits in Repeated Games," Games and Economic Behavior, Elsevier, vol. 6(3), pages 370-399, May.
    9. Tracy Xiao Liu & Jenna Bednar & Yan Chen & Scott Page, 2019. "Directional behavioral spillover and cognitive load effects in multiple repeated games," Experimental Economics, Springer;Economic Science Association, vol. 22(3), pages 705-734, September.
    10. Cho, In-Koo, 2005. "Introduction to learning and bounded rationality," Journal of Economic Theory, Elsevier, vol. 124(2), pages 127-128, October.
    11. Joshua M. Epstein, 2007. "Agent-Based Computational Models and Generative Social Science," Introductory Chapters, in: Generative Social Science Studies in Agent-Based Computational Modeling, Princeton University Press.
    12. Jehiel, Philippe, 1998. "Learning to Play Limited Forecast Equilibria," Games and Economic Behavior, Elsevier, vol. 22(2), pages 274-298, February.
    13. Samuelson, Larry & Swinkels, Jeroen M., 2003. "Evolutionary stability and lexicographic preferences," Games and Economic Behavior, Elsevier, vol. 44(2), pages 332-342, August.
    14. Sent, Esther-Mirjam, 2004. "The legacy of Herbert Simon in game theory," Journal of Economic Behavior & Organization, Elsevier, vol. 53(3), pages 303-317, March.
    15. von Siemens, Ferdinand A., 2013. "Intention-based reciprocity and the hidden costs of control," Journal of Economic Behavior & Organization, Elsevier, vol. 92(C), pages 55-65.
    16. Rubinstein, A. & Wolnsky, A., 1992. "A Rermark on Infinitely Repeated Extensive Games," Papers 4-92, Tel Aviv - the Sackler Institute of Economic Studies.
    17. O. Gossner, 2000. "Sharing a long secret in a few public words," THEMA Working Papers 2000-15, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    18. Ellingsen, Tore & Johannesson, Magnus & Mollerstrom, Johanna & Munkhammar, Sara, 2012. "Social framing effects: Preferences or beliefs?," Games and Economic Behavior, Elsevier, vol. 76(1), pages 117-130.
    19. Barr, Jason & Saraceno, Francesco, 2009. "Organization, learning and cooperation," Journal of Economic Behavior & Organization, Elsevier, vol. 70(1-2), pages 39-53, May.
    20. Goeschl, Timo & Jarke, Johannes, 2014. "Trust, but verify? When trustworthiness is observable only through (costly) monitoring," WiSo-HH Working Paper Series 20, University of Hamburg, Faculty of Business, Economics and Social Sciences, WISO Research Laboratory.

    More about this item

    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:arx:papers:2007.01896. See general information about how to correct material in RePEc.

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

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.