Answer: An M-PCE is exactly computable in time \(\operatorname{poly}(m,\tau,L)\), with algebraic strategy coordinates represented by integer polynomials and rational isolating intervals.
Theorem 11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a two-player game G = ({1, 2}, A, u), we can compute an M-PCE in polynomial time. 5.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two finite action sets and a finite support of member types \(t\), each assigned to side \(i(t)\in\{1,2\}\), with rational mass \(\mu_t\) and rational utility table \(r_t(a_1,a_2)\), let \(q_i=\sum_{t:i(t)=i}\mu_t>0\) and \(U_i^\mu(a_1,a_2)=q_i^{-1}\sum_{t:i(t)=i}\mu_t r_t(a_1,a_2)\). Compute mixed strategies \(x,y\) forming an M-PCE of the induced two-player game; equivalently, maximize \(\alpha\) subject to \(U_i^\mu(x,y)\ge \mathrm{BU}_i^\mu+\alpha\) for both \(i\), where \(\mathrm{BU}_i^\mu\) is the paper’s best-response benchmark in the induced game.
Let \(A_1,A_2\) be nonempty finite action sets and \(m=|A_1|+|A_2|\). A society is given by its support: the list of its \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has a side \(i(t)\in\{1,2\}\) and an explicitly listed utility table \(r_t:A_1\times A_2\to\mathbb Q\), with either sign allowed. Both sides have positive mass \(q_i=\sum_{t:i(t)=i}\mu_t\). Let \(L\) be the total binary input length.
Define \(U_i^\mu(a_1,a_2)=q_i^{-1}\sum_{t:i(t)=i}\mu_t r_t(a_1,a_2)\), extended to independently mixed strategies by expectation. Each side chooses one strategy in \(S_i=\Delta(A_i)\); there are no side payments.
For \(j\ne i\), define \(\mathrm{BR}_j^\mu(s_i)=\operatorname*{arg\,max}_{s_j\in S_j}U_j^\mu(s_i,s_j)\) and \(\mathrm{BU}_i^\mu=\sup\{U_i^\mu(s_i,s_j):s_i\in S_i,\ s_j\in\mathrm{BR}_j^\mu(s_i)\}\). All best responses, including ties, enter this supremum.
An M-PCE is a pair \((x,y)\in S_1\times S_2\) attaining the largest \(\alpha\in\mathbb R\) for which \(U_i^\mu(x,y)\ge\mathrm{BU}_i^\mu+\alpha\) for both sides. Exact strategy coordinates may be real algebraic numbers, represented by integer polynomials and rational isolating intervals.
Can an M-PCE of this mass society be computed in polynomial time in \(m,\tau,L\), or is this computation NP-hard?
For explicitly represented finite two-player normal-form games, computing an M-PCE is known to admit a polynomial-time algorithm ([Rong–Halpern](https://www.cs.cornell.edu/home/halpern/papers/Cooperative.pdf)); the [expanded treatment](https://www.cs.cornell.edu/~rongnan/publications/ce_journal.pdf) also states this result.
No separate complexity result for the support-and-mass input model was verified.
An M-PCE can be computed exactly in time polynomial in \(m,\tau,L\), with strategy coordinates represented by integer polynomials and rational isolating intervals.
The support-and-mass representation can be converted into an explicitly represented two-player game of polynomial binary length. I prove this reduction and give an exact algorithm, including the bit-complexity justification.
Write \(n_i=|A_i|\). Define two rational payoff matrices by
\(M_i(a,b)=\dfrac{\sum_{t:i(t)=i}\mu_t r_t(a,b)}{\sum_{t:i(t)=i}\mu_t}\), for \(i\in\{1,2\}\).
The denominators are positive by the hypothesis \(q_i>0\). Let \(G_\mu\) be the two-player normal-form game with action sets \(A_1,A_2\) and payoff matrices \(M_1,M_2\).
For every independently mixed profile \((x,y)\),
\(x^{\mathsf T}M_i y=\sum_{a,b}x_a y_b\,q_i^{-1}\sum_{t:i(t)=i}\mu_t r_t(a,b)=U_i^\mu(x,y)\).
Consequently, the society and \(G_\mu\) have exactly the same strategy spaces and expected utilities. In particular:
This identification uses the specified premise that each side chooses one distribution over its action set.
Each numerator is a sum of at most \(\tau\) products of input rationals. For any such sum, use the product of the constituent denominators as a common denominator. Its binary length is at most the sum of their binary lengths. The resulting numerator has polynomial binary length as well: adding at most \(\tau\) integers increases the maximum summand length by at most \(\lceil\log_2\tau\rceil\).
The same reasoning applies to \(q_i\). Dividing by a positive rational \(q_i\) preserves polynomial binary length, even when \(q_i\) is numerically very small.
Thus all intermediate rationals and all entries of \(M_1,M_2\) have polynomial binary length. There are \(2n_1n_2\) entries, and their construction uses \(O(\tau n_1n_2)\) rational arithmetic operations. The aggregate game therefore has polynomial description length and is constructible in \(\operatorname{poly}(m,\tau,L)\) bit operations.
For this section, write \(U_i(x,y)=x^{\mathsf T}M_i y\).
Fix \(x\), and define the pure best-response set of side \(2\) by
\(B_2(x)=\operatorname*{arg\,max}_{b\in A_2}x^{\mathsf T}M_2 e_b\).
A mixed strategy \(y\) is a best response to \(x\) exactly when its support lies in \(B_2(x)\). Indeed, its payoff is an average of pure-action payoffs; this average attains their maximum exactly when every action receiving positive probability attains that maximum.
It follows that
\(\max_{y\in\mathrm{BR}_2(x)}U_1(x,y)=\max_{b\in B_2(x)}x^{\mathsf T}M_1e_b\).
For each \(b\in A_2\), solve the rational linear program
\(\text{maximize }x^{\mathsf T}M_1e_b\),
subject to
\(x\ge 0,\quad \sum_{a\in A_1}x_a=1,\quad x^{\mathsf T}M_2e_b\ge x^{\mathsf T}M_2e_c\quad\text{for every }c\in A_2\).
Ignore infeasible programs. Every feasible region is compact, so its optimum is attained. The maximum of their optimal values is exactly \(\mathrm{BU}_1\): the constraints assert that \(b\) is a best response, and the preceding identity shows that allowing mixed best responses cannot improve the benchmark beyond a pure best response.
At least one program is feasible, because every \(x\) has a pure best response.
Interchanging the sides gives \(\mathrm{BU}_2\). Explicitly, for each \(a\in A_1\), maximize \(e_a^{\mathsf T}M_2y\) over \(y\in\Delta(A_2)\), subject to
\(e_a^{\mathsf T}M_1y\ge e_c^{\mathsf T}M_1y\quad\text{for every }c\in A_1\).
Rational linear programming computes these optimal values exactly in polynomial bit time. Their binary lengths are polynomial: an optimal value can be obtained at a rational vertex, whose coordinates have polynomial binary length by the determinant bounds for rational linear systems.
Set \(\beta_i=\mathrm{BU}_i\). Both benchmarks are therefore exactly computable rationals of polynomial binary length.
Define
\(F(x,y)=\min\{U_1(x,y)-\beta_1,\ U_2(x,y)-\beta_2\}\).
This function is continuous on the nonempty compact set \(\Delta(A_1)\times\Delta(A_2)\). Hence its maximum \(\alpha^\ast\) is attained, and its maximizers are exactly the M-PCEs.
We next prove the support bound needed for efficient exact optimization.
Lemma. For every profile \((x,y)\), there is a profile \((\widehat x,\widehat y)\) such that both strategies have support size at most two and
\(U_i(\widehat x,\widehat y)\ge U_i(x,y)\quad\text{for }i\in\{1,2\}\).
Proof. Hold \(y\) fixed and maximize \(U_1(z,y)\) subject to
\(z\in\Delta(A_1),\qquad U_2(z,y)\ge U_2(x,y)\).
The feasible set is a nonempty compact polytope, since it contains \(x\). Choose an optimal vertex \(\widehat x\).
Every vertex of this polytope has at most two positive coordinates. To prove this, suppose a feasible point \(z\) has at least three positive coordinates. There is a nonzero vector \(h\), supported on those coordinates, satisfying the two homogeneous equations
\(\sum_a h_a=0,\qquad U_2(h,y)=0\).
Such a vector exists because there are at least three unknowns and at most two independent linear equations. For sufficiently small \(\varepsilon>0\), both \(z+\varepsilon h\) and \(z-\varepsilon h\) remain nonnegative. They preserve normalization and \(U_2(z,y)\), so both are feasible. They are distinct and have midpoint \(z\); therefore \(z\) is not a vertex.
Thus \(\widehat x\) has support size at most two, and
\(U_1(\widehat x,y)\ge U_1(x,y),\qquad U_2(\widehat x,y)\ge U_2(x,y)\).
Now hold \(\widehat x\) fixed and maximize \(U_2(\widehat x,w)\) subject to
\(w\in\Delta(A_2),\qquad U_1(\widehat x,w)\ge U_1(\widehat x,y)\).
The identical vertex argument gives an optimal \(\widehat y\) of support size at most two. Both utilities weakly increase again, proving the lemma. \(\square\)
Applying the lemma to a maximizer of \(F\) produces another maximizer with both supports of size at most two, since \(F\) is nondecreasing in each utility.
Enumerate all nonempty subsets \(I\subseteq A_1\) and \(J\subseteq A_2\) with \(|I|,|J|\le 2\). Their number is
\(\bigl(n_1+\binom{n_1}{2}\bigr)\bigl(n_2+\binom{n_2}{2}\bigr)=O(m^4)\).
For a two-action support, represent its strategy by probabilities \(p,1-p\), or \(q,1-q\), respectively. For a singleton support, let its strategy be constant, independent of the corresponding parameter.
On each support pair, define the two surplus polynomials
\(g_i(p,q)=U_i(x(p),y(q))-\beta_i\).
Each has the form
\(g_i(p,q)=a_i pq+b_i p+c_i q+d_i\),
with rational coefficients of polynomial binary length. The restricted problem is to maximize \(\min\{g_1(p,q),g_2(p,q)\}\) over \(p,q\in[0,1]\).
Use the standard fixed-dimension real-algebraic algorithmic fact: for fixed numbers of variables, input polynomials, and polynomial degrees, quantifier elimination and algebraic sampling take polynomial time in the binary coefficient length. They can produce an algebraic sample point from any nonempty set specified by such a first-order formula. Quantifier-elimination and sampling bounds underlying this fact are given in [Basu’s treatment of algorithms in real algebraic geometry](https://arxiv.org/pdf/1409.1534), particularly Theorems 2.16 and 2.27.
Here the optimizer set is specified by the following formula in free variables \(p,q,z\):
\(0\le p\le1,\quad 0\le q\le1,\quad z\le g_1(p,q),\quad z\le g_2(p,q)\),
together with
\(\forall p',q'\ \bigl[(0\le p'\le1\ \land\ 0\le q'\le1)\Rightarrow(g_1(p',q')\le z\ \lor\ g_2(p',q')\le z)\bigr]\).
The first part states that the current profile achieves surplus at least \(z\). The universally quantified part states that every profile on these supports has minimum surplus at most \(z\). Thus the formula describes exactly the restricted optimizers and their optimal value.
All hypotheses of the algorithmic fact hold:
Consequently, each support pair yields an exact algebraic optimizer in polynomial bit time. The coordinates have bounded algebraic degree and polynomial coefficient length, and can be represented by integer polynomials and rational isolating intervals. Exact comparison of the resulting optimal values also takes polynomial time, using real-root isolation and sign determination for bounded-degree algebraic numbers.
Choose a support pair with the largest restricted optimum and output its strategies, with zero probabilities outside those supports. Section 3 proves that this profile is a global M-PCE.
Aggregation, benchmark computation, and all \(O(m^4)\) restricted optimizations take \(\operatorname{poly}(m,\tau,L)\) bit operations. The output has polynomial length in the requested algebraic representation.
This proves the polynomial-time result for the stated support-and-mass model. It also agrees with [Rong–Halpern, Theorem 5.5](https://www.cs.cornell.edu/~rongnan/publications/ce_journal.pdf), which establishes polynomial-time M-PCE computation for explicitly represented two-player games. No enumeration of unlisted types or expansion of rational masses into individuals is required.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time exact computation of an M-PCE, with one minor gap in documenting the algebraic sampling and output-representation guarantees. I found no false mathematical step or substantive obstruction.
The matrices \(M_i\) are well-defined because \(q_i>0\). The displayed expected-utility identity is correct: all sums are finite, and independent mixing gives the weights \(x_a y_b\).
Equality of utilities on every profile, together with identical strategy spaces, preserves best-response sets, both benchmarks, and the inequalities defining feasible values of \(\alpha\). This includes all best-response ties. Thus an M-PCE of the aggregate game is precisely an M-PCE of the society.
The reduction respects the support input model: it processes only listed types and never expands masses into individuals.
Finding: Correct.
The rational-arithmetic bounds are sound.
There are \(2n_1n_2\) output entries. The asserted \(O(\tau n_1n_2)\) arithmetic-operation bound is valid, and all operands have polynomial binary length. Consequently, the construction has polynomial bit complexity.
Negative utilities introduce no difficulty.
Finding: Correct.
For fixed \(x\), a mixed response maximizes side \(2\)'s utility exactly when every action assigned positive probability maximizes its pure-action utility. The averaging argument establishes both directions, including ties.
Side \(1\)'s utility is also linear in that response. Its maximum over the best-response simplex therefore equals the maximum over its pure best-response actions. This justifies the reduction to one LP for each \(b\in A_2\).
Each LP has exactly the required constraints: they permit \(b\) whenever it is a best response, without imposing unique optimality. Feasible regions are closed subsets of a simplex and hence compact. At least one is nonempty. Their finite maximum therefore equals the original supremum and shows that it is attained.
The side-swapped LPs correctly use side \(1\)'s utility for the best-response constraints and side \(2\)'s utility for the objective.
Exact rational LP optimization applies: dimensions and coefficient lengths are polynomial, and feasible objectives are bounded. The vertex and determinant argument correctly establishes polynomial binary length of the optimal values.
Finding: Correct.
The function \(F\) is continuous on a nonempty compact product of simplices, so its maximum exists. Its maximizers are exactly the profiles attaining the largest feasible \(\alpha\).
The support lemma is valid:
This argument also covers dependent constraint equations, inactive utility constraints, and singleton action sets. Both utilities weakly increase throughout, so applying the lemma to a global maximizer preserves global optimality.
Finding: Correct.
The support count is correct and is \(O(m^4)\). Including singleton supports handles \(n_i=1\). Allowing probabilities at the endpoints also permits strategies whose actual support is smaller than the enumerated subset.
Substitution into the bilinear utilities yields precisely the stated polynomial form, with polynomial coefficient length.
The optimizer formula is logically correct. Its first part says the chosen profile has minimum surplus at least \(z\). Its universal part says every profile has minimum surplus at most \(z\), because
\[
\min\{g_1(p',q'),g_2(p',q')\}\le z
\]
is equivalent to the displayed disjunction. Applying this condition to the chosen profile forces equality.
There are five variables, constantly many polynomial conditions, and degree at most two. Rational denominators can be cleared positively, preserving inequality directions. Compactness establishes nonemptiness even for negative optimal surplus or constant payoff polynomials.
Finding: Correct.
The fixed-dimension algorithmic fact invoked by the prover is standard and applicable here. In particular, Theorem 2.27 of [Basu’s survey](https://arxiv.org/pdf/1409.1534) supplies quantifier-elimination bounds on operation counts, output degrees, and intermediate integer bit lengths. With the stated fixed parameters, these give polynomial bit complexity.
Minor issue: The citation does not explicitly document the complete sampling-to-output guarantee. Theorem 2.16 is formulated using an infinitesimal extension and arithmetic complexity; it does not itself state polynomial-time production of separate integer polynomials and rational isolating intervals for real sample coordinates. The write-up also leaves the conversion from an algebraic sample representation to the requested coordinate representation implicit.
This is a documentation gap, not a false assertion or a need for new mathematics.
Minimum clarification: Supply a precise reference for polynomial-bit-complexity sampling of real points under the stated fixed parameters, including the standard conversion to the requested coordinate representation.
The subsequent comparison claim is valid for bounded-degree algebraic numbers of polynomial coefficient length. Equality and ties can be handled exactly; any maximizing support pair suffices. The support lemma then establishes global optimality.
The concluding reference to [Rong–Halpern, Theorem 5.5](https://www.cs.cornell.edu/~rongnan/publications/ce_journal.pdf) accurately identifies their polynomial-time M-PCE result.
⟨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.