Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark Convergence of the iterated prisoner’s dilemma game. (English) Zbl 1006.60009 Comb. Probab. Comput. 11, No. 2, 135-147 (2002). 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. Reviewer: Anton Ştefănescu (Bucureşti) Cited in 1 ReviewCited in 7 Documents MSC: 60C05 Combinatorial probability 91A20 Multistage and repeated games Keywords:Pavlov process; absorption time; optimal absorption time; exponential absorption PDFBibTeX XMLCite \textit{M. Dyer} et al., Comb. Probab. Comput. 11, No. 2, 135--147 (2002; Zbl 1006.60009) Full Text: DOI