×

Convergence of the iterated prisoner’s dilemma game. (English) Zbl 1006.60009

Let \(G= (V, E)\) be a connected graph with \(n\) vertices \((n\geq 4)\). A Pavlov process having the state space \(\{-1,1\}^V\) is defined as follows: If the current state is \((X(i), i\in V)\), then an edge \(\{i,j\}\in E\) is chosen uniformly at random and the next state replaces \(X(i)\) and \(X(j)\) by \(X(i) X(j)\). The process has a unique absorbing state, namely \(X^*(i)= 1\), \(i\in V\), and the authors investigate the absorption time when \(G\) is a cycle or it is a complete graph. The two main results of the paper prove that the process has optimal absorption time (polynomial) in the first case and exponential absorption time in the second case.

MSC:

60C05 Combinatorial probability
91A20 Multistage and repeated games
PDFBibTeX XMLCite
Full Text: DOI