Answer: \(\Delta_2^p\)-complete, hence \(\mathrm{NP}\)-hard; fixed-parameter tractable with parameter \(m\), in time \(O(\tau L^2+(\tau m^2+m^2 2^m)(L+\log(m+1)))\).
Theorem 4.14 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose that a voting rule R is (K, d)- rationalizable, where K ∈{S, U, M, C}. and d is a normal ℓ1- votewise distance. Then the R-winner problem is FPT with respect to the number of candidates. Due to limited space we skip the proof. The main idea is that our problem can be reformulated as an integer linear program with O(|C|!) variables, where |C| is the number of candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), a distribution \(\mu\) with binary-rational masses over \(\tau\) complete rankings, and a candidate \(c\), decide whether \(c\) is first in some ranking minimizing \(\sum_t \mu_t\,\operatorname{Kendall}(t,\pi)\) over all rankings \(\pi\) of \(C\).
Let \(C\) be a nonempty candidate set with \(m=|C|\), and let \(c\in C\). Rankings are strict total orders.
A society is given by its support: a list of \(\tau\) distinct rankings \(t\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Use the standard Kendall distance. A candidate is a winner if it is first in at least one ranking minimizing \(\sum_t\mu_t\operatorname{Kendall}(t,\pi)\) over all rankings \(\pi\) of \(C\); retain all tied minimizers.
Is this winner decision problem in \(\mathrm P\) or \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it fixed-parameter tractable with parameter \(m\), with running time \(f(m)\operatorname{poly}(\tau,L)\)?
For explicit finite electorates, Kemeny winner determination is fixed-parameter tractable in \(m\) and is \(\Theta_2^p\)-complete. [The complexity of Kemeny elections](https://www.sciencedirect.com/science/article/pii/S0304397505005785)
For binary integer weights or multiplicities, the identical winner objective is \(\Delta_2^p\)-complete. [High-Multiplicity Election Problems](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1558.pdf) The normalized rational-mass formulation is an equivalent encoding, so the requested hardness-versus-polynomial-time target is already settled.
The problem is \(\mathrm{NP}\)-hard and fixed-parameter tractable with parameter \(m\). More precisely, it is \(\Delta_2^p\)-complete under polynomial-time many-one reductions.
Here, binary-rational masses mean rational numbers whose numerators and denominators are encoded in binary. The proof below establishes the encoding equivalence and gives an exact algorithm with explicit bit-complexity bounds. When \(m=1\), the sole candidate is always a winner.
For a ranking \(\pi\), write its objective value as
\(\displaystyle K_\mu(\pi)=\sum_t\mu_t\operatorname{Kendall}(t,\pi).\)
Integer multiplicities to normalized masses. Consider an election represented by distinct strict rankings \(t\) with positive binary integer multiplicities \(w_t\). Put
\(\displaystyle W=\sum_t w_t,\qquad \mu_t=\frac{w_t}{W}.\)
These masses are positive and sum to one. For every ranking \(\pi\),
\(\displaystyle K_\mu(\pi)=\frac{1}{W}\sum_t w_t\operatorname{Kendall}(t,\pi).\)
Multiplication by the positive constant \(1/W\) preserves all comparisons and equalities between objective values. Consequently, it preserves every minimizing ranking and every winner.
This transformation has polynomial running time and output length: the bit length of \(W\) is at most the largest multiplicity bit length plus \(\lceil\log_2\tau\rceil+1\), and each output mass can be represented by the pair \((w_t,W)\). Neither the candidate set nor the support size changes.
Normalized masses to integer multiplicities. Conversely, write each input mass as \(\mu_t=a_t/b_t\), with positive binary integers \(a_t,b_t\). Define
\(\displaystyle D=\prod_t b_t,\qquad w_t=a_t\frac{D}{b_t}.\)
Each \(w_t\) is a positive integer. Normalization gives
\(\displaystyle \sum_t w_t=D\sum_t\mu_t=D.\)
Moreover,
\(\displaystyle \sum_t w_t\operatorname{Kendall}(t,\pi)=D K_\mu(\pi).\)
Thus this transformation also preserves exactly the minimizing rankings and winners. The bit length of \(D\) is at most \(1+\sum_t\log_2 b_t\), hence is \(O(L)\). Since \(w_t\le D\), every multiplicity has \(O(L)\) bits, and the entire transformation is polynomial in the input length. No electorate expansion is needed.
Applying the cited theorem. Theorem 6.5 of Fitzsimmons and Hemaspaandra states that Kemeny winner determination in high-multiplicity representation is \(\Delta_2^p\)-complete. Their definition uses strict rankings and declares a candidate a winner precisely when it occurs first in some ranking minimizing total Kendall distance. Thus its hypotheses and tie convention agree with this task. [High-Multiplicity Election Problems, Section 6](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1558.pdf)
The two polynomial-time transformations above therefore establish \(\Delta_2^p\)-completeness for the normalized rational-mass problem. In particular, it is \(\mathrm{NP}\)-hard; a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
Use the integer multiplicities obtained above. For distinct candidates \(a,b\), define
\(\displaystyle q_{a,b}=\sum_{t:\,a\text{ precedes }b\text{ in }t}w_t.\)
If \(\pi\) places \(a\) before \(b\), this pair contributes \(q_{b,a}\) to its weighted Kendall objective: exactly the rankings placing \(b\) before \(a\) disagree on that pair. Hence
\(\displaystyle K_w(\pi)=\sum_{a\text{ precedes }b\text{ in }\pi}q_{b,a}.\)
For each subset \(S\subseteq C\), let \(F(S)\) be the minimum of this pairwise sum over all strict rankings of \(S\), counting only pairs contained in \(S\). Set \(F(\varnothing)=0\).
Recurrence. For every nonempty \(S\),
\(\displaystyle F(S)=\min_{x\in S}\left(F(S\setminus\{x\})+\sum_{y\in S\setminus\{x\}}q_{y,x}\right).\)
To prove this, fix the first candidate \(x\) of a ranking of \(S\). Every pair involving \(x\) contributes \(q_{y,x}\), independently of the order of the remaining candidates. All other contributions are exactly those of the remaining ranking on \(S\setminus\{x\}\). Their minimum is \(F(S\setminus\{x\})\), which is attained because there are finitely many rankings. Taking the minimum over all possible first candidates proves the recurrence.
Compute the states in increasing order of subset size. Induction on that size, using the proved recurrence, shows that every computed value is exact.
The minimum score among rankings beginning with the designated candidate \(c\) is
\(\displaystyle F_c=F(C\setminus\{c\})+\sum_{y\in C\setminus\{c\}}q_{y,c}.\)
Therefore,
\(\displaystyle c\text{ is a winner}\quad\Longleftrightarrow\quad F_c=F(C).\)
Indeed, equality means that an attained minimum among rankings beginning with \(c\) is also a global minimum. Conversely, any globally minimizing ranking beginning with \(c\) forces this equality. This comparison retains all tied winners.
Let \(B=O(L+\log(m+1))\). Because \(\sum_t w_t=D\), pairwise totals are at most \(D\), and every score computed by the recurrence is at most \(\binom m2D\). Thus all arithmetic operands have \(O(B)\) bits.
Using schoolbook integer arithmetic:
The resulting running time is
\(\displaystyle O\!\left(\tau L^2+(\tau m^2+m^2 2^m)(L+\log(m+1))\right).\)
This has the required form \(f(m)\operatorname{poly}(\tau,L)\), proving fixed-parameter tractability in \(m\).
The cleared-denominator score is an integer between \(0\) and \(U=\binom m2D\). The threshold question “does some ranking have score at most \(k\)?” belongs to \(\mathrm{NP}\): a ranking is a polynomial-size certificate, and its score can be checked using the pairwise totals.
Binary search over this interval determines the optimum using \(O(\log(U+1))=O(L+\log(m+1))\) oracle queries. After finding the optimum \(K^\ast\), one further \(\mathrm{NP}\) query asks whether a ranking beginning with \(c\) has score at most \(K^\ast\). Its answer is exactly the winner decision.
All preprocessing, query construction, and certificate checks take polynomial time. Thus the problem belongs to \(\mathrm P^{\mathrm{NP}}=\Delta_2^p\), independently confirming the upper bound used in the completeness statement.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The hardness transfer preserves the complete set of minimizing rankings, and the exact algorithm establishes fixed-parameter tractability in \(m\). I found no major or minor issues.
The prover explicitly interprets binary-rational masses as fractions with binary-encoded numerators and denominators. This agrees with the encoding equivalence stated in USER_TASK. It uses \(\tau\) as the number of supported rankings throughout, without expanding multiplicities into individual voters.
The case \(m=1\) is explicitly handled correctly: there is one possible ranking, and the sole candidate is a winner.
Since every \(w_t\) is positive, \(W=\sum_t w_t\) is positive. The masses \(w_t/W\) are positive and sum to one.
The displayed identity \(K_\mu(\pi)=K_w(\pi)/W\) is correct for every ranking \(\pi\). Scaling by the same positive constant preserves both strict comparisons and equalities, so it preserves all minimizers and the stated winner convention.
The bound on the bit length of \(W\) is valid. Writing each mass as \((w_t,W)\) produces polynomial output length, even though the denominator is repeated. Distinctness of rankings and support size are preserved.
Each denominator \(b_t\) divides \(D=\prod_t b_t\), so \(w_t=a_tD/b_t\) is a positive integer. Both displayed identities,
\[
\sum_t w_t=D
\]
and
\[
K_w(\pi)=D K_\mu(\pi),
\]
follow from the input normalization and the definitions.
The product’s bit-length bound is correct. Since the positive multiplicities sum to \(D\), each satisfies \(w_t\leq D\). Thus each output multiplicity has \(O(L)\) bits, and the conversion has polynomial running time and output length. No assumption that the input fractions are reduced is needed.
The cited theorem is accurately identified: Theorem 6.5 establishes \(\Delta_2^p\)-completeness for high-multiplicity Kemeny winner determination. The paper’s definitions use strict total orders, positive integer counts of distinct votes, and the convention that a candidate wins by appearing first in a minimizing consensus ranking. Its hardness argument uses polynomial-time many-one reductions. These match the prover’s application. [High-Multiplicity Election Problems, Sections 2 and 6](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1558.pdf)
Consequently, the encoding transformations transfer completeness to the rational-mass formulation. The conclusions of \(\mathrm{NP}\)-hardness and that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\) are valid.
The orientation of \(q_{a,b}\) is correct. When the proposed ranking places \(a\) before \(b\), precisely the supported rankings placing \(b\) before \(a\) disagree on that pair, contributing \(q_{b,a}\).
The recurrence correctly conditions on the first candidate \(x\). Every pair involving \(x\) contributes \(q_{y,x}\); the remaining pairs contribute the objective on \(S\setminus\{x\}\). These contributions are independent of one another in exactly the way stated.
The base case, finite attainment of the minima, and evaluation in increasing subset size justify every computed state. No missing structural lemma is required.
The expression for \(F_c\) correctly gives the minimum over rankings beginning with \(c\). Such rankings exist, including when the remainder is empty.
The equivalence \(F_c=F(C)\) correctly characterizes whether at least one global minimizer begins with \(c\). Both directions are justified, and equality retains tied minimizers as required.
The bounds \(q_{a,b}\leq D\) and \(K_w(\pi)\leq \binom m2D\) are correct. Intermediate pair sums and recurrence evaluations also fit within the stated \(O(L+\log(m+1))\) bit bound.
The schoolbook preprocessing bound, pairwise-total bound, and subset-state arithmetic count are valid upper bounds. Their sum gives the displayed running time
\[
O\!\left(\tau L^2+(\tau m^2+m^2 2^m)(L+\log(m+1))\right).
\]
Its dependence on \(\tau,L\) has a fixed polynomial exponent, so it establishes the requested fixed-parameter tractability.
A ranking is a polynomial-size certificate for the threshold question, and its score can be checked in polynomial time. The integer search range and oracle-query bound are correct; the separately handled case \(m=1\) causes no problem.
After the optimum is found, the additional query restricting the first candidate to \(c\) exactly decides winner membership. Thus the independent \(\Delta_2^p\) membership argument is sound.
No additional clarification or repair is needed.
⟨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.