Answer: \(\mathrm{NP}\)-complete, even for \(\tau\leq 8\) with masses in \(\{1/8,2/8,\ldots,8/8\}\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding whether a given alternative is a ranked pairs winner is NP-complete, if the number of voters is even and at least eight.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of complete rankings over candidates \(C\), with positive binary-rational masses \(\mu_t\) summing to \(1\), define \(M_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\). Include an edge \(a\to b\) of strength \(M_\mu(a,b)\) whenever this margin is positive. Given a target \(c^\star\), determine whether it is top-ranked in at least one outcome of neutral Ranked Pairs over all permitted tie-breakings.
Let \(C\) be a nonempty candidate set with \(m=|C|\), and let \(c^\star\in C\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings, each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For distinct candidates define \(M_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\).
Neutral Ranked Pairs processes every unordered candidate pair in decreasing order of \(|M_\mu(a,b)|\), allowing every ordering within equal-strength groups. Start with an empty directed relation. For a nonzero margin, try adding the majority-preferred orientation; if this creates a directed cycle, add the opposite orientation instead. For a zero margin, either orientation may be tried first, again adding its opposite if necessary. After every pair has been processed, the relation is a strict complete ranking. All rankings obtainable through these choices are outcomes.
Is deciding whether \(c^\star\) is top-ranked in at least one outcome solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete winner membership is NP-complete for every fixed even number of voters at least eight (Brandt, Harrenstein, Kardel, and Seedig, 2013). [Brill and Fischer](https://webspace.maths.qmul.ac.uk/felix.fischer/publications/bf_ranked.pdf) also establish unrestricted discrete NP-completeness and polynomial-time computation when the tie-breaking rule is fixed.
The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau\leq 8\) and every mass belongs to \(\{1/8,2/8,\ldots,8/8\}\). Consequently, it admits an algorithm polynomial in \(m,\tau,L\) only if \(\mathrm{P}=\mathrm{NP}\).
The proof uses the discrete hardness theorem stated in the question and a polynomial-time reduction that preserves every obtainable ranking.
The known theorem states that deciding whether a designated candidate is a neutral Ranked Pairs winner is \(\mathrm{NP}\)-complete for profiles consisting of exactly eight voters with strict complete rankings. This is the eight-voter case of Theorem 3 of [Brandt, Harrenstein, Kardel, and Seedig](https://pub.dss.in.tum.de/brandt-research/fewvoters.pdf).
The relevant rule agrees with the formulation in the question: process unordered pairs by decreasing absolute majority margin; try the majority orientation, or a freely chosen orientation when the margin is zero; and add the opposite orientation if the attempted orientation creates a cycle. Winners are the top candidates obtainable under some tie-breaking rule. See Section 3 of [Brill and Fischer](https://webspace.maths.qmul.ac.uk/felix.fischer/publications/bf_ranked.pdf).
For completeness, unrestricted tie-breaking in that formulation permits precisely the choices allowed here. Its tie-breaking rule is a total order on ordered candidate pairs. Given any desired processing order and any desired first orientations for zero-margin pairs, place the two orientations of each unordered pair consecutively in that processing order, placing the desired first orientation first. This defines a compatible total order; diagonal pairs may be placed arbitrarily. Conversely, any such total order induces an allowed processing order and zero-margin choices. Thus the possible outcomes coincide.
Take an instance of the eight-voter problem, with rankings \(R_1,\ldots,R_8\), candidate set \(C\), and designated candidate \(c^\star\).
Let \(T\) contain exactly the distinct rankings appearing in the profile. For each \(t\in T\), define its multiplicity and mass by
\(k_t=|\{i\in\{1,\ldots,8\}:R_i=t\}|\), and \(\mu_t=k_t/8\).
This produces a valid society:
Let the discrete majority margin be
\(D_R(a,b)=\sum_{i=1}^{8}\bigl(\mathbf{1}[a\succ_{R_i}b]-\mathbf{1}[b\succ_{R_i}a]\bigr)\).
Grouping identical rankings gives, for every distinct \(a,b\),
\(M_\mu(a,b)=\sum_{t\in T}\frac{k_t}{8}\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr)=\frac{1}{8}D_R(a,b)\).
Multiplication by the same positive constant preserves all margin signs, all zero margins, and all comparisons and equalities between absolute strengths. Therefore the two instances admit exactly the same processing orders and attempted orientations.
Fix any such choices. Initially both procedures have the empty relation. If their relations agree before processing a pair, their attempted orientations agree, and the cycle tests have the same answer. Hence their added orientations agree. Induction over all pairs proves that their final rankings coincide. Because the admissible choices also coincide, their entire outcome sets are equal.
In particular, \(c^\star\) is a discrete Ranked Pairs winner if and only if it is top-ranked in some outcome of the constructed society.
The transformation is polynomial-time: compare the eight rankings, group identical ones, and attach their multiplicities divided by eight. It outputs at most eight rankings and masses of constant encoding length. This proves \(\mathrm{NP}\)-hardness under the asserted restrictions.
A certificate specifies a permutation of the \(\binom{m}{2}\) unordered pairs, together with a first-orientation bit for every zero-margin pair. Its length is \(O(m^2\log(m+1))\).
First, all margins and strength comparisons can be computed exactly in polynomial time. Write each input mass as \(\mu_t=p_t/q_t\), with binary-encoded integers and \(q_t>0\). Set \(Q=\prod_{t\in T}q_t\). The bit length of \(Q\) is \(O(L)\). For each pair compute the integer
\(W(a,b)=\sum_{t\in T}p_t(Q/q_t)\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr)\).
Then \(M_\mu(a,b)=W(a,b)/Q\). Consequently, signs and absolute-strength comparisons reduce to exact integer comparisons. All integers involved have polynomial bit length, and there are \(O(\tau m^2)\) summands to process.
The verifier checks that the certificate lists every unordered pair exactly once and that strengths are nonincreasing. It then simulates the stated procedure. In an acyclic directed graph \(G\), adding \(a\to b\) creates a cycle exactly when \(G\) already contains a directed path from \(b\) to \(a\); reachability is polynomial-time computable.
The fallback orientation preserves acyclicity. Indeed, if \(G\) contains a path from \(b\) to \(a\), it cannot also contain a path from \(a\) to \(b\), since those paths would form a directed cycle. Thus adding \(b\to a\) is safe.
After all pairs have been processed, the graph is an acyclic tournament. It is transitive: if \(a\to b\) and \(b\to d\), the alternative orientation \(d\to a\) would form a directed triangle. Hence the graph represents a strict complete ranking.
Finally, the verifier accepts exactly when \(c^\star\) has an outgoing edge to every other candidate. Every accepting certificate therefore witnesses a valid outcome with \(c^\star\) on top, and every such outcome supplies an accepting certificate. This proves membership in \(\mathrm{NP}\), completing the proof.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes \(\mathrm{NP}\)-completeness, including the claimed restriction to \(\tau\leq 8\) and masses in \(\{1/8,2/8,\ldots,8/8\}\). I found no major or minor mathematical issues.
Theorem 3 of [Brandt, Harrenstein, Kardel, and Seedig](https://pub.dss.in.tum.de/brandt-research/fewvoters.pdf) states the claimed \(\mathrm{NP}\)-completeness result for even voter counts of at least eight. The paper explicitly identifies its Ranked Pairs variant as the neutral variant. Applying its eight-voter case is legitimate.
The rule identification is also correct. Section 3 of [Brill and Fischer](https://webspace.maths.qmul.ac.uk/felix.fischer/publications/bf_ranked.pdf) specifies:
These match the task’s rule.
The prover’s equivalence argument for tie-breaking choices is valid. Putting the two orientations of each unordered pair consecutively in a total order realizes any prescribed processing order within strength groups and any prescribed first orientations for zero margins. Ordering these blocks across different strengths imposes no additional restriction, because strengths take priority. Conversely, the cited definition converts each total order into allowed pair-processing and orientation choices. Diagonal ordered pairs have no effect.
Finding: The external theorem is stated sufficiently precisely, its relevant hypotheses are satisfied, and the rule correspondence is justified.
For an eight-voter profile, grouping identical rankings gives distinct support elements with positive multiplicities \(k_t\). Consequently:
Repeated voter rankings are permitted in the source problem, and grouping them is compatible with the target’s requirement that support rankings be distinct.
Finding: The reduction produces valid instances under the asserted restrictions.
The grouping computation is exact:
\[ M_\mu(a,b)=\frac{1}{8}D_R(a,b). \]
The same positive factor applies to every pair. It therefore preserves signs, zero margins, strict strength comparisons, and strength ties.
Thus the two instances have identical admissible processing orders and first-orientation choices. The induction comparing their procedures is sound: equal current relations and equal attempted orientations give equal cycle-test results and equal added orientations. This proves equality of final rankings for every shared choice sequence, and hence equality of the entire outcome sets.
The designated-candidate equivalence follows directly from that equality.
Finding: The reduction preserves precisely the property being decided, not merely a weaker property.
Only eight rankings need to be compared and grouped. Their number is fixed, and each output mass has constant encoding length. The output ranking data have polynomial size in the source input, and grouping takes polynomial time.
Finding: This is a valid polynomial-time many-one reduction establishing the claimed restricted \(\mathrm{NP}\)-hardness.
A permutation of the \(\binom{m}{2}\) pairs and at most one bit per pair have total length \(O(m^2\log(m+1))\).
For the stated binary integer encoding of numerators and denominators, the product \(Q=\prod_t q_t\) has bit length bounded by the sum of the denominator bit lengths, hence \(O(L)\). Each quotient \(Q/q_t\) is an exact integer. The products and sums defining \(W(a,b)\) have polynomial bit length.
Since \(Q>0\), signs and absolute-strength comparisons can be checked using the integer numerators. Ranking comparisons and all arithmetic operations require polynomial time.
Finding: The arithmetic verification remains polynomial in bit complexity; it does not assume unit-cost arithmetic on arbitrarily large numbers.
The verifier checks pair coverage and nonincreasing strength, then follows the specified procedure.
The cycle criterion is correct: adding \(a\to b\) creates a directed cycle exactly when a path from \(b\) to \(a\) already exists. If that path exists in an acyclic graph, a path in the reverse direction cannot also exist. Therefore the fallback edge preserves acyclicity.
Processing each unordered pair exactly once produces a tournament. The prover’s directed-triangle argument correctly establishes transitivity of an acyclic tournament. The resulting relation is therefore a strict complete ranking.
The final acceptance condition—an outgoing edge from \(c^\star\) to every other candidate—is exactly top-ranked membership. Certificate soundness and completeness are both established.
For \(m=1\), the pair list is empty and the outgoing-edge condition is vacuously satisfied, correctly accepting the sole candidate. No omitted exceptional case affects the argument.
Finding: Membership in \(\mathrm{NP}\) is fully justified.
None. The write-up requires no mathematical repair or additional clarification.
⟨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.