Fault-tolerant strategies in the Iterated Prisoner's Dilemma

作者：Pelc Andrzej^*

来源：Information Processing Letters, 2010, 110(10): 389-395.

DOI：10.1016/j.ipl.2010.03.007

• Prisoner's Dilemma
• Robust strategy
• Algorithms
• Fault-tolerance
• Bounded memory

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 sigma is called robust, if in any population consisting of copies of two types of strategies, sigma itself and some other strategy tau, the strategy sigma is never worse than tau. 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.

• 出版日期2010-4-30