Game Implementation: What Are the Obstructions?

The strongest honest case is a Class-B mirror: the continuous version is meaningful, genuinely high-multiplicity, and remains hard because the paper’s combinatorics live in strategy selection rather than in the number of agents.

Take a population with two types, \(A\) and \(B\), each of mass \(1/2\). A type is a complete role description: its strategy set and its payoff table. There may be arbitrarily many—or a nonatomic continuum of—agents of each type, all indistinguishable within type. Let \(p\in\Delta(X_A)\) and \(q\in\Delta(X_B)\) describe the fractions of the two populations choosing each strategy. Thus the mass choosing \(x\in X_A\) is \(p_x/2\), and similarly for \(B\).

The base utility of an \(A\)-agent choosing \(x\) is the expected payoff

\[ u_A(x,q)=\sum_{y\in X_B}q_yU_A(x,y), \]

and analogously

\[ u_B(y,p)=\sum_{x\in X_A}p_xU_B(x,y). \]

This is the standard anonymous/random-matching high-multiplicity extension of a two-player normal-form game. The designer chooses finite rational payment tables \(v_A(x,y)\) and \(v_B(x,y)\). At population state \((p,q)\), the corresponding promises are their affine extensions:

\[ V_A(x,q)=\sum_y q_yv_A(x,y),\qquad V_B(y,p)=\sum_x p_xv_B(x,y). \]

The objective is to minimize worst-case expected total payment over population states in which every type uses only an undominated strategy:

\[ \operatorname{cost}(v)= \max_{\substack{p\text{ supported on }X_A^\star\\ q\text{ supported on }X_B^\star}} \left( \frac12\sum_{x,y}p_xq_yv_A(x,y) + \frac12\sum_{x,y}p_xq_yv_B(x,y) \right). \]

Here \(X_A^\star\) and \(X_B^\star\) are the undominated strategies under the modified population utilities. Given desired sets \(O_A\subseteq X_A\) and \(O_B\subseteq X_B\), the problem asks whether there is a payment table with cost at most \(\delta\) such that

\[ X_A^\star\subseteq O_A,\qquad X_B^\star\subseteq O_B. \]

Call this Affine Population GAME IMPLEMENTATION\(_\infty\). A solution is the finite payment table \(v\); the continuum lies in the possible mass distributions \(p,q\), not in an unrepresentable infinite payment object.

This is recognisably the paper’s problem. It does not replace implementation by equilibrium selection, welfare maximization, or a smooth approximation. It keeps the same object—payment promises designed to eliminate undominated strategies—and the same worst-case payment objective. The only change is that many identical agents occupy each of the two roles and their behavior is represented by masses.

My lead anchor is Theorem 3.1: “GAME IMPLEMENTATION is NP-hard, even for two players and zero budget.” This theorem is proved in the paper; the reduction is from X3C, cited there to Schaefer (1978). It transfers directly to the population problem above. For any fixed payment table, the difference between two \(A\)-strategies is affine in \(q\). Therefore one strategy dominates another for every population distribution \(q\) exactly when it dominates it against every pure \(B\)-strategy. The same holds for \(B\). Hence the continuous undominated strategy sets are exactly the finite game’s undominated strategy sets.

The cost also transfers. The population cost is an expectation over pure pairs \((x,y)\), so its maximum is attained at a pure population state. With masses \(1/2,1/2\), it is just one half of the paper’s two-player cost; the zero budget in Theorem 3.1 remains zero. The paper’s large “\(\infty\)” promises can be replaced, as usual, by sufficiently large finite rational payments.

Thus the theorem yields NP-hardness for a society with only two distinct types and arbitrarily many agents per type. The hardness is not coming from population multiplicity at all. It is carried by the exponentially rich choice of strategies and by the combinatorial problem of selecting which desired strategy dominates each undesired one. In the ChoCo trichotomy this is Class B: hardness transfers, rather than dissolving under continuization.

A plausible regime is a large anonymous incentive system with two homogeneous roles—for example, validators and auditors in a blockchain protocol, or two large populations of randomly matched participants. Every validator has the same menu, utilities, and payment parameters; every auditor likewise. The protocol designer wants all undominated actions to lie in an approved set while minimizing the worst-case reward exposure. The paper itself motivates GAME IMPLEMENTATION through blockchain incentives, so this is not an artificial reinterpretation. Here \(N\) can be millions or nonatomic while \(\tau=2\). The mass \(p_x/2\) has direct meaning: the fraction of the role population taking action \(x\).

The second anchor is Theorem 5.1: “EXACT GAME IMPLEMENTATION is NP-hard, even for two players and rectangular desired strategy-profile sets.” This is also proved in the paper, via a reduction from 3-COLORING. The corresponding continuous problem is *Affine Population EXACT GAME IMPLEMENTATION\(_\infty\)*. It has the same instance format and objective, but asks for

\[ X_A^\star=O_A,\qquad X_B^\star=O_B. \]

The two types have identical strategy sets and identical base-game structure, just as the two players do in the theorem; payment promises may remain role-specific, as in the paper. The theorem’s \(\delta=1\) becomes \(\delta=1/2\) under the normalized population masses, an immaterial scaling.

This second mirror matters independently. Exact implementation must both eliminate every undesired strategy and preserve every desired strategy as undominated. Allowing the population to mix does not weaken that requirement: because dominance inequalities are affine in the opponent’s mass distribution, checking all distributions is equivalent to checking the pure states used in the discrete proof. The 3-coloring obstruction therefore survives intact. I would again classify this mirror as Class B.

These two mirrors cover the paper’s main two-player hardness results. I would not claim, without additional work, that Theorem 4.1’s bounded-degree graphical-game hardness automatically transfers to a continuum of locally interacting populations: there the identity of the neighborhood graph is much more delicate. Nor would I claim that Theorem 6.2’s finite-game algorithm immediately gives a polynomial-time continuum algorithm. Those are separate follow-up questions.

The natural next questions are whether population GAME IMPLEMENTATION becomes tractable when both types have a fixed constant number of strategies; whether the hardness of Theorem 4.1 survives in a continuum graphical game with binary actions and a bounded-degree interaction kernel; and how the answer changes if payment promises may be arbitrary nonlinear functions of population distributions rather than affine extensions of finite payment tables.

The weakest point is precisely that affine restriction. The paper allows an arbitrary promise \(V_i(x,y)\) on a named two-player profile, whereas my population model permits its canonical expected-value extension to aggregate behavior. A referee could say that arbitrary nonlinear state-contingent promises define a richer continuous problem. That objection is fair. My defence is that the affine extension is not a tractability trick: it is the natural finite representation of a payment rule in an anonymous random-matching population, and it preserves both dominance and worst-case cost exactly. It gives a real high-multiplicity mirror of the paper’s question, even though it does not claim to represent every possible continuum incentive system.