Answer: $\mathrm{NP}$-hard, even when $\tau=2$ or when $m=2$. Decision and exact algebraic profile computation are possible in $L^{O(1)}(m\tau+2)^{O((m\tau)^3)}$ bit operations.
Corollary 3.6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an n–player game, the problem of finding an SNE is NP–complete when n is constant.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\), finite action sets \(A_t\), and rational multilinear payoff functions of aggregate action shares, decide whether there is a type-symmetric mixed profile \(\sigma_t\) that is a Nash equilibrium and admits no positive-mass coalition deviation that strictly benefits every deviating type; if one exists, return it.
A society is nonatomic and given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a nonempty finite action set \(A_t\); put \(m=\max_t|A_t|\). For every \(t,a\), the input specifies a multilinear polynomial \(u_{t,a}(z)\) by an explicit list of monomials with binary-rational coefficients, with degree at most one in each coordinate. Its values lie in \([0,1]\) on feasible aggregate vectors; coefficients may have either sign. Let \(L\) be the total input bit length.
A type-symmetric profile assigns every individual of type \(t\) the same independent mixed strategy \(\sigma_t\in\Delta(A_t)\), with real probabilities. Aggregate shares are indexed by type and action: \(z_{t,a}=\mu_t\sigma_{t,a}\). The payoff to a type-\(t\) individual using \(q\in\Delta(A_t)\) at aggregate \(z\) is \(V_t(q,z)=\sum_{a\in A_t}q_a u_{t,a}(z)\).
Nash equilibrium requires \(V_t(\sigma_t,z)\ge V_t(q,z)\) for every \(t\) and \(q\in\Delta(A_t)\): an individual has zero mass and leaves \(z\) unchanged. Indifference is allowed.
A coalition selects real masses \(0\le c_t\le\mu_t\), with \(\sum_t c_t>0\), and replacement independent mixed strategies \(\rho_t\in\Delta(A_t)\) for its participating types. Outsiders retain their strategies, so \(z'_{t,a}=(\mu_t-c_t)\sigma_{t,a}+c_t\rho_{t,a}\). The deviation is profitable precisely when \(V_t(\rho_t,z')>V_t(\sigma_t,z)\) for every \(t\) with \(c_t>0\). Partial-type coalitions and the grand coalition are allowed.
Call a profile strong if it is a Nash equilibrium and has no profitable coalition deviation. The problem is to decide whether a strong type-symmetric profile exists and, if so, compute one.
Is deciding existence of such a profile in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\).
For finite normal-form games with a fixed number of players, strong Nash equilibrium computation is stated to be \(\mathrm{NP}\)-complete; verifying a rational profile is in \(\mathrm{P}\). [Source](https://arxiv.org/html/1711.06318)
No result settling the exact nonatomic problem defined above was located in the literature search.
Deciding existence is $\mathrm{NP}$-hard for the exact nonatomic model in the question. This holds even under either restriction:
All masses and coefficients in the reductions are dyadic rationals.
Put $N=\sum_t|A_t|\le m\tau$. There are deterministic algorithms with the following bit-operation bounds:
| Task | Running time |
|---|---|
| Decide existence | $L^{O(1)}(N+2)^{O(N^2)}$ |
| Decide existence and output an exact strong profile when one exists | $L^{O(1)}(N+2)^{O(N^3)}$ |
In particular, the second bound is at most
$$ L^{O(1)}(m\tau+2)^{O((m\tau)^3)}. $$
The output probabilities are represented by integer polynomials and rational isolating intervals. Rational probabilities are not assumed.
Thus fixing both $m$ and $\tau$ gives polynomial-time solvability. Fixing only either parameter retains $\mathrm{NP}$-hardness. For $m=1$, the unique profile is trivially strong.
Consider any collection of encoding types, all of whose action payoffs are identically $1$. Add a guard type $g$ of positive mass $\mu_g$, with actions $C,D$.
Let $F$ depend only on encoding aggregate coordinates, and suppose
$$ 0\le F(z)\le1 $$
on feasible aggregates. Choose a rational $\theta\in[0,1]$, write $x=z_{g,C}/\mu_g$, and define
$$ u_{g,C}(z)=\frac{1+(1+\theta-F(z))x}{4}, \qquad u_{g,D}(z)=\frac{2+(1+\theta-F(z))x}{4}. $$
These payoffs satisfy the input promise: $0\le x\le1$ and $0\le1+\theta-F\le2$, so both lie in $[0,1]$.
Lemma. A profile is strong exactly when the guard plays $D$ purely and the encoding strategies satisfy $F\ge\theta$.
Proof. At every feasible aggregate,
$$ u_{g,D}(z)-u_{g,C}(z)=\frac14. $$
Because an individual leaves the aggregate unchanged, Nash equilibrium requires the guard to play $D$ purely. Conversely, every profile with a pure-$D$ guard is Nash, since all encoding types are indifferent.
An encoding type cannot participate in a profitable coalition: its payoff remains $1$ after every deviation, whereas profitability requires strict improvement for every participating type. Hence any profitable coalition consists exclusively of guard individuals, and $F$ remains unchanged.
At a Nash profile the guard’s payoff is $1/2$. For a guard-only deviation, let
$$ \lambda=\frac{c_g}{\mu_g}\in(0,1], \qquad p=\rho_{g,C}\in[0,1]. $$
The new normalized $C$-share is $x'=\lambda p$. Coalition members receive
$$ V_g(\rho_g,z') = \frac{2-p+(1+\theta-F)\lambda p}{4}. $$
Their gain is therefore
$$ V_g(\rho_g,z')-\frac12 = \frac{p\bigl((1+\theta-F)\lambda-1\bigr)}4. $$
If $F\ge\theta$, then $0\le1+\theta-F\le1$, so this gain is nonpositive for every $\lambda,p$. This includes every permitted partial-type and mixed deviation.
If $F<\theta$, the entire guard type can switch to pure $C$: taking $\lambda=p=1$ gives gain $(\theta-F)/4>0$.
This proves the characterization, including the equality case $F=\theta$. $\square$
If $F$ is multilinear in encoding coordinates, the guard payoffs remain multilinear: multiplication introduces only the distinct coordinate $z_{g,C}$.
We reduce from CLIQUE on a simple graph $G=(\{1,\ldots,n\},E)$ and an integer $2\le k\le n$.
For $w$ in the probability simplex, define
$$ F_G(w)=2\sum_{\{i,j\}\in E}w_iw_j. $$
Its range satisfies
$$ 0\le F_G(w) \le2\sum_{i<j}w_iw_j =1-\sum_iw_i^2 \le1. $$
Let $\omega(G)$ be the maximum clique size. We prove
$$ \max_{w\in\Delta(\{1,\ldots,n\})}F_G(w) = 1-\frac1{\omega(G)}. $$
Continuity and compactness give a maximizer. Choose one having minimum support size.
Suppose nonadjacent vertices $i,j$ both belong to its support. Hold all other coordinates fixed and preserve $w_i+w_j=s$. The terms involving these coordinates are
$$ 2w_iA+2w_jB, $$
where
$$ A=\sum_{\ell:\{i,\ell\}\in E}w_\ell, \qquad B=\sum_{\ell:\{j,\ell\}\in E}w_\ell. $$
Both sums remain fixed: the absence of the edge $\{i,j\}$ means neither involves either changing coordinate. Moving all mass $s$ to $i$ when $A\ge B$, and to $j$ otherwise, cannot decrease the objective. Since the original point was a global maximizer, the resulting point is another maximizer with smaller support, a contradiction.
Consequently, the support is a clique of some size $r\le\omega(G)$. On that support,
$$ F_G(w)=1-\sum_iw_i^2 \le1-\frac1r \le1-\frac1{\omega(G)}. $$
Here $\sum_iw_i^2\ge1/r$ follows from Cauchy–Schwarz. Conversely, the uniform distribution on a maximum clique attains $1-1/\omega(G)$. The identity follows.
Set
$$ \alpha=1-\frac1{k-1}, \qquad \beta=1-\frac1k. $$
Choose the specific power of two
$$ q=2^{\lceil\log_2(k(k-1))\rceil+1}, \qquad \theta=\frac{\lfloor q\alpha\rfloor+1}{q}. $$
Then $q>k(k-1)$ and $q\le4k(k-1)$, so $\theta$ has $O(\log k)$ bits. Moreover,
$$ \alpha<\theta \le\alpha+\frac1q <\alpha+\frac1{k(k-1)} =\beta. $$
Introduce exactly two types, each of mass $1/2$:
Set $w_i=2z_{e,i}$ and use $F=F_G(w)$ in the gadget. Feasible encoding aggregates correspond exactly to simplex points $w$.
The gadget implies that a strong profile exists exactly when some $w$ satisfies $F_G(w)\ge\theta$.
If $\omega(G)\ge k$, then
$$ \max F_G = 1-\frac1{\omega(G)} \ge\beta>\theta. $$
If $\omega(G)\le k-1$, then
$$ \max F_G \le\alpha<\theta. $$
Thus a strong profile exists exactly when the CLIQUE instance is positive.
In aggregate coordinates,
$$ F(z)=8\sum_{\{i,j\}\in E}z_{e,i}z_{e,j}. $$
The explicit guard payoffs are
$$ u_{g,C}(z) = \frac14+\frac{1+\theta}{2}z_{g,C} -4\sum_{\{i,j\}\in E}z_{g,C}z_{e,i}z_{e,j}, $$
$$ u_{g,D}(z) = \frac12+\frac{1+\theta}{2}z_{g,C} -4\sum_{\{i,j\}\in E}z_{g,C}z_{e,i}z_{e,j}. $$
Each cubic monomial uses distinct coordinates. The payoffs are multilinear, have degree at most $3$, and satisfy the promised range by the gadget lemma.
The construction has
$$ \tau=2,\qquad m=n,\qquad L=O((n+|E|)\log(n+2)). $$
It is a polynomial-time reduction. This proves $\mathrm{NP}$-hardness with two types.
Start with a $3$-CNF formula. Remove tautological clauses and repeated literals within clauses. Append a positive unit clause on a fresh variable. Appending this clause preserves satisfiability and guarantees at least one remaining clause.
Write $n$ for the resulting number of variables and $M\ge1$ for the number of clauses. Each clause has at most three literals on distinct variables.
For each variable $i$, introduce an encoding type with actions $0,1$, both having payoff $1$. Put
$$ w_i=\frac{z_{i,1}}{\mu_i}\in[0,1]. $$
For clause $j$, define its failure polynomial
$$ B_j(w)= \prod_{\text{positive literals }i\text{ in }j}(1-w_i) \prod_{\text{negative literals }i\text{ in }j}w_i. $$
Every $B_j$ is nonnegative on the cube and multilinear of degree at most $3$. Set
$$ h=\lceil\log_2 M\rceil, \qquad F(w)=1-2^{-h}\sum_{j=1}^M B_j(w). $$
Since $0\le B_j\le1$ and $M\le2^h$,
$$ 0\le F(w)\le1. $$
We claim
$$ \exists w\in[0,1]^n:\ F(w)=1 \quad\Longleftrightarrow\quad \text{the formula is satisfiable}. $$
A satisfying Boolean assignment makes every clause failure vanish, proving one direction.
Conversely, $F(w)=1$ forces every $B_j(w)=0$, because these polynomials are nonnegative. In each clause, some failure factor is zero. For a positive literal this requires $w_i=1$; for a negative literal it requires $w_i=0$. Assign variables with integral coordinates accordingly, and assign all other variables arbitrarily. Every clause retains a true literal. The assignments are consistent because they come from the same vector $w$.
Add the guard with threshold $\theta=1$. Choose
$$ b=\lceil\log_2(n+2)\rceil. $$
Give every variable type and the guard mass $2^{-b}$. Add a one-action dummy type of mass
$$ 1-(n+1)2^{-b}>0 $$
and constant payoff $1$. All masses are positive dyadic rationals and sum to one. The dummy cannot participate profitably.
By the gadget lemma, a strong profile exists exactly when $F\ge1$, equivalently when $F=1$, equivalently when the formula is satisfiable.
Each clause failure expands into at most eight monomials. Normalizing by the dyadic masses preserves rational coefficients, and multiplication by the guard coordinate preserves multilinearity and increases degree by at most one. Therefore
$$ m=2,\qquad \tau=n+2, $$
the payoff degree is at most $4$, and
$$ L=O((n+M)\log(n+M+2)). $$
This proves $\mathrm{NP}$-hardness with two actions per type.
Let $N=\sum_t|A_t|$. Introduce candidate variables
$$ X=(\sigma,z,v), \qquad \dim X=K=2N+\tau. $$
Let $P(X)$ be the conjunction, over the appropriate types and actions, of
$$ \sigma_{t,a}\ge0,\qquad \sum_a\sigma_{t,a}=1,\qquad z_{t,a}=\mu_t\sigma_{t,a}, $$
$$ v_t=\sum_a\sigma_{t,a}u_{t,a}(z), \qquad v_t\ge u_{t,a}(z). $$
These conditions express feasibility and Nash equilibrium exactly. Indeed, the payoff against a fixed aggregate is linear in the individual’s strategy, so dominating every pure-action payoff is equivalent to dominating every mixed-strategy payoff.
Introduce deviation variables
$$ W=(c,\rho,y), \qquad \dim W=2N+\tau. $$
Let $D(X,W)$ assert
$$ 0\le c_t\le\mu_t,\qquad \sum_tc_t>0, $$
$$ \rho_{t,a}\ge0,\qquad \sum_a\rho_{t,a}=1, $$
$$ y_{t,a}=(\mu_t-c_t)\sigma_{t,a}+c_t\rho_{t,a}, $$
and, for every type,
$$ c_t=0 \quad\lor\quad \sum_a\rho_{t,a}u_{t,a}(y)>v_t. $$
Thus $D$ expresses exactly an admissible profitable coalition. Strategies for nonparticipating types cause no restriction: their coalition masses are zero.
Define
$$ Q(X)=P(X)\land\forall W\,\neg D(X,W). $$
The existence question is exactly
$$ \exists X\,\forall W\, \bigl(P(X)\land\neg D(X,W)\bigr). $$
There are $O(N)$ distinct polynomial atoms, each of total degree at most $N+1$. The formula can be constructed with sparse bit length polynomial in $L$. In particular, multiplying a listed payoff monomial by a strategy variable adds one factor without expanding substituted aggregate expressions.
Multiplying each polynomial by a positive common denominator gives integer coefficients of bit size $L^{O(1)}$ and preserves every sign condition.
The following property avoids the multivariate sampling issue identified in the verifier report.
Lemma. The set of strong profiles is compact.
Proof. The feasible strategy space is the compact product $\prod_t\Delta(A_t)$. Nash equilibrium is a closed condition, since it consists of finitely many weak inequalities between continuous functions.
The set of profiles admitting a profitable coalition is relatively open in the feasible strategy space. To prove this, fix a profitable deviation at a profile $\sigma$, including its masses $c$ and strategies $\rho$. Its participating types form a fixed finite set. For each participating type, the gain
$$ V_t\bigl(\rho_t,y(\sigma)\bigr) - V_t\bigl(\sigma_t,z(\sigma)\bigr) $$
is continuous in $\sigma$ and strictly positive at the given profile. All these gains therefore remain positive in a sufficiently small neighborhood. The same $c,\rho$ remain admissible throughout that neighborhood, because their admissibility does not depend on $\sigma$.
Consequently, having no profitable coalition is relatively closed. Intersecting it with the Nash conditions gives a closed subset of a compact space. $\square$
Let
$$ S=\{X:Q(X)\}. $$
For each feasible $\sigma$, the coordinates $z$ and $v$ are uniquely determined continuous functions of $\sigma$. Hence $S$ is compact as well.
Fix an ordering of the $K$ coordinates. Every nonempty compact subset of $\mathbb R^K$ has a unique lexicographically least point: minimize the first coordinate; within the resulting nonempty compact set minimize the second; continue through all coordinates.
Write $X'\prec X$ for strict lexicographic comparison, expressed as
$$ X'\prec X \quad\Longleftrightarrow\quad \bigvee_{j=1}^K \left( X'_j<X_j \land \bigwedge_{i<j}X'_i=X_i \right). $$
The lexicographically least point of $S$ is characterized by
$$ R(X)= Q(X)\land \neg\exists X'\bigl(Q(X')\land X'\prec X\bigr). $$
Using a fresh copy $W'$ of the deviation variables, define the quantifier-free formula
$$ \begin{aligned} E(X,W,X',W')={}&P(X)\land\neg D(X,W)\\ &{}\land \bigl( \neg(X'\prec X) \lor\neg P(X') \lor D(X',W') \bigr). \end{aligned} $$
Then
$$ R(X) \quad\Longleftrightarrow\quad \forall(W,X')\,\exists W'\,E(X,W,X',W'). $$
To check this equivalence, the first two conjuncts enforce $Q(X)$. For every earlier feasible candidate $X'$, the last conjunct requires a profitable deviation, which is exactly the assertion that $X'$ does not satisfy $Q$. For an infeasible or non-earlier $X'$, any $W'$ suffices.
For coordinate $j$, define
$$ \Phi_j(x)= \exists X_{-j}\, \forall(W,X')\, \exists W'\, E(X,W,X',W') \bigm|_{X_j=x}. $$
When $S$ is nonempty, $\Phi_j$ defines the singleton containing coordinate $j$ of its lexicographically least point. Crucially, all these singleton formulas describe coordinates of the same point.
Each formula has three quantifier blocks of size $O(N)$, one free variable, $O(N)$ distinct polynomials, and Boolean length $O(N^2)$.
We use the following conservative consequence of the block quantifier-elimination theorem. For a fixed number $r$ of quantifier blocks of sizes $k_1,\ldots,k_r$, $\ell$ free variables, $s$ integer polynomials of degree at most $d$, and coefficient bit size at most $B$, its arithmetic-operation count and output length are bounded by
$$ (s+d+2)^{C_r(\ell+1)\prod_i(k_i+1)}. $$
Intermediate integer bit sizes are bounded by
$$ B(d+2)^{C_r(\ell+1)\prod_i(k_i+1)}. $$
Here $C_r$ depends only on $r$. These estimates follow directly from [Basu’s survey, Theorem 2.16](https://www.math.purdue.edu/~sbasu/raag_survey2011.pdf), including its explicit integer-size bound. Polynomial-time integer arithmetic converts them to bit-operation bounds.
The dense input representation required by such algorithms also fits the claimed running times. In $O(N)$ variables and degree at most $N+1$, the number of monomial slots per polynomial is at most
$$ (N+2)^{O(N)}. $$
Filling these slots from our sparse lists costs
$$ L^{O(1)}(N+2)^{O(N)}, $$
which is absorbed below.
For existence, there are two quantifier blocks of size $O(N)$ and no free variables. Therefore decision takes
$$ L^{O(1)}(N+2)^{O(N^2)} $$
bit operations.
For each coordinate formula $\Phi_j$, there are three blocks of size $O(N)$ and one free variable. Quantifier elimination produces an equivalent univariate Boolean formula $\Psi_j(x)$ whose length, polynomial degrees, and coefficient bit sizes are all bounded by
$$ L^{O(1)}(N+2)^{O(N^3)}. $$
Its computation satisfies the same bit-time bound.
We explain why a singleton univariate formula gives ordinary real algebraic output in polynomial time in its explicit size, degrees, and coefficient bit sizes.
Remove constant polynomial atoms by evaluating them. Let $p_1,\ldots,p_s$ be the remaining nonzero, nonconstant integer polynomials, and put
$$ H=\prod_{i=1}^s p_i. $$
If $\Psi$ defines $\{\alpha\}$, then $H(\alpha)=0$. Otherwise, all polynomial signs would be constant on some open neighborhood of $\alpha$, making $\Psi$ true throughout that neighborhood—a contradiction.
Construct the square-free part $H_{\mathrm{sf}}$ and isolate its real roots. Integer-polynomial root isolation produces rational isolating intervals in polynomial bit time in degree and coefficient bit size, including ordinary real output. Relevant explicit bounds are in [Emiris–Mourrain–Tsigaridas, Theorem 5.1 and Remark 5.2](https://who.paris.inria.fr/Elias.Tsigaridas/files/emt-lncs-2006.pdf). Their Theorems 2.1–2.4 and Corollary 2.1 also provide polynomial bit bounds for square-free parts, gcds, and Sturm root counts.
For completeness, signs at each isolated root $\beta$ can be determined as follows. If $\beta$ is a rational endpoint, evaluate each $p_i$ directly. Otherwise, use an isolating interval $(a,b)$ whose endpoints are not roots of $H_{\mathrm{sf}}$. Compute
$$ G_i=\gcd(p_i,H_{\mathrm{sf}}). $$
A Sturm count determines whether $G_i$ has a root in $(a,b)$. Since this interval contains exactly one root of $H_{\mathrm{sf}}$, a positive count is equivalent to $p_i(\beta)=0$. If the count is zero, $p_i$ has no root in the interval, so its sign at $\beta$ equals its sign at any rational interior point.
Thus every atom of $\Psi$ can be evaluated at every root. Exactly one root satisfies $\Psi$. Return that root using $H_{\mathrm{sf}}$ and its isolating interval.
All product-polynomial sizes remain polynomial in the univariate input parameters. Indeed, if the $p_i$ have degree at most $d$ and coefficient bit size at most $B$, then
$$ \deg H\le sd, \qquad \log_2\|H\|_1 \le s\bigl(B+\log_2(d+1)\bigr), $$
using multiplicativity of the coefficient $\ell^1$-norm bound. Therefore the extraction stage is polynomial in the quantifier-elimination output parameters.
Apply this procedure to the $N$ strategy-coordinate formulas. Their roots are coordinates of one common lexicographically least strong profile, so assembling them produces a valid exact profile. The total bit time is
$$ L^{O(1)}(N+2)^{O(N^3)}. $$
The two reductions establish hardness directly for the specified nonatomic deviations, including partial-type coalitions and strict profitability. The exact algorithm uses compactness, quantifier elimination with controlled integer sizes, and univariate root isolation.
Therefore existence is $\mathrm{NP}$-hard, while decision and exact computation are polynomial in $L$ when both $m$ and $\tau$ are fixed. No membership claim in $\mathrm{NP}$ is needed or asserted.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. Both hardness reductions apply directly to the specified nonatomic model, and the exact decision and computation algorithms have the claimed bounds. I found no major or minor mathematical issue.
The payoff range is valid. On feasible aggregates, the assumptions give
$$ 0\le x\le1, \qquad 0\le1+\theta-F\le2. $$
Consequently, both guard payoffs belong to $[0,1]$.
The identity
$$ u_{g,D}(z)-u_{g,C}(z)=\frac14 $$
holds at every feasible aggregate. Since an individual leaves the aggregate unchanged, every Nash equilibrium must assign zero probability to $C$. Conversely, a pure-$D$ guard together with arbitrary encoding strategies is Nash: the guard strictly prefers $D$, and every encoding action has constant payoff $1$.
The exclusion of encoding types from profitable coalitions is justified. Their baseline and replacement payoffs both equal $1$, so a coalition containing positive mass of any such type cannot satisfy the required strict improvement for every participant. This also excludes the dummy type used later.
For guard-only deviations, the variables satisfy exactly the permitted ranges
$$ \lambda\in(0,1], \qquad p\in[0,1]. $$
The aggregate formula gives $x'=\lambda p$. Direct substitution confirms the stated gain:
$$ V_g(\rho_g,z')-\frac12 = \frac{p\bigl((1+\theta-F)\lambda-1\bigr)}4. $$
If $F\ge\theta$, this gain is nonpositive throughout the allowed domain. If $F<\theta$, the choice $\lambda=p=1$ gives strictly positive gain. The equality case $F=\theta$ is correctly handled: a zero gain does not constitute a profitable deviation.
Multiplication by $z_{g,C}$ preserves multilinearity because $F$ contains only encoding coordinates. The lemma therefore establishes precisely the characterization needed by both reductions.
The graph optimization identity is proved correctly.
This reasoning also covers an edgeless graph, where $\omega(G)=1$ and the maximum objective is $0$.
The threshold calculation is correct. For $2\le k\le n$,
$$ \beta-\alpha=\frac1{k(k-1)}. $$
The selected power of two satisfies
$$ k(k-1)<q\le4k(k-1), $$
and the rounding rule gives
$$ \alpha<\theta\le\alpha+\frac1q<\beta. $$
Thus $\theta$ is dyadic, belongs to $[0,1]$, and has the claimed encoding length.
With encoding mass $1/2$, the substitution $w_i=2z_{e,i}$ identifies all feasible encoding strategies with the full simplex. The guard lemma and the strict threshold separation prove both directions of the reduction equivalence.
The aggregate-coordinate expansion is correct:
$$ F(z)=8\sum_{\{i,j\}\in E}z_{e,i}z_{e,j}. $$
Substituting this into the guard payoffs yields exactly the coefficients printed in the output. Simplicity of the graph ensures that each cubic monomial uses distinct coordinates. The construction satisfies the payoff promise, has exactly two positive-mass types, and has polynomial encoding size.
Verified conclusion: existence is $\mathrm{NP}$-hard even with $\tau=2$ and total payoff degree at most $3$.
The formula preprocessing preserves satisfiability. Removing tautological clauses and duplicate literals has the stated effect. Appending a positive unit clause on a fresh variable preserves satisfiability and ensures $M\ge1$.
Each failure polynomial correctly represents the probability that its clause fails under independent variable probabilities. Distinct variables within a clause ensure multilinearity, and every factor lies in $[0,1]$. Hence
$$ 0\le B_j(w)\le1. $$
The normalization satisfies $M\le2^h$, so the stated bound $0\le F\le1$ follows.
The equivalence between $F(w)=1$ and satisfiability is rigorous. Nonnegativity forces every $B_j(w)$ to vanish. A vanishing product supplies an integral coordinate that makes a literal true. Assigning all integral coordinates according to the same vector cannot introduce inconsistent assignments, and assigning the remaining coordinates arbitrarily preserves those true literals.
The mass construction is valid because
$$ 2^b\ge n+2>n+1. $$
Thus the dummy mass is strictly positive, and all masses sum to one. All masses are dyadic. Normalizing encoding coordinates multiplies coefficients by powers of two, so the resulting coefficients remain dyadic as well.
At threshold $\theta=1$, the guard characterization requires $F\ge1$, which is equivalent to $F=1$ by the already established range bound. Each clause contributes at most eight expanded monomials. Multiplication by the distinct guard coordinate preserves multilinearity and raises the degree by at most one.
The stated parameters and input-size estimate follow.
Verified conclusion: existence is $\mathrm{NP}$-hard even with $m=2$ and total payoff degree at most $4$.
The formula $P(X)$ correctly expresses feasibility, baseline payoffs, and Nash equilibrium. Once $v_t$ is constrained to equal the baseline payoff, the inequalities
$$ v_t\ge u_{t,a}(z) $$
for every action are equivalent to the required inequalities against every mixed strategy, by linearity in that strategy.
The formula $D(X,W)$ matches the coalition definition exactly:
Requiring replacement strategies for nonparticipating types does not change existence of a deviation: their action sets are nonempty, and these strategies have no effect when $c_t=0$.
The dimensions of both variable tuples are correct. The polynomial count is $O(N)$, and the degree bound $N+1$ accounts for multiplication of payoff monomials by strategy variables. Introducing aggregate variables avoids substitution-induced expansion. Clearing denominators by positive integers preserves all comparisons and has polynomial coefficient bit cost.
The compactness proof is sound. A fixed profitable deviation remains admissible as the profile varies. Its finitely many participating types have continuous, strictly positive gains at the original profile, so all gains remain positive in a common relative neighborhood.
Thus profiles admitting profitable coalitions form a relatively open set. Their complement is relatively closed, as is the Nash set. Strong profiles therefore form a compact set.
The extension to $S$ is justified because $z$ and $v$ are uniquely determined continuous functions of the strategy profile.
Successive coordinate minimization on nonempty compact sets establishes existence and uniqueness of the lexicographically least point. No unsupported assumption about lexicographic order is used.
The quantified characterization is also correct. For fixed $X$, the first two conjuncts of $E$ enforce $Q(X)$. For any earlier candidate satisfying $P(X')$, the final conjunct requires a witness to $D(X',W')$. For all other candidates, it imposes no restriction.
Allowing $W'$ to depend on both universally quantified tuples does not change this equivalence: the relevant deviation assertion depends only on $X'$ and $W'$.
Consequently, every $\Phi_j$ defines the appropriate coordinate of the same unique point. This resolves the possible consistency problem of independently choosing coordinate projections.
The conservative theorem statement used in the output is supported by [Basu’s Theorem 2.16](https://www.math.purdue.edu/~sbasu/raag_survey2011.pdf). It supplies block-dependent arithmetic complexity, output formula and degree bounds, and an explicit bound on intermediate integer bit sizes.
The application meets its hypotheses: integer polynomial comparisons, finite Boolean formulas, and alternating real quantifier blocks. Here $s,d=O(N)$, the coefficient bit size is $L^{O(1)}$, and the number of blocks is fixed.
The existence sentence has two blocks of size $O(N)$ and no free variables. Each coordinate formula has three blocks of size $O(N)$ and one free variable. Substitution into the stated bounds gives the claimed exponents $O(N^2)$ and $O(N^3)$.
Dense conversion fits within the stated bounds. Polynomial-time integer arithmetic and the controlled integer sizes justify the conversion to bit-operation complexity.
The singleton argument is valid. After constant atoms are evaluated, if no remaining polynomial vanished at the singleton coordinate, all relevant signs would remain unchanged on an open neighborhood. The formula would then hold on that neighborhood, contradicting singletonhood.
The product $H$ therefore contains the desired coordinate as a root. Its degree and coefficient-size bounds follow from the stated coefficient norm estimate. Taking its square-free part retains its distinct roots.
The cited root-isolation result provides polynomial bit complexity for integer univariate polynomials; Remark 5.2 explicitly removes the auxiliary degree-versus-coefficient-size restriction. The same paper describes rational isolating-interval output. These hypotheses apply to the constructed polynomial. [Emiris–Mourrain–Tsigaridas](https://who.paris.inria.fr/Elias.Tsigaridas/files/emt-lncs-2006.pdf)
The root-sign procedure is correct. Every root of $p_i$ is a root of $H_{\mathrm{sf}}$. Within an interval containing exactly one root of $H_{\mathrm{sf}}$, a gcd root count therefore detects exactly whether $p_i$ vanishes at that root. Otherwise its sign is constant throughout the interval. Rational endpoint roots are handled separately.
Exactly one isolated root satisfies the singleton formula. Applying this procedure to the strategy coordinates returns the common canonical strong profile, with the claimed total complexity.
The output establishes $\mathrm{NP}$-hardness for the exact continuous problem and supplies exact algorithms with running times
$$ L^{O(1)}(N+2)^{O(N^2)} $$
for decision, and
$$ L^{O(1)}(N+2)^{O(N^3)} $$
for decision and exact computation, where $N\le m\tau$.
The fixed-parameter consequences follow. The case $m=1$ is correctly identified as trivial because every permitted replacement strategy leaves the aggregate and payoffs unchanged.
No repair or additional clarification is needed. The proof neither relies on transferring the finite-game result nor asserts unsupported membership in $\mathrm{NP}$.
⟨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.