Computing Optimal Equilibria in Repeated Games with Restarts

Ratip Emin Berker, Vincent Conitzer, Shaowei Cai

Abstract

In anonymous environments such as online marketplaces, the threat of retaliation is often insufficient to maintain cooperation because "serial defectors" can simply find new partners to avoid punishment. This paper introduces a model of repeated games with restarts, where a "hazing" period of low payoffs is used to build trust and deter cheating. We provide a mathematical stability condition and develop efficient algorithms—including Dynamic Programming, Integer Linear Programming, and a Fully Polynomial-Time Approximation Scheme (FPTAS)—to find welfare-maximizing hazing sequences. Experimental results demonstrate that these methods are highly scalable, enabling the computation of optimal equilibria in complex games within milliseconds.

Introduction: The Challenge of Serial Defection

Traditional game theory relies on long-term relationships to sustain cooperation through threats like the "grim-trigger" strategy. However, in anonymous settings, players can defect and restart their history with a new partner. To address this, we study equilibria with restarts. If a player deviates, the relationship ends, and both must find new partners and undergo an "unpleasant" hazing period before reaching high-payoff cooperation. The challenge is finding the optimal sequence of actions that minimizes the cost of this hazing while ensuring that no player has an incentive to defect.

Methodology and Algorithms

The problem, formalized as OptRep, involves finding a sequence of payoffs where the cumulative "cost of restarting" (lost payoffs during hazing) exceeds the potential gain from deviation at every step. We identify a property called threshold-monotonicity, which simplifies the search space by showing that optimal sequences follow a specific order based on the "threshold" of each action.

Based on this, we propose three primary computational approaches:

  1. Dynamic Programming (DP): Tracks the "hazing so far" to find exact solutions in pseudo-polynomial time.
  2. Integer Linear Programming (ILP): A robust alternative for games with large payoffs or high temptation.
  3. FPTAS: An approximation scheme that provides a $(1+\epsilon)$ near-optimal solution with significant speedups.

Experimental Evaluation

We evaluated our algorithms using synthetic benchmarks of symmetric two-player games with up to 90 actions and varying "Maximum Payoffs of Deviation" (MPD) to test how the solvers scale with the temptation to cheat.

Runtime performance of ILP, DP, and FPTAS algorithms across varying numbers of actions and Maximum Payoffs of Deviation (MPD).

As shown in the experimental results, the algorithms exhibit distinct scaling behaviors. The ILP is particularly robust as the temptation to cheat (MPD) increases, eventually outperforming the DP when MPD exceeds approximately 1500. The FPTAS consistently offers the fastest runtimes, allowing for a controlled trade-off between optimality and computational speed. For a game with 30 actions, the ILP can find the optimal equilibrium in just a few milliseconds.

Conclusion

Our work demonstrates that cooperation can be stabilized in anonymous environments through structured hazing periods. By providing efficient algorithms to compute these optimal sequences, we offer a practical framework for designing trust-building mechanisms in digital platforms. Future research will explore extensions to asymmetric games and settings with partial anonymity where players might reveal some history to skip part of the hazing.

Summary updated

BibTeX
@inproceedings{berker2024computing,
  author = {Ratip Emin Berker and Vincent Conitzer and Shaowei Cai},
  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