Nice Invincible Strategy for the Average-Payoff IPD

Shiheng Wang, Fangzhen Lin

Introduction

The Iterated Prisoner’s Dilemma (IPD) serves as the foundational model for understanding the evolution of cooperation among self-interested agents. Since Robert Axelrod's seminal tournaments, the search for the "best" strategy has evolved from simple heuristics like Tit-for-Tat to complex mathematical constructs like Zero-Determinant (ZD) strategies. This paper introduces a new class: invincible strategies. These are defined as strategies that are mathematically guaranteed never to be outscored by an opponent in terms of long-run average payoff.

Defining the Game and Invincibility

The study focuses on memory-one strategies, where a player's decision to cooperate (C) or defect (D) depends solely on the outcome of the previous round. These strategies are represented by a vector $\mathbf{p} = (p_1, p_2, p_3, p_4)$, where each $p_i$ is the probability of cooperating after the outcomes $CC, CD, DC,$ and $DD$, respectively.

The payoffs for these outcomes are defined by a standard matrix:

Standard IPD payoff matrix where R is Reward, S is Sucker's payoff, T is Temptation, and P is Punishment.

A strategy is considered invincible if, for any opponent strategy $\mathbf{q}$, the player's average payoff $s_X$ is greater than or equal to the opponent's average payoff $s_Y$ ($s_X \ge s_Y$).

The Three Conditions of Invincibility

Through rigorous mathematical analysis using Markov chains and the Press-Dyson determinant method, the authors derive Theorem 4, which provides the necessary and sufficient conditions for invincibility in the IPD:

  1. $p_2 + p_3 \le 1$: The combined probability of cooperating after "sucker" ($CD$) or "temptation" ($DC$) outcomes must be low.
  2. $p_4 = 0$: The strategy must never cooperate after mutual defection.
  3. $p_2 \neq 1$: This prevents edge cases where an opponent could force a stationary state that favors them.

Crucially, these conditions do not restrict $p_1$. A strategy can have $p_1 = 1$ (always cooperate after mutual cooperation), making it "nice" while remaining invincible. Furthermore, Theorem 6 proves that an invincible player's payoff is bounded: $s_X \ge P$ and $s_Y \le R$, ensuring the invincible player never falls below the punishment of mutual defection while the opponent never exceeds the reward of mutual cooperation.

Evolutionary Dynamics: Invincibility as a Catalyst

To test the performance of these strategies in a population, the authors employed the Moran Process, a stochastic model of evolutionary selection. In a population consisting only of "Win-Stay Lose-Shift" (WSLS) agents and pure Defectors, cooperation often fails to take hold because Defectors exploit the initial cooperative moves of others. However, the introduction of an invincible strategy changes the landscape.

Comparison of Moran Process simulations. (a) Without an invincible strategy, WSLS fails to overcome Defectors. (b) With an invincible strategy added, it acts as a catalyst, suppressing Defectors and allowing WSLS to dominate the population.

As shown in the simulations, an invincible strategy—even one that is not "nice"—can act as a catalyst for cooperation. By effectively suppressing the fitness of pure defectors, the invincible strategy creates an environment where more cooperative strategies like WSLS can eventually thrive and reach fixation, even if the invincible strategy itself does not become the dominant type.

Conclusion and Future Directions

This research provides a definitive characterization of strategies that refuse to lose in the IPD. By proving that invincibility is compatible with "niceness," the authors offer a more optimistic view of strategic stability. Furthermore, the discovery of the "catalyst" effect suggests that the presence of even a few invincible agents can fundamentally shift the evolutionary trajectory of a population toward mutual cooperation.

Future work may explore higher-memory strategies or the application of invincibility to more complex multi-player games. The robust nature of these strategies across different payoff structures indicates that invincibility is a powerful and generalizable concept in game theory.

Summary updated

Abstract

The Iterated Prisoner's Dilemma (IPD) is a well-known benchmark for studying the long term behaviours of rational agents. Many well-known strategies have been studied, from the simple tit-for-tat (TFT) to more involved ones like zero determinant and extortionate strategies studied recently by Press and Dyson. In this paper, we consider what we call invincible strategies. These are ones that will never lose against any other strategy in terms of average payoff in the limit. We provide a simple characterization of this class of strategies, and show that invincible strategies can also be nice. We discuss its relationship with some important strategies and generalize our results to some typical repeated 2x2 games. It's known that experimentally, nice strategies like the TFT and extortionate ones can act as catalysts for the evolution of cooperation. Our experiments show that this is also the case for some invincible strategies that are neither nice nor extortionate.
BibTeX
@inproceedings{wang2020nice,
  author = {Shiheng Wang and Fangzhen Lin},
  title = {{Nice Invincible Strategy for the Average-Payoff IPD}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5604},
}
Figure