Answer: Achieving approximation ratio \(\max\{1,\delta\log m\}\) is \(\mathrm{NP}\)-hard for some constant \(\delta>0\), even with dyadic rational masses.
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a δ > 0 s. t. (dswap, Maximin)- OPTMANIPULATION does not admit a polynomial-time δ log |C|-approximation algorithm unless P=NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a rational distribution \(\nu\) over rankings of total mass \(1-\beta\), a caucus of mass \(\beta>0\) with common true ranking \(R\), and a target \(p\) ranked first by \(R\), find a ranking \(L\) minimizing \(d_{\mathrm{swap}}(R,L)\) such that \(p\) is the unique Maximin winner under \(\mu_L=\nu+\beta\delta_L\), or report that none exists. Here \(M_{\mu_L}(c)=\min_{d\ne c}\sum_{t:\,c\succ_t d}\mu_{L,t}\), and the required condition is \(M_{\mu_L}(p)>M_{\mu_L}(q)\) for every \(q\ne p\).
Given candidates \(C\) with \(m=|C|\ge 2\), a nonnegative rational measure \(\nu\) over strict rankings with total mass \(1-\beta\), a binary rational \(0<\beta\le 1\), a common true ranking \(R\), and its first-ranked candidate \(p\), the caucus of mass \(\beta\) must submit one common strict ranking \(B\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is support size, not the number of possible rankings. Here take \(\tau=|\operatorname{supp}(\nu+\beta\delta_R)|\). State running times in \(m,\tau\), and the total input bit length \(L\).
The resulting society is \(\mu_B=\nu+\beta\delta_B\), where \(\delta_B\) is unit mass on \(B\). Its Maximin score is \(M_{\mu_B}(c)=\min_{d\in C\setminus\{c\}}\sum_{t:\,c\succ_t d}\mu_B(t)\).
A ranking is feasible exactly when \(M_{\mu_B}(p)>M_{\mu_B}(q)\) for every \(q\ne p\); ties are unsuccessful. Minimize the Kendall swap distance \(d_{\mathrm{swap}}(R,B)\), with optimum \(+\infty\) if no ranking is feasible. Approximation is multiplicative, including instances with optimum zero.
Can this problem be approximated in polynomial time within \(\max\{1,\delta\log m\}\) for every constant \(\delta>0\), or is achieving this ratio NP-hard for some constant \(\delta>0\)?
For finite unweighted elections with one manipulator, logarithmic-factor approximation is impossible unless \(\mathrm{P}=\mathrm{NP}\), even when the target is the manipulator’s favorite; the distance-bounded decision problem is NP-complete. [Obraztsova–Elkind](https://www.ifaamas.org/Proceedings/aamas2012/papers/2D_3.pdf)
No result for exactly the rational-mass, common-ballot approximation problem was identified in the literature search.
The hardness alternative holds: for some constant \(\delta>0\), achieving approximation ratio \(\max\{1,\delta\log m\}\) is \(\mathrm{NP}\)-hard. Consequently, polynomial-time approximation within this ratio is impossible unless \(\mathrm{P}=\mathrm{NP}\).
The reduction below preserves the entire feasible set and every ballot’s swap cost. It even produces instances whose masses are dyadic rationals.
We use Obraztsova–Elkind’s Theorem 4.7: for some constant \(a>0\), minimizing swap distance for a single manipulator under Maximin cannot be approximated within \(a\log m\) in polynomial time unless \(\mathrm{P}=\mathrm{NP}\). Their setting requires a unique winner, and their hardness construction places the target first in the manipulator’s true ranking. These conventions are stated in Section 2, Remark 3.4, and the proof of Theorem 4.7. [Obraztsova–Elkind, *Optimal Manipulation of Voting Rules*](https://www.ifaamas.org/Proceedings/aamas2012/papers/2D_3.pdf)
Thus the source problem has exactly the relevant success condition and preference restriction. What remains is to transfer it to the rational-mass support representation without changing the approximation objective.
Consider a source election with \(n\) explicitly listed voters and candidate set \(C\). Let voter \(i\) be the manipulator, let its true ranking be \(R\), and let \(p\) be first in \(R\). Write the other rankings as \(R_j\), for \(j\ne i\).
For a submitted ranking \(B\), define the integer pairwise count
\[ K_B(c,d)=\sum_{j\ne i}\mathbf 1[c\succ_{R_j}d]+\mathbf 1[c\succ_B d]. \]
The source Maximin score is therefore
\[ M^{\mathrm{src}}_B(c)=\min_{d\ne c}K_B(c,d). \]
Choose the smallest power of two \(D\) satisfying \(D\ge n\), and put
\[ \beta=\frac1D,\qquad \alpha=\frac{D-n}{2D}. \]
Choose any strict ranking \(T\) of \(C\), and let \(T^{\mathrm{rev}}\) be its reverse. Construct
\[ \nu=\frac1D\sum_{j\ne i}\delta_{R_j} +\alpha\delta_T+\alpha\delta_{T^{\mathrm{rev}}}. \]
Coincident rankings are merged, and zero-mass terms are omitted.
All masses are nonnegative dyadic rationals. Moreover,
\[ \nu(C!)=\frac{n-1}{D}+2\alpha =\frac{D-1}{D}=1-\beta. \]
Here \(\nu(C!)\) denotes the total mass over strict rankings. Hence the constructed instance satisfies the required mass conditions, including \(0<\beta\le1\).
For every pair of distinct candidates, exactly one of \(T\) and \(T^{\mathrm{rev}}\) ranks the first candidate above the second. Consequently, for every submitted ballot \(B\),
\[ \sum_{t:\,c\succ_t d}\mu_B(t) =\frac{K_B(c,d)}D+\alpha. \]
Because the scaling factor is positive and the additive term is independent of \(d\),
\[ M_{\mu_B}(c) =\min_{d\ne c}\left(\frac{K_B(c,d)}D+\alpha\right) =\frac{M^{\mathrm{src}}_B(c)}D+\alpha. \]
It follows, for every \(q\ne p\), that
\[ M_{\mu_B}(p)>M_{\mu_B}(q) \quad\Longleftrightarrow\quad M^{\mathrm{src}}_B(p)>M^{\mathrm{src}}_B(q). \]
Thus a ballot is feasible in the constructed instance exactly when it makes \(p\) the unique source-election winner.
The candidate set and the true ranking are unchanged. Therefore every ballot also has exactly the same objective value:
\[ d_{\mathrm{swap}}(R,B)_{\mathrm{target}} =d_{\mathrm{swap}}(R,B)_{\mathrm{source}}. \]
The optima coincide, including optimum zero and optimum \(+\infty\). This is an exact, approximation-preserving reduction.
The constructed society \(\nu+\beta\delta_R\) uses at most the \(n\) original rankings and the two additional reverse rankings. Hence its support size satisfies
\[ \tau=\left|\operatorname{supp}(\nu+\beta\delta_R)\right|\le n+2. \]
This bound concerns the actual support, rather than the number of possible rankings.
Since \(D<2n\), except for the harmless case \(n=D=1\), every aggregated mass has a numerator and denominator requiring \(O(\log(n+1))\) bits. With candidates indexed by integers, the target input length satisfies
\[ L=O\!\left(\tau m\log m+\tau\log(n+1)\right). \]
The reduction can be implemented by sorting the explicitly listed rankings, merging equal rankings, and calculating their masses. It takes time polynomial in the source input length and produces polynomial output length.
Therefore an algorithm running in \(\operatorname{poly}(m,\tau,L)\) on the target instances would yield a polynomial-time algorithm on the source elections. No expansion of binary masses into individual voters is needed.
For completeness, a proposed target ballot can be checked using \(O((\tau+1)m^2)\) rational arithmetic operations. All intermediate rational numbers have bit length \(O(L)\); elementary arithmetic consequently gives a verification bound of \(O((\tau+1)m^2L^2)\). Computing its swap distance takes an additional \(O(m^2)\) elementary comparisons.
Fix the constant \(a>0\) from the known hardness theorem, and choose any fixed \(\delta\) satisfying \(0<\delta<a\).
Suppose a polynomial-time target algorithm achieved
\[ \rho(m)=\max\{1,\delta\log m\}. \]
For all sufficiently large \(m\), this is \(\delta\log m\), and hence is at most \(a\log m\). Applying the exact reduction and returning the resulting ballot would achieve that factor for the source problem.
The bounded range of smaller candidate counts cannot remove the hardness. For any fixed bound \(M\), source instances with \(m<M\) can be solved exactly by enumerating all \(m!\) ballots and checking their scores. This takes \(O(m!\,nm^2)\) elementary operations, which is polynomial in the source input length when \(M\) is fixed. Thus restricting logarithmic inapproximability to sufficiently large candidate counts preserves the hardness statement.
The hypothetical target algorithm would therefore contradict the known logarithmic inapproximability theorem unless \(\mathrm{P}=\mathrm{NP}\). This settles the requested alternative.
⟨structured verdict parsed — rendered above⟩
The argument proves the hardness alternative. The cited theorem has the required winner convention and favorite-candidate restriction. The reduction preserves feasibility and swap distance for every submitted ballot, and its representation has polynomial size. No major or minor mathematical issues were found.
Theorem 4.7 states logarithmic-factor inapproximability for single-voter Maximin manipulation under swap distance, unless \(\mathrm{P}=\mathrm{NP}\). Section 2 adopts adversarial tie-breaking, corresponding to the unique-winner setting for the manipulator’s favorite. Remark 3.4 and the construction in the theorem’s proof confirm that the target candidate is first in the manipulator’s true ranking. Thus the restrictions needed here hold on the hard source instances. [Obraztsova–Elkind, Sections 2–4](https://www.ifaamas.org/Proceedings/aamas2012/papers/2D_3.pdf)
The source Maximin score and swap-distance definitions also agree with those used in the task. The citation is sufficiently precise, and its relevant hypotheses are satisfied.
The source contains a designated manipulator, so \(n\ge1\). The chosen power of two satisfies \(D\ge n\), making both \(\beta=1/D\) and \(\alpha=(D-n)/(2D)\) nonnegative, with \(0<\beta\le1\).
The total noncaucus mass calculation is correct:
\[ \frac{n-1}{D}+2\frac{D-n}{2D} =\frac{D-1}{D} =1-\beta. \]
Every mass is dyadic. Merging coincident rankings preserves the measure, and omitting zero-mass terms produces the required positive-mass support list.
The edge case \(n=D=1\) is valid: then \(\beta=1\), \(\alpha=0\), and \(\nu\) is the zero measure. If \(D=n>1\), the padding terms likewise vanish without affecting any argument.
For distinct candidates \(c,d\), exactly one of \(T\) and its reverse ranks \(c\) above \(d\). Their combined contribution to that directed pairwise count is therefore exactly \(\alpha\), not \(2\alpha\).
The nonmanipulator ballots contribute their original counts divided by \(D\), and the caucus ballot contributes the manipulator’s original unit contribution divided by \(D\). Consequently, the stated identity
\[ \sum_{t:\,c\succ_t d}\mu_B(t) =\frac{K_B(c,d)}{D}+\alpha \]
holds for every strict ballot \(B\) and every distinct pair.
Because \(1/D>0\) and \(\alpha\) is independent of the opponent, taking the minimum gives precisely
\[ M_{\mu_B}(c)=\frac{M^{\mathrm{src}}_B(c)}{D}+\alpha. \]
Thus every strict comparison between candidates’ Maximin scores is preserved. Score ties are also preserved, so unsuccessful source ties cannot become successful target outcomes. This verifies the claimed equivalence of feasible ballots.
The requirement \(m\ge2\) ensures that every score minimum is over a nonempty set.
The candidate set, true ranking, and submitted ballot are unchanged. Hence their Kendall swap distance is unchanged.
Together with identical feasible sets, this establishes equality of the optima. It also handles both exceptional cases:
The reduction therefore preserves multiplicative approximation guarantees, including the task’s zero-optimum requirement.
The initial target society contains only original source rankings and the two padding rankings. Therefore
\[ \tau\le n+2. \]
This is a bound on actual support after merging, as required.
All aggregated masses can be represented with denominator \(2D\). Their numerators are at most \(2D\), so their binary descriptions require \(O(\log(n+1))\) bits. Since \(D<2n\), the stated encoding bound
\[ L=O\!\left(\tau m\log m+\tau\log(n+1)\right) \]
is valid. The separately supplied true ranking and caucus mass fit within this bound because \(\tau\ge1\).
Sorting, merging, and computing masses take polynomial time in the explicitly listed source input. Both target support size and target bit length are polynomially bounded in that input. Hence an algorithm with running time \(\operatorname{poly}(m,\tau,L)\) would give a polynomial-time source algorithm.
The submitted ballot changes the initial support by at most one additional ranking, so using \(\tau+1\) in the operation bound is safe. Accumulating all directed pairwise counts takes \(O((\tau+1)m^2)\) rational arithmetic operations; computing minima and checking strict score inequalities fits within that bound.
Exact sums and comparisons can be performed with intermediate bit length \(O(L)\). In particular, denominator lengths remain bounded by the total input denominator length when fractions are reduced or accumulated over a common denominator. Elementary arithmetic therefore supports the stated conservative bound
\[ O((\tau+1)m^2L^2). \]
The additional \(O(m^2)\) comparison count for swap distance is also correct.
For fixed \(0<\delta<a\), sufficiently large \(m\) satisfy
\[ \max\{1,\delta\log m\} =\delta\log m \le a\log m. \]
The exact reduction preserves \(m\), so the hypothetical target algorithm would provide the forbidden source approximation on this range.
For a fixed bound \(M\), enumerating all ballots when \(m<M\) takes \(O(m!\,nm^2)\) elementary operations. Since \(m!\) is then bounded by a constant, this is polynomial in source input length. This correctly removes the finite small-\(m\) range from the asymptotic hardness argument.
No repair or additional clarification is needed. The write-up resolves the requested approximation-hardness alternative, including support representation, binary masses, strict winning, and exceptional optimum values.
⟨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.