Answer: \(\mathrm{NP}\text{-complete}\), already for \(m=2\).
Theorem 4.10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an LIG, along with a designated subset of k players in it, it is NP-complete to decide if there exists a PSNE consistent with those k players playing the action 1.
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\), thresholds \(b_t\), type-level influence coefficients \(W_{st}\), and prescribed masses \(p_t\leq\mu_t\), decide whether a nonatomic type-block LIG has an equilibrium in which at least \(p_t\) mass of each type chooses \(+1\). Let \(z_t\in[p_t,\mu_t]\) be the mass of type \(t\) choosing \(+1\), set \(a_t=2z_t-\mu_t\), and define \(F_t=\sum_{s\in T}W_{st}a_s-b_t\). Every agent, including those in the prescribed mass, must best respond: \(z_t=\mu_t\) when \(F_t>0\), \(z_t=0\) when \(F_t<0\), and any \(z_t\in[0,\mu_t]\) when \(F_t=0\), with a split at indifference assigning pure actions to different agents.
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type is a nonatomic block whose agents choose one of \(m=2\) actions, \(\{-1,+1\}\). Input thresholds \(b_t\) and directed influence coefficients \(W_{st}\) are arbitrary signed binary rationals, including \(W_{tt}\); input requirements satisfy \(0\leq p_t\leq\mu_t\) and \(\sum_t p_t>0\).
For a measurable pure-action assignment, let \(z_t\in[0,\mu_t]\) be the mass choosing \(+1\), set \(a_t=2z_t-\mu_t\), and define \(F_t=\sum_{s\in T}W_{st}a_s-b_t\). A type-\(t\) agent choosing \(x\) receives payoff \(xF_t\); an individual deviation leaves all aggregates unchanged.
An equilibrium requires \(z_t=\mu_t\) if \(F_t>0\), \(z_t=0\) if \(F_t<0\), and permits any \(z_t\in[0,\mu_t]\) if \(F_t=0\), assigning pure actions to different indifferent agents. Every agent, including the prescribed mass, must best respond.
Decide whether such an equilibrium exists with \(z_t\geq p_t\) for every \(t\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this equilibrium-existence problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite linear influence games with signed weights and thresholds, deciding whether a pure-strategy Nash equilibrium exists in which a designated nonempty subset chooses \(+1\) is NP-complete ([Irfan and Ortiz](https://arxiv.org/abs/1303.2147)).
No result settling exactly the nonatomic problem defined above was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete, already for \(m=2\). Hardness holds even when all types have equal dyadic masses and every requirement is either \(0\) or the type’s entire mass.
An exact algorithm runs in \(3^\tau\operatorname{poly}(m,\tau,L)\) time. Thus polynomial time in all three parameters would imply \(\mathrm{P}=\mathrm{NP}\).
Write \(a_t=2z_t-\mu_t\). The mass requirement becomes
\[ 2p_t-\mu_t\leq a_t\leq\mu_t, \]
and the influence field is \(F_t=\sum_s W_{st}a_s-b_t\).
For each type, equilibrium is equivalent to satisfying at least one of these three regimes:
The mass bounds remain imposed in every regime. To verify the equivalence, an endpoint aggregate assigns everyone the corresponding action, which is optimal precisely under the stated weak sign condition. An interior aggregate assigns positive mass to both actions, so both must be optimal; their payoffs are \(F_t\) and \(-F_t\), requiring \(F_t=0\). Conversely, when \(F_t=0\), any permitted split is an equilibrium.
Guess one regime for each type. The resulting constraints form a rational linear feasibility problem with \(\tau\) variables and \(O(\tau)\) constraints. Its encoding length is polynomial in \(L\): all coefficients are input rationals, apart from the bounds obtained by rational arithmetic.
The polynomial-time theorem for rational linear programming therefore gives a deterministic polynomial-time verifier for the guessed regime list. This proves membership in \(\mathrm{NP}\). Enumerating all \(3^\tau\) lists gives the claimed exact running time.
Nonatomicity ensures that every feasible mass split can be realized by measurable pure-action assignments within each type.
Let a three-SAT instance have variables \(v_1,\ldots,v_n\) and clauses \(C_1,\ldots,C_k\), each containing three literal occurrences. We may restrict to \(n,k\geq1\); empty instances are trivial and do not affect hardness.
Create:
There are \(M=3n+k\) types so far. Let \(N\) be the smallest power of two with \(N\geq M\), and add \(N-M\) dummy types. Set
\[ \tau=N,\qquad \mu_t=\frac1N \]
for every type. These masses are positive dyadic rationals and sum to \(1\).
Define the normalized aggregate
\[ x_t=\frac{a_t}{\mu_t}=Na_t\in[-1,1]. \]
Thus \(x_t=-1\) means everyone chooses \(-1\), \(x_t=1\) means everyone chooses \(+1\), and an interior value represents a split.
Specify the fields as follows:
\[ F_{V_i}=x_{V_i}, \]
\[ F_{P_i}=x_{V_i}-\frac12, \qquad F_{Q_i}=-x_{V_i}-\frac12. \]
For a literal \(\ell\), write \(A(\ell)=P_i\) when \(\ell=v_i\), and \(A(\ell)=Q_i\) when \(\ell=\neg v_i\). For each clause \(C_j=(\ell_{j1}\lor\ell_{j2}\lor\ell_{j3})\), set
\[ F_{D_j}=x_{A(\ell_{j1})}+x_{A(\ell_{j2})}+x_{A(\ell_{j3})}+1. \]
For every dummy type \(H\), set \(F_H=1\).
Finally, impose
\[ p_{D_j}=\mu_{D_j}=\frac1N, \qquad p_t=0\quad\text{for all other types}. \]
Hence \(\sum_t p_t=k/N>0\), as required.
These fields have exactly the permitted form. Explicitly:
All unspecified weights are zero. Repeated literal occurrences contribute their multiplicity to the corresponding coefficient.
At a variable type, the field is \(F_{V_i}=x_{V_i}\).
If \(0<x_{V_i}<1\), then \(F_{V_i}>0\), so equilibrium requires \(x_{V_i}=1\), a contradiction. Similarly, \(-1<x_{V_i}<0\) is impossible. Consequently, every equilibrium satisfies
\[ x_{V_i}\in\{-1,0,1\}. \]
All three values are compatible with that type’s equilibrium condition: the endpoints have the matching strict sign, and \(0\) gives indifference.
The literal fields never vanish at these three possible variable values. Their uniquely determined equilibrium aggregates are:
| \(x_{V_i}\) | \(x_{P_i}\) | \(x_{Q_i}\) |
|---|---|---|
| \(-1\) | \(-1\) | \(1\) |
| \(0\) | \(-1\) | \(-1\) |
| \(1\) | \(1\) | \(-1\) |
Indeed, \(x_{V_i}-1/2>0\) exactly when \(x_{V_i}=1\), and \(-x_{V_i}-1/2>0\) exactly when \(x_{V_i}=-1\).
Thus a positive literal type chooses \(+1\) exactly when its variable aggregate is \(1\); a negative literal type does so exactly when its variable aggregate is \(-1\). A variable aggregate of \(0\) activates neither literal.
The requirement \(p_{D_j}=\mu_{D_j}\) forces \(x_{D_j}=1\). This is an equilibrium precisely when \(F_{D_j}\geq0\).
Let \(r_j\) be the number of literal occurrences in clause \(C_j\) whose literal type has aggregate \(1\). The other \(3-r_j\) occurrences have aggregate \(-1\). Therefore
\[ F_{D_j}=r_j-(3-r_j)+1=2r_j-2. \]
It follows that the clause requirement is compatible with equilibrium exactly when
\[ r_j\geq1. \]
The equality case \(r_j=1\) gives \(F_{D_j}=0\); assigning the entire clause type to \(+1\) is then permitted by the stated equilibrium definition.
Given a satisfying Boolean assignment, set \(x_{V_i}=1\) for true variables and \(x_{V_i}=-1\) for false variables.
Set the literal aggregates according to the table, and set every clause and dummy aggregate to \(1\).
Each variable type best responds because its field equals its endpoint aggregate. Each literal type best responds because its aggregate matches the strict sign of its field. Every clause has at least one true literal, so \(r_j\geq1\) and \(F_{D_j}\geq0\). Dummy types have positive field and aggregate \(1\).
Thus all agents best respond, and every mass requirement holds.
Conversely, suppose the constructed instance has a feasible equilibrium.
For each variable, assign it true when \(x_{V_i}=1\), false when \(x_{V_i}=-1\), and arbitrarily when \(x_{V_i}=0\).
Every clause must have \(r_j\geq1\). Choose one of its literal occurrences whose literal aggregate is \(1\). The table shows that this occurrence comes from a variable with a nonzero aggregate and that the resulting Boolean assignment makes this literal true.
The arbitrary assignments to zero-aggregate variables cannot change these witnessed true literals. Hence every clause is satisfied.
This proves the equivalence between satisfiability and existence of the required nonatomic equilibrium.
Because \(M\leq N<2M\), the constructed support size is \(O(n+k)\). Every nonzero weight has magnitude at most \(3N\); thresholds belong to \(\{-1,0,1/2\}\); masses and requirements are dyadic rationals with \(O(\log N)\) bits.
Even a dense encoding of the influence matrix has length \(O(N^2\log N)\), so the construction is a polynomial-time reduction.
The reduction proves \(\mathrm{NP}\)-hardness for fixed \(m=2\). Together with membership in \(\mathrm{NP}\), it establishes \(\mathrm{NP}\)-completeness for exactly the nonatomic problem in the question.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the argument establishes \(\mathrm{NP}\)-completeness for the specified nonatomic problem, already with \(m=2\). I found no major or minor issues requiring repair.
The substitution \(a_t=2z_t-\mu_t\) correctly converts the requirement \(p_t\leq z_t\leq\mu_t\) into
\[
2p_t-\mu_t\leq a_t\leq\mu_t.
\]
Since \(p_t\geq0\), these bounds also enforce \(a_t\geq-\mu_t\).
The three regimes correctly characterize equilibrium. At \(a_t=-\mu_t\), everyone chooses \(-1\), which is optimal exactly when \(F_t\leq0\). At \(a_t=\mu_t\), everyone chooses \(+1\), which is optimal exactly when \(F_t\geq0\). At an interior aggregate, positive masses choose both actions, so equilibrium requires their payoffs to coincide, giving \(F_t=0\).
The regimes may overlap at indifferent endpoints; this does not affect their disjunctive characterization. Retaining the mass bounds in every regime ensures that indifference cannot bypass a requirement.
A regime list has polynomial length: one of three choices for each of the \(\tau\) types. For a fixed list, all constraints are non-strict rational linear equalities or inequalities in \(\tau\) variables.
The application of polynomial-time rational linear feasibility is justified. The coefficients are explicitly encoded rationals, and forming \(2p_t-\mu_t\) increases their binary encoding lengths by only a polynomial amount. There are \(O(\tau)\) constraints, although the field constraints can contain \(O(\tau^2)\) coefficients; these coefficients are already accounted for in the input length \(L\).
A deterministic polynomial-time feasibility algorithm therefore verifies the guessed regime list. An explicit rational aggregate certificate is unnecessary because the verifier itself decides feasibility.
Enumerating all regime lists gives the stated running time
\[
3^\tau\operatorname{poly}(m,\tau,L).
\]
Here \(m=2\) is fixed by the problem.
The realization claim is also valid: a nonatomic finite-measure block admits a measurable subset of any prescribed mass between zero and its total mass. Thus feasible aggregates correspond to measurable pure-action assignments.
The construction uses \(M=3n+k\) initial types and pads to a power of two \(N\). With \(n,k\geq1\), it produces a nonempty support and satisfies
\[
M\leq N<2M.
\]
The masses \(1/N\) are positive dyadic rationals and sum to one.
The normalization \(x_t=Na_t\) correctly gives \(x_t\in[-1,1]\). Each displayed field translates into the allowed convention
\[
F_t=\sum_s W_{st}a_s-b_t.
\]
In particular, the variable self-influence is permitted by the task; the negative literal field uses coefficient \(-N\); and the clause constant \(+1\) corresponds to threshold \(-1\).
Repeated literal occurrences are correctly represented by adding their coefficient contributions. All unspecified coefficients are zero, so clause and dummy aggregates introduce no additional terms into variable or literal fields.
Requirements satisfy \(0\leq p_t\leq\mu_t\), and
\[
\sum_t p_t=k/N>0.
\]
The reduction therefore respects every input restriction.
For a variable type, \(F_{V_i}=x_{V_i}\). A positive interior value would require the aggregate to equal \(1\), and a negative interior value would require it to equal \(-1\). Hence precisely the possible local equilibrium values are
\[
x_{V_i}\in\{-1,0,1\}.
\]
The proof correctly retains the indifferent value zero rather than claiming that variables must be Boolean.
At these three values, neither literal field vanishes. Direct substitution verifies every entry of the table: a positive literal has aggregate \(1\) exactly at variable value \(1\), a negative literal has aggregate \(1\) exactly at variable value \(-1\), and both have aggregate \(-1\) at variable value zero.
The full-mass clause requirement forces \(x_{D_j}=1\), whose equilibrium condition is \(F_{D_j}\geq0\).
Counting literal occurrences, including repetitions, gives
\[
F_{D_j}=r_j-(3-r_j)+1=2r_j-2.
\]
Since \(r_j\) is an integer between zero and three, this field is nonnegative exactly when \(r_j\geq1\).
The equality case is handled correctly. With exactly one active literal, the clause type is indifferent, and assigning all its agents \(+1\) is permitted.
A satisfying assignment yields endpoint variable aggregates, the prescribed literal aggregates, and aggregate \(1\) for every clause and dummy type. The proof checks the best-response condition for every type, including the indifferent clause case, and all requirements hold.
Conversely, every feasible equilibrium gives each clause an active literal occurrence. The table ensures that its variable has a nonzero aggregate and that the extracted Boolean assignment satisfies that literal. Assigning zero-aggregate variables arbitrarily cannot invalidate any such witness. Consequently, the extracted assignment satisfies all clauses.
Thus the additional fractional variable possibility does not create a false positive.
Literal multiplicities bound nonzero weights by \(3N\). All coefficients, masses, thresholds, and requirements have \(O(\log N)\)-bit encodings. Even a dense influence matrix therefore has polynomial size, and the construction is computable in polynomial time.
The reduction establishes hardness for fixed \(m=2\), equal dyadic masses, and requirements restricted to zero or full mass. Combined with membership in \(\mathrm{NP}\), it settles exactly the requested problem. No additional clarification or missing lemma 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.