--- title: "Computing Optimal Equilibria in Repeated Games with Restarts" authors: - "Ratip Emin Berker" - "Vincent Conitzer" doi: "10.24963/ijcai.2024/295" url: "https://ijcai.org/proceedings/2024/295" pdf: "https://ijcai.org/proceedings/2024/0295.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "2669-2677" track: "Main Track" keywords: - "Game Theory and Economic Paradigms: GTEP: Noncooperative games" --- # Computing Optimal Equilibria in Repeated Games with Restarts Ratip Emin Berker, Vincent Conitzer *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 2669-2677. DOI: [10.24963/ijcai.2024/295](https://doi.org/10.24963/ijcai.2024/295) ## 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. ## Full text ## 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: Table 1: Payoffs of a two-player symmetric game (row, column) | | D | C1 | C2 | |----|------|------|------| | D | 4,4 | 11,0 | 14,0 | | C1 | 0,11 | 5,5 | 0,0 | | C2 | 0,14 | 0,0 | 8,8 | 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]. Figure 1: The semi-log plots of runtimes of Algorithms 1,2, and 3 (with " = 0▷3↪ 0▷2↪ and 0▷1). Each data point is averaged over 5000 trials. Top Row: Fixed number of actions (n); x-axis shows Maximum Payoff from Deviation (MPD). Bottom Row: Fixed MPD; x-axis shows n. ![Image](https://ijcai.org/proceedings/2024/fulltext/295/image_000000_6af1db419b2f686c6881af443d9fe66339aca1c7e0143a5583c58abab492e1e7.png) 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. Figure 2: Runtimes of Algorithms 1 and 2 for a fixed number of actions (30) as a function of Maximum Payoff of Deviation (MDP). Each data point is averaged over 5000 trials. ![Image](https://ijcai.org/proceedings/2024/fulltext/295/image_000001_95c4d9d2a0b30f7573f0d49ce64b9ddb8ba609091c50c16e605eeca313006954.png) 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. ## References 1. [Andersen and Conitzer, 2013] Garrett Andersen and Vin- cent Conitzer. Fast equilibrium computation for infinitely repeated games. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, pages 53-59, Bellevue, WA, USA, 2013. 2. [Borgs et al., 2010] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou. The myth of the Folk Theorem. Games and Economic Behavior, 70(1):34-43, 2010. 3. [Conitzer and Oesterheld, 2023] Vincent Conitzer and Cas- par Oesterheld. Foundations of cooperative AI. In Pro- ceedings of the Thirty-Seventh AAAI Conference on Arti- ficial Intelligence, pages 15359-15367, Washington, DC, USA, 2023. 4. [Conitzer and Yokoo, 2010] Vincent Conitzer and Makoto Yokoo. Using mechanism design to prevent false-name manipulations. AI Magazine, 31(4):65-77, 2010. 5. [Dafoe et al., 2021] Allan Dafoe, Yoram Bachrach, Gillian Hadfield, Eric Horvitz, Kate Larson, and Thore Grae- pel. Cooperative AI: machines must learn to find common ground. Nature, 593(7857):33-36, 2021. 6. [Datta, 1996] Saikat Datta. Building trust. Sticerd -theo- retical economics paper series, Suntory and Toyota Inter- national Centres for Economics and Related Disciplines, LSE, 1996. 7. [Fujiwara-Greve and Okuno-Fujiwara, 2009] Takako Fujiwara-Greve and Masahiro Okuno-Fujiwara. Voluntar- ily separable repeated prisoner's dilemma. The Review of Economic Studies, 76(3):993-1021, 2009. 8. [Ghosh and Ray, 1996] Parikshit Ghosh and Debraj Ray. Co- operation in community interaction without information flows. The Review of Economic Studies, 63(3):491-519, 1996. 9. [Harsanyi, 1967] John C. Harsanyi. Games with incomplete information played by "Bayesian" players, i-iii. part i. the basic model. Management Science, 14(3):159-182, 1967. 10. [Ibarra and Kim, 1975] Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM, 22(4):463-468, oct 1975. 11. [Izquierdo et al., 2014] Luis R. Izquierdo, Segismundo S. Izquierdo, and Fernando Vega-Redondo. Leave and let leave: A sufficient condition to explain the evolutionary emergence of cooperation. Journal of Economic Dynam- ics and Control, 46:91-113, 2014. 12. [Jansen and Kraft, 2018] Klaus Jansen and Stefan E.J. Kraft. A faster FPTAS for the unbounded knapsack problem. European Journal of Combinatorics, 68:148-174, 2018. 13. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller. [Kontogiannis and Spirakis, 2008] 14. Spyros C. Kontogiannis and Paul G. Spirakis. Equilibrium points in fear of cor- related threats. In Proceedings of the Fourth Workshop on Internet and Network Economics (WINE), pages 210-221, Shanghai, China, 2008. 15. [Kranton, 1996] Rachel E Kranton. The Formation of Co- operative Relationships. The Journal of Law, Economics, and Organization, 12(1):214-233, April 1996. 16. [Lawler, 1979] Eugene L. Lawler. Fast approximation algo- rithms for knapsack problems. Mathematics of Operations Research, 4(4):339-356, 1979. 17. [Littman and Stone, 2005] Michael L. Littman and Peter Stone. A polynomial-time Nash equilibrium algorithm for repeated games. Decision Support Systems, 39:55-66, 2005. 18. [Lueker, 1975] G.S. Lueker. Two NP-complete problems in nonnegative integer programming. Technical Report 178, Computer Science Laboratory, Princeton University, 1975. 19. [Magazine and Chern, 1984] Michael J. Magazine and Maw-Sheng Chern. A note on approximation schemes for multidimensional knapsack problems. Mathematics of Operations Research, 9(2):244-247, 1984. 20. [Rob and Yang, 2010] Rafael Rob and Huanxing Yang. Long-term relationships as safeguards. Economic Theory, 43(2):143-166, 2010. 21. [Rudin, 1976] Walter Rudin. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976. 22. [Wei, 2019] Dong Wei. A model of trust building with anonymous re-matching. Journal of Economic Behavior & Organization, 158:311-327, 2019. 23. [Wojtczak, 2018] Dominik Wojtczak. On strong NP- completeness of rational problems. In Fedor V. Fomin and Vladimir V. Podolskii, editors, Computer Science -Theory and Applications, pages 308-320, Cham, 2018. Springer International Publishing. 24. [Yokoo et al., 2001] Makoto Yokoo, Yuko Sakurai, and Shi- geo Matsubara. Robust combinatorial auction pro- tocol against false-name bids. Artificial Intelligence, 130(2):167-181, 2001. 25. [Yokoo et al., 2004] Makoto Yokoo, Yuko Sakurai, and Shi- geo Matsubara. The effect of false-name bids in combi- natorial auctions: New fraud in Internet auctions. Games and Economic Behavior, 46(1):174-188, 2004.