d4-conf-atal-2013-0282 (d4-conf-atal-2013-0282)

Given candidates \(C\), \(k\) as part of the input, a rational distribution \(\mu\) over finitely supported types \(\theta=(R_\theta,\pi_\theta)\), and a candidate \(c\) who is initially the unique \(k\)-approval winner, what is the minimum total cost of transferring mass from each type to output rankings so that some \(a\ne c\) has \(k\)-approval score at least that of \(c\)? Each unit transferred from \(\theta\) to ranking \(R'\) costs \(d_{\pi_\theta}(R_\theta,R')\), the minimum adjacent-swap price for that conversion, and transfers preserve each type's total mass.

Let \(C\) contain \(m\geq 2\) candidates, let \(1\leq k<m\) be part of the input, and let \(c\in C\) initially be the unique \(k\)-approval winner.
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\).
Each type \(\theta=(R_\theta,\pi_\theta)\) consists of a strict linear ranking and an explicitly listed function \(\pi_\theta:C\times C\to\mathbb Z_{\geq0}\), with entries encoded in binary. Swapping adjacent candidates with \(x\) immediately above \(y\) costs \(\pi_\theta(x,y)\); symmetry is not required, and prices remain fixed throughout a swap sequence.
For any output ranking \(R'\), let \(d_{\pi_\theta}(R_\theta,R')\) be the minimum total price of an admissible adjacent-swap sequence converting \(R_\theta\) into \(R'\).
A transfer consists of real masses \(x_{\theta,R'}\geq0\) satisfying \(\sum_{R'}x_{\theta,R'}=\mu(\theta)\). Its cost is \(\sum_{\theta,R'}x_{\theta,R'}d_{\pi_\theta}(R_\theta,R')\); scores are weighted by transferred mass. It succeeds if some \(a\neq c\) has score at least that of \(c\), so a tie suffices without tie-breaking.
Is deciding whether the minimum successful transfer cost is at most an input binary rational budget \(B\geq0\) in \(\mathrm P\), or is it NP-hard? State running times in \(m,\tau,k,L\), where \(L\) is the total input bit length.
Discretely, general-cost destructive swap bribery for input \(k\)-approval is NP-complete even with two voters. [Source](https://www.ifaamas.org/Proceedings/aamas2013/docs/p415.pdf)
For continuous constructive swap bribery, general-cost \(k\)-approval is polynomial-time solvable for each fixed \(k\); this concerns making a designated candidate a winner, rather than destroying uniqueness. [Source](https://arxiv.org/html/2608.25444v1)
No result settling the destructive mass-transfer problem above was located.

Result. The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau=2\) and both types have mass \(\frac12\).

For general inputs, an exact algorithm runs in
\[ \bigg(\tau m^2\binom{m}{k}\bigg)\operatorname{poly}(L) +m\operatorname{poly}(\tau,L). \]
Thus it is polynomial-time solvable for every fixed \(k\), and also for every fixed \(m-k\).

1. Directed swap distance

For two rankings \(R,R'\), define their directed inversion set by
\[ I(R,R')=\{(x,y):x\succ_R y,\ y\succ_{R'}x\}. \]
Then
\[ d_\pi(R,R')=\sum_{(x,y)\in I(R,R')}\pi(x,y). \]

Indeed, each inverted pair must change relative order. Its first crossing swaps \(x\) immediately above \(y\), costing \(\pi(x,y)\). Nonnegative prices therefore give the stated lower bound.

For the upper bound, repeatedly swap an adjacent pair whose order disagrees with \(R'\). Each swap decreases the number of disagreements by one. A corrected pair is never swapped again, so each initially inverted pair crosses exactly once, in its initial direction. This proves the formula, including for asymmetric prices.

Consequently, all destination costs are integers and can be computed using \(O(m^2)\) arithmetic operations.

2. A polynomial-time reduction

We use the following known \(\mathrm{NP}\)-complete problem: given one ranking \(R\) on a candidate set \(A\), nonnegative integer swap prices \(\pi\), a designated candidate \(p\), an approval parameter \(\ell\), and an integer budget \(\delta\), decide whether \(p\) can be moved into the top \(\ell\) positions within budget. Hardness holds with \(2\leq\ell<|A|\) and \(p\) initially below those positions: the cited reduction places \(p\) last. With one voter, being an \(\ell\)-approval co-winner is exactly membership in the top \(\ell\). [Elkind, Faliszewski, and Slinko, *Swap Bribery*, Theorem 4.5](https://arxiv.org/pdf/0905.3885#page=10).

Write \(n=|A|\), and define
\[ q=\min\{d_\pi(R,R'):p\text{ belongs to the top }\ell\text{ positions of }R'\}. \]
Thus the source instance is affirmative exactly when \(q\leq\delta\).

Let
\[ P=\sum_{x\succ_R y}\pi(x,y), \qquad M=4(P+\delta+1). \]
Moving \(p\) to the first position shows that \(q\leq P\). In particular,
\[ M>2q \quad\text{and}\quad M>2\delta. \]

Introduce a new candidate \(c\) and a disjoint dummy set \(D\) of size \(n\). Fix an order of \(D\). The new election uses
\[ C=A\cup\{c\}\cup D,\qquad m=2n+1,\qquad k=\ell+1, \qquad B=\frac{\delta}{2}. \]

There are two types, each of mass \(\frac12\):

• Type \(1\) has ranking \(R_1=c\succ R\succ D\). Its prices equal \(\pi(x,y)\) when \(x,y\in A\), and equal \(M\) otherwise.
• Type \(2\) has ranking \(R_2=c\succ p\succ D\succ(A\setminus\{p\})\). Every swap costs \(M\).

All rankings and prices are explicitly listed, and the construction has polynomial encoding length.

Initially, \(c\) has score \(1\). Candidate \(p\) receives approval only from type \(2\). Every other original candidate receives approval only from type \(1\), while every dummy receives approval only from type \(2\). Hence every opponent has score at most \(\frac12\), and \(c\) is the unique winner.

We will prove the stronger identity
\[ \text{minimum successful transfer cost}=\frac q2. \]

3. Upper bound

Choose an original ranking \(R'\) attaining \(q\). Transfer all type-\(1\) mass to \(c\succ R'\succ D\), and leave type \(2\) unchanged.

The inversion formula shows that the destination cost for type \(1\) is exactly \(q\). Both \(c\) and \(p\) then have score \(1\), so the transfer succeeds at cost \(\frac q2\).

4. Lower bound for arbitrary real transfers

Call a type-\(1\) destination *protected* if it inverts any pair that is not wholly contained in \(A\). Such a destination costs at least \(M\), by the inversion formula.

Every unprotected type-\(1\) destination has the form
\[ c\succ R'\succ D, \]
with the fixed dummy order.

Call a type-\(2\) destination protected if it differs from \(R_2\). Every such destination contains an inversion and therefore costs at least \(M\).

For any transfer, let \(t_1,t_2\) denote the masses sent to protected destinations of the respective types, and put
\[ t=t_1+t_2. \]
Its cost is at least \(Mt\).

*Opponents other than \(p\).* Fix \(a\in C\setminus\{c,p\}\). On unprotected destinations, \(a\) can receive approval from at most one of the two types: original candidates from type \(1\), and dummies from type \(2\). Thus its approval from unprotected mass is at most \(\frac12\). Its approval from protected mass is at most \(t\).

Candidate \(c\) is approved on all unprotected mass, so
\[ \operatorname{score}(a)-\operatorname{score}(c) \leq \frac12+t-(1-t) =-\frac12+2t. \]
If \(a\) ties or beats \(c\), necessarily \(t\geq\frac14\). The transfer then costs at least
\[ \frac M4>\frac q2. \]

*Opponent \(p\).* Let \(y\) be the unprotected type-\(1\) mass whose destination approves \(p\). Every such destination costs at least \(q\) per unit mass.

On unprotected type-\(1\) mass, \(c\) is always approved. Therefore this mass contributes
\[ y-\left(\frac12-t_1\right) \]
to the score of \(p\) minus that of \(c\). Unprotected type-\(2\) mass contributes zero, since both candidates are approved there. Protected mass contributes at most \(t\). Consequently,
\[ \operatorname{score}(p)-\operatorname{score}(c) \leq y-\frac12+t_1+t. \]
If \(p\) ties or beats \(c\), then
\[ y\geq\frac12-t_1-t\geq\frac12-2t. \]

The protected mass and the mass counted by \(y\) are disjoint. Nonnegative costs therefore imply
\[ \begin{aligned} \operatorname{cost} &\geq qy+Mt\\ &\geq q\left(\frac12-2t\right)+Mt\\ &=\frac q2+(M-2q)t\\ &\geq\frac q2. \end{aligned} \]

This argument applies to arbitrary real masses. Together with the upper bound, it proves the claimed optimum identity. Therefore
\[ \text{minimum successful cost}\leq B \quad\Longleftrightarrow\quad q\leq\delta. \]
The reduction proves \(\mathrm{NP}\)-hardness with exactly two supported types.

5. Exact algorithm and running time

Fix a type \(\theta\) and an approval set \(S\subseteq C\) of size \(k\). Form the ranking \(\widehat R_{\theta,S}\) by listing \(S\) first and its complement second, preserving their respective internal orders from \(R_\theta\).

Every destination approving exactly \(S\) must invert every initially ordered pair \(x\succ_{R_\theta}y\) with \(x\notin S\) and \(y\in S\). The ranking \(\widehat R_{\theta,S}\) inverts precisely these pairs. Hence its cost
\[ Q_\theta(S)= \sum_{\substack{x\succ_{R_\theta}y\\x\notin S,\ y\in S}} \pi_\theta(x,y) \]
is the minimum cost of obtaining approval set \(S\).

For a fixed challenger \(a\neq c\), a destination contributes only one of three values to its score difference:
\[ h=\mathbf1[a\in S]-\mathbf1[c\in S]\in\{-1,0,1\}. \]
For each achievable value, compute
\[ D_{\theta,a,h} =\min_{\substack{|S|=k\\ \mathbf1[a\in S]-\mathbf1[c\in S]=h}} Q_\theta(S). \]

The minimum cost of making \(a\) tie or beat \(c\) is exactly the following linear program, omitting unachievable states:
\[ \begin{aligned} \text{minimize}\quad& \sum_{\theta,h}D_{\theta,a,h}y_{\theta,h}\\ \text{subject to}\quad& \sum_h y_{\theta,h}=\mu(\theta) &&\text{for every }\theta,\\ &\sum_{\theta,h}h\,y_{\theta,h}\geq0,\\ &y_{\theta,h}\geq0. \end{aligned} \]

To verify equivalence, aggregate any transfer according to its type and score-difference value \(h\). Its cost is at least the displayed objective. Conversely, implement each variable using a ranking attaining \(D_{\theta,a,h}\). This preserves the required score difference and attains that objective.

Enumerating all \(\binom mk\) approval sets computes all necessary costs and minima in \(O(\tau m^2\binom mk)\) arithmetic operations. Each cost has polynomial bit length in \(L\). There are \(m-1\) linear programs, each with at most \(3\tau\) variables and \(O(\tau)\) constraints. Exact rational linear programming therefore gives the running time stated above.

Since
\[ \binom mk\leq m^{\min\{k,m-k\}}, \]
this also yields a running time of
\[ m^{\min\{k,m-k\}+O(1)}\operatorname{poly}(\tau,L). \]
Only the listed \(\tau\) types are processed.

6. Membership in \(\mathrm{NP}\)

For any challenger \(a\), the feasible region of its linear program is compact. An optimum therefore exists at a vertex.

Such a vertex has at most \(\tau+1\) positive variables. Indeed, with more positive variables, their columns are linearly dependent in the \(\tau\) mass equations together with the score-difference row. A sufficiently small perturbation in both directions preserves feasibility, contradicting extremality.

The constraint coefficients belong to \(\{-1,0,1\}\), and the right-hand sides are the input rational masses. Standard determinant bounds, or Cramer’s rule after clearing denominators, give polynomial bit length for the positive variables.

An affirmative instance consequently has a certificate consisting of a challenger, at most \(\tau+1\) type–destination rankings, and rational transferred masses of polynomial bit length. The verifier checks mass conservation, computes destination costs using the inversion formula, and checks the budget and score inequality, all in polynomial time.

Thus the decision problem is \(\mathrm{NP}\)-complete.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The reduction establishes NP-hardness for exactly two supported types of equal mass, including arbitrary real transfers. The algorithm and certificate argument establish the stated upper bounds and NP membership. I found no major or minor mathematical issues requiring repair.

• Directed swap distance.

The inversion formula is correct for the directed, fixed-price model in USER_TASK. Each initially inverted pair must cross at least once, and its first crossing has its initial direction. Nonnegative prices justify summing these necessary costs as a lower bound, even if a sequence includes additional crossings.

The proposed upper-bound procedure is valid: swapping an adjacent disagreement changes only that pair’s relative order and removes one disagreement. A corrected pair cannot subsequently be selected by this procedure. Thus it reaches the destination while crossing each required pair exactly once.

Zero prices and asymmetric prices cause no exception. Computing the inversion sum takes \(O(m^2)\) arithmetic operations; its bit length is polynomial in the explicitly encoded input.

• The cited hardness premise.

The citation is accurate and applicable. Theorem 4.5 establishes NP-completeness for input approval parameter with a single voter. Its reduction places the preferred candidate last, uses nonnegative integer prices, and sets the approval parameter to \(N+1\) on \(2N+1\) candidates. This supports the asserted restriction \(2\leq\ell<|A|\). The paper uses the nonunique-winner convention and the same directed adjacent-swap model. [Elkind, Faliszewski, and Slinko, *Swap Bribery*, Theorem 4.5](https://arxiv.org/pdf/0905.3885#page=10).

With one voter, membership in the approved positions is indeed equivalent to being a co-winner. Consequently, the source question is exactly whether \(q\leq\delta\), as the prover states.

• Reduction parameters and encoding.

The bound \(q\leq P\) is justified by moving \(p\) to first place: the required crossings are a subset of the initially ordered pairs summed in \(P\).

The choice \(M=4(P+\delta+1)\) gives both \(M>2q\) and \(M>2\delta\). It also gives the stronger inequality used later, \(M/4>q/2\).

The target parameters satisfy the task’s domain restrictions. In particular, \(m=2n+1\) and \(k=\ell+1\) give \(1\leq k<m\). The dummy set is large enough that the approved positions in type \(2\) contain no member of \(A\setminus\{p\}\).

The explicitly listed rankings and price tables have polynomial size. Summation to obtain \(P\), construction of \(M\), and representation of \(B=\delta/2\) require only polynomial bit length and time.

• Initial uniqueness and upper bound.

Both types approve \(c\), so its initial score is \(1\). Because \(p\) initially lies below the first \(\ell\) positions of \(R\), type \(1\) does not approve it. Type \(2\) approves it.

Every other original candidate can initially receive approval only from type \(1\), and every dummy only from type \(2\). Hence each opponent’s score is at most \(1/2\), establishing the required initial unique winner.

A ranking attaining \(q\) exists because there are finitely many original rankings. Embedding it between \(c\) and the fixed dummy block introduces no inversions outside \(A\), so its type-\(1\) cost is exactly \(q\). Transferring mass \(1/2\) to it makes both \(p\) and \(c\) score \(1\), at total cost \(q/2\). This is a successful tie under the task’s convention.

• Protected destinations.

A protected type-\(1\) destination necessarily incurs at least one inversion priced \(M\). Conversely, absence of such inversions forces \(c\) first, every original candidate above every dummy, and the original dummy order. The stated characterization of unprotected destinations is therefore exact.

Any changed type-\(2\) ranking has a nonempty inversion set, and every such inversion costs \(M\). Thus its protected destinations also cost at least \(M\).

The aggregate protected mass \(t=t_1+t_2\) consequently incurs cost at least \(Mt\). This argument concerns destination costs directly and does not impose any discreteness on transferred masses.

• Lower bound for opponents other than \(p\).

For each such opponent, unprotected approval comes from at most one type, whose total available mass is \(1/2\). Protected approval is at most \(t\). Meanwhile, \(c\) receives approval from all unprotected mass, of total mass \(1-t\).

Therefore the displayed inequality
\[ \operatorname{score}(a)-\operatorname{score}(c)\leq-\frac12+2t \]
is valid. Success by this opponent requires \(t\geq1/4\), giving cost at least \(M/4>q/2\).

The estimate need not be tight to establish the claimed lower bound.

• Lower bound for opponent \(p\).

Every unprotected type-\(1\) destination counted by \(y\) puts \(p\) in the first \(\ell\) positions of its original-candidate block, so its per-unit cost is at least \(q\).

The score accounting is correct:

• Unprotected type-\(1\) mass contributes \(y-(1/2-t_1)\).
• Unprotected type-\(2\) mass contributes zero.
• Protected mass contributes at most \(t\).

Thus success requires \(y\geq1/2-t_1-t\geq1/2-2t\).

The two charged portions of mass are disjoint, making \(\operatorname{cost}\geq qy+Mt\) valid. Substitution yields the claimed bound \(q/2+(M-2q)t\geq q/2\).

This remains valid when \(1/2-2t\) is negative, since \(q\geq0\); it also covers \(q=0\). There is no hidden assumption that a transfer moves an entire type.

Together with the upper bound, this establishes the exact optimum \(q/2\) and the required equivalence with the source budget.

• Approval-set minimization and linear programming.

For a prescribed approval set \(S\), all initially ordered pairs with an unapproved candidate above an approved candidate must invert. The stable two-block ranking in the output inverts exactly those pairs. Nonnegative prices therefore establish that \(Q_\theta(S)\) is the minimum destination cost for that approval set.

For a fixed challenger, its difference from \(c\) depends only on the state \(h\in\{-1,0,1\}\). Minimizing costs separately within these states loses no relevant information.

Both directions of the LP equivalence are explicitly justified: aggregation gives a lower bound, and selecting a minimizing destination for each state realizes the objective. Omitting unachievable states correctly handles boundary cases, including \(m=2\), \(k=1\).

• Running time.

The enumeration bound \(O(\tau m^2\binom{m}{k})\) is consistent with computing each set cost and updating the state minima for all challengers. These updates do not require another multiplicative factor of \(m\) beyond the stated quadratic work per set.

Each challenger’s LP has at most \(3\tau\) variables and \(O(\tau)\) constraints. Its rational coefficients, masses, and computed integer costs have polynomial bit length, so polynomial-time rational LP algorithms apply.

The displayed total running time follows. The inequality \(\binom{m}{k}\leq m^{\min\{k,m-k\}}\) supports polynomial time for fixed \(k\) and fixed \(m-k\). The algorithm processes the listed support, rather than enumerating possible types.

• NP membership.

The LP feasible region is bounded by the type-mass equations and is closed. It is nonempty because the allowed destination rankings permit the challenger to be approved while \(c\) is unapproved. Thus an optimum exists at a vertex.

The column-dependence argument correctly bounds the number of positive variables by \(\tau+1\). Its perturbation preserves both the mass equations and the score row, so it works whether the score inequality is tight or slack.

The determinant argument applies to a system of polynomial dimension with integer coefficients of bounded magnitude and rational right-hand sides of input bit length. Hence a vertex solution has polynomial-size rational coordinates.

A certificate can list the challenger, at most \(\tau+1\) destinations with their originating types, and their transferred masses. Computing distances, verifying conservation and nonnegativity, and checking scores and budget all take polynomial time. No computation of the exponentially enumerated state minima is required by the certificate verifier.

No additional clarification is needed to make the mathematical argument verifiable.

⟨structured verdict parsed — rendered above⟩