Answer: Polynomial-time solvable: the exact minimum bribery cost is computable in time polynomial in \(m,\tau,L\).
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor single-peaked electorates, weakCondorcet- weighted-$bribery, weakCondorcet-negative-weighted- bribery, and weakCondorcet-negative-weighted-$bribery are NP-complete, and the remaining five weakCondorcet bribery cases are in P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C\), a societal order \(L\), a target \(p\), and a rational distribution \(\mu\) over supported types \(t=(P_t,w_t,q_t)\), where \(P_t\) is an \(L\)-single-peaked ranking and \(w_t,q_t\) are positive integer vote weights and bribe prices, choose transfers \(x_{t,Q}\ge 0\) to \(L\)-single-peaked rankings \(Q\), preserving \(\sum_Q x_{t,Q}=\mu_t\). Minimize \(\sum_t q_t\sum_{Q\ne P_t}x_{t,Q}\) subject, for each \(c\ne p\), to \(\sum_t w_t\sum_Q x_{t,Q}(\mathbf{1}[p\succ_Q c]-\mathbf{1}[c\succ_Q p])\ge 0\). What is the complexity of computing this minimum in \(m\), \(\tau\), and the input bit lengths?
Let \(C\) be a nonempty candidate set with \(m=|C|\), let \(\mathcal L\) be a societal linear order on \(C\), and let \(p\in C\).
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\).
Each type is \(t=(P_t,w_t,q_t)\), where \(P_t\) is a strict \(\mathcal L\)-single-peaked ranking and \(w_t,q_t\) are positive integers encoded in binary. Weight and price remain attached to transferred mass.
Let \(\mathcal S(\mathcal L)\) contain all strict \(\mathcal L\)-single-peaked rankings. A bribery chooses real transfers \(x_{t,Q}\geq 0\), for \(Q\in\mathcal S(\mathcal L)\), with \(\sum_Q x_{t,Q}=\mu_t\). Its cost is \(\sum_t q_t\sum_{Q\neq P_t}x_{t,Q}\); unchanged mass is free, and changed mass may rank \(p\) first.
The target must become a weak Condorcet winner: for every \(c\in C\setminus\{p\}\), require \(\sum_t w_t\sum_Q x_{t,Q}(\mathbf 1[p\succ_Q c]-\mathbf 1[c\succ_Q p])\geq 0\). Pairwise ties are permitted, and no unique winner is required.
Can the exact minimum bribery cost be computed in polynomial time in \(m,\tau,L\), or is deciding whether it is at most a given binary rational budget \(B\geq 0\) NP-hard? Here \(L\) is the total input bit length, including the budget for the decision problem.
For discrete single-peaked electorates, weighted priced bribery to make a target a weak Condorcet winner is NP-complete; each voter is indivisible and every replacement ranking must respect the given societal order. This classification concerns indivisible voters and does not establish a classification for divisible mass.
The exact minimum bribery cost is computable in polynomial time in \(m,\tau,L\). The problem reduces to a fractional knapsack problem on the types whose peaks lie on one side of \(p\).
The argument below uses divisibility explicitly; it does not apply to indivisible voters.
Write the societal order as \(c_1\mathrel{\mathcal L}\cdots\mathrel{\mathcal L}c_m\), and let \(p=c_h\). The peak of a strict ranking is its first-ranked candidate. Single-peakedness means that, on either side of the peak, candidates closer to the peak are preferred to candidates farther away.
For any society of single-peaked rankings, define:
Here a mass \(z\) with attached weight \(w\) contributes \(wz\). Because transfers preserve each type’s mass and weight, \(W=\sum_t w_t\mu_t>0\) is invariant under bribery.
Lemma. The candidate \(p\) is a weak Condorcet winner exactly when \(A\leq W/2\) and \(R\leq W/2\).
Proof. Suppose first that \(h>1\). A ranking prefers \(c_{h-1}\) to \(p\) exactly when its peak lies strictly left of \(p\):
Consequently, \(p\)’s pairwise margin against \(c_{h-1}\) is \(W-2A\). Likewise, when \(h<m\), its margin against \(c_{h+1}\) is \(W-2R\). Thus weak Condorcet victory requires both stated inequalities. If a neighbor is absent, the corresponding side mass is zero, so its inequality holds automatically.
Conversely, fix any \(c_j\) with \(j<h\). Every ranking whose peak has index at least \(h\) prefers \(p\) to \(c_j\), by monotonicity on the left side of its peak. Therefore, the weighted mass preferring \(c_j\) to \(p\) is at most \(A\). Since rankings are strict, \(p\)’s margin against \(c_j\) is at least \(W-2A\), which is nonnegative if \(A\leq W/2\).
The symmetric argument gives a margin of at least \(W-2R\) against every candidate right of \(p\). This proves sufficiency. For \(m=1\), the winner condition is vacuous and both side masses are zero. ∎
Fix a single-peaked ranking \(Q^\star\) with peak \(p\). Such a ranking exists: rank \(p\) first, then the candidates to its left in decreasing index order, then those to its right in increasing index order. This ranking is monotone away from its peak on both sides.
Consider any feasible bribery. For every type whose original peak differs from \(p\), let \(y_t=\sum_{Q\neq P_t}x_{t,Q}\), its changed mass. Replace all that changed mass by \(Q^\star\), retaining the remaining mass at \(P_t\).
This preserves cost: \(Q^\star\neq P_t\), so the new cost for this type is exactly \(q_ty_t\). It cannot decrease any pairwise margin involving \(p\), since each changed portion now contributes \(+w_t\) per unit mass against every opponent, the maximum possible contribution.
For a type whose original peak is already \(p\), simply retain all its mass at \(P_t\). Its contribution against every opponent is already maximal, and this removes any cost incurred by changing it.
Thus every feasible bribery admits a feasible replacement of no greater cost in which only types originally having peaks different from \(p\) are changed, and all changed mass goes to \(Q^\star\).
Let \(T_-\) and \(T_+\) be the original types with peaks respectively left and right of \(p\), and define \(A=\sum_{t\in T_-}w_t\mu_t\) and \(R=\sum_{t\in T_+}w_t\mu_t\).
In a bribery of the normalized form just proved, the resulting side masses are \(A'=A-\sum_{t\in T_-}w_ty_t\) and \(R'=R-\sum_{t\in T_+}w_ty_t\), with \(0\leq y_t\leq\mu_t\).
By the lemma, feasibility is therefore equivalent to
\( \sum_{t\in T_-}w_ty_t\geq A-W/2 \)
and
\( \sum_{t\in T_+}w_ty_t\geq R-W/2. \)
These conditions and the dominance argument establish that optimizing over these variables gives exactly the original minimum.
The side masses satisfy \(A+R\leq W\), because the remaining weighted mass has peak \(p\). Hence they cannot both exceed \(W/2\).
If both are at most \(W/2\), the initial society already makes \(p\) a weak Condorcet winner, and the minimum cost is zero.
Otherwise, let \(T\) be the types on the unique side whose weighted mass \(H\) exceeds \(W/2\), and put \(D=H-W/2>0\).
Changing mass on the other side is unnecessary: its winner inequality already holds, and deleting such changes restores that side only to its original, permissible mass. Deleting those changes also reduces cost.
The exact optimization is consequently
\( \min \sum_{t\in T}q_ty_t \), subject to \(0\leq y_t\leq\mu_t\) and \(\sum_{t\in T}w_ty_t\geq D\).
It is feasible, since the available weighted mass is \(H>D\).
For each \(t\in T\), define its weighted capacity \(a_t=w_t\mu_t\), its price per unit of weighted mass \(r_t=q_t/w_t\), and the chosen weighted amount \(z_t=w_ty_t\).
Sort these types so that \(r_1\leq\cdots\leq r_n\). Let \(S_i=\sum_{k=1}^{i}a_k\), with \(S_0=0\), and let \(j\) be the least index satisfying \(S_j\geq D\).
Choose \(z_i^\star=a_i\) for \(i<j\), \(z_j^\star=D-S_{j-1}\), and \(z_i^\star=0\) for \(i>j\). These amounts satisfy all capacity bounds and have total exactly \(D\).
The resulting cost is
\( \displaystyle K^\star=\sum_{i<j}q_i\mu_i+\frac{q_j}{w_j}\left(D-\sum_{i<j}w_i\mu_i\right). \)
To prove optimality, take any feasible vector \(z\). Its cost difference from the greedy vector is
\( \displaystyle \sum_i r_i z_i-\sum_i r_i z_i^\star=\sum_i(r_i-r_j)(z_i-z_i^\star)+r_j\left(\sum_i z_i-D\right). \)
Every term on the right is nonnegative:
Thus no feasible vector has smaller cost. Setting \(y_i^\star=z_i^\star/w_i\) and transferring that mass to \(Q^\star\) realizes the minimum in the original bribery model.
Only the boundary type may require a proper fraction of its mass. This is precisely where divisibility matters.
Write the input masses as \(\mu_t=u_t/v_t\), and let \(V=\prod_t v_t\). The binary length of \(V\) is at most the sum of the binary lengths of the input denominators, hence is \(O(L)\).
All weighted masses and cumulative capacities can be represented with denominator \(V\); \(D\) can be represented with denominator \(2V\). Their numerators have polynomial bit length because they are sums of at most \(\tau\) products of input integers and \(V/v_t\).
Sorting rates requires only exact integer comparisons: compare \(q_i/w_i\) and \(q_k/w_k\) by comparing \(q_iw_k\) and \(q_kw_i\).
Finally, the displayed optimum has a possible common denominator \(2Vw_j\), also of polynomial bit length. Thus exact arithmetic throughout uses numbers of polynomial bit length.
Finding peaks takes \(O(m\tau)\) ranking inspections, and sorting uses \(O(\tau\log\tau)\) comparisons. The remaining arithmetic is polynomial in \(L\) and \(\tau\). Therefore the exact minimum is computable in polynomial time in \(m,\tau,L\); comparison with a binary rational budget \(B\) is also polynomial-time.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct. The argument establishes the exact minimum cost, proves that its solution is realizable by an allowed bribery, and verifies polynomial bit complexity. No major or minor mathematical issues were found.
The characterization of weak Condorcet victory is correct.
For an existing left neighbor \(c_{h-1}\), single-peakedness implies that a ranking prefers \(c_{h-1}\) to \(p\) exactly when its peak lies strictly left of \(p\). Thus the weighted mass opposing \(p\) in this comparison is exactly \(A\), and the margin is \(W-2A\). The symmetric statement for the right neighbor gives \(W-2R\).
For any more distant candidate left of \(p\), every ranking with peak at or right of \(p\) prefers \(p\) to that candidate. Hence the opposing weighted mass is at most \(A\), establishing the claimed lower bound on the margin. The symmetric reasoning applies on the right.
The proof correctly handles absent neighbors and the case \(m=1\). Nonnegative margins correspond precisely to the required weak victory, including ties.
The proposed ranking \(Q^\star\) exists and is single-peaked: its restrictions to each side of \(p\) rank candidates in order of increasing distance along that side.
For a type whose original peak differs from \(p\), one has \(Q^\star\neq P_t\). Redirecting all its changed mass to \(Q^\star\) therefore preserves its cost exactly. Its contribution against every opponent becomes maximal, so no margin decreases.
For a type originally peaking at \(p\), restoring all its mass to \(P_t\) also maximizes every relevant pairwise contribution and removes its change cost.
These operations preserve each type’s mass and attached weight and price. Consequently, every feasible bribery has a normalized feasible replacement of no greater cost. Conversely, every feasible normalized choice is an allowed original bribery. The asserted equality of optimization values follows.
The inequality \(A+R\leq W\) is valid because the omitted weighted mass consists of types peaking at \(p\). Therefore both side masses cannot strictly exceed \(W/2\).
When neither exceeds \(W/2\), zero cost is feasible and optimal because all costs are nonnegative.
When exactly one side exceeds \(W/2\), removing changes on the other side restores its original side mass, which already satisfies its inequality. In normalized form this does not affect the excessive side’s mass. Thus restricting the optimization to the excessive side is justified.
The demand \(D=H-W/2\) is positive and strictly less than the available capacity \(H\), since \(W>0\). The resulting fractional optimization is feasible.
The substitution \(z_t=w_ty_t\) preserves the capacity constraints and transforms the objective into \(\sum_t r_tz_t\), with \(r_t=q_t/w_t>0\).
The boundary index \(j\) exists because total capacity is \(H>D\). Its minimality gives \(S_{j-1}<D\leq S_j\), so the proposed boundary amount satisfies its capacity bounds. The greedy allocation has total weighted amount exactly \(D\).
The displayed cost-difference identity is algebraically correct. Each summand has the claimed sign, including tied rates, and the final term is nonnegative for every feasible allocation. This proves optimality even when a competing allocation exceeds the demand.
Dividing by the positive weights gives permitted real transfers. The displayed optimum formula correctly converts full capacities to costs \(q_i\mu_i\).
The common-denominator argument is valid. The product \(V\) has bit length bounded by the sum of input denominator bit lengths. Weighted masses and their sums consequently have polynomial-size integer representations, and introducing \(W/2\) requires only the additional factor \(2\).
Rate comparisons use exact cross-products of positive integers of polynomial bit length. The optimum has a common denominator \(2Vw_j\), with a numerator of polynomial bit length. Thus the arithmetic operations and their intermediate representations remain polynomially bounded.
The stated number of ranking inspections, sorting comparisons, and arithmetic operations is polynomial in the specified parameters. Comparing the exact rational optimum with the supplied rational budget is also polynomial-time.
None is required. The proof resolves the divisible-mass task and correctly distinguishes its conclusion from the stated indivisible-voter classification.
⟨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.