Computing Optimal Equilibria in Repeated Games with Restarts

Ratip Emin Berker, Vincent Conitzer

Abstract

Infinitely repeated games can support cooperative outcomes that are not equilibria in the one-shot game. The idea is to make sure that any gains from deviating will be offset by retaliation in future rounds. However, this model of cooperation fails in anonymous settings with many strategic agents that interact in pairs. Here, a player can defect and then avoid penalization by immediately switching partners. In this paper, we focus on a specific set of equilibria that avoids this pitfall. In them, agents follow a designated sequence of actions, and restart if their opponent ever deviates. We show that the socially-optimal sequence of actions consists of an infinitely repeating goal value, preceded by a hazing period. We introduce an equivalence relation on sequences and prove that the computational problem of finding a representative from the optimal equivalence class is (weakly) NP-hard. Nevertheless, we present a pseudo-polynomial time dynamic program for this problem, as well as an integer linear program, and show they are efficient in practice. Lastly, we introduce a fully polynomial-time approximation scheme that outputs a hazing sequence with arbitrarily small approximation ratio.

Introduction

In classic game theory, strategies like the "Grim Trigger" support cooperation by threatening permanent retaliation. However, in anonymous environments—such as online marketplaces or decentralized AI networks—players can often "reset" their identities to escape punishment. A "serial defector" can cheat one partner and immediately find another who is unaware of their history, perpetually exploiting the system.

This paper addresses this challenge by studying equilibria with restarts. In this model, every new partnership begins with a specific sequence of actions. If a deviation occurs, the partnership terminates, and players must restart the sequence from the beginning with new partners. The goal is to design a sequence that is both stable (incentivizing cooperation) and optimal (maximizing long-term payoffs).

Methods

The authors focus on the limit where the discount factor $\beta \to 1$. They characterize the optimal strategy as a two-phase sequence:

  1. Hazing Period: A finite sequence of lower-payoff actions acting as an "entry cost" to the relationship.
  2. Goal Value: An infinitely repeating high-payoff state (ideally the best possible outcome).

The core computational problem, OptRep, is proven to be (weakly) NP-hard via a reduction from the Unbounded Subset-Sum Problem. To address this, three algorithmic approaches are proposed:

  • Dynamic Programming (DP): A pseudo-polynomial time algorithm effective for games where payoffs are small integers.
  • Integer Linear Program (ILP): This approach leverages the "threshold-monotonic" property of optimal sequences—where actions are sorted by the amount of hazing required for stability—to solve the problem efficiently in practice.
  • FPTAS: A Fully Polynomial-Time Approximation Scheme providing a near-optimal sequence within any desired error margin $\epsilon$.

Results

The algorithms were evaluated using synthetic symmetric games with varying numbers of actions and "Maximum Payoffs of Deviation" (MPD) to test scaling and robustness.

Runtime performance of ILP, DP, and FPTAS across varying numbers of actions and MPD values.

The evaluation revealed distinct performance characteristics among the methods. The DP algorithm is highly efficient for games with small payoffs but its runtime scales significantly with the MPD, reflecting its pseudo-polynomial nature. In contrast, the ILP is remarkably robust; its runtime remains largely independent of payoff magnitudes, making it the preferred choice for high-stakes games.

Comparison of ILP and DP runtimes as the Maximum Payoff of Deviation (MPD) increases, highlighting the pseudo-polynomial scaling of DP versus the robustness of ILP.

The study also confirms that the socially optimal sequence always converges to the single highest payoff action ($p_\Omega$) following the hazing period. The hazing period effectively filters out defectors by ensuring the immediate gain from cheating is outweighed by the cost of having to endure the entry period again with a new partner.

Conclusion and Future Work

This work settles the theoretical complexity of finding optimal restart equilibria and provides practical tools for their computation. While the current focus is on symmetric games, future work could extend these models to asymmetric settings (e.g., employer-employee relationships) or Bayesian games where players have private information about their valuation of the future. Additionally, exploring "partial anonymity" where reputation systems can shorten hazing periods remains a promising direction for decentralized cooperation.

Summary updated

Abstract

Infinitely repeated games can support cooperative outcomes that are not equilibria in the one-shot game. The idea is to make sure that any gains from deviating will be offset by retaliation in future rounds. However, this model of cooperation fails in anonymous settings with many strategic agents that interact in pairs. Here, a player can defect and then avoid penalization by immediately switching partners. In this paper, we focus on a specific set of equilibria that avoids this pitfall. In them, agents follow a designated sequence of actions, and restart if their opponent ever deviates. We show that the socially-optimal sequence of actions consists of an infinitely repeating goal value, preceded by a hazing period. We introduce an equivalence relation on sequences and prove that the computational problem of finding a representative from the optimal equivalence class is (weakly) NP-hard. Nevertheless, we present a pseudo-polynomial time dynamic program for this problem, as well as an integer linear program, and show they are efficient in practice. Lastly, we introduce a fully polynomial-time approximation scheme that outputs a hazing sequence with arbitrarily small approximation ratio.
BibTeX
@inproceedings{berker2024computing,
  author = {Ratip Emin Berker and Vincent Conitzer},
  title = {{Computing Optimal Equilibria in Repeated Games with Restarts}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=K4XQXwTaiV},
}
Figure