| paper | Computing Optimal Equilibria in Repeated Games with Restarts |
| authors | Ratip Emin Berker, Vincent Conitzer |
| venue | IJCAI 2024 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 1
statement extracted from the paper’s text layer
Given a finite action set \(A\), finite type set \(\Theta\), rational masses \(\mu_\theta\ge 0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), rational type payoff tables \(p_\theta(a),p_\theta^*(a)\), and a common goal action \(g\) satisfying \(p_\theta(g)\ge p_\theta(a)\), define \(h_\theta(a)=p_\theta(g)-p_\theta(a)\), \(t_\theta(a)=p_\theta^*(a)-p_\theta(g)\), and \(\Delta_\theta=p_\theta^*(g)-p_\theta(g)\). Find a finite hazing sequence \(S=(a_0,\ldots,a_{\ell-1},g,g,\ldots)\) minimizing \(\mathcal H_\mu(S)=\sum_{\theta}\mu_\theta\sum_{i=0}^{\ell-1}h_\theta(a_i)\), subject for every \(\theta\) with \(\mu_\theta>0\) to \(\sum_{i=0}^{k-1}h_\theta(a_i)>t_\theta(a_k)\) for every \(k<\ell\) and \(\sum_{i=0}^{\ell-1}h_\theta(a_i)>\Delta_\theta\); the decision version asks whether \(\mathcal H_\mu(S)\le B\).
A high-multiplicity anonymous-rematching market with clone types \(\theta\), masses \(\mu_\theta\), type-conditioned cooperative and deviation payoffs, one public finite hazing sequence followed by perpetual cooperation, unilateral typewise restart constraints, and population-average hazing as the objective.
The opponent's strongest point is that the paper's actual input contains no population counts and, in the proposed model, \(\mu\) changes only the objective while feasibility is imposed typewise; making partner composition determine \(p_\theta\) would require a new matching kernel and a richer Bayesian repeated game.
fatal: False
The mirror carries Theorem 1 and Corollary 1 as inherited hardness on the \(|\Theta|=1\) subproblem; it recovers Theorems 2–4 only on that same degenerate slice and leaves the heterogeneous complexity open.
I would make a qualified but genuine positive case, led by the paper’s Theorem 1, strengthened by Corollary 1.
The mirror is a population version of the anonymous rematching model. Let \(\Theta\) be a finite set of agent types, with rational masses \(\mu_\theta\) summing to \(1\). A type is a complete payoff and information profile: for every action \(a\), it specifies the expected cooperative payoff \(p_\theta(a)\) and the best permitted one-shot deviation payoff \(p_\theta^*(a)\). These may already incorporate the distribution of partners encountered under anonymous rematching. Thus agents of the same type are genuine clones.
Assume there is a common cooperative action \(g\) satisfying \(p_\theta(g)\ge p_\theta(a)\) for every type and action. A public restart plan is a finite hazing sequence followed by perpetual cooperation, \(S=(a_0,\ldots,a_{\ell-1},g,g,\ldots)\). Every agent follows this sequence; after a deviation, the relationship ends and the deviator starts the sequence again with a fresh anonymous partner.
Define \(h_\theta(a)=p_\theta(g)-p_\theta(a)\), \(t_\theta(a)=p_\theta^*(a)-p_\theta(g)\), and \(\Delta_\theta=p_\theta^*(g)-p_\theta(g)\). The plan is stable in the \(\beta\to1\) limit if, for every positive-mass type \(\theta\), every hazing position \(k<\ell\) satisfies \(\sum_{i<k}h_\theta(a_i)>t_\theta(a_k)\), and the complete hazing satisfies \(\sum_{i<\ell}h_\theta(a_i)>\Delta_\theta\). Its social cost is the population-average hazing \(\mathcal H_\mu(S)=\sum_{\theta}\mu_\theta\sum_{i<\ell}h_\theta(a_i)\).
This gives the following precise problem.
Lead problem: Continuum-OptRep. The input consists of \(A\), \(\Theta\), rational masses \(\mu_\theta\), rational payoff tables \(p_\theta,p_\theta^*\), and a designated common goal action \(g\). Find a finite sequence \((a_0,\ldots,a_{\ell-1})\) minimizing \(\mathcal H_\mu(S)\), subject to the typewise strict stability inequalities above. Its decision version asks whether a stable plan of cost at most \(B\) exists.
This is an author-recognizable extension rather than a literal restatement. It preserves the paper’s central objects: anonymous rematching, unilateral deviation, restarting, a common public action sequence, hazing costs, and social optimization. It only replaces one payoff profile by a high-multiplicity distribution of clone profiles. The scenario is plausible for a large marketplace of autonomous trading, employment, or contracting agents: millions of agents but perhaps tens of behavioural/payoff types, all using the same public onboarding or trust-building protocol.
The rational-clone test also works cleanly. If \(\mu_\theta=N_\theta/N\), then \(N_\theta\) named agents can be replaced by \(N_\theta\) clones of type \(\theta\). Multiplying \(\mathcal H_\mu\) by \(N\) gives total hazing, while the stability inequalities remain exactly the individual incentive constraints. The continuum does not replace an individual deviation by a coalition: in an atomless population, a deviator has zero effect on the partner distribution, which is precisely why the restart calculation remains meaningful.
The anchor is Theorem 1, proved in this paper: “OptRep is (weakly) NP-hard, and the corresponding decision problem is NP-complete.” In the one-type slice, set \(\mu_{\theta}=1\), \(h_\theta=h\), \(t_\theta=t\), and \(\Delta_\theta=\Delta\). Continuum-OptRep then becomes exactly the paper’s Definition 3, OptRep. Therefore Theorem 1 transfers immediately. The paper’s Corollary 1, also proved here using Wojtczak’s cited strong-NP-completeness result, gives the stronger statement for rational inputs: the corresponding continuous problem is strongly NP-hard, with a strongly NP-complete decision version.
I would classify this as Class B: hardness transfers, not continuum-specific hardness. The reduction already works with one population type, so the difficulty is not caused by population multiplicity. That is still a valuable mirror: it identifies a problem whose repeated-game combinatorics survive continuization. On the one-type slice, the paper’s Theorems 2 and 3 and its Theorem 4 also carry over verbatim: pseudo-polynomial exact algorithms and the FPTAS remain available. I would not claim those algorithms automatically solve the full multi-type problem, because simultaneous typewise stability constraints create a genuinely new multi-criteria optimization question.
The full problem generates worthwhile follow-ups: is it fixed-parameter tractable in \(|\Theta|\)? Does the FPTAS survive for boundedly many types? Can population-weighted stability replace universal stability without changing the equilibrium interpretation? What happens when types have different cooperative goal actions, or when a player observes a partner’s type before deviating? Those are natural extensions of the paper’s Section 7 discussion of Bayesian games and heterogeneous agents, rather than arbitrary relaxations.
The weakest point is that the theorem-level hardness transfer can be dismissed as population-cosmetic: the reduction uses \(|\Theta|=1\), so \(\mu\) does no computational work. Moreover, the multi-type model is an extension of the paper’s symmetric single-game setting, and the common-goal assumption is restrictive. Still, the objection does not eliminate the mirror. The paper itself starts from anonymous populations and explicitly identifies multiple agent types as future work; the proposed model preserves its strategic semantics while making the population a genuine continuous object. At minimum, it supplies a faithful high-multiplicity continuation of the paper’s central computational problem and a clear boundary between inherited hardness and the open complexity caused by heterogeneous population structure.
The proponent’s transfer is formally correct but programme-irrelevant. Setting \(|\Theta|=1\) makes Continuum-OptRep exactly OptRep, yet this does not produce a continuous population problem. The paper’s computational input is already an aggregate two-player game, \(G=\{(p(j),p^*(j))\}_{j=1}^n\); it contains no \(N\) agents, individual records, matching capacities, or population state. Cloning a type \(N\) times therefore changes nothing. Clearing denominators merely decorates an already compressed game with a population interpretation.
The same defeats Theorem 1 and Corollary 1. Their hardness survives because the population variable disappears, not because a high-multiplicity problem embeds into the continuous one. Theorem 2, Theorem 3, and Theorem 4 likewise carry over only on the singleton-type slice. They provide no algorithmic or structural result about a society whose mass distribution matters.
In the proposed multi-type formulation, \(\mu\) does not enter feasibility at all. Every positive-mass type must satisfy its own incentive constraints, regardless of whether its mass is \(0.5\) or \(10^{-12}\); \(\mu\) only supplies weights in the objective
\[
\mathcal H_\mu(S)=\sum_i\sum_\theta \mu_\theta h_\theta(a_i).
\]
Thus the population has no effect on equilibrium, rematching, or the available sequences. It is merely a coefficient in a weighted finite optimization problem. Allowing a type of zero mass to escape the constraints also creates a discontinuous convention rather than a meaningful atomless limit.
A better model exposes the problem. In a genuinely heterogeneous anonymous market, payoffs should be indexed by both player and partner types, such as \(p_{\theta,\phi}(a)\) and \(p^*_{\theta,\phi}(a)\), together with a matching kernel determined by \(\mu\). Then restart values, deviation gains, and possibly the prescribed policy depend on partner composition and history. Retaining the paper’s common public sequence suppresses precisely that heterogeneity and returns to a weighted payoff-table problem. Allowing type-contingent sequences or history-dependent disclosure instead creates a new Bayesian repeated-matching problem, not a continuization of OptRep.
The proposed social objective is also an added modelling choice. The paper can equate individual and social optimality because the game is symmetric. With heterogeneous types, minimizing population-average hazing may sacrifice some types and need not represent the paper’s notion of an optimal equilibrium. Replacing it by Pareto, typewise, or coalition-based stability would each define a different equilibrium-design problem; positive-mass deviations would no longer be the paper’s unilateral Nash deviations.
The rational-clone argument therefore passes only the weakest fidelity test. It shows that one may replicate the proposed types by named clones, but it does not show that the paper’s discrete problem has a high-multiplicity regime whose compression is useful. The only faithful mirror is population-cosmetic; the version in which population composition genuinely matters is a new heterogeneous repeated-game programme whose computational questions are not supplied by the paper’s theorems.
That is the strongest defensible negative case. It is not an airtight proof that no worthwhile typed matching model could ever be studied; such a model is plausible. But the proponent has established at most a promising re-modelling direction, not a worthwhile continuous mirror of this paper’s named computational results.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.