Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine, Istrate, Gabriel and Jerrum, Mark (2002) Convergence of the iterated prisoner's dilemma game. Combinatorics, Probability & Computing, Volume 11 (Number 2). pp. 135-147. doi:10.1017/S096354830100503X ISSN 0963-5483.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

We consider a stochastic process based on the iterated prisoner's dilemma game. During the game, each of n players has a state, either cooperate or defect. The players are connected by an 'interaction graph', During each step of the process, an edge of the graph is chosen uniformly at random and the states of the players connected by the edge are modified according to the Pavlov strategy. The process converges to a unique absorbing state in which all players cooperate. We prove two conjectures of Kittock: the convergence rate is exponential in n when the interaction graph is a complete graph, and it is polynomial in n when the interaction graph is a cycle. In fact, we show that the rate is O(n log n) in the latter case.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Combinatorics, Probability & Computing
Publisher:	Cambridge University Press
ISSN:	0963-5483
Official Date:	March 2002
Dates:	Date Event March 2002 Published
Volume:	Volume 11
Number:	Number 2
Number of Pages:	13
Page Range:	pp. 135-147
DOI:	10.1017/S096354830100503X
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item