Answer: Polynomial-time solvable; both the minimum radius and a witnessing reassignment can be computed.
Proposition 4.8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of computing the (C, c d∞swap)- score of a given candidate c in an election E = (C, V ) is in P. PROOF. It can be verified that the following algorithm runs in polynomial time and computes the (C, c d∞swap)-score of c. 1. Set k = 0. 2. If c is a Condorcet winner of E then return k. 3. For each vote where c is not ranked first, swap c and its pre- decessor. 4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, a target \(c\), and a rational distribution \(\mu\) over \(\tau\) complete rankings with \(\sum_t\mu_t=1\), find the least integer \(r\) for which there are masses \(x_{t,u}\geq 0\) satisfying \(\sum_u x_{t,u}=\mu_t\), \(x_{t,u}=0\) whenever the Kendall swap distance \(d_{\mathrm{swap}}(t,u)>r\), and \(\sum_{t,u:\,c\succ_u d}x_{t,u}>1/2\) for every opponent \(d\neq c\). Return \(r\) and a witnessing reassignment.
Let \(C\) be a set of \(m\geq 1\) candidates, let \(c\in C\), and let \(\mathcal R(C)\) denote all strict complete rankings of \(C\).
A society is given by its support: a list \(T\subseteq\mathcal R(C)\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). The parameter \(\tau\) is the support size, not the number \(m!\) of possible rankings; \(L\) is the total input bit length.
Use Kendall swap distance \(d_{\mathrm{swap}}\). A reassignment may split each type's mass among arbitrary rankings, including rankings outside \(T\).
For a nonnegative integer radius \(r\), feasibility means there exist real masses \(x_{t,u}\geq0\) satisfying \(\sum_{u\in\mathcal R(C)}x_{t,u}=\mu_t\), with \(x_{t,u}=0\) whenever \(d_{\mathrm{swap}}(t,u)>r\), and \(\sum_{t\in T}\sum_{u:\,c\succ_u d}x_{t,u}>1/2\) for every \(d\in C\setminus\{c\}\). Pairwise ties do not suffice.
The computational problem is to find the least feasible integer \(r\) and a witnessing reassignment, represented by its positive entries as binary rationals.
Can this minimum radius and a witnessing reassignment be computed in time polynomial in \(m,\tau,L\), or is deciding feasibility for an input radius \(r\) NP-hard, with its binary encoding included in \(L\)?
For an explicitly listed finite electorate, the minimum maximum number of adjacent swaps per voter needed to make a designated candidate a strict Condorcet winner is polynomial-time computable. [Source](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R74.pdf)
The literature search located no result explicitly treating the normalized, splittable-mass problem defined above.
The minimum radius and a witnessing reassignment are computable in time polynomial in \(m,\tau,L\). In fact, an optimal witness assigns each type’s entire mass to a single ranking.
The decisive property is that moving \(c\) upward by as many as \(r\) positions simultaneously achieves every pairwise victory involving \(c\) that is individually achievable within \(r\) swaps.
For a ranking \(t\), let \(p_t(a)\in\{1,\ldots,m\}\) denote the position of candidate \(a\), with position \(1\) highest.
Lemma. Suppose \(d\succ_t c\), and put \(g=p_t(c)-p_t(d)\). Every ranking \(u\) satisfying \(c\succ_u d\) has \(d_{\mathrm{swap}}(t,u)\geq g\).
Proof. There are exactly \(g-1\) candidates strictly between \(d\) and \(c\) in \(t\). For each such candidate \(z\), the original ranking satisfies \(d\succ_t z\succ_t c\).
If \(u\) preserved both comparisons \(d\succ_u z\) and \(z\succ_u c\), transitivity would give \(d\succ_u c\), contradicting \(c\succ_u d\). Thus, for every intermediate \(z\), at least one of the unordered pairs \(\{d,z\}\) and \(\{z,c\}\) reverses its order. The pair \(\{d,c\}\) also reverses.
These give at least \(g\) distinct reversed pairs. An adjacent swap changes the relative order of exactly one unordered pair, so every swap sequence from \(t\) to \(u\) contains at least \(g\) swaps. This proves the lemma.
The bound is attained by moving \(c\) upward exactly \(g\) positions.
For a nonnegative integer \(r\), define \(s_r(t)\) by moving \(c\) upward in \(t\) by \(k_t(r)=\min\{r,p_t(c)-1\}\) positions, preserving the relative order of all other candidates.
This uses exactly \(k_t(r)\) adjacent swaps, so \(d_{\mathrm{swap}}(t,s_r(t))=k_t(r)\leq r\).
For every opponent \(d\neq c\), define \(a_{t,d}=\max\{0,p_t(c)-p_t(d)\}\). Directly from the construction,
\(c\succ_{s_r(t)}d\quad\Longleftrightarrow\quad a_{t,d}\leq r.\)
Indeed, candidates originally below \(c\) remain below it. A candidate originally above \(c\) is passed precisely when its position gap from \(c\) is at most \(r\).
Moreover, every \(u\) with \(d_{\mathrm{swap}}(t,u)\leq r\) satisfies
\(c\succ_u d\quad\Longrightarrow\quad c\succ_{s_r(t)}d.\)
For an opponent originally below \(c\), this follows because \(s_r(t)\) still ranks \(c\) above it. For an opponent originally above \(c\), the lemma gives \(a_{t,d}\leq d_{\mathrm{swap}}(t,u)\leq r\), so \(s_r(t)\) also ranks \(c\) above it.
Thus \(s_r(t)\) simultaneously attains every pairwise victory that any allowed destination ranking could attain.
Define the attainable support against \(d\) by
\(A_d(r)=\sum_{t\in T:\,a_{t,d}\leq r}\mu_t.\)
Proposition. Radius \(r\) is feasible if and only if \(A_d(r)>1/2\) for every \(d\neq c\).
Necessity. Let \(x\) be any allowed reassignment, including one with real masses and arbitrary splitting. If \(a_{t,d}>r\), the lemma shows that no allowed destination of type \(t\) ranks \(c\) above \(d\). Every other type contributes at most its entire mass. Consequently,
\(\sum_{t\in T}\sum_{u:\,c\succ_u d}x_{t,u}\leq\sum_{t:\,a_{t,d}\leq r}\mu_t=A_d(r).\)
A strict pairwise majority therefore requires \(A_d(r)>1/2\).
Sufficiency. Assign each type’s entire mass to \(s_r(t)\): set \(x_{t,s_r(t)}=\mu_t\), and set every other entry to zero.
The row sums are correct, and every positive entry satisfies the radius constraint. By the characterization in Section 2, the resulting support against each \(d\) is exactly \(A_d(r)\). Hence all the required strict inequalities hold.
This proves the criterion and shows that splitting mass cannot improve feasibility.
If \(m=1\), the pairwise conditions are vacuous. Return radius \(0\) and \(x_{t,t}=\mu_t\).
Assume \(m\geq2\). Every \(a_{t,d}\) lies in \(\{0,\ldots,m-1\}\), and \(A_d(m-1)=1\). Define
\(r_d=\min\{j\in\{0,\ldots,m-1\}:A_d(j)>1/2\}.\)
Each \(A_d\) is nondecreasing. The feasibility criterion therefore gives the exact optimum
\(r_{\min}=\max_{d\in C\setminus\{c\}}r_d.\)
An algorithm computes all positions and gaps, finds these thresholds, and returns the \(\tau\) positive entries \(x_{t,s_{r_{\min}}(t)}=\mu_t\).
The criterion proves minimality: any smaller radius fails the strict-majority requirement for at least one opponent. The construction proves feasibility at the returned radius.
Write each input mass as \(\mu_t=\alpha_t/\beta_t\), where \(\alpha_t,\beta_t\) are positive binary integers. Let
\(D=\prod_{t\in T}\beta_t,\qquad w_t=\alpha_t(D/\beta_t).\)
The bit length of \(D\) is at most \(1+\sum_t\log_2\beta_t\), hence \(O(L)\). Each \(w_t\) is a positive integer, and normalization gives \(\sum_t w_t=D\), so these weights also have \(O(L)\) bits.
For each opponent \(d\), form the buckets
\(H_d(j)=\sum_{t:\,a_{t,d}=j}w_t,\qquad j\in\{0,\ldots,m-1\}.\)
Then \(r_d\) is the first index \(j\) for which
\(2\sum_{i=0}^{j}H_d(i)>D.\)
This exact integer comparison enforces strict majority: equality is rejected.
Computing positions and filling buckets takes \(O(m\tau)\) elementary operations; scanning the buckets takes \(O(m^2)\) operations. All arithmetic uses integers of polynomial bit length. Computing \(D\) and the weights likewise takes polynomial time.
For a supplied binary radius \(r\), one may replace it by \(\min\{r,m-1\}\), since radius \(m-1\) is always feasible. Thus a large binary radius causes no enumeration proportional to its numeric value.
The witness has exactly \(\tau\) positive entries. Its masses are copied from the input, and its destination rankings are explicitly constructed in polynomial time. Its total encoding length is polynomial.
[Proposition 4.8 of the cited paper](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R74.pdf) gives the finite-electorate algorithm that repeatedly moves \(c\) upward in every vote. The proof above establishes directly why the same operation solves the normalized, splittable-mass problem, with exact rational arithmetic and a polynomial-size witness.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes a polynomial-time algorithm for both the minimum radius and a rational witnessing reassignment. No major or minor mathematical issues were found.
The proof addresses the stated support representation directly: it processes the \(\tau\) listed types and their binary rational masses. It does not expand the society into an electorate whose size depends on the denominators.
Its necessity argument allows arbitrary real-valued splitting and every destination in \(\mathcal R(C)\). Its sufficiency argument constructs a reassignment within that same domain. Thus the proof covers the full continuous problem.
For an opponent \(d\) initially above \(c\), the positive gap \(g=p_t(c)-p_t(d)\) counts one more than the number of intermediate candidates.
For each intermediate candidate \(z\), preserving both \(d\succ z\) and \(z\succ c\) would contradict \(c\succ d\) by transitivity. Therefore at least one of the two stated pairs must reverse.
The distinctness assertion is valid: pairs associated with different intermediate candidates cannot coincide, and none equals \(\{d,c\}\). Consequently there are at least \(g\) distinct reversed pairs. Every such pair must be swapped at least once in an adjacent-swap sequence, while each adjacent swap changes only one pair’s order. This establishes the claimed lower bound.
Moving \(c\) upward exactly \(g\) positions reverses its comparison with \(d\) using \(g\) swaps, so the attainment claim is also correct.
The construction \(s_r(t)\) is well-defined for every nonnegative integer \(r\), including \(r=0\) and radii exceeding the number of positions above \(c\).
Moving \(c\) upward by \(k_t(r)\) positions uses that many swaps and reverses exactly that many comparisons involving \(c\). Thus the claimed distance equality holds.
The equivalence
\[
c\succ_{s_r(t)}d\quad\Longleftrightarrow\quad a_{t,d}\leq r
\]
handles both possible original orders correctly. Opponents originally below \(c\) have \(a_{t,d}=0\) and remain below it. Opponents originally above \(c\) are passed exactly when their positive position gap is at most \(r\).
The subsequent implication for every allowed destination \(u\) follows from the proved lower bound when \(d\) is initially above \(c\), and directly from the construction otherwise. This proves the required coordinatewise dominance of one destination ranking; it does not merely optimize each pair separately using incompatible rankings.
In the necessity argument, \(a_{t,d}>r\) implies that \(d\) was initially above \(c\), so the lemma applies. Such a type contributes no admissible mass to support against \(d\). Each remaining type contributes at most \(\mu_t\), by nonnegativity and its row-sum constraint.
Hence the bound by \(A_d(r)\) applies to every allowed reassignment, including split real masses. Strict feasibility therefore requires \(A_d(r)>1/2\); equality cannot suffice.
For sufficiency, the proposed assignment has the required row sums, nonnegative rational entries, and admissible destinations. Its support against each opponent is exactly \(A_d(r)\). The strict inequalities therefore hold simultaneously whenever the criterion holds. The conclusion that splitting cannot improve feasibility is justified.
For \(m=1\), all pairwise conditions are vacuous, and the unchanged reassignment at radius \(0\) is feasible and optimal.
For \(m\geq2\), every gap lies between \(0\) and \(m-1\). At radius \(m-1\), every constructed destination ranks \(c\) first, so every \(A_d(m-1)=1\). Thus every threshold \(r_d\) exists.
Monotonicity and the exact feasibility criterion justify
\[
r_{\min}=\max_{d\in C\setminus\{c\}}r_d.
\]
The proof establishes both feasibility at this radius and infeasibility at every smaller nonnegative integer radius.
The denominator product \(D\) has \(O(L)\) bits even when the fractions are not reduced. Each division \(D/\beta_t\) is exact. Normalization gives \(\sum_t w_t=D\), so individual weights, bucket sums, and cumulative sums have \(O(L)\) bits; doubling adds at most one bit.
The stated position, bucket, and scanning operation counts are polynomial in \(m,\tau\). Standard binary integer multiplication, exact division, addition, and comparison on these operands take polynomial time. No operation requires enumerating a number of voters proportional to \(D\).
The integer comparison rejects exact half-mass support. Capping a supplied radius at \(m-1\) preserves feasibility and avoids dependence on its numerical magnitude.
The witness contains exactly one positive entry per source type. Coincident destination rankings do not merge these entries because their source indices differ. Copying the input masses and explicitly recording \(\tau\) destination rankings gives a polynomial-size binary rational witness.
Proposition 4.8 states polynomial-time computation of the finite-electorate score under the maximum swap-distance objective, and its algorithm repeatedly moves \(c\) upward in every applicable vote. The prover’s description matches the [cited proposition](https://www.ifaamas.org/Proceedings/aamas2011/papers/C6_R74.pdf).
The continuous conclusion follows from Sections 1–5 independently of that citation. No unverified transfer theorem is needed.
No additional clarification or repair 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.