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: The Challenge of Anonymous Cooperation

In classical game theory, the "Folk Theorem" posits that cooperation can be sustained in infinitely repeated games through the threat of future retaliation. Strategies like "Grim Trigger" ensure that any short-term gain from defection is outweighed by the long-term loss of cooperation. However, this mechanism collapses in anonymous environments. If agents can easily mask their identities or find new partners after defecting, the threat of retaliation vanishes. This "serial defection" is a significant barrier for autonomous agents, such as trading bots, operating in large-scale, anonymous networks.

The Hazing Mechanism

To address this, the authors propose Equilibria with Restarts. In this framework, players agree on a sequence of actions. If a deviation occurs, the relationship is terminated, and both players must restart the sequence from the beginning with new partners.

The core innovation is the "hazing" period—a sequence of initial rounds with low payoffs. This period acts as a non-refundable entry cost. For an equilibrium to be stable, the one-time gain from cheating in any round must be less than the cost of re-entering the hazing period. The goal is to find an Optimal Representative (OptRep): a sequence that is stable and minimizes the total "hazing cost" relative to the maximum possible cooperative payoff.

Algorithmic Solutions

The authors prove that finding the optimal hazing sequence is (weakly) NP-hard, reducing it from the Unbounded Subset-Sum Problem. Despite this theoretical hurdle, they develop three practical algorithms:

  1. Dynamic Programming (DP): A pseudo-polynomial time algorithm that is highly efficient when payoffs are small.
  2. Integer Linear Programming (ILP): A formulation that utilizes "threshold-monotonicity"—the insight that optimal sequences can be ordered by their deviation thresholds—to solve the problem efficiently across a wider range of payoffs.
  3. FPTAS: A Fully Polynomial-Time Approximation Scheme that allows users to trade off runtime for a guaranteed near-optimal solution with a tunable error margin ($\epsilon$).

Experimental Results

The algorithms were evaluated using synthetic symmetric games, varying the number of actions and the Maximum Payoff of Deviation (MPD).

Runtime performance of ILP, DP, and FPTAS algorithms across varying game parameters.

As shown in the figure, the DP algorithm is exceptionally fast for games with low MPD, but its runtime increases significantly as the potential gains from deviation grow. In contrast, the ILP is more robust to payoff scales; while it starts slower than DP, it becomes the superior choice as MPD increases (outperforming DP when MPD exceeds ~1500). The FPTAS provides a flexible middle ground, with runtimes decreasing as the allowed error margin ($\epsilon$) increases, effectively balancing accuracy and computational cost.

Conclusion and Future Directions

This work provides a robust theoretical and algorithmic foundation for sustaining cooperation in anonymous settings. By framing the problem as a "hazing" cost, the authors bridge the gap between game theory and combinatorial optimization. Future research directions include extending these models to asymmetric games, where fairness and complex goal sequences become critical, and exploring Bayesian settings where players have private information about their payoffs.

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