Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k\), even for dyadic masses; in XP in the encoded input length, but not FPT unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateHD-NE is W[1]-hard parameterized by overlap of the input instance, even when the cost of the each position for each party is zero. Moreover, assuming ETH, there is no (n + m)o(ov)/ log(ov) time algorithm for HD-NE.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite line \([m]\), parties with candidate sets \(C_i\), and a finitely supported binary-rational distribution \(\mu\) over voter locations, does there exist a nomination profile \(s\) in which every party’s expected payoff is at least its payoff from any unilateral change of nominee? All candidate costs are zero, and the parameter is the maximum overlap of the parties’ candidate intervals.
Given integers \(m,n\geq1\), let \([m]=\{1,\ldots,m\}\) have distance \(|x-y|\). Each party \(i\in[n]\) has an explicitly listed nonempty candidate set \(C_i\subseteq[m]\), and all candidate costs are zero.
A society is given by its support: the list of its \(\tau\) voter-location types with positive mass, each mass a binary rational. Locations lie in \([m]\), and masses sum to \(1\); \(\tau\) is the support size, not the number of possible types.
A nomination profile chooses one position \(s_i\in C_i\) per party. At each voter location, divide its mass equally among the distinct nearest occupied nominee positions, then equally among the parties nominating each such position. Party \(i\)'s payoff \(u_i(s)\) is its total allocated mass.
A pure Nash equilibrium satisfies \(u_i(s)\geq u_i(x,s_{-i})\) for every \(i\in[n]\) and every \(x\in C_i\), with allocations recomputed after the unilateral change.
The parameter is \(k=\max_{j\in[m]}|\{i:j\in[\min C_i,\max C_i]\}|\), using closed intervals even when candidate sets have gaps.
All integers are binary encoded; let \(L\) be the total input bit length. State running times in \(m,n,\tau,L,k\), with polynomial time measured in the encoded input length.
Is deciding whether such a pure Nash equilibrium exists in \(\mathrm{P}\), or is it NP-hard?
If it is NP-hard, is it nevertheless FPT parameterized by \(k\), given the discrete problem's \(\mathrm{W}[1]\)-hardness by overlap?
For integer voter counts, equilibrium existence is NP-complete ([Harrenstein et al., 2021](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p593.pdf)).
The discrete problem is \(\mathrm{W}[1]\)-hard by overlap even with zero costs, and admits an XP algorithm by overlap ([Deligkas et al., 2022](https://www.ijcai.org/proceedings/2022/0035.pdf)). No result specifically treating the support-encoded rational-mass formulation was verified.
The support-encoded problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k\), even when every positive mass is dyadic. Consequently:
The hardness conclusions follow from a polynomial-time, overlap-preserving transfer of the cited integer-voter results. The XP bound requires avoiding a scan through all \(m\) positions; an explicit construction is given below.
Write the support as \((y_t,w_t)_{t=1}^{\tau}\), where \(w_t=a_t/b_t>0\), and put \(S=\sum_{i=1}^{n}|C_i|\). Because candidate sets and support entries are explicitly listed, \(n,\tau,S\leq L\), up to encoding constants.
For a profile \(s\), let \(P(s)\) be its distinct occupied positions and let \(c_s(p)=|\{i:s_i=p\}|\). Define
\[ H_t(s)=\left\{p\in P(s):|y_t-p|=\min_{z\in P(s)}|y_t-z|\right\}. \]
On a line, \(|H_t(s)|\leq2\): positions at a fixed distance from \(y_t\) belong to \(\{y_t-d,y_t+d\}\). The stipulated allocation rule therefore gives
\[ u_i(s)=\sum_{t=1}^{\tau} \frac{w_t\,\mathbf{1}_{\{s_i\in H_t(s)\}}} {|H_t(s)|\,c_s(s_i)}. \]
All comparisons can be performed exactly. Indeed, let
\[ B=\prod_{t=1}^{\tau}b_t,\qquad D=2n!B. \]
Every payoff contribution has denominator dividing \(D\). The bit length of \(D\) is \(O(L+n\log(n+1))\), since the total bit length of the listed denominators is at most \(L\).
A certificate specifies one listed candidate per party. For each party, compute its current payoff and its payoff after each listed unilateral deviation. Scanning all nominees for each voter type computes one such payoff in \(O(n\tau)\) arithmetic operations.
For example, using schoolbook integer arithmetic, verification takes
\[ O\!\left(n\tau(S+n)\bigl(L+n\log(n+1)\bigr)^2\right) \]
bit operations. Here \(S\leq\min(nm,L)\), and coordinates are manipulated in binary. This is polynomial in \(L\), without enumerating \([m]\). Thus the problem belongs to \(\mathrm{NP}\).
Consider a zero-cost integer-voter instance on \([M]\), with \(N\geq1\) parties, counts \(v_y\geq0\), and positive total count
\[ W=\sum_{y=1}^{M}v_y. \]
Let \(k_0\) be its closed-interval overlap. An instance originally indexed from zero can first be translated by one; this preserves distances and overlap.
Set
\[ b=\lfloor\log_2 W\rfloor+1,\qquad Q=2^b. \]
Thus \(W<Q\leq2W\). Construct a support-encoded instance as follows:
All listed masses are positive dyadic rationals, and their sum is one.
For an original voter position \(y\in[M]\), every original nominee is at distance at most \(M-1\), whereas the new nominee is at distance at least \(2M\). Hence the new nominee never affects the allocation of original voters, in any profile or unilateral deviation.
Conversely, the mass at \(3M\) is always allocated entirely to the new party. Therefore, for every original party \(i\) and every original profile \(s\),
\[ u_i^{\mathrm{new}}(s,3M)=\frac{u_i^{\mathrm{old}}(s)}{Q}. \]
The same identity holds after every allowed unilateral deviation. Multiplication by the positive constant \(1/Q\) preserves all equilibrium inequalities. The added party has no alternative strategy. Consequently,
\[ s\text{ is an equilibrium of the original instance} \quad\Longleftrightarrow\quad (s,3M)\text{ is an equilibrium of the constructed instance}. \]
All original party intervals remain inside \([M]\). The new party’s interval is the disjoint singleton \(\{3M\}\). Since \(k_0\geq1\), the new overlap is exactly
\[ k=\max(k_0,1)=k_0. \]
If \(t=|\{y:v_y>0\}|\), the new parameters satisfy
\[ m=3M,\qquad n=N+1,\qquad \tau=t+1\leq M+1. \]
Let \(L_0\) denote the source input length under an explicit table or explicit voter-list encoding. Then \(M,t\), the number of listed candidates, and the bit length of \(W\) are polynomially bounded by \(L_0\). In particular, under the cited dense encodings, the output length is \(O(L_0^2)\), and the transformation takes polynomial time in \(L_0\). It never expands \(W\) into individual voters.
Harrenstein et al., Theorem 3.14, proves \(\mathrm{NP}\)-completeness of equilibrium existence for the zero-cost integer-voter model. Its two-stage tie allocation agrees with the rule here, and its input representation explicitly lists voter counts and candidate availability along the line. Thus the transformation in Section 2 is a polynomial many-one reduction from that problem. Together with Section 1, this proves \(\mathrm{NP}\)-completeness. [Harrenstein et al. (2021)](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p593.pdf)
Deligkas et al., Theorem 5, proves \(\mathrm{W}[1]\)-hardness for the integer-voter model parameterized by closed-interval overlap, even with zero candidate costs. Their overlap definition is exactly \(k_0=\max_y|\{i:y\in[\min C_i,\max C_i]\}|\), and their allocation rule also agrees with ours. Section 2 therefore gives a polynomial parameterized reduction with \(k=k_0\), proving \(\mathrm{W}[1]\)-hardness of the support-encoded formulation. [Deligkas et al. (2022)](https://www.ijcai.org/proceedings/2022/0035.pdf)
An algorithm running in \(f(k)L^c\), for a computable \(f\) and constant \(c\), would consequently imply \(\mathrm{FPT}=\mathrm{W}[1]\). This is the precise conditional obstruction to FPT.
For completeness, the following sweep construction establishes XP in \(L\); it does not assume that \(m\) is polynomially bounded.
Let
\[ P=\bigcup_{i=1}^{n}C_i=\{p_1<\cdots<p_q\}. \]
Then \(q\leq\min(m,S)\). At coordinate \(x\in P\), call party \(i\) active if \(x\in[\min C_i,\max C_i]\). There are at most \(k\) active parties. A party enters at its first candidate coordinate and leaves after its last.
For an occupied position \(x\), its allocated mass depends only on its nearest distinct occupied positions \(\ell<x<r\), with a missing neighbor represented by infinity.
Let \(V(x;\ell,r)\) denote this allocated mass before division among parties at \(x\). Explicitly, evaluate each support type against \(x,\ell,r\): it contributes \(w_t\) when \(x\) is uniquely nearest, \(w_t/2\) when \(x\) ties with a neighbor, and zero otherwise.
Farther occupied positions cannot change this allocation. For example, for \(z>r>x\), the condition that a voter weakly prefers \(x\) to \(r\) is \(y_t\leq(x+r)/2\), which implies \(y_t<(x+z)/2\), so it strictly prefers \(x\) to \(z\). The argument on the left is symmetric.
Thus a party at \(x\), sharing that position with \(c\) parties, receives \(V(x;\ell,r)/c\). Computing \(V\) requires only the \(\tau\) support entries and polynomial-bit arithmetic.
For each active party \(i\), store guesses
\[ (s_i,\ell_i,r_i,c_i), \]
where \(s_i\in C_i\), \(\ell_i,r_i\) are its proposed nearest distinct occupied neighbors, and \(c_i\in\{1,\ldots,k\}\) is its proposed position multiplicity. These guesses prescribe its current payoff as \(V(s_i;\ell_i,r_i)/c_i\). Retain them while the party remains active.
Also store:
Every stored position belongs to \(P\), and every multiplicity is at most \(k\), because all parties nominating a position are active there.
For a fixed active set, the number of states is at most
\[ T=\bigl(q(q+1)^2k\bigr)^k(qk+1)^5. \]
This bound allows invalid states, which the algorithm rejects.
At coordinate \(x\), compute
\[ h(x)=|\{i\text{ active at }x:s_i=x\}|. \]
This counts all nominees at \(x\), because a party able to nominate \(x\) must be active there.
First check the global occupancy predictions. If \(h(x)>0\), the first predicted future occupied position must be \(x\), with multiplicity \(h(x)\). If \(h(x)=0\), the predicted list must not contain \(x\).
Whenever \(s_i=x\), check that \(\ell_i,r_i,c_i\) equal the neighbors and multiplicity supplied by these global lists. Hence every party’s guessed current payoff is verified at its selected coordinate.
Next, for every \(i\) with \(x\in C_i\) and \(s_i\neq x\), check the deviation to \(x\). Removing \(i\) vacates its old position precisely when it was that position’s sole occupant. Therefore:
The three stored future positions suffice for this second calculation: when \(x\) is occupied, they contain \(x\) and its next two occupied positions; when \(x\) is empty, they contain its next two.
Let the resulting opponent neighbors be \(\ell,r\). After the deviation, the multiplicity at \(x\) is \(h(x)+1\), so the deviation payoff is exactly
\[ \frac{V(x;\ell,r)}{h(x)+1}. \]
Reject the state if this exceeds the party’s prescribed current payoff.
When \(x\) is occupied, append it to the past list and retain the last two entries. Remove it from the future list. If that list previously had three entries, guess a possible new third entry beyond the retained positions. If it previously had fewer than three, it already asserted that no additional occupied position existed, so do not append one. At an unoccupied coordinate, leave both lists unchanged.
Between consecutive candidate coordinates, forget departing parties, introduce guesses for entering parties, and require agreement for parties active at both coordinates. Initialize with an empty past list and finish with an empty future list.
These rules verify every predicted occupied position and its multiplicity when its coordinate is processed. They also reject every actual occupied position omitted from the predictions. Thus an accepting sweep has the true global neighbor lists.
An accepting sweep determines one consistent strategy per party. Each party’s proposed current payoff is checked at its selected position, and each possible deviation is checked at its destination. Hence the resulting profile is an equilibrium.
Conversely, an equilibrium supplies all party guesses and global lists from its actual profile. Every local check and transition then passes. This proves both soundness and completeness.
Enumerating states and compatible pairs gives the conservative running-time bound
\[ qT^2\operatorname{poly}(n,\tau,L) = (k+1)^{O(k)}(q+1)^{O(k)}\operatorname{poly}(n,\tau,L). \]
Since \(q\leq\min(m,S)\leq L\), this is \((k+1)^{O(k)}L^{O(k)}\), establishing XP in the encoded input length. Dependence on the potentially enormous domain size \(m\) occurs through listed coordinates and their bit lengths, not through a scan of \([m]\).
⟨structured verdict parsed — rendered above⟩
The classification is correct in substance: the reduction establishes NP-completeness and \(\mathrm{W}[1]\)-hardness for the support-encoded rational-mass problem, including dyadic masses. The XP construction has a routine boundary ambiguity, and the encoding discussion contains an overstatement. Neither issue undermines the hardness conclusions.
Assessment: proved with minor gaps.
The payoff formula matches the specified allocation rule. Since the candidate sets are nonempty and \(n\geq1\), every profile has at least one occupied position, so the minimum defining \(H_t(s)\) exists.
The bound \(|H_t(s)|\leq2\) is correct: at any fixed distance from a voter location, there are at most two distinct positions on the line. Dividing first by \(|H_t(s)|\) and then by the multiplicity at the chosen position implements the required two-stage allocation.
The common-denominator argument is valid. Each contribution has denominator
\(b_t|H_t(s)|c_s(s_i)\), which divides \(2n!B\), because \(b_t\mid B\), \(|H_t(s)|\in\{1,2\}\), and \(c_s(s_i)\leq n\). This also covers \(n=1\).
The stated bit-length bound is correct. Payoffs and their comparisons can therefore be computed exactly with polynomial-bit integers.
The certificate has polynomial length, and the verifier checks every listed unilateral deviation. Scanning nominees for every support entry suffices to compute the deviating party’s payoff. The displayed verification bound is conservative and polynomial in \(L\); binary coordinates do not require enumerating the domain.
Conclusion: NP membership is established.
The construction assumes a positive integer total \(W\), as required by the source model. With the stated choice of \(b\), the bound \(W<Q\leq2W\) is correct, including when \(W\) is a power of two.
All constructed support masses are positive and dyadic. Their sum is
\(W/Q+(Q-W)/Q=1\). The added support location is distinct from every original support location.
The distance separation is valid, including \(M=1\):
Thus original allocations are unchanged except for multiplication by \(1/Q\), both before and after every allowed unilateral deviation. The added party has no alternative strategy. The asserted equilibrium equivalence follows.
The overlap calculation is also correct. Original intervals lie inside \([M]\), and the added interval is the disjoint singleton \(\{3M\}\). Nonempty candidate sets and \(N\geq1\) imply \(k_0\geq1\), so the resulting overlap equals \(k_0\).
Conclusion: the transfer preserves equilibrium existence and the parameter exactly.
Section 2 states that \(M\) is polynomially bounded by \(L_0\) under “an explicit table or explicit voter-list encoding.” This is justified for the cited dense representations, but does not follow for a list of individual voters with binary coordinates.
For example, a domain of size \(M=2^r\), one voter at position \(1\), and one party with candidate set \(\{1\}\) can have voter-list input length \(O(r)\). Its domain size is exponential in that length.
This does not invalidate the application to the cited dense encodings. It is an overstatement about an additional representation.
Minimum clarification: specify that the claimed polynomial bound on \(M\) applies to dense encodings, or define the intended voter-list representation precisely.
The external theorem applications are verified.
Harrenstein et al., Theorem 3.14, states NP-completeness of deciding equilibrium existence. Section 2 defines the same two-stage allocation, and its input-representation paragraph specifies a dense table of voter counts and candidate availability. Candidate costs are absent from that model. These hypotheses match the source required by the transfer. [Harrenstein et al. (2021)](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p593.pdf)
Deligkas et al., Theorem 5, states \(\mathrm{W}[1]\)-hardness parameterized by overlap even with zero costs. Its overlap definition uses the closed intervals from each party’s first to last candidate, and its utility formula divides midpoint ties between positions before dividing among colocated parties. The input includes voter counts at every domain position. [Deligkas et al. (2022)](https://www.ijcai.org/proceedings/2022/0035.pdf)
Consequently, the polynomial transfer gives both claimed hardness results. Combining NP-hardness with Section 1 establishes NP-completeness. Exact parameter preservation establishes the stated conditional obstruction to FPT.
Conclusion: the principal questions in USER_TASK are resolved.
The assertion that an occupied position’s allocation depends only on its nearest distinct occupied neighbors is correct. The midpoint comparison supplied in the output excludes farther positions whenever the current position is weakly preferred to its nearer neighbor.
With absent neighbors interpreted appropriately, the definition also covers a sole occupied position. No voter can tie between three distinct positions on a line, so the contribution rule for \(V\) is sufficient.
Every party choosing a position is active at that position. Therefore position multiplicity is at most \(k\), and \(h(x)\) counts all nominees at \(x\).
Each party remains active throughout the interval containing all its candidate coordinates, including gaps. Retaining its guesses throughout that interval ensures a consistent strategy and a consistent prescribed payoff.
The state-count bound is valid as an upper bound, using absence markers for missing list entries and neighbors. There are at most \(k\) active parties and five global position–multiplicity slots.
The stored neighbor information is sufficient. Removing one party can delete at most one occupied position. A deleted nearest opponent position must be replaced by the next position on that side; otherwise the nearest opponent position remains unchanged.
Two past positions suffice on the left. Three future positions suffice on the right because, when \(x\) is occupied, one slot is occupied by \(x\) itself.
For a checked deviation, \(s_i\neq x\), so the party was not already counted in \(h(x)\). Its destination multiplicity is therefore exactly \(h(x)+1\).
Using a guessed current payoff before its eventual verification is legitimate: an accepting path must verify that same retained guess at the party’s selected coordinate.
The replenishment instruction is ambiguous when the previous future list contains exactly three positions but there is no fourth occupied position. It says to “guess a possible new third entry beyond the retained positions,” without explicitly allowing absence.
For a concrete boundary case, take three parties with singleton candidate sets \(\{1\}\), \(\{2\}\), and \(\{3\}\), on a domain of size \(3\), with unit mass at position \(1\). The unique profile is an equilibrium. Its initial future list has three entries. After processing position \(1\), a mandatory new entry beyond position \(3\) is impossible.
Thus a literal mandatory-append interpretation would fail completeness. The intended handling of this endpoint is a routine clarification, requiring no new mathematical argument.
Minimum clarification: state whether replenishment may guess that no further occupied position exists, and include that possibility in the transition specification.
Subject to this endpoint clarification, predicted positions are verified when reached, omitted actual occupied positions are rejected, and retained list entries keep their multiplicities. Every party’s current payoff and every possible deviation are checked.
The soundness and completeness arguments then stand. Enumerating compatible state pairs gives the claimed XP bound. Since \(q\leq S\leq L\), the algorithm’s dependence on the domain is through listed binary coordinates rather than a scan of all \(m\) positions.
Only two clarifications are needed:
No major issue was found in the hardness transfer, the theorem applications, or the substantive sweep argument.
⟨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.