The undecidability of the spatialized prisoner's dilemma

Theory and Decision 42 (1):53-80 (1997)
In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner's Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurations of Prisoner's Dilemma strategies will take the form of such cellular automata
Keywords Undecidability  Prisoner's Dilemma  cellular automata  game theory  decision theory  computability
Categories (categorize this paper)
DOI 10.1023/A:1004959623042
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,305
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Anthony F. Beavers (2011). Recent Developments in Computing and Philosophy. Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 42 (2):385-397.

Add more citations

Similar books and articles
Christopher Stephens (1996). Modelling Reciprocal Altruism. British Journal for the Philosophy of Science 47 (4):533-551.
Colin Grant (2004). The Altruists' Dilemma. Business Ethics Quarterly 14 (2):315-328.

Monthly downloads

Added to index


Total downloads

54 ( #88,822 of 1,932,568 )

Recent downloads (6 months)

21 ( #27,541 of 1,932,568 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.