Fault-tolerant strategies in the Iterated Prisoner's Dilemma

The aim of this paper is to determine how well can strategies in the Iterated Prisoner's Dilemma (IPD) behave in the presence of errors. A highly desirable property of strategies in IPD, even without errors, is their robustness. A strategy σ is called robust, if in any population consisting of copies of two types of strategies, σ itself and some other strategy τ, the strategy σ is never worse than τ. For example, the well known simple strategy tit-for-tat is robust. However, tit-for-tat is very vulnerable to errors: already one mistake in its execution can cause it to lose the property of robustness. The ultimate resistance to errors is captured by the notion of perfect fault-tolerance: a strategy has this property, if any distortion of it on an arbitrary finite number of moves remains robust. Do there exist perfectly fault-tolerant strategies in IPD? Somewhat surprisingly, the answer is yes: indeed we describe such a strategy and we prove that it has this very strong resistance to errors. However, we prove that no strategy with bounded memory can have this property. We then go on to show that preserving robustness under distortions on any fixed initial segment of moves is possible with bounded memory.