Answer: \(\mathrm{NP\text{-}complete}\), and therefore \(\mathrm{NP\text{-}hard}\)
Theorem 6.8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet n ≥8 be a fixed even integer. Then WIN- NER DETERMINATION for Sequential-Borda-Loser (aka Baldwin), restricted to instances with exactly n voters, is NP-complete. In addition, if the ETH is true, then the prob- lem cannot be solved in 2o(m) · poly(m) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, a rational distribution μ over complete rankings of C, and a designated candidate d, does there exist a sequential Baldwin elimination in which each round removes a minimum weighted-Borda-score candidate and d is the last remaining candidate?
Given a candidate set \(C\), explicitly listed complete ranking types \(T\subseteq L(C)\), and binary-encoded rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), let \(S\subseteq C\) be the surviving candidates. For \(c\in S\), define its Borda score as \(\sum_{t\in T}\mu_t\bigl(|S|-\operatorname{pos}_{t|S}(c)+1\bigr)\).
A Sequential-Borda-Loser elimination is legal if, at each round, it removes any surviving candidate of minimum current Borda score, then restricts every ranking to the survivors. Given \(d\in C\), ask whether some legal elimination sequence leaves \(d\) as the sole final survivor.
Target. Is this rational-mass Sequential-Borda-Loser winner-determination problem solvable in polynomial time, or is it NP-hard?
Nearest known results. In the discrete setting, Sequential-Borda-Loser winner determination is NP-complete even when the number of voters is any fixed even \(n\ge 8\); consequently, the unrestricted discrete problem is NP-hard.
No result for the exact rational-mass formulation is asserted here.
Rational-mass Sequential-Borda-Loser winner determination is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when there are at most eight ranking types and every mass is an integer multiple of \(1/8\).
The hardness statement uses the given premise that discrete Sequential-Borda-Loser winner determination is \(\mathrm{NP}\)-complete for every fixed even number \(n\geq 8\) of voters.
Fix \(n=8\). Consider a discrete instance consisting of:
For every distinct ranking \(t\) occurring among these eight ballots, let
\[ k_t=\left|\{i\in\{1,\ldots,8\}:t_i=t\}\right|. \]
Construct the rational-mass instance with the same candidate set and distinguished candidate, ranking-type set
\[ T=\{t_i:i\in\{1,\ldots,8\}\}, \]
and masses
\[ \mu_t=\frac{k_t}{8}. \]
These masses are nonnegative and satisfy
\[ \sum_{t\in T}\mu_t = \frac{1}{8}\sum_{t\in T}k_t = 1. \]
The construction is polynomial-time. Indeed, there are at most eight types, and every mass has a constant-size denominator.
For a surviving set \(S\subseteq C\), define the positive-base discrete Borda score
\[ B^{\mathrm{disc},+}_S(c) = \sum_{i=1}^{8} \left( |S|-\operatorname{pos}_{t_i|S}(c)+1 \right). \]
The mass score in the constructed instance is
\[ \begin{aligned} B^\mu_S(c) &= \sum_{t\in T} \frac{k_t}{8} \left( |S|-\operatorname{pos}_{t|S}(c)+1 \right)\\ &= \frac{1}{8} B^{\mathrm{disc},+}_S(c). \end{aligned} \]
Consequently, for all \(c,c'\in S\),
\[ B^\mu_S(c)\leq B^\mu_S(c') \quad\Longleftrightarrow\quad B^{\mathrm{disc},+}_S(c) \leq B^{\mathrm{disc},+}_S(c'). \]
Thus the minimum-score candidates are exactly the same in both instances for every possible surviving set \(S\).
If the cited discrete theorem uses the conventional zero-based Borda score
\[ B^{\mathrm{disc},0}_S(c) = \sum_{i=1}^{8} \left( |S|-\operatorname{pos}_{t_i|S}(c) \right), \]
then
\[ B^{\mathrm{disc},+}_S(c) = B^{\mathrm{disc},0}_S(c)+8. \]
The added quantity \(8\) is independent of \(c\), so it also leaves the set of minimum-score candidates unchanged.
By induction on the number of elimination rounds, an elimination sequence is legal in the discrete instance if and only if it is legal in the constructed mass instance. Therefore,
\[ d\text{ can be the final survivor in the discrete instance} \quad\Longleftrightarrow\quad d\text{ can be the final survivor in the mass instance}. \]
This is a polynomial-time many-one reduction. Hence the rational-mass problem is \(\mathrm{NP}\)-hard.
Let \(m=|C|\). A certificate is an ordering
\[ (c_1,\ldots,c_{m-1}) \]
of \(C\setminus\{d\}\), interpreted as the proposed elimination sequence.
At round \(j\), let
\[ S_j=C\setminus\{c_1,\ldots,c_{j-1}\}. \]
The verifier checks that, for every \(x\in S_j\),
\[ B^\mu_{S_j}(c_j)\leq B^\mu_{S_j}(x). \]
Positions in every restricted ranking can be computed by scanning the explicitly listed ranking. It remains to justify that the rational comparisons are polynomial-time exact computations.
Write each input mass as
\[ \mu_t=\frac{a_t}{b_t}, \]
where \(a_t,b_t\) are binary-encoded integers and \(b_t>0\). Let
\[ D=\prod_{t\in T}b_t. \]
Its bit length satisfies
\[ \log D=\sum_{t\in T}\log b_t, \]
which is at most linear in the total encoding length of the masses. Multiplying a score comparison by \(D>0\) reduces it to comparison of binary integers:
\[ D\left(B^\mu_{S_j}(x)-B^\mu_{S_j}(c_j)\right) = \sum_{t\in T} a_t\frac{D}{b_t} \left( \operatorname{pos}_{t|S_j}(c_j) - \operatorname{pos}_{t|S_j}(x) \right). \]
Every position difference has absolute value at most \(m-1\), and all integers in this expression have polynomial bit length. Standard binary integer arithmetic therefore verifies each comparison in polynomial time. There are only polynomially many rounds and comparisons.
Thus the problem belongs to \(\mathrm{NP}\).
The rational-mass formulation does not make possible-winner determination polynomial-time: the fixed-eight-voter discrete instances embed exactly after normalization. Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness. Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the target. The reduction correctly embeds the fixed-eight-voter discrete problem into the rational-mass formulation, preserves every legal elimination sequence, and establishes membership in \(\mathrm{NP}\).
No substantive gaps, false statements, or missing hypotheses were found.
The prover legitimately invokes the supplied premise that the discrete problem is \(\mathrm{NP}\)-complete for exactly eight voters.
Grouping identical ballots into ranking types and assigning each distinct type \(t\) mass \(k_t/8\) is correct. The masses are nonnegative, sum to \(1\), have constant-size encodings, and produce at most eight explicitly listed types. The construction is polynomial-time.
For every surviving set \(S\), expanding each type according to its multiplicity gives
\[ B^\mu_S(c)=\frac{1}{8}B^{\mathrm{disc},+}_S(c). \]
Multiplication by the positive constant \(1/8\) preserves all pairwise score comparisons, including equality. Therefore it preserves the complete set of minimum-score candidates, not merely one selected loser.
The treatment of the conventional zero-based Borda definition is also correct: the positive-base score adds exactly \(1\) per voter, hence \(8\) to every candidate’s score in every round. This uniform shift preserves minima and ties.
Because this equivalence holds for every possible surviving set, the induction asserting equivalence of legal elimination sequences is valid. Consequently, the distinguished candidate is a possible final survivor in one instance exactly when it is in the other.
The construction is a polynomial-time many-one reduction from the fixed-eight-voter discrete problem. Thus the claimed \(\mathrm{NP}\)-hardness, including the restriction to at most eight ranking types with masses that are multiples of \(1/8\), follows.
An ordering of all candidates other than \(d\) is a polynomial-size certificate. Under the ordinary meaning of “ordering of \(C\setminus\{d\}\),” it contains every such candidate exactly once.
At each round, checking that the proposed eliminated candidate has score no larger than every surviving candidate exactly verifies the legality condition.
The common-denominator argument is valid. Although \(D=\prod_t b_t\) may be numerically large, its binary length is the sum of the denominator bit lengths and is therefore polynomial in the input length. The displayed cleared-denominator identity has the correct sign and cancels the candidate-independent terms. All resulting integers have polynomial bit length, so exact comparisons require polynomial time.
There are only \(m-1\) rounds and polynomially many comparisons per round. Hence membership in \(\mathrm{NP}\) is established.
The claimed \(\mathrm{NP}\)-completeness is justified. In particular, the answer correctly classifies the target problem as \(\mathrm{NP}\)-hard.
⟨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.