Answer: \(\mathrm{NP}\)-complete, already for \(\tau=2\) and \(\delta=0\).
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGAME IMPLEMENTATION is NP-hard, even for two players and zero budget. We reduce from the following NP-hard problem (Schaefer 1978): X3C Instance: A set of 3ˆn elements A and a collection of 3ˆn sets C} such that Cj ⊂A and |Cj| = 3 for every j ∈{0, . . . , 3ˆn −1} and every element ai ∈A appears in exactly three sets, i.e., |{C ∈C | ai ∈ C}| = 3. Question: Is there an exact cover of A, i.e., a subcol- lection S ⊂C s.t. |S| = ˆn and A = S C∈S C? Let I = (A = {a0, . . . , a3ˆn−1}, C = {C0, . . . , C3ˆn−1}) be an instance of X3C, where |A| = 3ˆn.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two role types A and B of mass 1/2, finite strategy sets, rational payoff tables, desired sets, and budget delta, decide whether finite rational pairwise payment tables exist such that under random matching and affine expected utilities every globally undominated strategy lies in its desired set and the maximum normalized expected payment over undominated population states is at most delta.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here the support consists of roles \(A,B\), each of mass \(1/2\), so total mass is \(1\) and \(\tau=2\).
Each role has a nonempty finite pure-strategy set \(S_i\) and a nonempty desired subset \(D_i\subseteq S_i\). Input includes arbitrary signed rational payoff tables \(u_A,u_B:S_A\times S_B\to\mathbb Q\) and a binary rational budget \(\delta\ge0\). Let \(m=|S_A|+|S_B|\) and let \(L\) be the total input bit length.
A population state consists of conditional strategy distributions \(p\in\Delta(S_A)\), \(q\in\Delta(S_B)\). Each individual meets one uniformly sampled individual of the opposite role; matching is independent of strategies.
Payments are finite tables \(v_A,v_B:S_A\times S_B\to\mathbb Q_{\ge0}\), with no prescribed upper bound. Modified expected utilities are \(F_A(a;q)=\sum_b q_b(u_A(a,b)+v_A(a,b))\) and \(F_B(b;p)=\sum_a p_a(u_B(a,b)+v_B(a,b))\).
A pure strategy globally dominates another if its modified expected utility is at least the other's at every opposite-role distribution and strictly greater at some such distribution. Only pure strategies may dominate; comparisons use the original full strategy sets, without iterative deletion. Let \(U_A(v),U_B(v)\) be the strategies with no global dominator; ties alone do not constitute domination.
The normalized payment per unit total population mass is \(C_v(p,q)=\tfrac12\sum_{a,b}p_aq_b(v_A(a,b)+v_B(a,b))\). Define \(\operatorname{cost}(v)=\max\{C_v(p,q):\operatorname{supp}(p)\subseteq U_A(v),\operatorname{supp}(q)\subseteq U_B(v)\}\), allowing real population distributions.
The decision problem asks whether such payment tables exist with \(U_A(v)\subseteq D_A\), \(U_B(v)\subseteq D_B\), and \(\operatorname{cost}(v)\le\delta\); desired strategies may themselves be dominated.
Is this continuous decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), with \(\tau=2\) fixed and the budget encoded in \(L\).
Discrete game implementation with pure weak dominance and rectangular desired sets is \(\mathrm{NP}\)-hard even for two players and zero budget ([source](https://arxiv.org/pdf/2212.00699)). No result settling this exact continuous formulation was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete, already for \(\tau=2\) and \(\delta=0\).
The continuous population distributions preserve both the discrete dominance relation and the discrete worst-case cost, up to the factor \(1/2\). Below, I prove this equivalence, address finite rational payments, and give an exact algorithm running in \(2^{O(m\log m)}\operatorname{poly}(m,L)\) time.
Fix finite payment tables and write \(W_i(a,b)=u_i(a,b)+v_i(a,b)\).
Lemma 1. A strategy \(a'\) globally dominates \(a\) for role \(A\) exactly when
\(W_A(a',b)\ge W_A(a,b)\quad\text{for every }b\in S_B,\)
with strict inequality for at least one \(b\).
Proof. Necessity of the weak inequalities follows by testing the opposite-role distributions concentrated on individual strategies.
Conversely, these inequalities imply, for every \(q\in\Delta(S_B)\),
\(F_A(a';q)-F_A(a;q)=\sum_b q_b\bigl(W_A(a',b)-W_A(a,b)\bigr)\ge0.\)
A strict coordinate gives strict inequality at the distribution concentrated on that coordinate. If no coordinate is strict, the expected utilities agree at every distribution. This also establishes necessity of a strict coordinate. The proof for role \(B\) is identical, comparing columns instead of rows. \(\square\)
Thus the dominance relation is precisely pure weak dominance in the corresponding two-player game, with comparisons against the original full strategy sets.
Lemma 2. Each role has an undominated strategy, and every dominated strategy has an undominated dominator.
Proof. Represent each strategy by its finite vector of modified payoffs against all opposite-role pure strategies. Domination means coordinatewise inequality with at least one strict coordinate. It is transitive and strictly increases the sum of coordinates.
Starting from any dominated strategy and repeatedly choosing a dominator therefore visits distinct strategies. Finiteness forces the process to terminate at an undominated strategy. Transitivity makes that terminal strategy a dominator of the original strategy. \(\square\)
Lemma 3. For every finite payment table,
\(\operatorname{cost}(v)=\frac12\max_{a\in U_A(v),\,b\in U_B(v)}\bigl(v_A(a,b)+v_B(a,b)\bigr).\)
Proof. Lemma 2 makes both undominated sets nonempty. For any admissible \(p,q\), the numbers \(p_aq_b\) are nonnegative and sum to one over \(U_A(v)\times U_B(v)\). Hence
\(C_v(p,q)\le\frac12\max_{a\in U_A(v),\,b\in U_B(v)}\bigl(v_A(a,b)+v_B(a,b)\bigr).\)
Equality is attained by concentrating \(p,q\) on a maximizing pair. These distributions are permitted population states. \(\square\)
In particular, when \(\delta=0\), nonnegativity of payments gives
\(v_A(a,b)=v_B(a,b)=0\quad\text{for every }(a,b)\in U_A(v)\times U_B(v).\)
Payments elsewhere remain unrestricted by this cost condition.
This section proves that finite rational payments suffice whenever finite real payments would suffice. It also establishes membership in \(\mathrm{NP}\).
Choose nonempty sets \(K_A\subseteq D_A\) and \(K_B\subseteq D_B\). For every strategy outside these sets, choose a proposed dominator:
\(d_A:S_A\setminus K_A\longrightarrow K_A,\qquad d_B:S_B\setminus K_B\longrightarrow K_B.\)
For these fixed choices, construct a rational linear program with variables \(v_A,v_B,\varepsilon\), maximizing \(\varepsilon\), subject to the following constraints.
First, require nonnegative payments and a bounded margin:
\(v_A(a,b)\ge0,\qquad v_B(a,b)\ge0,\qquad 0\le\varepsilon\le1.\)
For each \(a\in S_A\setminus K_A\), require
\(W_A(d_A(a),b)-W_A(a,b)\ge0\quad\text{for every }b\in S_B,\)
and
\(\sum_{b\in S_B}\bigl(W_A(d_A(a),b)-W_A(a,b)\bigr)\ge\varepsilon.\)
For each \(b\in S_B\setminus K_B\), require
\(W_B(a,d_B(b))-W_B(a,b)\ge0\quad\text{for every }a\in S_A,\)
and
\(\sum_{a\in S_A}\bigl(W_B(a,d_B(b))-W_B(a,b)\bigr)\ge\varepsilon.\)
Finally, impose the budget throughout the chosen rectangle:
\(v_A(a,b)+v_B(a,b)\le2\delta\quad\text{for every }(a,b)\in K_A\times K_B.\)
All these constraints are linear because \(W_i=u_i+v_i\) and the utilities are input constants.
Proposition 4. The instance admits an implementation if and only if some choice of \(K_A,K_B,d_A,d_B\) gives a feasible linear program whose optimal value is positive.
Proof: soundness. Suppose such a program has a solution with \(\varepsilon>0\). Every coordinate difference in a proposed domination comparison is nonnegative, and its sum is positive. Consequently at least one coordinate is strictly positive. Lemma 1 therefore shows that every strategy outside \(K_i\) is dominated. Thus
\(U_A(v)\subseteq K_A\subseteq D_A,\qquad U_B(v)\subseteq K_B\subseteq D_B.\)
The budget constraints hold on the entire chosen rectangle and hence on the actual undominated rectangle. Lemma 3 gives \(\operatorname{cost}(v)\le\delta\).
The chosen sets need not equal the actual undominated sets; this is why no constraints forbidding domination within \(K_i\) are necessary.
Proof: completeness. Suppose an implementation exists, initially allowing finite real payments. Set \(K_i=U_i(v)\). These sets are nonempty by Lemma 2 and lie in \(D_i\). For every strategy outside \(K_i\), Lemma 2 supplies a dominator in \(K_i\); choose it as \(d_i\).
Every resulting coordinate difference is nonnegative, and every domination comparison has a strictly positive sum. There are finitely many such comparisons. Choose \(\varepsilon>0\) no larger than one and no larger than any of these positive sums. If there are no comparisons, choose \(\varepsilon=1\). Lemma 3 supplies the budget constraints. The resulting branch is therefore feasible with positive objective value. \(\square\)
Rationality and computation. Each branch is a rational linear program with \(2|S_A||S_B|+1=O(m^2)\) variables, \(O(m^2)\) constraints, and encoding length polynomial in \(m,L\).
The standard polynomial-time theorem for rational linear programming applies: feasibility and a bounded optimum can be determined exactly, and a rational optimal solution can be produced with polynomial encoding length. Here the objective is bounded by \(0\le\varepsilon\le1\). Consequently, a branch admitting positive real margin also admits a finite rational payment table with positive margin.
This argument preserves the budget exactly, including when it holds with equality; it does not rely on perturbing payments.
A certificate consists of the sets \(K_i\) and maps \(d_i\), requiring \(O(m\log m)\) bits. A verifier constructs the branch and checks whether its optimal value is positive in \(\operatorname{poly}(m,L)\) time. Hence the decision problem belongs to \(\mathrm{NP}\).
Use the supplied discrete hardness theorem: two-player game implementation under pure weak dominance is \(\mathrm{NP}\)-hard at zero budget, with rectangular desired sets. Its construction has nonempty desired sets and utilities in \(\{0,1,2\}\). See [Chen et al., Theorem 3.1](https://arxiv.org/pdf/2212.00699).
There is one finite-payment detail to address. That proof writes some completeness payments as \(\infty\), with all remaining payments zero. Such notation can be eliminated: replace each formerly infinite modified utility by \(M=3\), assigning payment \(3-u_i(a,b)\) there. Leave zero-payment entries unchanged.
Originally, each modified utility was either a value in \(\{0,1,2\}\) or \(\infty\). The replacement preserves every equality, weak inequality, and strict inequality between corresponding payoff coordinates: finite values stay unchanged, infinite values become the same value \(3\), and \(3\) exceeds every finite value. Thus all dominance relations and undominated sets are preserved. Since the original promises vanish on the undominated rectangle, the replacement still costs zero. All replacement payments are finite nonnegative integers.
Now transform a discrete instance with budget \(\beta\) into the society instance as follows:
For any finite payment tables, Lemma 1 identifies the discrete and population undominated sets exactly. Lemma 3 gives
\(\operatorname{cost}_{\mathrm{population}}(v)=\tfrac12\operatorname{cost}_{\mathrm{discrete}}(v).\)
Because both undominated sets are nonempty, the discrete rectangular requirement
\(U_A(v)\times U_B(v)\subseteq D_A\times D_B\)
is equivalent to the two requirements \(U_A(v)\subseteq D_A\) and \(U_B(v)\subseteq D_B\).
Thus a rational population implementation yields a discrete implementation with the corresponding budget. Conversely, a finite real discrete implementation yields a population implementation over the reals, and Proposition 4 supplies finite rational payments satisfying the same population budget.
This is a polynomial-time many-one reduction. In the hard instances, \(\beta=\delta=0\), so budget scaling introduces no additional issue. The reduction fixes \(\tau=2\). Therefore the population problem is \(\mathrm{NP}\)-hard; together with Section 3, it is \(\mathrm{NP}\)-complete.
For the exact algorithm, enumerate the sets and maps in Section 3. There are at most \(2^m\) choices of the sets and at most \(m^m\) choices of the maps. Each branch takes \(\operatorname{poly}(m,L)\) time to check. Hence the total running time is
\(2^m m^m\operatorname{poly}(m,L)=2^{O(m\log m)}\operatorname{poly}(m,L),\qquad \tau=2.\)
The certificate verifier runs in \(\operatorname{poly}(m,L)\) time. Both bounds use the binary encoding of \(\delta\) included in \(L\), with no dependence on its numerical magnitude.
Unless \(\mathrm P=\mathrm{NP}\), there is no polynomial-time algorithm in \(m,L\), and no algorithm of the form \(f(\tau)\operatorname{poly}(m,L)\): hardness already holds at the fixed support size \(\tau=2\).
⟨structured verdict parsed — rendered above⟩
The output resolves the intended problem: its argument establishes \(\mathrm{NP}\)-completeness for fixed \(\tau=2\), already at \(\delta=0\). I found one minor clarification needed concerning the payment domain of the imported discrete result. The internal dominance, cost, and LP arguments are sound.
Testing distributions concentrated on individual opposite-role strategies establishes every coordinatewise weak inequality. Conversely, their nonnegative weighted sum establishes the required inequality at every distribution.
Strictness is handled correctly: a strict coordinate supplies a distribution witnessing strict improvement, and equality at every coordinate precludes strict improvement anywhere. The column comparison for role \(B\) has the same justification.
This uses the full original strategy sets and pure dominators, exactly as required.
For finite real payoff vectors, coordinatewise domination with at least one strict coordinate is transitive and strictly increases the coordinate sum. Therefore a domination chain cannot revisit a strategy.
Finiteness and nonemptiness of each strategy set ensure termination at an undominated strategy. Transitivity establishes that the terminal strategy dominates the original one. Identical payoff vectors cause no difficulty: ties do not create domination.
Both undominated sets are nonempty by Lemma 2. For admissible distributions, the products \(p_aq_b\) form nonnegative weights summing to one on their rectangle. Consequently the expected payment cannot exceed its largest entry.
Concentrating both distributions on a maximizing pair attains that entry, including the normalization factor \(1/2\). Thus the stated maximum is exact; allowing real distributions introduces no additional worst-case cost.
At \(\delta=0\), nonnegative payments indeed force both payment entries to vanish at every undominated profile. This places no constraint on payments outside that rectangle.
In soundness, each proposed domination comparison has nonnegative coordinate differences and a positive sum when \(\varepsilon>0\). Hence it has a strict coordinate, as required by Lemma 1. Every strategy outside \(K_i\) is therefore dominated.
No assumption that strategies within \(K_i\) remain undominated is necessary. The actual undominated rectangle is contained in \(K_A\times K_B\), where the imposed budget inequalities suffice.
In completeness, choosing \(K_i=U_i(v)\) is legitimate: these sets are nonempty and desired. Lemma 2 supplies each proposed dominator in \(K_i\). The minimum of finitely many positive comparison sums supplies a positive common margin. The explicitly treated case of no comparisons is also correct.
Signed original utilities do not affect these arguments. The payment variables themselves remain constrained to be nonnegative.
Each branch has \(O(m^2)\) variables and constraints. Forming the sums of input rationals preserves polynomial encoding length.
The rational LP theorem invoked is sufficiently specified for this use: feasibility and bounded optimization admit exact polynomial-time computation and polynomial-length rational solutions. Its hypotheses hold because the constraints are rational and the objective satisfies \(0\le\varepsilon\le1\). Unbounded payment variables do not make the objective unbounded.
Consequently, a positive feasible real margin yields rational payments satisfying the same budget exactly. No approximation or perturbation is required.
The guessed sets and maps have \(O(m\log m)\) encoding length. A deterministic polynomial-time LP computation is a valid certificate verifier; the certificate need not itself contain the payments. Thus the \(\mathrm{NP}\) claim follows.
The cited theorem concerns two players, zero budget, pure weak dominance, and rectangular desired profiles. Its construction uses utilities in \(\{0,1,2\}\), and its completeness payments use zero and infinity. These are the source properties needed here. [Chen et al., Sections 2–3](https://arxiv.org/pdf/2212.00699).
Replacing every infinite modified utility by \(3\) preserves all coordinate comparisons: finite values remain below \(3\), and formerly infinite values remain tied with each other. The payments \(3-u_i(a,b)\) are finite nonnegative integers. Preserving the undominated sets and leaving their zero-payment rectangle unchanged preserves zero cost.
The factor \(1/2\), rectangular-set equivalence, and fixed support size are all correct. Nonemptiness of both undominated sets is essential to the rectangular-set equivalence and has already been proved.
Minor issue: the source’s preliminary definition permits real-valued promises without explicitly imposing nonnegativity, although its zero-budget hardness proof uses nonnegativity. The prover should explicitly restrict its discrete equivalence and imported hardness statement to the intended nonnegative-payment formulation. [Chen et al., Section 2 and proof of Theorem 3.1](https://arxiv.org/pdf/2212.00699).
This is a domain clarification rather than a missing hardness argument: the task supplies the intended discrete hardness premise, and the cited construction and its zero-budget soundness reasoning apply to nonnegative payments. An unrestricted equivalence with signed discrete promises should not be claimed.
The bounds \(2^m\) for the sets and \(m^m\) for the maps are valid upper bounds, including branches with empty map domains. Checking each branch takes \(\operatorname{poly}(m,L)\) time.
The resulting bound
\(2^{O(m\log m)}\operatorname{poly}(m,L)\), with \(\tau=2\), is justified. Exact LP computation incorporates the binary budget encoding in \(L\), without dependence on the budget’s numerical magnitude.
Hardness at fixed \(\tau=2\) also justifies the stated exclusions of polynomial-time and \(f(\tau)\operatorname{poly}(m,L)\) algorithms, conditional on \(\mathrm P\ne\mathrm{NP}\).
The minimum feedback is to add an explicit nonnegative-payment qualification to Section 4’s discrete theorem and equivalence statements. No additional mathematical construction is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.