d4-conf-sigecom-2003-0005 (d4-conf-sigecom-2003-0005)

Given a finite two-player game \(G=(A_1,A_2,u_1,u_2)\) with rational payoffs, a target set \(D\subseteq A_1\times A_2\), and \(k\ge 0\), consider a unit mass of independent encounters, each retaining the original atomic two-player game. The population has role types \(1\) and \(2\), each of mass \(1/2\). Does there exist a pair of nonnegative bonus tables \(v_i:A_1\times A_2\to\mathbb{R}_{\ge 0}\) such that \(\varnothing\ne ND_1(v)\times ND_2(v)\subseteq D\) and every rational outcome distribution \(\rho\) supported on \(ND_1(v)\times ND_2(v)\) has \(\int (v_1+v_2)\,d\rho\le k\)?

Input: an explicitly tabulated two-player game \(G=(A_1,A_2,u_1,u_2)\) with finite nonempty action sets and payoffs \(u_i:A_1\times A_2\to\mathbb Q\), a nonempty explicitly listed set \(D\subseteq A_1\times A_2\), and a binary integer \(k\ge0\).
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 types are roles \(1,2\), each of mass \(1/2\), so \(\tau=2\).
There is a unit mass of independent encounters, each playing \(G\). A common pair of committed bonus tables \(v_i:A_1\times A_2\to\mathbb R_{\ge0}\) changes encounter payoffs to \(u_i+v_i\).
Let \(ND_i(v)\) be the pure actions not weakly dominated by another pure action in this modified game, testing against every original opponent action once, without iterated deletion. Equal payoff vectors do not dominate each other.
Call the bonuses feasible if \(\varnothing\ne ND_1(v)\times ND_2(v)\subseteq D\) and every probability distribution \(\rho\) with rational entries supported on that product satisfies \(\int(v_1+v_2)\,d\rho\le k\). The distribution may be any joint distribution; cost is total payment per unit encounter mass.
Let \(m=|A_1|+|A_2|\) and \(L\) be the total binary input length; state running times in \(m,\tau,L\).

Is deciding whether feasible bonus tables exist solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

Discrete worst-case-cost implementation is NP-hard for two players. The original hardness proof was erroneous; Chen et al. establish hardness even at zero budget ([original result](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/monderer04a.pdf), [corrected hardness](https://arxiv.org/pdf/2212.00699)).
No separately formulated result for this encounter-mass version was located.

The problem is \(\mathrm{NP}\)-hard, even when \(\tau=2\) and \(k=0\). The encounter-mass cost constraint is exactly the discrete worst-case cost constraint.

1. The undominated product is always nonempty

Fix finite nonnegative bonus tables \(v_1,v_2\). For player \(i\), write \(w_i=u_i+v_i\), and choose an action \(a_i\) maximizing
\(\sum_{b\in A_{-i}}w_i(a_i,b)\).

Such a maximizer exists because the action set is finite and nonempty. If another action weakly dominated \(a_i\), its payoff would be at least as large at every opponent action and strictly larger at one. Its sum would therefore be strictly larger, contradicting maximality.

Consequently, \(ND_i(v)\ne\varnothing\) for both players. In particular, the nonemptiness requirement in the task does not introduce an additional restriction.

2. Encounter-mass cost equals worst-case cost

Let \(S(v)=ND_1(v)\times ND_2(v)\), and define \(c_v(a,b)=v_1(a,b)+v_2(a,b)\). Since \(S(v)\) is finite and nonempty, the number
\(C(v)=\max_{(a,b)\in S(v)}c_v(a,b)\)
exists.

For every permitted rational probability distribution \(\rho\),
\[ \text{ } \]
\(\displaystyle \int(v_1+v_2)\,d\rho =\sum_{(a,b)\in S(v)}\rho(a,b)c_v(a,b) \le C(v)\sum_{(a,b)\in S(v)}\rho(a,b) =C(v).\)

Conversely, choose a pair \((a^\ast,b^\ast)\) attaining this maximum. Its point-mass distribution has entries in \(\{0,1\}\), hence rational entries, and is permitted by the task. Its cost is exactly \(C(v)\).

Thus, for every fixed pair of bonus tables,
\(\displaystyle \left[\text{every permitted }\rho\text{ has cost at most }k\right] \iff \left[\max_{(a,b)\in S(v)}(v_1(a,b)+v_2(a,b))\le k\right]. \)

This equivalence holds for arbitrary real bonuses; it does not require rational bonuses or an approximation argument.

The role masses \(1/2,1/2\) introduce no additional factor: the task explicitly defines cost per unit encounter mass as the integral of the total payment \(v_1+v_2\).

3. The hardness theorem and its hypotheses

The external result used is [Chen et al., Theorem 3.1](https://arxiv.org/pdf/2212.00699): two-player Game Implementation is \(\mathrm{NP}\)-hard at zero budget, with cost measured by the maximum total payment over undominated profiles. Their domination rule compares pure actions against every original opponent action, requiring a weak inequality everywhere and a strict inequality somewhere. Their reduction has payoffs in \(\{0,1,2\}\) and a nonempty rectangular desired set.

The intended payment domain is nonnegative bonuses, as defined in the [original model, Section 2](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/monderer04a.pdf). We use the corrected hardness result, not the original hardness proof.

There is a finite-payment detail in the corrected proof: some forward witnesses are written using \(\infty\). These can be replaced by \(3\). The actions eliminated by those comparisons receive zero bonuses, so their modified payoffs are at most \(2\); a bonus of \(3\) preserves every required strict comparison. Bonuses vanish on the product of the chosen action sets, so eliminating the other actions still gives zero cost. Thus the hardness construction admits finite nonnegative witnesses.

4. Polynomial reduction

Take a zero-budget instance from that hardness construction. Retain its two action sets, payoff tables, and desired set, setting \(D\) equal to that desired set and \(k=0\). Supply the two supported role types, each with mass \(1/2\). Hence \(\tau=2\).

All input requirements hold:

• The game is explicitly tabulated, finite, and has rational payoffs.
• The desired set is nonempty. If supplied through its two rectangular factors, explicitly list their Cartesian product.
• The budget \(0\) has constant binary encoding length.
• The society has exactly two supported types with rational masses.

For any finite nonnegative bonus tables, the domination tests in the source and target problems coincide. By Section 2, their cost tests also coincide. Therefore those tables implement the source desired set at zero worst-case cost if and only if they are feasible for the encounter-mass instance. Taking the existential quantifier over bonus tables preserves this equivalence.

The reduction copies the payoff tables and lists at most \(|A_1||A_2|\le m^2/4\) desired pairs. Including binary action identifiers, its running time is \(O(L+m^2\log(m+1)+\tau)\), where \(L\) is the total explicit encoding length; here \(\tau=2\). In particular, it is polynomial.

Consequently, an algorithm running in \(\operatorname{poly}(m,\tau,L)\) for the stated problem would solve an \(\mathrm{NP}\)-hard problem in polynomial time. Such an algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\). This settles the requested hardness classification; no claim of membership in \(\mathrm{NP}\) is needed.

⟨structured verdict parsed — rendered above⟩

The claimed hardness classification is sound in substance. The cost equivalence is rigorous, and the cited reduction applies to the intended nonnegative-payment model. There is one minor clarification needed concerning the payment domain in the corrected paper.

• Nonemptiness of the undominated product — correct.

All modified payoff entries are finite real numbers. Therefore the sum used to select an action is finite, and a maximizer exists.

Weak domination, under the task’s definition, would strictly increase that sum: every coordinate weakly increases and at least one strictly increases. This contradicts maximality. Equal payoff vectors cause no problem because they do not satisfy the strict inequality requirement.

Thus both undominated action sets, and consequently their Cartesian product, are nonempty. This also covers singleton action sets.

• Equivalence of the two cost constraints — correct.

For fixed bonus tables, the undominated product is finite and nonempty, so the maximum payment exists. Every permitted distribution produces a convex combination of the payments on that product and therefore has cost at most the maximum.

Conversely, a point mass at a maximizing profile is a rational probability distribution. Hence the universal distribution constraint implies the maximum-payment constraint.

The quantifiers are handled correctly: the equivalence holds separately for every fixed pair of bonus tables, including tables with irrational entries. No rationality assumption on payments is introduced.

The statement about role masses is also correct under the task’s explicit definition of cost as total payment per unit encounter mass.

• External hardness theorem — verified, with a minor domain clarification.

Theorem 3.1 establishes two-player, zero-budget hardness. The paper’s domination definition uses all original opponent actions, with weak inequalities everywhere and a strict inequality somewhere. Its construction uses the stated bounded integer payoffs and rectangular desired set. These match the target restrictions. [Chen et al., Sections 2–3](https://arxiv.org/pdf/2212.00699)

Minor issue: the corrected paper formally defines payment promises as functions into \(\mathbb R\), without explicitly imposing nonnegativity there. The prover identifies nonnegative bonuses as the intended domain and cites the original model, which explicitly requires them. However, it should acknowledge this discrepancy instead of leaving the relationship between the two formal definitions implicit. [Chen et al., Section 2](https://arxiv.org/pdf/2212.00699), [Monderer and Tennenholtz, Section 2](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/monderer04a.pdf)

This is expositional rather than blocking: the cited construction’s forward payments are nonnegative, and its reverse argument uses nonnegativity. The minimum clarification is to say explicitly that the theorem is being used in this intended nonnegative-payment formulation.

• Replacing infinite payments — valid.

The cited forward construction uses infinite payments in comparisons against actions receiving zero bonuses. Its required comparisons and zero-cost conclusion are recorded in Claim 3.2 and the following paragraph. [Chen et al., proof of Theorem 3.1](https://arxiv.org/pdf/2212.00699)

The prover’s bound checks out: an eliminated action’s modified payoff is at most \(2\), while an entry receiving bonus \(3\) has modified payoff at least \(3\). Thus the required strict comparisons survive. Entries without infinite payments are unchanged.

The argument needs only to eliminate all actions outside the chosen sets; it does not need to preserve every domination relation among chosen actions. Since payments vanish on their product, further domination within those sets cannot invalidate zero cost.

• Reduction and encoding — correct.

Copying the game preserves every domination comparison. Explicitly listing a rectangular desired set requires at most \(|A_1||A_2|\) pairs. The inequality \(|A_1||A_2|\le m^2/4\) is correct.

The claimed running time is polynomial for the explicit encoding used here. The constant budget and two rational role masses satisfy the input requirements. The construction’s desired factors are nonempty on its nontrivial hardness instances.

The existential equivalence follows from the fixed-table equivalence, with finite forward witnesses supplied by the preceding argument.

• Final complexity conclusion — correct.

Hardness at fixed \(\tau=2\) and \(k=0\) suffices to establish hardness of the full target problem. The conditional exclusion of a polynomial-time algorithm is stated correctly. No membership claim is needed.

⟨structured verdict parsed — rendered above⟩