Payoff landscapes and the robustness of selfish optimization in iterated games

Arjun Mirani, Alex McAvoyarXiv 2021 · arXiv

Introduction

The Iterated Prisoner’s Dilemma (IPD) serves as a fundamental model for the evolution of cooperation. A decade ago, the discovery of "Zero-Determinant" (ZD) strategies suggested that a player could unilaterally enforce a linear relationship between their payoff and their opponent's. Theoretically, this allows a player to incentivize a selfish opponent to cooperate. However, this paper investigates whether real-world learners—modeled as local "hill-climbers"—actually reach these global optima or if they become trapped in suboptimal regions of the payoff landscape.

Methodology

The study employs a combination of analytical proofs and numerical simulations. The authors model a selfish player using Projected Gradient Ascent (PGA), where the player iteratively adjusts their strategy in the direction of increasing payoffs while remaining within the bounds of valid probability space $[0, 1]^4$. They analyze the geometry of these payoff landscapes to identify where gradients vanish and conduct simulations across $10^5$ initial strategies to map "basins of attraction." To test robustness, they also incorporate "Local Random Search" and "Trembling Hand" noise models.

Payoff Landscapes and Strategy Dynamics

A central finding is the "Boundary Rule": in symmetric 2x2 games, a selfish learner using gradient ascent will almost always converge to a strategy on the boundary of the strategy space, where at least one action becomes deterministic.

Payoff landscapes and reachable payoff regions for various memory-one strategies. Panels (a-e) show the feasible payoff regions (blue) and the set of payoffs reachable by a learner (grey) against specific fixed strategies (red dots). Panel (f) illustrates the distribution of final outcomes.

The robustness of ZD strategies is found to be surprisingly brittle. While they can theoretically force cooperation, their effectiveness depends heavily on game parameters (e.g., $2P < S + T < 2R$). Outside these conditions, the landscape becomes rugged, and learners often fail to find the cooperative global peak.

Key Results

  • Convergence to Boundaries: Theorem 1 establishes that stable points for PGA must lie on the boundary of the strategy hypercube.
  • Local Optima Traps: In games where alternating play is advantageous ($S + T > 2R$), approximately 15% of learners fail to reach the global optimum and get stuck in lower-paying strategies.
  • Non-ZD Fragility: Against general (non-ZD) memory-one strategies, simulations showed cases where up to 61% of learners converged to the worst possible local optimum.
  • Inefficiency of Noise: While noise can theoretically help agents escape local traps, the time scales required are often impractical for real-world applications.

Conclusion

The study demonstrates that the "payoff control" promised by ZD strategies is not as robust as previously assumed when facing realistic, local learners. The complexity of the payoff landscape creates significant hurdles, often leading selfish agents to suboptimal outcomes. Future research should extend these findings to multi-agent learning scenarios where both players adapt simultaneously, further complicating the dynamic landscape.

Summary updated

Abstract

In iterated games, a player can unilaterally exert influence over the outcome through a careful choice of strategy. A powerful class of such "payoff control" strategies was discovered by Press and Dyson (2012). Their so-called "zero-determinant" (ZD) strategies allow a player to unilaterally enforce a linear relationship between both players' payoffs. It was subsequently shown by Chen and Zinger (2014) that when the slope of this linear relationship is positive, ZD strategies are robustly effective against a selfishly optimizing co-player, in that all adapting paths of the selfish player lead to the maximal payoffs for both players (at least when there are certain restrictions on the game parameters). In this paper, we investigate the efficacy of selfish learning against a fixed player in more general settings, for both ZD and non-ZD strategies. We first prove that in any symmetric $2\times 2$ game, the selfish player's final strategy must be of a certain form and cannot be fully stochastic. We then show that there are prisoner's dilemma interactions for which selfish optimization does not always lead to maximal payoffs against fixed ZD strategies with positive slope. We give examples of selfish adapting paths that lead to locally but not globally optimal payoffs, undermining the robustness of payoff control strategies. For non-ZD strategies, these pathologies arise regardless of the original restrictions on the game parameters. Our results illuminate the difficulty of implementing robust payoff control and selfish optimization, even in the simplest context of playing against a fixed strategy.
BibTeX
@misc{mirani2021payoff,
  author = {Arjun Mirani and Alex McAvoy},
  title = {{Payoff landscapes and the robustness of selfish optimization in iterated games}},
  year = {2021},
  eprint = {2111.14246},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.14246},
}
Figure