Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateHare-Constructive-Shift-Bribery is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), designated candidate \(p\in C\), finite voter types \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), complete rankings \(\pi_t\), nondecreasing shift-price functions \(\rho_t(k)\), and budget \(b\), decide whether there are masses \(x_{t,k}\ge 0\) with \(\sum_k x_{t,k}=\mu_t\) and \(\sum_{t,k}\rho_t(k)x_{t,k}\le b\) such that, after shifting \(p\) upward by \(k\) positions for mass \(x_{t,k}\), \(p\) is the unique winner under Hare's simultaneous minimum-plurality elimination rule.
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(p\in C\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Each type specifies a strict complete ranking \(\pi_t\) and its shift-price table; identical rankings may have different prices.
If \(p\) has position \(r_t\) in \(\pi_t\), the explicitly listed prices \(\rho_t(k)\), for \(k\in\{0,\ldots,r_t-1\}\), are nonnegative binary integers, nondecreasing in \(k\), with \(\rho_t(0)=0\). The budget \(b\ge0\) is a binary rational. Prices are costs per unit mass; \(L\) denotes the total input bit length.
A shift allocation consists of real masses \(x_{t,k}\ge0\) satisfying \(\sum_{k=0}^{r_t-1}x_{t,k}=\mu_t\) and \(\sum_t\sum_{k=0}^{r_t-1}\rho_t(k)x_{t,k}\le b\). Before voting begins, mass \(x_{t,k}\) adopts the ranking obtained by moving \(p\) upward exactly \(k\) positions in \(\pi_t\), preserving the relative order of all other candidates.
Hare voting repeatedly computes plurality scores by mass on the rankings restricted to the surviving candidates. If all surviving candidates have equal scores, they are all declared winners and voting stops; otherwise, every candidate attaining the minimum score is eliminated simultaneously. Thus a sole survivor wins, and no tie-breaking order is used.
Is deciding whether a feasible shift allocation makes \(p\) the unique Hare winner solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of indivisible voters, constructive upward shift bribery under this rule is NP-complete ([Maushagen et al., 2018](https://aamas.csc.liv.ac.uk/Proceedings/aamas2018/pdfs/p1567.pdf)); the [2022 full version](https://link.springer.com/content/pdf/10.1007/s10472-022-09802-5.pdf) also establishes hardness in the nonunique-winner model.
With unit prices, the discrete problem is FPT in the number of candidates and separately in the number of voters, but \(\mathrm{W}[1]\)-hard in the number of shift operations ([Zhou and Guo, 2020](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p1665.pdf)). No result settling the exact divisible-mass problem above was located.
The decision problem is \(\mathrm{NP}\)-complete. This holds even when all input masses and the budget are dyadic rationals, and every type initially ranks \(p\) within its first four positions.
The reduction below permits arbitrary real allocations and explicitly accounts for small shifts on expensive types.
We reduce from restricted exact cover by three-element sets. An instance consists of a universe \(X\), with \(|X|=3q\) and \(q\ge1\), and a family \(\mathcal S=\{S_1,\ldots,S_{3q}\}\), where each set has three elements and each element occurs in exactly three sets. The question is whether some \(q\) sets cover \(X\). This problem is \(\mathrm{NP}\)-complete by [Gonzalez, Theorem A.1](https://www.cs.columbia.edu/~verma/classes/uml/ref/clustering_minimize_intercluster_distance_gonzalez.pdf).
The family has \(3q\) members because counting element-set incidences gives \(3|\mathcal S|=3|X|\). Moreover, any cover using at most \(q\) members must be an exact cover: these sets contain at most \(3q\) incidences altogether.
We first specify unnormalized masses. Normalization will divide all masses and the budget by the same positive number, leaving all score comparisons unchanged.
Introduce:
The following table specifies ranking prefixes. Complete each prefix by appending all unlisted candidates after \(p\), in any fixed order.
| Unnormalized mass | Ranking prefix | Types included |
|---|---|---|
| \(1\) | \(s_i\succ x\succ z\succ p\) | Each \(i\), each \(x\in S_i\) |
| \(1\) | \(s_i\succ p\) | Each \(i\) |
| \(3\) | \(d_i\succ s_i\succ p\) | Each \(i\) |
| \(4\) | \(x\succ z\succ p\) | Each \(x\in X\) |
| \(8\) | \(p\) | One type |
| \(\frac92\) | \(z\succ p\) | One type |
Call the \(s_i\succ p\) types cheap. Their only positive shift has price \(1\).
Set \(M=8q\). Every other type has price \(M\) for every allowed positive shift. All types have price zero for shift zero. These tables contain nonnegative integers and are nondecreasing.
The table’s total mass is
\[ \text{(formula below)} \]
\(W_0=3q(3+1+3)+3q\cdot4+8+\frac92=33q+\frac{25}{2}.\)
To obtain dyadic normalized masses, let \(W\) be the least power of two satisfying \(W\ge W_0+100\), and put \(A=W-W_0\).
Introduce padding candidates \(h_1,\ldots,h_N\), where \(N=\lceil A/5\rceil\). Since \(A\ge100\), we have \(N\ge20\), and
\(\frac{19N}{4}\le5N-5<A\le5N.\)
Thus \(J=4A-19N\) is an integer satisfying \(0\le J\le N\). Give \(J\) padding types mass \(5\), and the other \(N-J\) padding types mass \(\frac{19}{4}\). Each has prefix \(h_\ell\succ z\succ p\), with price \(M\) for every positive shift. Their masses sum to
\(5J+\frac{19}{4}(N-J)=\frac{19N+J}{4}=A.\)
Now divide every mass by \(W\), and set the actual budget to \(b=q/W\). The masses sum to one. All masses and the budget are dyadic rationals.
Because \(W<2(W_0+100)\), we have \(N=O(q)\). The construction therefore has polynomially many candidates and types, polynomial input length, and explicitly listed price tables. Every prefix places \(p\) within its first four positions.
From now on, scores, allocated masses, and costs are measured in the unnormalized units. The budget in these units is \(q\).
Fix any feasible allocation. Let \(y_i\in[0,1]\) be the cheap mass shifted from \(s_i\succ p\) to \(p\succ s_i\). Let \(\eta\) be the total mass receiving a positive shift on expensive types.
The budget constraint is exactly
\(\sum_i y_i+M\eta\le q.\)
Consequently, \(\eta\le q/M=\frac18\).
Define the reference profile by keeping the cheap shifts \(y_i\), while restoring every expensive type to its original ranking. For a surviving set \(R\) containing \(p\), write \(s_R(c)\) and \(\bar s_R(c)\) for actual and reference plurality scores.
Moving \(p\) upward preserves the relative order of all other candidates. On a ranking restricted to \(R\), it can therefore change the top candidate only by replacing some candidate with \(p\). It cannot transfer score between two candidates different from \(p\). Hence, for every \(c\ne p\),
\(\bar s_R(c)-\eta\le s_R(c)\le\bar s_R(c),\)
and
\(\bar s_R(p)\le s_R(p)\le\bar s_R(p)+\eta.\)
These bounds hold for every surviving set containing \(p\), regardless of the actual elimination history. Also, the mass \(8\) ranking \(p\) first ensures \(s_R(p)\ge8\) throughout any round in which \(p\) survives.
Suppose \(\mathcal S'\) is an exact cover of size \(q\). Shift all cheap mass belonging to its sets, and make no expensive shifts. This costs exactly \(q\).
The initial scores are:
| Candidates | Score |
|---|---|
| \(p\) | \(8+q\) |
| Selected set candidates | \(3\) |
| Unselected set candidates | \(4\) |
| Sentinels | \(3\) |
| Element candidates | \(4\) |
| \(z\) | \(\frac92\) |
| Padding candidates | \(\frac{19}{4}\) or \(5\) |
Thus the first round simultaneously eliminates every sentinel and every selected set candidate.
Each element receives exactly one unit from the selected sets, because they form an exact cover. Each unselected set candidate receives its sentinel’s mass \(3\). The resulting scores are:
Therefore the next round eliminates \(z\) alone.
Afterward, every surviving opponent of \(p\) has score at most \(7\). Indeed, a surviving set candidate receives at most its original mass \(4\) plus sentinel mass \(3\); a surviving element receives its mass \(4\) plus at most three incident membership masses; and a padding candidate receives only its own mass, at most \(5\). No other ranking can transfer to these candidates while \(p\) survives.
Since \(p\)’s score is at least \(8\), every subsequent elimination removes opponents of \(p\). A tied stopping round containing an opponent is impossible. Eventually \(p\) is the sole survivor.
Assume the source instance has no exact cover, and fix an arbitrary feasible allocation.
Consider rounds whose starting surviving set contains at least one sentinel. We prove inductively that such rounds eliminate only sentinels and set candidates.
A surviving sentinel has reference score \(3\), so the minimum actual score is at most \(3\). Until an element or padding candidate is eliminated:
Thus none of these candidates can be eliminated in such a round. This proves the induction. The election cannot stop with equal scores during this phase, since a sentinel scores at most \(3\), whereas \(p\) scores at least \(8\). Each round removes candidates, so eventually all sentinels disappear.
Let \(I\) consist of the indices of set candidates eliminated during this phase, including those eliminated simultaneously with the last sentinels.
If \(d_i\) has already disappeared while \(s_i\) survives, the reference score of \(s_i\) is \(7-y_i\ge6\). Its actual score is consequently greater than \(3\). Therefore any \(s_i\) eliminated during the sentinel phase must have its own sentinel present at the start of its elimination round.
Its reference score in that round is \(4-y_i\). Because its actual score is at most \(3\), the perturbation bound gives
\(4-y_i-\eta\le3,\qquad\text{so}\qquad y_i\ge1-\eta.\)
Write \(r=|I|\). Since \(r\le3q<M\), the budget implies
\(q\ge\sum_i y_i+M\eta\ge r(1-\eta)+M\eta=r+(M-r)\eta\ge r.\)
Hence \(|I|\le q\). This inequality accounts for every expensive shift; it does not assume that expensive types are unbribable.
Immediately after the sentinel phase, every element, every padding candidate, \(p\), and \(z\) still survives. The eliminated set candidates are precisely those indexed by \(I\).
For \(x\in X\), define \(a_I(x)=|\{i\in I:x\in S_i\}|\). Its reference score is \(4+a_I(x)\). Since \(|I|\le q\) and there is no exact cover, some element is uncovered.
At this point:
| Candidates | Actual-score bound |
|---|---|
| Uncovered elements | Between \(4-\eta\) and \(4\) |
| Covered elements | At least \(5-\eta\) |
| Remaining set candidates | At least \(6-\eta\) |
| \(z\) | Between \(\frac92-\eta\) and \(\frac92\) |
| Padding candidates | At least \(\frac{19}{4}-\eta\) |
| \(p\) | At least \(8\) |
Because \(\eta\le\frac18\), every minimum-score candidate is an uncovered element. The next round therefore eliminates a nonempty collection of uncovered elements and no other candidates.
The original mass \(4\) of any such element has prefix \(x\succ z\succ p\). After its elimination, the reference score of \(z\) is at least \(\frac92+4=\frac{17}{2}\). Thus the actual score of \(z\) is at least
\(\frac{17}{2}-\eta\ge\frac{67}{8}>7.\)
As long as \(p\) and \(z\) survive, every other remaining candidate has actual score at most \(7\):
Upward shifts cannot increase these scores. Meanwhile, \(p\) scores at least \(8\), and \(z\)’s score cannot decrease when other candidates are eliminated.
Consequently, while another candidate remains, both \(p\) and \(z\) have strictly greater scores than the minimum. The rule continues eliminating other candidates until only \(p\) and \(z\) remain.
In this final pair, the reference score of \(p\) is
\(8+3q+9q=12q+8,\)
coming from its own type, all cheap types, and all sentinel types. The reference score of \(z\) is
\(12q+9q+\frac92+A=21q+\frac92+A,\)
coming from the element types, membership types, its own type, and all padding types.
Therefore
\(s_{\{p,z\}}(z)-s_{\{p,z\}}(p)\ge9q-\frac72+A-2\eta>0.\)
The inequality is strict because \(q\ge1\), \(A\ge100\), and \(\eta\le\frac18\). Thus \(p\) is eliminated and \(z\) wins alone.
This proves that a successful allocation exists if and only if the source instance has an exact cover. The polynomial construction establishes \(\mathrm{NP}\)-hardness.
Real allocation variables require a certificate argument.
Suppose a successful real allocation exists. Its elimination history is an ordered partition \(E_1,\ldots,E_\ell\) of \(C\setminus\{p\}\), where each \(E_j\) is the nonempty batch eliminated in one round. Let \(R_j=C\setminus\bigcup_{i<j}E_i\), and choose \(e_j\in E_j\).
For this fixed history, each round’s plurality scores are linear functions of the allocation variables, with coefficients in \(\{0,1\}\). Consider the following closed rational linear system:
The successful real allocation has strictly positive gaps between each eliminated batch and every survivor. There are finitely many such gaps, so this system has a solution with \(\delta>0\).
The feasible region is bounded: \(0\le x_{t,k}\le\mu_t\), and \(0\le\delta\le1\). Hence maximizing \(\delta\) attains a positive optimum at a rational vertex.
There are at most \(\tau m+1\) variables and polynomially many constraints, all with polynomial encoding length. Clearing denominators in each row preserves polynomial coefficient bit lengths. A vertex is determined by a full-rank collection of active constraints; Cramer’s rule and the determinant bound give polynomial bit lengths for its coordinates. Thus a successful allocation exists with polynomially encoded rational masses.
A verifier can check its constraints and simulate Hare exactly using rational arithmetic. There are at most \(m-1\) elimination rounds, and all arithmetic has polynomial bit complexity. Therefore the problem belongs to \(\mathrm{NP}\).
Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction handles arbitrary real allocations, respects simultaneous elimination, and establishes hardness under the stated input restrictions. The certificate argument establishes membership in \(\mathrm{NP}\). I found no mathematical gaps or false steps.
The cited source matches the problem used in the reduction: exact cover by three-element sets where every element occurs in exactly three sets is \(\mathrm{NP}\)-complete. This is precisely RXC3 as defined in Section 3 and established in Theorem A.1 of [Gonzalez’s paper](https://www.cs.columbia.edu/~verma/classes/uml/ref/clustering_minimize_intercluster_distance_gonzalez.pdf).
The incidence calculation is correct: three occurrences for each of \(3q\) elements give \(9q\) incidences, and each set contributes three, so the family has \(3q\) members.
The assertion about covers of size at most \(q\) is also correct. Covering \(3q\) elements with at most \(q\) three-element sets requires exactly \(q\) sets and no overlapping incidences. Thus such a cover is exact.
All ranking prefixes end at \(p\); completing them with the remaining candidates after \(p\) gives strict complete rankings. Those appended candidates cannot receive transfers from these types while \(p\) survives.
The price tables meet the task’s requirements. Cheap types have one positive shift costing \(1\), and all other available positive shifts cost the integer \(M=8q\). These tables are nonnegative and nondecreasing.
The total unnormalized mass is correctly computed:
\(3q(3+1+3)+3q\cdot4+8+\frac92=33q+\frac{25}{2}\).
The padding calculation also checks out:
Every listed type has positive mass. Dividing by the power of two \(W\) produces dyadic masses summing to one and the dyadic budget \(q/W\). Scaling masses and budget together preserves both feasibility and every score comparison.
The bound \(W<2(W_0+100)\) gives \(N=O(q)\). Explicitly completing every ranking therefore still requires only polynomial input length. All types place \(p\) within the first four positions.
Assessment: The construction is valid and polynomially encoded.
The budget identity \(\sum_i y_i+M\eta\le q\) correctly includes every positive shift on an expensive type, regardless of its shift distance. Hence \(\eta\le1/8\).
The reference-profile comparison is valid for every surviving set containing \(p\). Moving \(p\) upward preserves the order of all other candidates, so the restricted top candidate either stays unchanged or changes to \(p\). It cannot change from one opponent to another.
Thus each opponent loses between zero and \(\eta\) score relative to the reference profile, while \(p\) gains between zero and \(\eta\). These bounds do not require the actual and reference profiles to have the same elimination history.
The permanently \(p\)-first mass establishes the lower bound \(s_R(p)\ge8\).
Assessment: This argument correctly controls arbitrary fractional shifts, including partial shifts on expensive types.
Shifting all cheap mass for the \(q\) selected sets costs exactly \(q\). The initial score table is correct, and the minimum score is \(3\), attained precisely by the selected set candidates and all sentinels.
Their simultaneous elimination has the stated consequences:
The resulting score of \(p\) is correctly \(8+4q\). The other scores are also correct, and \(z\), with score \(\frac92\), is strictly below every other survivor. Therefore \(z\) is eliminated alone.
Afterward, the asserted opponent bound of \(7\) is valid. The ranking prefixes restrict every possible transfer to the listed recipients or to \(p\); candidates appended after \(p\) cannot receive additional score while \(p\) survives.
Since \(p\) always scores at least \(8\), it is never a minimum-score candidate while an opponent remains. Nor can an all-equal stopping round occur with an opponent present.
Assessment: An exact cover yields a unique win for \(p\) under the specified simultaneous-elimination rule.
The induction is valid. Whenever a sentinel survives, the minimum score is at most \(3\). The lower bounds for elements, padding candidates, \(z\), and \(p\) are all strictly greater than \(3\), using \(\eta\le1/8\). Consequently, only sentinels and set candidates can be eliminated during this phase.
Equal-score termination is impossible because a surviving sentinel scores at most \(3\), whereas \(p\) scores at least \(8\). The phase therefore ends after finitely many eliminations.
A set candidate whose own sentinel has already disappeared has reference score \(7-y_i\ge6\), so it cannot be eliminated during this phase. For an eliminated set candidate whose sentinel remains, the reference score is correctly \(4-y_i\), yielding \(y_i\ge1-\eta\).
Writing \(r=|I|\), the calculation
\(q\ge r(1-\eta)+M\eta=r+(M-r)\eta\ge r\)
is valid because \(r\le3q<8q=M\). Therefore at most \(q\) set candidates disappear during the sentinel phase.
Since there is no exact cover and \(|I|\le q\), some element is uncovered.
The post-phase reference scores and actual-score bounds are correct. Uncovered elements have score at most \(4\); every other category has score strictly greater than \(4\). Thus the next eliminated batch is nonempty and consists entirely of uncovered elements.
Eliminating even one such element gives \(z\) reference score at least \(\frac{17}{2}\). The perturbation bound gives actual score at least \(\frac{67}{8}>7\).
While \(p\) and \(z\) survive, every other candidate has actual score at most \(7\). Meanwhile \(p\) scores at least \(8\), and \(z\)’s plurality score cannot decrease as other candidates disappear. Hence neither can be eliminated or enter an all-equal stopping round while another candidate remains.
The final reference scores are correctly counted:
The difference bound \(9q-\frac72+A-2\eta>0\) is valid throughout the stated parameter range. Thus \(z\) defeats \(p\).
Assessment: Every feasible real allocation fails when the source instance has no exact cover. Both directions of the reduction are established.
The fixed-history linear system correctly represents simultaneous elimination: eliminated candidates have equal scores, and every survivor exceeds that score by at least \(\delta\). Positive \(\delta\) also excludes premature all-equal termination.
A successful allocation supplies positive gaps for every nonterminal round. The bounded rational polyhedron therefore has a positive maximum of \(\delta\), attained at a vertex.
The vertex-size argument is valid: there are polynomially many variables and constraints, row denominators can be cleared with polynomial bit length, and the full-rank active-constraint argument with Cramer’s rule gives polynomially encoded rational coordinates. Lower-dimensional feasible regions do not invalidate this argument.
Exact rational simulation then verifies feasibility and the unique win in polynomial time. The single-candidate case causes no obstruction.
Assessment: Membership in \(\mathrm{NP}\) is established.
No additional mathematical clarification is required.
⟨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.