Answer: polynomial-time solvable
Theorem 14 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn single-peaked electorates, in the unique winner model, for 3-candidate eliminate(veto), 1. weighted-bribery with complete votes is in P. 2. weighted-bribery with top-truncated votes is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed three-candidate axis \(L\), a rational distribution \(\mu\) over voter types \(t=(w,b)\), where \(w\) is the voting weight and \(b\) is a legal top-truncated single-peaked ballot, a preferred candidate \(p\), and a budget \(\beta\), can at most \(\beta\) mass be bribed so that \(p\) is the unique winner under eliminate(veto), using the paper’s round-up and vote-deletion conventions?
Fix a candidate set \(C\) with \(m=3\) and an axis \(\ell\). Legal ballots are nonempty prefixes of strict single-peaked rankings on \(\ell\); omitted candidates are tied below all listed candidates. Complete ballots are allowed.
A society is given by its support: the list of the \(\tau\) types \(t=(w,b)\) with positive mass \(\mu_t\), each mass a binary rational, with \(\sum_t\mu_t=1\). Weights \(w\) are positive integers encoded in binary. Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Given \(p\in C\) and a binary rational budget \(\beta\in[0,1]\), bribery may split each type's mass arbitrarily among legal replacement ballots, preserving its weight. Changing mass \(x\) costs \(x\), independently of weight; unchanged mass costs nothing, and total cost must be at most \(\beta\).
Under \(\operatorname{eliminate}(\mathrm{veto})\), restrict ballots to surviving candidates and discard a ballot once none of its listed candidates survives. In each round apply veto with round-up scoring: listed candidates receive their positional veto score and omitted candidates receive zero; mass \(x\) of weight \(w\) multiplies these scores by \(wx\). Eliminate one minimum-score candidate and repeat until one remains. The winner set contains every possible final survivor over all choices among tied minimum-score candidates; unique victory means this set is \(\{p\}\).
Is deciding whether an admissible bribery makes \(p\) the unique winner polynomial-time solvable or NP-hard? State running times in \(m=3\), \(\tau\), and \(L\).
For finite single-peaked weighted electorates with three candidates, unique-winner bribery is NP-complete with top-truncated ballots and polynomial-time solvable with complete ballots ([Menon–Larson](https://cs.uwaterloo.ca/~klarson/papers/ML.AAAI2016.pdf)). No result settling this exact divisible-mass problem was located.
The divisible-mass problem is polynomial-time solvable for \(m=3\). It reduces to three rational linear programs, each with \(11\tau+1\) variables and \(O(\tau)\) constraints. The resulting bit running time is \(\operatorname{poly}(\tau,L)\).
The proof explicitly handles every permitted choice among tied minimum-score candidates.
Write the axis as \(a\prec_\ell b\prec_\ell c\). The strict single-peaked complete rankings are precisely
\((a,b,c),\quad(b,a,c),\quad(b,c,a),\quad(c,b,a).\)
Indeed, an endpoint peak forces the remaining order toward the opposite endpoint; a middle peak permits either order of the endpoints. Their distinct nonempty prefixes form the legal ballot set \(\mathcal B\):
Thus \(|\mathcal B|=11\).
For each input type \(t=(w_t,b_t)\) and each \(b\in\mathcal B\), introduce a variable \(x_{t,b}\): the mass originating from type \(t\) whose final ballot is \(b\). Exactly the admissible mass transfers satisfy
\[
\]
\(x_{t,b}\geq 0,\qquad \sum_{b\in\mathcal B}x_{t,b}=\mu_t\quad\text{for every }t,\)
together with the budget constraint
\(\displaystyle \sum_t\sum_{\substack{b\in\mathcal B\\b\neq b_t}}x_{t,b}\leq\beta.\)
To justify this representation, any admissible bribery determines these variables by recording its destination masses. Conversely, any feasible assignment specifies an admissible split of every type. The mass \(x_{t,b_t}\) can be left unchanged, while each remaining portion is changed exactly once. Hence the displayed budget counts exactly the required cost and preserves every portion’s weight.
For a surviving set \(U\subseteq C\) with \(|U|\in\{2,3\}\), let \(b|_U\) be the ballot obtained by deleting candidates outside \(U\).
Define \(v_U(b,d)\) to equal \(1\) if \(d\) occurs in \(b|_U\) at a position strictly less than \(|U|\), and \(0\) otherwise. These are exactly the prescribed round-up veto coefficients:
Consequently, the score of \(d\in U\) is the linear function
\(\displaystyle S_U(d;x)=\sum_t\sum_{b\in\mathcal B}w_t\,v_U(b,d)\,x_{t,b}.\)
Restriction and discard depend only on the ballot and the surviving set, so these formulas apply to every elimination branch.
Let the two rivals of \(p\) be \(q\) and \(r\), and abbreviate \(S_C(d;x)\) by \(S(d)\).
Lemma. The winner set is \(\{p\}\) if and only if one of the following three cases holds.
| First-round minimum set | Necessary and sufficient conditions |
|---|---|
| \(\{q\}\) | \(S(p)>S(q)\), \(S(r)>S(q)\), and \(S_{\{p,r\}}(p;x)>S_{\{p,r\}}(r;x)\) |
| \(\{r\}\) | \(S(p)>S(r)\), \(S(q)>S(r)\), and \(S_{\{p,q\}}(p;x)>S_{\{p,q\}}(q;x)\) |
| \(\{q,r\}\) | \(S(q)=S(r)\), \(S(p)>S(q)\), \(S_{\{p,r\}}(p;x)>S_{\{p,r\}}(r;x)\), and \(S_{\{p,q\}}(p;x)>S_{\{p,q\}}(q;x)\) |
Proof. If \(p\) belongs to the first-round minimum set, an allowed tie-breaking choice eliminates \(p\). The eventual survivor is then a rival, contradicting unique victory. Thus the nonempty minimum set must be one of \(\{q\},\{r\},\{q,r\}\). The first-round conditions in the table describe these sets exactly.
Following an allowed first elimination, only \(p\) and one rival remain. Then \(p\) survives every allowed elimination choice exactly when its score strictly exceeds that rival’s score. Equality permits eliminating \(p\), and a smaller score forces its elimination.
For a singleton first-round minimum set there is one resulting pair; for \(\{q,r\}\), both resulting pairs must satisfy the strict comparison. This proves both directions. \(\square\)
Construct one linear program for each row of the table. Include the mass and budget constraints, introduce a variable \(\varepsilon\), and impose
\(0\leq\varepsilon\leq1.\)
Keep the row’s equality, if present. Replace each strict comparison \(A(x)>B(x)\) by
\(A(x)-B(x)\geq\varepsilon,\)
and maximize \(\varepsilon\).
Accept precisely when at least one program is feasible and has optimal value \(\varepsilon^\star>0\).
Correctness. Suppose a bribery satisfies one table row. Its finitely many required score differences are all positive. Let \(\delta\) be their minimum. Taking \(\varepsilon=\min\{1,\delta\}>0\) gives a feasible point of that row’s program.
Conversely, any feasible point with \(\varepsilon>0\) satisfies all the original strict comparisons, as well as the required equality and bribery constraints. The lemma therefore guarantees unique victory.
Finally, each feasible region is compact: conservation and nonnegativity give \(0\leq x_{t,b}\leq\mu_t\), and \(\varepsilon\) lies in \([0,1]\). All constraints are closed. Thus every feasible program attains its optimum; the test does not rely on an unattained supremum or on numerical tolerance.
Each program has \(11\tau+1\) variables and at most \(12\tau+7\) constraint rows, counting nonnegativity constraints and counting each equality as one row.
All coefficients are rational. Score coefficients belong to \(\{0,w_t,-w_t\}\); other coefficients are small integers, and the right-hand sides use the input masses and budget. Each weight appears only a constant number of times in the score rows. Therefore the full dense encoding of each program has size \(O(\tau^2+L)\), including its zero entries.
Rational linear programming admits exact polynomial-time optimization in the binary encoding length, including infeasibility detection and exact comparison of the optimal value with zero. This applies also to programs with equality constraints and lower-dimensional feasible regions. See [MIT’s notes on polynomial-time linear programming](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
More explicitly, if \(T_{\mathrm{LP}}(n,k,B)\) denotes a polynomial bit-time bound for rational linear programming with \(n\) variables, \(k\) constraint rows, and encoding length \(B\), our running time is bounded by
\(O(\tau^2+L)+3T_{\mathrm{LP}}\!\left(11\tau+1,\;12\tau+7,\;O(\tau^2+L)\right)=\operatorname{poly}(\tau,L),\qquad m=3.\)
A positive instance also has a rational successful bribery of polynomial encoding length: a bounded rational polytope has an optimal vertex, whose coordinates have polynomial bit length by Cramer’s rule and determinant bounds.
The finite-electorate hardness result in [Menon–Larson](https://cs.uwaterloo.ca/~klarson/papers/ML.AAAI2016.pdf) does not transfer to this model. Here arbitrary splitting makes the transfer constraints linear, and three candidates leave only three first-round cases to check.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned divisible-mass problem. It establishes polynomial-time solvability for \(m=3\), with three rational linear programs of \(11\tau+1\) variables and at most \(12\tau+7\) constraint rows each. No major or minor mathematical issues were found.
The enumeration is correct. On the axis \(a\prec_\ell b\prec_\ell c\), an endpoint peak forces the remaining candidates’ order, while a middle peak permits either endpoint order. This gives exactly the four listed complete rankings.
Their distinct nonempty prefixes consist of three singleton ballots, four length-two ballots, and four complete ballots. Thus \(|\mathcal B|=11\). No legal ballot is missing, and none is counted twice.
The transfer variables correctly retain each portion’s originating weight. Nonnegativity and the equalities
\[
\sum_{b\in\mathcal B}x_{t,b}=\mu_t
\]
preserve each type’s mass.
The budget expression correctly charges every portion whose destination ballot differs from its original ballot, independently of weight. Mass assigned to the original ballot can remain unchanged at zero cost.
Both directions of the representation are justified: every admissible final allocation yields such variables, and every feasible assignment specifies an admissible allocation. Arbitrary divisibility introduces no integrality restriction.
The coefficient definition agrees with the specified scoring rule:
In particular, a singleton ballot awards its listed candidate score one while at least two candidates survive.
Restriction and discard depend solely on the surviving set and the ballot. A discarded ballot cannot later become nonempty because surviving sets only shrink. Consequently, the displayed linear score formula correctly describes every relevant elimination branch.
The lemma exhausts all possibilities.
If \(p\) is initially a minimum-score candidate, eliminating \(p\) is permitted and necessarily produces a rival winner. Therefore unique victory requires the initial minimum set to exclude \(p\), leaving exactly the three sets listed in the table.
The table’s initial comparisons describe those minimum sets exactly. After the first elimination, \(p\) wins under every permitted tie choice precisely when its score strictly exceeds the remaining rival’s score. Equality permits eliminating \(p\); a smaller score forces that elimination.
When both rivals are initially tied for minimum, either may be eliminated, so both resulting two-candidate comparisons are necessary and sufficient. The proof handles all ties, including an initial three-way tie and a second-round tie.
The common-margin construction is valid. Each table row has finitely many strict comparisons. At any allocation satisfying that row, their minimum difference is positive, so the stated choice of \(\varepsilon\) gives a feasible positive margin.
Conversely, any feasible positive margin implies every required strict comparison. The equality in the tied-rival case remains enforced exactly.
The compactness argument is also correct: conservation bounds every transfer variable, the margin variable is bounded, and all constraints are closed. Every feasible program therefore attains its optimum. Acceptance based on an exactly positive optimum correctly decides existence, including when feasible margins are extremely small.
The variable count is exactly \(11\tau+1\).
For the largest program, the constraint count is
\[
11\tau+\tau+1+2+1+3=12\tau+7:
\]
transfer nonnegativity, conservation, budget, two margin bounds, the rival-score equality, and three margin comparisons. Each singleton-minimum program has one fewer row.
The coefficient and encoding bounds are sound. Score-difference coefficients are zero or signed input weights, and each weight is repeated only constantly many times in score rows. The remaining dense entries contribute \(O(\tau^2)\) bits, while the input-dependent coefficients and right-hand sides contribute \(O(L)\).
The invoked rational-LP theorem is stated adequately: exact optimization and infeasibility detection take polynomial bit time, including with equalities and lower-dimensional feasible regions. Its hypotheses are satisfied. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time LP algorithms, precision, lower-dimensional feasibility, and optimization.
The stated running time is therefore justified:
\[
O(\tau^2+L)+3T_{\mathrm{LP}}\!\left(11\tau+1,12\tau+7,O(\tau^2+L)\right)
=\operatorname{poly}(\tau,L),\qquad m=3.
\]
The polynomial-size rational witness claim also follows from the stated bounded-polytope vertex property and determinant bounds. Finite-electorate hardness creates no contradiction because this proof addresses arbitrary mass splitting.
No mathematical repair or additional clarification 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.