Answer: \(\mathrm{NP\text{-}complete}\) for every \(t\in\{2,\ldots,K\}\), and hence \(\mathrm{NP\text{-}hard}\).
Theorem 4.4 — class: hardness
Deciding whether there exists a t-local equilibrium is NP-hard, for t ∈{2, . . . ,K}, even under narcissistic preferences. Sketch of proof. We perform a reduction from Exact Cover by 3-Sets (X3C), a problem known to be NP-complete [13]. In an instance of X3C, we are given a set X = {x1,x2, . . . ,x3q} and a set S = {S1,S2, . . . ,Sr } of 3-element subsets of X and we ask whether there exists an exact cover, i.e., a subset S′ ⊆S such that every element of X occurs in exactly one member of S′, in other words S′ is a partition of X. We construct a BSC game as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(K\), candidates \(C\), explicitly represented strategy sets \(H_i\subseteq\{0,1\}^K\), truthful positions, narcissistic candidate preferences, a tie-breaking order, \(t\in\{2,\ldots,K\}\), and a sparse rational distribution \(\mu\) over \(H=\{0,1\}^K\), define \(F_\mu(s)\) by plurality with distance-minimizing candidates sharing each type's mass equally. Decide whether there exists \(s\in\prod_i H_i\) such that no candidate has a strictly improving deviation to \(s_i'\in H_i\) with \(d_H(s_i,s_i')\le t\).
Given \(K\), candidates \(C=\{c_1,\ldots,c_m\}\), truthful positions \(p_i\in\{0,1\}^K\), and explicitly listed strategy sets \(H_i\subseteq\{0,1\}^K\) with \(p_i\in H_i\), let \(s\in\prod_i H_i\) be an announced-position profile. Let \(\mu:\{0,1\}^K o\mathbb{Q}_{\ge0}\) be given by its sparse support and satisfy \(\sum_x\mu(x)=1\).
For each type \(x\), split its mass equally among the candidates minimizing Hamming distance from \(x\). Candidate scores are the resulting total masses; \(F_\mu(s)\) is the highest-scoring candidate, with ties resolved by the given fixed order. Candidates are narcissistic: \(c_i\) strictly prefers winning to any other winner and is indifferent among all other winners.
A profile is a \(t\)-local equilibrium if no \(c_i\) can choose \(s_i'\in H_i\) with \(d_H(s_i,s_i')\le t\) so that \(F_\mu(s_i',s_{-i})=c_i e F_\mu(s)\).
Target. For \(t\in\{2,\ldots,K\}\), is deciding whether such a \(t\)-local equilibrium exists for the sparse rational-distribution model NP-hard, or solvable in polynomial time?
Nearest known result. For the finite-voter version of this problem, deciding existence of a \(t\)-local equilibrium is NP-hard for every \(t\in\{2,\ldots,K\}\), even with narcissistic preferences.
For every \(t\in\{2,\ldots,K\}\), deciding whether a \(t\)-local equilibrium exists in the sparse rational-distribution model is \(\mathrm{NP\text{-}complete}\). In particular, it is \(\mathrm{NP\text{-}hard}\), and therefore is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
The hardness follows by an exact polynomial-time embedding of the known finite-voter problem.
Consider an instance of the finite-voter version from the stated known result. Let its voter positions be the multiset
\[ \{v_1,\ldots,v_n\}\subseteq\{0,1\}^K, \]
where \(n\geq 1\). All candidate data, namely \(C\), the truthful positions \(p_i\), the explicitly listed strategy sets \(H_i\), the parameter \(t\), and the fixed candidate tie-breaking order, are retained unchanged.
For every \(x\in\{0,1\}^K\), define its multiplicity by
\[ M_x=\bigl|\{j:v_j=x\}\bigr|. \]
Construct a sparse distribution with support
\[ S=\{x:M_x>0\} \]
and masses
\[ \mu(x)=\frac{M_x}{n} \]
for \(x\in S\). Then \(\mu(x)\) is nonnegative and rational, and
\[ \sum_{x\in S}\mu(x)=\frac{1}{n}\sum_{x\in S}M_x=1. \]
The support has at most \(n\) elements. Each mass has numerator at most \(n\) and denominator \(n\), so its binary representation has length \(O(\log n)\). Aggregating identical voter positions and writing these fractions is therefore polynomial-time in the finite-voter input size.
Fix an arbitrary announced-position profile \(s\in\prod_i H_i\). For every voter type \(x\), let
\[ A_x(s)=\operatorname*{arg\,min}_{c_i\in C}d_H(x,s_i) \]
be the set of candidates closest to \(x\), and let \(r_x(s)=|A_x(s)|\).
In the finite-voter instance, the score of candidate \(c_i\) is
\[ \operatorname{score}^{\mathrm{fin}}_i(s) = \sum_{x\in S} M_x\frac{\mathbf 1[c_i\in A_x(s)]}{r_x(s)}. \]
In the constructed distributional instance, its score is
\[ \begin{aligned} \operatorname{score}^{\mu}_i(s) &= \sum_{x\in S} \mu(x)\frac{\mathbf 1[c_i\in A_x(s)]}{r_x(s)}\\ &= \sum_{x\in S} \frac{M_x}{n} \frac{\mathbf 1[c_i\in A_x(s)]}{r_x(s)}\\ &= \frac{1}{n}\operatorname{score}^{\mathrm{fin}}_i(s). \end{aligned} \]
Thus the entire candidate score vector is multiplied by the same positive constant \(1/n\). Consequently, all strict score comparisons and all score ties are preserved. Since the fixed candidate tie-breaking order is also unchanged,
\[ F_\mu(s)=F_{\mathrm{fin}}(s) \]
for every profile \(s\).
This equality applies equally to every unilateral deviation. Hence, for every candidate \(c_i\) and every \(s_i'\in H_i\),
\[ F_\mu(s_i',s_{-i})=F_{\mathrm{fin}}(s_i',s_{-i}). \]
The strategy sets and Hamming distances are unchanged, so
\[ d_H(s_i,s_i')\leq t \]
holds in the constructed instance exactly when it holds in the finite-voter instance.
Because candidates are narcissistic, a deviation is strictly profitable precisely when it changes the winner from some candidate other than \(c_i\) to \(c_i\). The winner-preservation identity therefore gives
\[ F_\mu(s_i',s_{-i})=c_i\neq F_\mu(s) \]
if and only if
\[ F_{\mathrm{fin}}(s_i',s_{-i})=c_i\neq F_{\mathrm{fin}}(s). \]
Thus \(s\) is a \(t\)-local equilibrium in the finite-voter instance if and only if it is a \(t\)-local equilibrium in the constructed sparse-distribution instance. In fact, the two instances have exactly the same set of \(t\)-local equilibria.
The construction is therefore a polynomial-time many-one reduction preserving \(K\) and \(t\). Applying the stated finite-voter hardness theorem proves \(\mathrm{NP\text{-}hardness}\) for every \(t\in\{2,\ldots,K\}\).
A certificate is a profile \(s\in\prod_i H_i\). Because every \(H_i\) is explicitly listed, membership \(s_i\in H_i\) can be checked in polynomial time.
For a fixed profile, its winner can also be computed in polynomial time:
There are polynomially many supported types. Sums and comparisons of the input rationals require only polynomially many bit operations: after summing polynomially many rational terms, numerator and denominator bit lengths remain polynomial in the total input length.
Finally, for every candidate \(c_i\), enumerate all explicitly listed \(s_i'\in H_i\) satisfying \(d_H(s_i,s_i')\leq t\), compute \(F_\mu(s_i',s_{-i})\), and reject the certificate if
\[ F_\mu(s_i',s_{-i})=c_i\neq F_\mu(s). \]
The total number of tested deviations is at most \(\sum_i|H_i|\), which is bounded by the explicit input size. Verification is therefore polynomial-time, proving membership in \(\mathrm{NP}\).
The finite-voter and sparse rational-distribution formulations are equivalent on the image of the normalization construction, profile by profile and deviation by deviation. Therefore the target decision problem is \(\mathrm{NP\text{-}complete}\) for every permitted \(t\).
⟨structured verdict parsed — rendered above⟩
The prover maps each distinct voter position \(x\) of multiplicity \(M_x\) to distributional mass
\[ \mu(x)=\frac{M_x}{n}. \]
This is valid:
The claimed polynomial-time construction is justified.
For every profile \(s\), the distributional score satisfies
\[ \operatorname{score}^{\mu}_i(s) = \frac{1}{n}\operatorname{score}^{\mathrm{fin}}_i(s). \]
This computation correctly accounts for equal splitting among all nearest candidates, including coincident voter types and arbitrary nearest-candidate ties. Since \(n\geq 1\), multiplication by \(1/n\) preserves all score inequalities and equalities. Retaining the same fixed tie-breaking order therefore preserves the winner exactly.
The argument applies to every profile, so it also applies to every unilateral deviation.
The candidates' strategy sets, announced positions, Hamming metric, and radius \(t\) are unchanged. Thus the set of admissible local deviations is identical in the two instances.
Under narcissistic preferences, a deviation by \(c_i\) is strictly profitable exactly when \(c_i\) was not the original winner and becomes the new winner. The prover uses precisely this condition. Winner preservation consequently establishes profile-by-profile equivalence of \(t\)-local equilibrium.
This proves a valid polynomial-time many-one reduction from the stated finite-voter problem and establishes the claimed NP-hardness.
The proposed certificate is an explicitly represented profile \(s\in\prod_i H_i\). Because all \(H_i\) are explicitly listed, the verifier can enumerate every possible local unilateral deviation.
Winner computation is polynomial:
The assertion about rational bit lengths is correct: even a common denominator formed by multiplying polynomially many input denominators and tie sizes has bit length bounded by the sum of their bit lengths, hence polynomial in the input length.
Therefore membership in NP is established.
The reduction and NP-membership argument are correct and rigorous. The prover establishes the stronger classification of NP-completeness for every permitted \(t\), which fully answers the requested NP-hard-versus-polynomial-time question.
⟨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.