Answer: Polynomial-time solvable in both UNI and NON for every fixed \(\ell\ge3\), in \(O(\tau mL^2)+(\tau m+(m+\tau)L)^{O(1)}\) bit operations, with an absolute exponent independent of \(\ell\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateC-KT(ℓ)-Condorcet-UNI/NON are NP-hard for every ℓ≥3. PROOF. We first consider C-KT(3)-Condorcet-UNI. The reduction is from the X3C problem. Given an instance F = (U = {c1, c2, ..., c3κ}, S = {s1, s2, ..., s3κ) of X3C, we create an instance E for C-KT(3)-Condorcet-UNI as follows. Candidates: For each c ∈ U, we create a corresponding candidate.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates [0m\(C\), supported rankings [0m\(S\) with rational masses [0m\(\mu_t>0\) summing to [0m\(1\), a target [0m\(p\), a rational mass budget [0m\(\beta\), and fixed [0m\(\ell\ge3\), is there a transfer map [0m\(x_{t,r}\ge0\) from each source type [0m\(t\in S\) to rankings [0m\(r\ne t\) with [0m\(d_{\mathrm{KT}}(t,r)\le\ell\), such that [0m\(\sum_r x_{t,r}\le\mu_t\) for every [0m\(t\), total transferred mass is at most [0m\(\beta\), and the resulting society makes [0m\(p\) a Condorcet winner (UNI) or weak Condorcet winner (NON)?
Let \(C\) contain \(m\ge2\) candidates, let \(p\in C\), and fix an integer \(\ell\ge3\). Types are strict linear rankings of \(C\); write \(\mathcal R(C)\) for all such rankings and use Kendall–Tau distance \(d_{\mathrm{KT}}\).
A society is given by its support: a list \(S\) of \(\tau\) distinct types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in S}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
The input also specifies a binary rational budget \(0<\beta\le1\) and a model, UNI or NON; initially \(p\) is not a Condorcet winner in UNI, or not a weak Condorcet winner in NON.
A transfer consists of real masses \(x_{t,r}\ge0\), for \(t\in S\) and \(r\in\mathcal R(C)\setminus\{t\}\) with \(d_{\mathrm{KT}}(t,r)\le\ell\), satisfying \(\sum_r x_{t,r}\le\mu_t\) and \(\sum_{t,r}x_{t,r}\le\beta\). Destinations need not belong to \(S\); all other transfers are zero.
Extend \(\mu\) by zero outside \(S\). The resulting mass at ranking \(r\) is \(\nu_r=\mu_r-\sum_q x_{r,q}+\sum_{t\in S}x_{t,r}\), with outgoing mass zero for sources outside \(S\). Comparisons use total ranking mass; UNI requires \(p\) to beat every opponent strictly, while NON permits pairwise ties.
Is deciding whether such a transfer makes \(p\) win polynomial-time solvable or NP-hard, for each fixed \(\ell\ge3\) and each model? State running times in \(m,\tau,L\), with dependence on \(\ell\) explicit.
For discrete voters, the same constructive distance-restricted bribery problem is NP-hard for every fixed \(\ell\ge3\) in both models, and polynomial-time solvable for \(\ell\in\{1,2\}\). [Discrete results](https://doi.org/10.3233/978-1-61499-672-9-363)
Continuous Condorcet Shift Bribery is polynomial-time solvable; it allows only upward shifts of the target candidate and uses shift costs. No result for exactly the transfer problem above was located. [Continuous result](https://arxiv.org/html/2608.25444v1)
Both UNI and NON are polynomial-time solvable for every fixed \(\ell\ge3\). In fact, the algorithm has a polynomial bound independent of \(\ell\): it uses one canonical destination per supported type and solves a rational linear program with \(\tau+1\) variables and \(O(m+\tau)\) constraints.
A bit-operation bound is
\(O(\tau mL^2)+\bigl(\tau m+(m+\tau)L\bigr)^{O(1)}\),
where the exponent is an absolute constant independent of \(\ell\).
Write \(a\succ_t b\) when ranking \(t\) places \(a\) above \(b\). Kendall–Tau distance counts unordered candidate pairs whose relative order differs.
Lemma. Suppose \(q\) occupies position \(i\) and \(p\) occupies position \(j>i\) in \(t\). Every ranking \(r\) satisfying \(p\succ_r q\) has \(d_{\mathrm{KT}}(t,r)\ge j-i\).
Proof. The pair \(\{q,p\}\) reverses. For each of the \(j-i-1\) candidates \(b\) between them in \(t\), at least one of \(\{q,b\}\) and \(\{b,p\}\) must reverse: otherwise \(q\succ_r b\succ_r p\), contradicting \(p\succ_r q\).
These pairs are distinct for different intermediate candidates and distinct from \(\{q,p\}\). Thus there are at least \(1+(j-i-1)=j-i\) disagreements. \(\square\)
For each \(t\in S\), let \(k_t\) be the position of \(p\), and define \(h_t=\min\{\ell,k_t-1\}\). Let \(s_t\) be the ranking obtained by moving \(p\) upward exactly \(h_t\) positions, preserving the relative order of all other candidates.
Let \(G_t\) contain the candidates crossed by this shift. Explicitly,
\(G_t=\{q\in C\setminus\{p\}:k_t-h_t\le\operatorname{pos}_t(q)<k_t\}\).
The shift reverses precisely the pairs \(\{p,q\}\) with \(q\in G_t\), so \(d_{\mathrm{KT}}(t,s_t)=h_t\le\ell\). If \(h_t>0\), it is a permitted destination distinct from \(t\); if \(h_t=0\), then \(s_t=t\).
For a ranking \(r\) and opponent \(q\), define \(b_{r,q}=1\) if \(p\succ_r q\), and \(b_{r,q}=-1\) otherwise.
Dominance lemma. For every permitted destination \(r\) of source \(t\), and every opponent \(q\),
\(b_{s_t,q}\ge b_{r,q}\).
Proof. If \(p\succ_t q\), the upward shift preserves that comparison, so \(b_{s_t,q}=1\).
Now suppose \(q\succ_t p\). If \(q\in G_t\), again \(b_{s_t,q}=1\). Otherwise, \(q\) is more than \(\ell\) positions above \(p\): any predecessor within \(\ell\) positions belongs to \(G_t\). By the preceding lemma, no ranking within Kendall–Tau distance \(\ell\) can reverse this comparison. Consequently \(b_{r,q}=b_{s_t,q}=-1\). \(\square\)
We next verify that this pointwise dominance applies to the specified transfer model, including when destinations belong to the original support.
For any society \(\rho\), define its pairwise margin by
\(M_q(\rho)=\sum_{r\in\mathcal R(C)}\rho_r b_{r,q}\).
The transfer definition and linearity give
\(M_q(\nu)=M_q(\mu)+\sum_{t\in S}\sum_r x_{t,r}(b_{r,q}-b_{t,q})\).
Given any feasible transfer, replace all outgoing mass from each source with \(h_t>0\) by a transfer to \(s_t\), of amount
\(y_t=\sum_r x_{t,r}\).
For sources with \(h_t=0\), discard their outgoing transfers and set \(y_t=0\).
The replacement respects every source capacity and does not increase the total transferred mass. For \(h_t>0\), the dominance lemma shows that each replaced transfer weakly increases every margin. For \(h_t=0\), \(p\) is already first, so \(b_{t,q}=1\) for every opponent; every original outgoing transfer has nonpositive margin change, and discarding it weakly increases every margin.
Thus every feasible transfer can be replaced by canonical upward shifts without decreasing any pairwise margin. This preserves both strict and weak winning conditions.
Compute the initial margins
\(M_q=\sum_{t\in S}\mu_t b_{t,q}\)
for all \(q\ne p\). Since total mass is one, each margin belongs to \([-1,1]\).
Set \(u_t=\mu_t\) when \(h_t>0\), and \(u_t=0\) otherwise. Use variables \(y_t\), for \(t\in S\), and a common margin variable \(\delta\). Maximize \(\delta\), subject to:
The last constraint follows because moving mass \(y_t\) to \(s_t\) changes the margin against each crossed candidate from a contribution of \(-y_t\) to \(+y_t\), an increase of \(2y_t\). It leaves all other comparisons with \(p\) unchanged.
This LP is feasible: take every \(y_t=0\) and \(\delta=-1\). Its feasible region is closed and bounded, so its optimum \(\delta^\star\) is attained.
If the original problem admits a weak winning transfer, its canonical replacement has every margin nonnegative. Its amounts \(y_t\), together with \(\delta=0\), satisfy the LP. Hence \(\delta^\star\ge0\).
Conversely, if \(\delta^\star\ge0\), an optimal LP solution specifies permitted transfers \(t\to s_t\) whose margins are all nonnegative. Thus \(p\) is a weak Condorcet winner.
Therefore NON answers yes exactly when \(\delta^\star\ge0\).
If the original problem admits a strict winning transfer, its canonical replacement also has every margin strictly positive. There are only \(m-1\) opponents, so the minimum of these margins is strictly positive. Taking this minimum as \(\delta\) gives an LP solution with positive objective.
Conversely, if \(\delta^\star>0\), the canonical transfers specified by an optimal LP solution make every margin at least \(\delta^\star>0\).
Therefore UNI answers yes exactly when \(\delta^\star>0\). This handles strictness without assuming any fixed positive winning margin.
The LP has \(\tau+1\) variables and \(O(m+\tau)\) constraints. Its constraint-matrix entries belong to \(\{0,\pm1,\pm2\}\).
Let \(D\) be the product of the input denominators of all masses and the budget. Its binary length is \(O(L)\). Every initial margin and every right-hand side has denominator dividing \(D\), and numerator of binary length \(O(L)\). Thus a dense encoding of the LP has length
\(B=O\bigl(\tau m+(m+\tau)L\bigr)\).
Exact optimization of a rational LP takes polynomial time in its binary encoding length. This standard theorem applies here because the LP is rational, feasible, and bounded. See [MIT’s notes on polynomial-time LP algorithms](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html); polynomial-size rational optimal solutions follow from the vertex characterization and Cramer’s rule, as described in [the accompanying LP notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html). Consequently the sign tests on \(\delta^\star\) are exact.
For completeness, a positive optimum cannot require superpolynomial precision. Put \(n=\tau+1\). At an optimal vertex, choose \(n\) independent tight constraints, with integer coefficient matrix \(A\). Its entries have absolute value at most two, so Hadamard’s inequality gives \(|\det A|\le(2\sqrt n)^n\). Cramer’s rule expresses \(\delta^\star\) with denominator dividing \(D|\det A|\). Hence, if positive,
\(\delta^\star\ge1/\bigl(D(2\sqrt n)^n\bigr)\).
Its positivity is therefore distinguishable using polynomially many bits.
Reading rankings, computing the sets \(G_t\), and computing all margins take at most \(O(\tau mL^2)\) bit operations using elementary integer arithmetic. Adding rational LP optimization yields the stated bound
\(O(\tau mL^2)+\bigl(\tau m+(m+\tau)L\bigr)^{O(1)}\).
The only use of \(\ell\) is in \(h_t=\min\{\ell,k_t-1\}\); neither the LP size nor the polynomial exponent depends on it. The same argument even works when \(\ell\) is supplied in binary, with its encoding included in \(L\).
The dominance reduction also applies to discrete voters. However, discrete voters cannot be split into arbitrary real amounts, so the corresponding canonical-shift variables retain integrality restrictions. Here the permitted real masses make the linear program exact. Thus the polynomial-time result is consistent with the stated discrete hardness.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. Both models are polynomial-time solvable by the stated canonical-transfer reduction and rational LP. I found no major or minor mathematical issues.
The lower bound \(d_{\mathrm{KT}}(t,r)\ge j-i\) is valid.
The pair \(\{q,p\}\) must reverse. Each intermediate candidate \(b\) forces at least one additional reversal, because preserving both relevant comparisons would imply \(q\succ_r b\succ_r p\). The counted pairs are distinct, so there is no double counting. The argument also covers adjacent positions, where there are no intermediate candidates.
The construction of \(s_t\) is valid: shifting \(p\) upward by \(h_t\) reverses exactly \(h_t\) pairs, all involving \(p\). Thus its distance is within the permitted bound, and it differs from \(t\) precisely when \(h_t>0\).
The dominance proof correctly exhausts the possibilities for every opponent:
The last case remains valid when \(h_t=k_t-1<\ell\): then every predecessor belongs to \(G_t\), so there is no remaining predecessor.
Consequently, the simultaneous coordinatewise dominance claim is established.
The margin identity correctly accounts for both incoming and outgoing mass, including transfers whose destinations belong to \(S\).
Combining outgoing transfers into an amount \(y_t\) preserves the source-capacity constraint. The replacement does not increase the budget usage. Sources with \(h_t=0\) are correctly handled by discarding their outgoing transfers, because every such transfer has nonpositive effect on every margin involving \(p\).
There is no implicit redistribution of incoming mass: source capacities remain tied to the original masses \(\mu_t\), as required by the task. Destination collisions create no additional constraint.
Therefore, the reduction preserves feasibility and weakly improves every relevant margin.
The coefficient \(2\) is correct: crossing an opponent changes its contribution from \(-y_t\) to \(+y_t\). All other comparisons involving \(p\) remain unchanged.
The LP has the stated variables and constraints. Its proposed feasible point is valid because each initial margin is at least \(-1\). Explicit bounds on every variable make the feasible region compact, so the optimum is attained.
Both equivalences are proved in both directions:
For UNI, taking the minimum of finitely many strictly positive margins is legitimate because \(m-1\ge1\). The upper bound \(\delta\le1\) excludes no winning solution because margins of a normalized society cannot exceed \(1\).
The treatment of strict inequalities is therefore rigorous.
The common-denominator argument is correct. The product \(D\) has binary length \(O(L)\), and every right-hand side can be represented using that denominator with an \(O(L)\)-bit numerator.
The dense encoding bound
\(B=O(\tau m+(m+\tau)L)\)
is valid. Although the variable-bound rows contribute \(O(\tau^2)\) dense entries, these are absorbed by \(\tau L\), since the explicit input has \(L=\Omega(\tau)\).
The invoked theorem—exact rational LP optimization in time polynomial in binary encoding length—applies to this explicitly represented, rational, feasible, bounded LP. The cited [LP algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) support polynomial-time optimization; the [structural notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html) support the vertex and rational-size claims.
The supplementary precision calculation is also correct:
The stated lower bound on a positive optimum follows, and its required precision is polynomial.
The preprocessing bound \(O(\tau mL^2)\) is a valid conservative bound using elementary exact arithmetic. Combined with rational LP optimization, it establishes the claimed running time with an absolute polynomial exponent independent of \(\ell\).
The proof covers every fixed \(\ell\ge3\), both models, unrestricted permitted destinations, and real transfer masses. Its additional claim about binary-encoded \(\ell\) is supported by the same construction.
The discrete comparison is consistent: canonical dominance does not remove the integrality restrictions on discrete voters. No discrete hardness result is needed for the continuous proof.
No repair or additional 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.