Computing Optimal Equilibria in Repeated Games with Restarts

1 Introduction

In social dilemmas, individual incentives hinder collective benefit: mutual cooperation is the best outcome for both players, but it is not a Nash equilibrium. Consider the symmetric two-player game in Table 1:

Notice that for each player, D is the strictly dominant action, ensuring the maximum payoff against any fixed action of their opponent. This results in (D↪ D) being the only Nash however, mutual cooperation can be achieved: Consider the grim-trigger strategy where both players agree to play C2 in every round, but if their opponent defects, they switch to playing D in all future rounds. During the game, a player can increase their payoff in a round by at most 14 - 8 = 6 by defecting, but their payoff in all future rounds is now bound above by 4, as their opponent will switch to D, resulting in a per-round net loss of at least 8 - 4 = 4 compared to if they had stuck to C2. If the players value future rounds sufficiently (i.e., have a 'discount factor' close to 1, assumed true for the rest of this section), the gain of defecting (6, once) will be offset by loss due to the opponent retaliating (4, all future rounds), resulting in neither of the players defecting from C2.

This model of cooperation, however, fails in anonymous settings with many players, in which players can simply find a new partner to play with. This setting can model any situation that involves two-player interactions within a larger pool, such as monogamous relationships, employer-employee interactions, and two-person research collaborations. Critically, each of these 'partnerships' can last for arbitrarily many rounds, but can be terminated at any point by one of the partners, who can then find themselves a new partner in the larger pool. In this game-theoretic setting, a player can defect and avoid retaliation, if they are able to switch partners immediately following the defection. If there is no way for a player to check their partner's history (that is, players are anonymous), this setting may result in the emergence of 'serial defectors,' who perpetually defect on a partner and move on the next, even if all their partners would follow the 'grim trigger' strategy if the relationship continued. This is especially relevant for settings where the players are AI agents (such as trading bots), who might more easily conceal their identity compared to traditional human players.

To avoid this pitfall, we turn to a specific type of equilibria in such infinitely repeated two-player games, those with restarts. Instead of the grim-trigger strategy of 'defect forever once the opponent deviates', consider instead a strategy profile where all players agree on a planned sequence of actions to follow, and they restart the same sequence with a new partner if their opponent ever deviates from it. (In the context of our paper, the punishment strategy of simply leaving the relationship, thereby forcing the partner to restart as well, is in fact without loss of generality: no other punishment strategy could be more effective, because if it were more effective, the partner would simply leave the relationship.) 1

For instance, going back to the game in Table 1, say the two players agree on the sequence (D↪ C1↪ C2↪ C2↪ C2↪ ▷ ▷ ▷). If the players stick to the plan, the sequence of payoffs they receive is (4↪ 5↪ 8↪ 8↪ 8↪ ▷ ▷ ▷). Neither will deviate from the plan in the first round (D), as doing so can only lower their payoff. In the second round (C1), deviating brings a payoff of 11, but results in the opponent ending the relationship and having to go back to the start of the sequence with someone else. This results in a per-round average payoff of (4 + 11)◁2 = 7▷5 for the deviating player, which is less than the per-round payoff of 8 she can eventually receive by sticking to the planned sequence. Similarly, once the players get to the (C2) portion of their sequence, any deviation can bring at most a payoff of 14 (an increase of 6), but results in a restart where the next two rounds (4,5) does a total damage of (8-4)+(8-5) = 7 when compared to sticking with the sequence, making the overall sequence stable. Conceptually, the planned sequence consists of a 'hazing' period (D↪C1), followed by lasting sociallyoptimal cooperation (C2↪ C2↪ ▷▷▷).

Not every planned sequence is stable: an alternative plan (C1↪C2↪C2↪C2↪ ▷ ▷ ▷) would incentivize repeatedly deviating on the first step, to obtain 11 per round. Another alternative, (D↪C2↪C2↪C2↪ ▷ ▷ ▷), would see a player repeatedly deviating on the second step, ensuring a per round utility of (4 + 14)◁2 = 9 > 8. Both of these alternatives suffer from under-hazing, as the cost of a restart for a defecting player fails to offset the gains from defection.

(D↪C1↪C2↪C2↪ ▷ ▷ ▷) is not the only stable sequence; so is (D↪C1↪C1↪ ▷ ▷ ▷ ↪C1↪C2↪C2↪ ▷ ▷ ▷), for an arbitrarily large (positive) number of C1s. However, this results in unnecessarily delaying the socially optimal outcome of C2, i.e., overhazing. Hence, in this paper we ask: how can we optimize the payoff of a planned sequence, while ensuring its stability?

1.1 RelatedWork

Repeated games (without restarts) have long been of interest to the AI community. In contrast to one-shot games, they introduce a temporal component to the game, and they allow modeling settings where cooperation can be sustained thanks to the threat of deviators being punished in future rounds. This is now of particular interest in the context of the nascent research area of cooperative AI [Dafoe et al., 2021], especially for game-theoretic approaches to that [Conitzer and Oesterheld, 2023]. Thanks to the folk theorem, they also allow for more efficient computation of Nash equilibria than one-shot games, as was observed by [Littman and Stone, 2005] for two players. With three or more players the problem becomes hard again [Borgs et al., 2010], though in practice it can often be solved fast [Andersen and Conitzer, 2013] and if correlated punishment is allowed then the problem becomes easy again [Kontogiannis and Spirakis, 2008].

Separately, the role of anonymity in game theory has long been of interest to the AI community. Perhaps most significantly, in mechanism design, there is a long line of work on false-name-proof mechanisms, in which agents cannot benefit from participating multiple times using fake identifiers [Yokoo et al., 2001; Yokoo et al., 2004; Conitzer and Yokoo, 2010]. This is conceptually related to the work in this paper, insofar as an agent that restarts with a different partner makes use of a degree of anonymity in the system. However, in our context an agent does not use multiple identifiers simultaneously, and the work seems technically quite distinct.

1 The type of equilibrium we study remains an equilibrium in the standard repeated game setting (without restarts), and so is a refinement of the traditional concept. In this case, if one's partner deviates, one continues with the same partner but plays as if one were starting from the beginning, which is sufficient to deter deviation.

Cooperation in repeated games with the possibility of rematching with a new partner has been studied in the economic theory community, similarly identifying the importance of building up relations gradually. Our work differs from this literature in that we focus on the computational problem of optimizing the equilibrium, for arbitrary games, whereas the economics literature focuses on obtaining characterization results in specific settings such as lending and borrowing games [Datta, 1996; Wei, 2019], prisoner's dilemma [Fujiwara-Greve and Okuno-Fujiwara, 2009; Rob and Yang, 2010; Izquierdo et al., 2014], and environments with agents of multiple types [Kranton, 1996; Ghosh and Ray, 1996; Rob and Yang, 2010].

1.2 Overview

In Section 2, we introduce the concepts and notation. In Section 3, we introduce optimal sequences and prove their various properties. In Section 4, we define an equivalence relation on sequences based on their total discounted utility with high discount factor. In Section 5, we formalize the computational problem of computing a representative of the optimal equivalence class of this relation. As our main results, we prove an NP-hardness result and present three algorithms for the problem: a pseudo-polynomial time dynamic program and an integer linear program that exactly solves it, as well as a fully polynomial time approximation scheme. In Section 6, we report runtimes from our experiments with these algorithms. We present directions for future research in Section 7.

2 Preliminaries

In this work, we restrict our attention to symmetric games and strategies, which allows us to condense the representation of a game and thereby simplify the presentation. We discuss moving beyond symmetry in Section 7.

2.1 Problem Instance

Given a two-player finite, symmetric normal form game Γ with actions A = ¶a(1) ↪ ▷▷▷↪ a(n) ♦ and integer payoffs, we define:

• The cooperative payoff function p : A ! Z, which maps a(j) to the payoff that the two players receive in Γ if they both play a(j) for each j 2 [n].
• The deviation payoff function p⇤ : A!Z, which maps each a(j) to the max. payoff a player can achieve given they play any A ∩ ¶a(j) ♦ and their opponent plays a(j) .
• The discount factor β 2 [0↪ 1), such that if a player receives payoff pi in round i 2 N, her total discounted

utility is P1i=0 βipi. To avoid confusion, we use subscript i 2 N = ¶0↪ 1↪ ▷ ▷ ▷♦ to iterate over the rounds, and superscript j 2 [n] = ¶1↪ ▷ ▷ ▷ ↪ n♦ to iterate over actions.

Thus any finite symmetric game Γ can for our purposes be represented as G = (¶(p(j) ↪ p⇤(j) )♦j2[n]↪ β), where p(j) := p(a(j) ) and p⇤(j) := p⇤ (a(j) ). For instance, the game in Table 1 is represented as G1 = (¶(4↪ 0)↪ (5↪ 11)↪ (8↪ 14)♦↪ β).

2.2 Equilibria with Restarts

In this paper, we focus on strategy profiles σ where each player plans to follow the sequence of moves (a0↪ a1↪ ▷▷▷) 2 AN, and will restart the sequence if the other player deviates from it. We define pi := p(ai) and p⇤i := p⇤ (ai) for all i 2 N. Two forever-cooperating agents will achieve total discounted utility P1i=0 βipi, whereas an agent deviating on round k will achieve total discounted utility Pk-1 i=0 βipi + βk p⇤k + P1i=0 βi+k+1pi. 2 Accordingly, for σ to be stable (i.e., a Nash equilibrium), we need (for all k 2 N):

Since σ is completely defined by the planned sequence, we can succinctly represent it using its corresponding sequence of payoffs (pi)i2N 2 ¶p(j) ♦Nj2[n] and (p⇤i )i2N 2 ¶p⇤(j) ♦Nj2[n] .

3 Optimal Sequences

Given a game instance G, there can be infinitely many stable sequences (pi)i2N. For instance, given G1, our representation of the game in Table 1, both of the following sequences are stable for β = 0▷9, as they fulfill Equation (1) for all k 2 N:

The multitude of stable sequences for a given game raises two questions: how can we (i) determine which sequences are more desirable than others, and (ii) compute the most desirable sequences? The answer to (i) is straightforward in our context of symmetric games, where the payoffs of two cooperating players are the same. Thus, one can focus on maximizing total discounted utility without fairness concerns. For instance, P1i=0 βipai ⇡ 43▷1 and P1i=0 βipbi ⇡ 56▷9, indicating (pbi )i2N to be 'the better plan'. More generally, we define:

Definition 1 (Optimal sequence). Given any G = (¶(p(j) ↪ p⇤(j) )♦j2[n]↪ β), a sequence of payoffs (pi)i2N surpasses sequence (p0i )i2N if P1i=0 βipi > P1i=0 βip0i . A sequence (pi)i2N is an optimal sequence if:

1. it is stable, i.e., satisfies Equation (1) for all k 2 N, and
2. it is not surpassed by any other other stable sequence.

We first prove an existence result:

2 Note that this assumes the deviating agent never deviates again; this is WLOG, since deviating repeatedly in this way is an improvement if and only if deviating once in this way is an improvement.

Proposition 1. For any G = (¶(p(j) ↪ p⇤(j) )♦j2[n]↪ β), if there is any stable sequence, then an optimal sequence exists. This sequence is not necessarily unique.

Proof. The proof follows from the following claim. To save space, we present the proof of the claim as well as an example for non-uniqueness in Appendix A.1 of the full version of the paper.

Claim 1. Given any instance G, the set of achieveable total utilities is a closed set, where we say total t 2 R is achievable if there exists a stable sequence (pi)i2N with P1i=0 βipi = t.

Since the set of achievable total discounted utilities is closed and bounded, it contains its supremum [Rudin, 1976, Thm. 2.28], proving an optimal stable sequence exists.

Having proven the existence of optimal sequences, we now present two lemmas about their properties.

Lemma 1. Any optimal sequence will reach a step after which a single payoff (the highest in the sequence) is repeated forever. We call this payoff the goal value of the sequence.

Intuitively, Lemma 1 implies that any optimal sequence consists of an infinitely repeating goal value, the highest payoff, as well as a preceding hazing period, a finite sequence of non-maximal payoffs. These two stages are interdependent: an agent cooperates during the hazing period due to the promise of the goal value, whereas any defection after reaching the goal value is avoided by the threat of facing the hazing period again.

Lemma 2. For large enough β, the goal value of any optimal sequence is p⌦ := maxj2[n] p(j) .

Together, Lemmas 1 and 2 (proven in Appendix A.2) allow easily ruling out many sequences as non-optimal for sufficiently high values of β, including (pai )i2N and (pbi )i2N from above, the latter since it never converges to a goal value, and the former since it converges to one that is not the highest in the game. As we have seen in Lemma 2, the large β setting achieves the largest goal values, and accordingly, the largest gap between achieving cooperation and failing to do so, adding to the significance of computing stable and optimal sequences. Indeed, in much of the literature on repeated games in general (including folk theorems), the focus is on the limit case where β ! 1. Accordingly, in the next section, we study the optimality of sequences in the β ! 1 limit.

4 Limit-Utility Equivalence Classes

We say that a sequence (pi)i2N is stable in the β ! 1 limit if there exists a β0 such that (pi)i2N is stable for all β > β0 . Of course, as β ! 1, the total discounted utility diverges. Hence, we now introduce an equivalence relation that allows us to compare the total discounted utilities in this limit:

Definition 2 (Limit-utility equivalence). Given a game G = ¶(p(j) ↪ p⇤(j) )♦j2[n], two stable sequences (pi)i2N and (p0i )i2N are limit-utility equivalent if limβ!1 P1i=0 βi (pi -p0i ) = 0.

Indeed, this relationship is symmetric, reflexive, and transitive. We now introduce the optimal equivalence class:

Proposition 2. There exists a well-defined optimal limitutility equivalence class: that is, an equivalence class such that for any member sequence (pi)i2N and any other sequence (p0i )i2N, we have limβ!1 P1i=0 βi (pi - p0i ) ≥ 0.

Proof. By Lemmas 1 and 2, any (pi)i2N that converges to p⌦ = maxj2[n] p(j) will surpass any (p0i )i2N that does not, implying the equivalence class of the latter cannot be optimal. Ruling such sequences out allows us to define for any sequence of payoffs (pi)i2N a corresponding sequence of hazings (hi)i2N, where hi = p⌦ - pi. For any two sequences that converge to p⌦, we have limβ!1 P1i=0 βi (pi - p0i ) = P1i=0 h0i - P1i=0 hi, where neither of the sums diverge since hi 6= 0 or h0i 6= 0 for only finitely many i. Hence, the equivalence class of a sequence with goal value p⌦ is entirely determined by the (non-discounted) sum of its per-round hazings. By Lemma 2, there exists at least one such stable sequence (hi)i2N, say with total hazing H = P1i=0 hi. Since the total non-discounted hazing for any sequence is an integer and bounded below by 0, there can only be finitely many improvements over H, implying that there is a well-defined minimum total hazing Hmin with at least one corresponding stable sequence. Hence, any stable sequence with total hazing Hmin cannot be surpassed (as β ! 1) by any other stable sequence, either converging to p⌦ or not, proving its equivalence class is optimal.

5 Computational Problem: OptRep

Having proven the existence of the optimal equivalence class, the natural next question becomes: how do we compute a (representative) sequence from this class? Before formalizing this as computational problem, we investigate the stability condition given in Equation (1) in the β ! 1 limit:

Proposition 3. A sequence (pi)i2N with goal value p⌦ = maxj2[n] p(j) is stable in the β ! 1 limit if and only if the following holds for all k 2 N :

The proof is given in Appendix A.3. Intuitively, the left-hand side of (2) is the cost of restarting, as repeating each step i results in a loss of p⌦-pi (the so-called hazing cost) compared to the goal value, whereas the right-hand side is the gains from deviating, represented by the advantage over the goal value one can gain by deviating now. The inequality needs to be strict because, intuitively, for any β < 1, a "tie" between the two sides of the equation would be broken towards the side of deviation, as that deviation payoff comes earlier.

Motivated by this way of expressing the stability condition, we modify the representation of a game to fit our problem: Given G = ¶(p(j) ↪ p⇤(j) )♦j2[n] and p⌦ = maxj2[n] p(j) , for each j 2 [n] we define a corresponding hazing cost h(j) = p⌦ - p(j) and a threshold t(j) = p⇤(j) - p⌦. We now represent the game as G = ¶(h(j) ↪ t(j) )♦j2[n] and any sequence of payoffs (pi)i2N with the corresponding sequence of hazing costs (hi)i2N. The stability condition from (2) then becomes:

As shown in the proof of Prop 2, all members of the optimal limit-utility equivalence class necessarily have p⌦ as their goal value, and hence hi 6= 0 for finitely many i, and the equivalence class of any such sequences is entirely determined by P1i=0 hi. Any such stable sequence must satisfy P1i=0 hi > p⇤⌦ - p⌦ ⌘ ∆, to ensure (3) is fulfilled for the steps after reaching the goal value. Thus, the goal of finding a representative of the optimal equivalence class reduces to:

Definition 3 (OptRep). Given ¶(h(j) ↪ t(j) )♦j2[n] ⇢ Z+ ⇥ Z and ∆ 2 Z+, OptRep asks to find a finite sequence (hi)i2¶0♦[[`] 2 ¶h(j) ♦`+1 j2[n] for some ` 2 N such that P`i=0 hi is minimized, subject to:

Theorem 1. OptRep is (weakly) NP-hard, and the corresponding decision problem is NP-complete.

Proof. We will prove the theorem by reducing the Unbounded Subset-Sum Problem (USSP) to OptRep. USSP is NP-complete [Lueker, 1975] and asks:

Given positive integers ¶ai♦i2[m] and A, do there exist

non-negative integers ¶ri♦i2[m] such that Pmi=1 ri · ai = A? We now present our reduction: For each j 2 [m], define h(j) = aj and t(j) = -1 (in the payoff representation, this simply implies p⇤(j) = p⌦ - 1). Lastly, set ∆ = A - 1. We claim that the answer to the Unbounded Subset-Sum Problem is yes if and only if the total hazing of the optimal sequence computed by OptRep on input G = (¶(h(j) ↪ t(j) )♦j2[m]↪∆) is A. The backwards direction is obvious. For the forward direction, say that the answer to USSP is yes, with coefficents (rj)j2[m]. We can construct a finite hazing sequence (hi)i2¶0♦[[R] that has each h(j) repeating rj times, where R = Pmj=1 rj. Notice that (3) is fulfilled since ti = -1 for all i 2 ¶0♦ [ [R]. As for the final hazing threshold, we have PRi=0 hi = Pmj=1 rjaj = A = ∆ + 1 > ∆, so the overall sequence is stable. Since the total hazing will be integral, any sequence with less total hazing will fail to meet the threshold set by ∆. Hence, the total hazing of the optimal sequence computed by OptRep on input G = (¶(h(j) ↪ t(j) )♦j2m↪ ∆) is A.

The reduction proves that OptRep is NP-hard. The corresponding decision problem (of whether a stable sequence with total hazing H in the β ! 1 limit exists) is NP-complete, since, as we will see in Lemma 3, every sequence has a polynomial-size representation that does not change its total hazing cost, which can be computed in polynomial time.

As shown by [Wojtczak, 2018, Theorem 4], USSP becomes strongly NP-complete when the inputs are rational numbers rather than integers. Due to our reduction above, the same result readily translates to OptRep:

Corollary 1. OptRep with rational inputs is strongly NPhard, and the corresponding decision problem is strongly NPcomplete.

Considering the similarities between OptRep and USSP presented in the proof of Theorem 1, one might wonder if a reduction from OptRep to USSP is also possible. However, OptRep has additional challenges: instead of a set of items, we need to pick a sequence and ensure that every step of it meets the requirement in (3), as opposed to only a final capacity requirement.

Despite these challenges, we can exploit the structural properties of OptRep to develop techniques similar to those employed for knapsack problem variants such as USSP. One key observation is that the stability of a given sequence at any step solely depends on the hazing that has already occurred. This enables us to solve the problem with a dynamic program with a single state variable (the hazing so far), leading to:

Theorem 2. OptRep is solvable in pseudo-polynomial time.

Proof. We prove the theorem by showing the correctness, time complexity, and space complexity of Algorithm 1.

(a) Correctness: Due to integral hazing costs, the minimum hazing cost for any stable sequence is ∆+ 1. We prove (by strong induction on decreasing h) that once Algorithm 1 is complete, D[h] contains the minimum overshoot over this lower bound one can achieve starting from a hazing cost of h. As a base case, for any h ≥ ∆+ 1, the hazing goal has been met and the best we can do is an overshoot of h-∆-1 (Line 4). For any h < ∆+ 1, at least one more action needs to be added to meet the hazing goal. In Line 7, the algorithm chooses the next eligible action that minimizes the overshoot, where action j 2 [n] is eligible if the hazing so far, h, has met its threshold, t(j) . Inductively assuming that D[h0 ] is correct for all h0 > h ensures that D[h] is correctly set. Accordingly, D[0] gives the overshoot of a sequence from the optimal equivalence class, and the list A keeps track of the next steps to later reconstruct the sequence.

(b) Time complexity: Line 4 takes constant time and is implemented hmax = maxj2[n] h(j) times. Lines 5-8 take O(n) time and are executed O(∆) times. Since the sequence returned has at most ∆ + 1 actions, Lines 10-12 take O(∆) time. All other steps take constant time. Overall, the algorithm runs in O(n∆+ hmax) time, which can be improved to O(n∆) by feeding Line 4 into the definition of D[h] in Lines 5-8. This is polynomial in the input but, since input is represented in binary, exponential in the problem size.

(c) Space complexity: D and A both have ∆ variable entries, giving the algorithm a space complexity of O(∆). If we are not interested in reconstructing the representative sequence, the space complexity improves to O(min¶hmax↪∆♦), since we may only store the most recent hmax entries of D, which are sufficient for Line 7.

Alternatively, one can formulate OptRep as an Integer Linear Program (ILP), using binary variables for whether action (j) is the ith action in the sequence. But the hazing period can have as many as ∆+1 actions, resulting in O(n∆) variables, exponentially many. Instead, we ask if one can impose some structure on the output sequence without losing generality.

Algorithm 1 Dynamic Program for OptRep

Input: Final hazing goal: ∆ > 0↪ tuples of (hazing, thresholds) values for each action: ¶(h(j) ↪ t(j) )♦j2[n] ⇢ Z+ ⇥ Z Output: a list So representing a sequence from the optimal equivalence class, along its hazing cost Ho 2 Z+.

1: Let ` =∆+maxj2[n] h(j) . 2: D [inf]` , A [inf]` 3: for h = `↪ ` -1↪ ▷ ▷ ▷ ↪ 1↪ 0 do 4: if h ≥∆+1 then D[h] h-∆-1 5: else 6: Sh ¶j 2 [n] : h > t(j) ♦ 7: D[h] minj2Sh D[h+h(j) ] 8: A[h] argminj2Sh D[h+h(j) ] 9: Ho D[0] +∆+1, So [], i 0 10: while i 6= inf do 11: So So + [A[i]], i A[i] 12: end while 13: return So↪Ho

One intuitive candidate is monotonicity: does the optimal equivalence class always have a sequence with nonincreasing hazing costs (non-decreasing payoffs), considering the goal value is the highest payoff? The answer, it turns out, is no. Consider: ∆ = 10 with (h(1) ↪ t(1) ) = (5↪-1)↪ (h(2) ↪ t(2) ) = (6↪ 4). The sequence (h(1) ↪ h(2) ) is stable and achieves a hazing of 11. The minimum hazing from any non-increasing sequence is 15, by (h(1) ↪ h(1) ↪ h(1) ).

There is, however, a property that can be imposed on the sequences without ruling out the optimal equivalence class:

Lemma 3. Any stable sequence of the optimal equivalence class can be converted to a stable sequence in the same class where (a) all appearances of any action are adjacent and (b) actions appear in order j1↪ j2↪ ▷▷▷↪ j` where t(j1)  t(j2)  ▷ ▷ ▷  t(j`) . We call such sequences threshold-monotonic▷

Proof. For a given action j, say ij is its first appearance in the sequence. Move all appearances of h(j) to appear immediately after ij, pushing all the actions that were previously there to later steps, without changing their order. The total hazing (and hence the equivalence class) has not changed. The stability of all h(j) follows from its stability at step ij: once its threshold is met, this action will always be stable. All other actions are still stable since the hazing that precede them could have only increased. Repeating this for every j 2 [n] achieves (a).

Say the actions now appear in order j1↪ j2↪ ▷ ▷ ▷ ↪ jn. Assume the first k of them are the lowest k threshold actions (with the base case k = 0). Then the action with (k+1)th lowest threshold is jz for some z 2 ¶k+1↪ ▷ ▷ ▷ n♦. Move every occurrence of action jz to the starting point of action jk+1, sliding every other action to the right. The occurrences of action jz will be stable by the stability of jk+1 prior to the shift, which has an equal or greater threshold. All other actions are stable as their preceding hazing can only increase. Repeating this inductively results in the overall sequence fulfilling (b).

Algorithm 2 Integer Linear Program for OptRep

Input: Final hazing threshold: ∆ > 0↪ tuples of (hazing, thresholds) values for each action: ¶(h(j) ↪ t(j) )♦j2[n] ⇢ Z+⇥

Parameters: (8j 2 [n]) : r(j) indicating how many times action j is repeated in the output sequence

Output: Final values of [r(j) ]j2[n]

• 1: if t(1) ≥ 0 then raise error
• 4: (8j 2 [n] ∩ ¶1♦) Pj-1 j 0=1 r(j 0 )h(j 0 ) ≥ t(j) + 1
• 2: minimize Pnj=1 r(j)h(j) 3: subject to
• 5: Pnj=1 r(j)h(j) ≥∆+1 6: return [r(j) ]j2[n]

By Lemma 3, we can restrict our attention to thresholdmonotonic sequences while solving OptRep, leading to an ILP with O(n) variables, presented in Algorithm 2. Note that ordering actions by thresholds takes an additional O(n log n) preprocessing time. The assumption t(n)  ∆ is WLOG, since any action j with t(j) ≥ ∆+ 1 cannot be used until the final hazing threshold is met. The ILP returns [r(j) ]j2[n], the number of times each action is repeated, as this is sufficient to represent a threshold-monotonic sequence. As seen in our experiments in Section 6, Algo. 2 is efficient in practice.

Lemma 3 can also improve the space complexity of Algorithm 1: each A[h] can now store a size-n vector corresponding to [rj]j2[n], with Line 8 replaced with A[h][j ⇤ ] A[h][j ⇤ ] + 1 where j ⇤ = argminj2Sh D[h + h(j) ]. Thus, it now suffices to store only hmax entries of A and D. Call Algorithm 1 with this modification (as well as those mentioned in the proof of Theorem 2(b-c)) Algorithm 1⇤ . This leads to the below strengthening of Theorem 2:

Theorem 3. Algorithm 1⇤ solves OptRep in O(n∆) time using O(min¶∆↪ n · hmax♦) space. The space complexity is O(min¶∆↪ hmax♦) for the corresponding decision problem.

While efficient in practice, both Algorithms 1 and 2 are exponential in the worst case, which motivates the question of whether OptRep can be approximated with a Fully Polynomial Time Approximation Scheme (FPTAS), which runs in polynomial in the problem size and in 1◁", where " is the approximation ratio, given as an input. While we have given a pseudopolynomial-time algorithm for our problem, doing so in general does not guarantee the existence of an FPTAS: for instance, knapsack with multiple constraints is pseudopolynomial-time solvable but does not have an FPTAS unless P = NP [Magazine and Chern, 1984]. However, for OptRep there is in fact an FPTAS, given as Algorithm 3. The algorithm is a modification of Ibarra and Kim's original FPTAS for unbounded knapsack [1975], with additions that address the differences between OptRep and unbounded knapsack.

Theorem 4. Algorithm 3 is an FPTAS for OptRep, and runs in O(n log n + n "2 ) time.

Proof. (a) Correctness: To prove correctness, we first present several claims, the proofs of which are in Appendix A.4

Algorithm 3 FPTAS for OptRep

Input: Final hazing threshold: ∆ > 0↪ tuples of (hazing,

• thresholds) values for each action: ¶(h(j) ↪ t(j) )♦j2[n] ⇢ Z+⇥ Z, with t(1)  t(2)  ▷ ▷ ▷  t(n)  ∆ Output: ˆH↪ ˆL, where ˆL is a list of actions representing the output sequence, and ˆH is the corresponding hazing cost. 1: if t(1) ≥ 0 then raise error 2: F ¶j 2 [n] : ti < 0↪ hi ∆♦ 3: if F = ; then 4: ˆL [argminj2[n]:ti<0 h(j) ], ˆH h(ˆL[0]) 5: return ˆH↪ ˆL 6: j ⇤ minF, ˜H k·h(j ⇤ ) where k is themin. integer s.t. k · h(j ⇤ ) >∆ 7: δ ˜H ( "3 )2 , g j ˜Hδ k = j( 3" )2k, S ; 8: T [inf]g+1 , L [inf]g+1 , T[0] 0, L[0] [ ] 9: for j = 1↪ ▷ ▷ ▷ ↪ n do 10: if h(j)  "3 ˜H then S S + [j] 11: else 12: f (j) j h(j) δ k 13: for k = 0↪ ▷▷▷↪ g - f (j) do 14: if T[k] 6= inf and T[k] > t(j) and (T[k + f (j) ] = inf or T [k] + h(j) > T [k + f (j) ]) then 15: T[k + f (j) ] T[k] +h(j) 16: L[k + f (j) ] L[k] + [j] 17: js argminj2S t(j) 18: k⇤ argmink2¶0♦[[g]:T[k]>t(js) T[k]+nk ·h(js) where nk is the min. integer s.t. T[k] +nk · h(js) >∆ 19: ˆH T[k⇤ ] +nk⇤ · h(js) , ˆL L[k⇤ ] + [js]nk⇤ 20: return ˆH↪ ˆL

Claim 2. Say H⇤ is the optimal hazing. If the algo. returns on Line 5, ˆH =H⇤ . Else, ˜H ≥H⇤ ≥ 12 ˜H after Line 6.

Note that Line 7 sets a 'normalizing factor' of δ = ˜H ( "3 )2 , later used for computing normalized hazing costs f (j) = ⌅h(j) ◁δ⇧ and a normalized upper bound for the optimal hazing g = b ˜H◁δc.

Claim 5. Say (hi)i2¶0♦[[`] is any stable threshold-monotonic subsequence (i.e., it fulfills (3) for all k  `, but does not necessarily meet the final hazing goal ∆), where the order of actions is consistent with the labeling, with hi > "3 ˜H for all i and total hazing at most ˜H. Defining fi = bhi◁gc and F = P`i=0 fi, we must have T [F] ≥ P`i=0 hi in the end of the execution.

Claim 4. At any point during the execution starting from Line 8, for any k 2 ¶0↪ ▷▷▷↪ g♦, either T[k] = L[k] = inf or L[k] contains a list [j0↪ j1↪ ▷ ▷ ▷ ↪ j`] with P`i=0 f (ji) = k and P`i=0 h(ji) = T [k].

We now complete the proof of the theorem: Say (h?i )i2¶0♦[[`] is a member of the optimal equivalence class (P`i=0 h?i = H⇤ ), with corresponding normalized hazing costs (f ? i )i2¶0♦[[`] and F ⇤ = P`i=0 f ? i . By Lemma 3, we can assume WLOG that (h?i )i2¶0♦[[`] is threshold-monotonic, with respect to the current labeling of the actions.

Say ˆH = T[k⇤ ] + nk⇤ · hjs and ˆL = L[k⇤ ] + [js]nk⇤ are the final outputs of the algorithm, as set in Line 19, and S is the set of actions j with h(j)  ("◁3) ˜H, as filled in Line 10. By Claim 4, the total hazing of the sequence represented by ˆL is indeed ˆH. The stability of every step in L[k⇤ ] in ensured by the if statement in Line 14. The stability of the final nk⇤ steps is ensured by the T [k⇤ ] > t(js) condition in Line 18.

Case 1: (h?i )i2¶0♦[[`] has no element fromS. Then it fulfills the assumptions of Claim 5 (as H⇤  ˜H by Claim 2), implying T [F ⇤ ] ≥ H⇤ ≥ ∆+ 1 > t(js) . Since H⇤  ˜H, we have F ⇤  g, so T [F ⇤ ] is one of the options considered in Line 18 (with nF ⇤ = 0), implying ˆH  T[F ⇤ ]. By Claim 4, we get Pj2L[F ⇤ ] f (j) = F ⇤ = P`i=0 f ? i . Using Claim 3 twice:

Hence, ˆH  T[F ⇤ ]  (1+ "2 ) H⇤ , fulfilling the bound. Case 2: (h?i )i2¶0♦[[`] does have an action from S. Say i⇤ is the first index where such an action appears and F 0 = Pi⇤-1 i=0 f ? i . Then (h?i )i2¶0♦[[i⇤-1] satisfies the assumptions of Claim 5, so we have T [F 0 ] ≥ Pi⇤-1 i=0 h?i > t?i⇤ ≥ t(js) , where the inequalities follow from Claim 5, stability of hi⇤ and the minimality of t(js) , respectively. Then T[F 0 ] + nF 0h(js) is considered in Line 18, implying ˆH  T[F 0 ] + nF 0h(js) . Say nF 0 6= 0: since nF 0 is the smallest integer such that

fulfilling the bound. Otherwise, say nF 0 = 0, implying T[F 0 ] > ∆. By the same argument as Case 1, using Claims 4 and 3, we have T[F 0 ]  (1+ ✏2 )⇣Pi⇤-1 i=0 hi⌘. However, we have Pi⇤-1 i=0 hi  ∆ < H⇤ as otherwise item i⇤ would be unnecessary to reach the goal value. This gives us: ˆH  T [F 0 ]  (1 + "2 ) H⇤ , fulfilling the bounds.

Overall, we have shown that in all cases, the output ˆL contains a stable sequence with total hazing cost ˆH < (1+")H⇤ . (b) Time complexity: Ordering actions by thresholds takes O(n logn) time. Lines 1-8 take O(n) time. The outer loop in Line 9 gets executed O(n) times, each running a constant number of operations plus the inner loop in Line 13, which gets executed at most g = O(1◁"2 ) times with constant time per iteration. Thus, Lines 9-16 take O ( n "2 ) time. Lines 30, 31 take O(n) and O(g) time, respectively. Overall, Algo. 3 takesO (n logn+ n "2 ) time, polynomial in both n and 1" .

6 Experiments

We present the semi-log plots for the runtimes of Algorithms 1-3 in Figure 1. Given the number of actions n and a positive integer Maximum Payoff of Deviation (MPD), we generated a game by (for each action j 2 [n]) uniformly choosing p(j) from ¶i 2 Z : 0  i  30♦ and uniformly choosing p⇤(j) from ¶i 2 Z : p(j)  i  MPD♦. 3 As expected, the runtimes of all algorithms increase with increasing n, and the runtime of FPTAS increases with decreasing ". Similarly, consistent with our runtime analysis, Algorithm 1 (DP) increases with increasing MPD, since MPD and ∆ are positively correlated, whereas the other algorithms do not exhibit such an increase, as their runtimes are independent of the actual payoffs. 4 While the DP consistently outperforms the ILP in the plots, this trend is naturally reversed for high ∆, which we demonstrate by rerunning the same runtime experiment for these algorithms for larger values of MPD. Our results are presented in Figure 2.

3 Imposing p⇤(j) ≥ p(j) ensures ∆ > 0 for each game.

Notice that for n = 30, we see that the ILP (the runtime of which is robust to increases in the payoffs) starts to outperform the DP (the runtime of which steadily increases with increasing MPD) when the MPD reaches approximately 1500. The figure demonstrates the better performance of the ILP in the high ∆ limit, which corresponds to games requiring longer (in terms of the number of rounds) hazing periods before the goal value is reached.

7 FutureWork

As mentioned in Section 5, Algorithm 3 is inspired by the original FPTAS for the unbounded knapsack problem [Ibarra and Kim, 1975]. Since then, faster schemes for the same problem have been developed [Lawler, 1979; Jansen and Kraft, 2018]. It is possible that similar modifications can be made to these algorithms to enable them to solve OptRep, improving the runtime of its FPTAS.

A natural next step following our work is considering asymmetric games and strategies. While some of our results generalize to this setting, there are important differences. For example, goal values must be generalized to goal sequences to maximize payoff (e.g., if (C2↪ C2) from Table 1 instead had payoff (6,6), it would be better to forever alternate between (D↪C2) and (C2↪D)); hence, computing the "optimal goal sequence" is a separate computational problem on its own. A two-variable generalization of Algorithm 1 can compute sequences reaching a goal sequence that maximizes the total payoff, but fails for any other goal sequence. However, since fairness concerns come into play with asymmetric payoffs, maximizing the total payoff may not be sufficient, requiring novel algorithmic techniques.

4 In fact, as seen in Fig.1(top), the runtime for Algo. 3 sometimes decreases with increasing MPD. This is likely because increasing MPD increases the upper bound for the deviation payoffs but not for the cooperation payoffs, resulting in ∆ increasing while h(j) s stay in the same range. Thus, more actions are placed in S and skip the inner loop in Line 13, resulting in less computation by the FPTAS.

Another possible extension is to consider Bayesian games [Harsanyi, 1967], where agents have private information about how they value certain outcomes. In such games, play might differ depending on an agent's type, and we may even have defection and restarting on the path of play in equilibrium. For example, if a small fraction of the population obtains great benefit from deviating in the first round, it may be better to tolerate those few agents repeatedly taking advantage for one round and then finding another partner, than to add significant hazing for the entire population to prevent this. In this context, partial anonymity could also be of interest, for example where one can choose to reveal one's history to a new partner, for example to show that one behaved properly in a previous relationship but the partner unfairly defected.

Acknowledgments

We thank the Cooperative AI Foundation, Polaris Ventures (formerly the Center for Emerging Risk Research), and Jaan Tallinn's donor-advised fund at Founders Pledge for financial support. We are grateful to Matt Rognlie for his valuable contributions to the conceptualization of and preliminary work on this project. We thank Anupam Gupta for his helpful comments on FPTAS literature. Lastly, we thank the members of Foundations of Cooperative AI Lab (FOCAL) for comments and suggestions on earlier drafts of this work.