Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 1 — class: hardness
Given candidates \(A\), a target \(a\in A\), and an explicitly listed support of rankings \(\rho\) with binary rational masses \(\mu_\rho>0\) summing to \(1\), decide whether some total order \(\sigma\) of ordered candidate pairs makes \(a\) the top element of the ranked pairs outcome obtained by processing pairs in descending order of \(M_\mu(x,y)=\sum_\rho\mu_\rho\mathbf{1}[x\succ_\rho y]-\sum_\rho\mu_\rho\mathbf{1}[y\succ_\rho x]\), breaking ties by \(\sigma\), and locking pairs unless they create a cycle.
Let \(A\) be a nonempty candidate set, \(m=|A|\), and \(a\in A\) the target. Types are strict total rankings of \(A\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Masses sum to \(1\); \(\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\).
For distinct \(x,y\in A\), define \(M_\mu(x,y)=\sum_\rho\mu_\rho\mathbf{1}[x\succ_\rho y]-\sum_\rho\mu_\rho\mathbf{1}[y\succ_\rho x]\).
A tie-breaking rule \(\sigma\) is an arbitrary strict total order on all ordered pairs of distinct candidates. Starting with an empty directed graph, process every such pair in descending margin order, using \(\sigma\) for equal margins; add its edge unless doing so creates a directed cycle. Include zero and negative margins. The final relation is a strict total ranking.
Is deciding whether some \(\sigma\) makes \(a\) the top element of this ranking solvable in polynomial time, or is it NP-hard?
For finite unweighted voter profiles, deciding whether a designated candidate wins for some tie-breaking rule is NP-complete; constructing the outcome for a fixed tie-breaking rule is polynomial-time (Brill and Fischer, *The Price of Neutrality for the Ranked Pairs Method*, 2012).
No separate result for the rational-mass formulation is established by the supplied source.
The decision problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions.
For \(m=1\), the answer is always yes. The complexity result concerns instances with unrestricted \(m\) and \(\tau\). We prove hardness by normalizing explicit unweighted profiles, and membership in \(\mathrm{NP}\) by exact arithmetic on the rational support.
The supplied hardness theorem concerns explicit finite profiles of strict rankings. The source’s formulation processes unordered pairs in descending absolute margin order. It attempts the majority direction, chooses a direction by tie-breaking when the margin is zero, and immediately inserts the reverse direction if the attempted direction would create a cycle. [Brill and Fischer, Theorem 1](https://comsoc-community.org/assets/proceedings/comsoc-2012/Brill.pdf).
We first verify that its possible outcomes agree with those of the question’s ordered-pair procedure.
In any acyclic directed graph, attempting to insert \(x\to y\) creates a cycle exactly when there is already a directed path from \(y\) to \(x\). In that event, immediately inserting \(y\to x\) does not change reachability: that direction was already implied by a path.
For every unordered pair with nonzero margin, the question’s procedure considers its positive-margin direction before its negative-margin direction. Its positive-margin directions occur in exactly descending absolute margin order. Consequently, the positive stage of the question’s procedure and the corresponding stage of the unordered procedure have identical reachability relations, provided they use the same order among equal margins. This follows inductively: an accepted edge changes reachability identically, while an immediately inserted reverse edge in the unordered procedure changes no reachability.
At margin zero, associate each unordered pair with the first occurrence of either of its directions in the ordered procedure. These first occurrences specify an unordered-pair schedule and attempted orientations. After a pair’s first occurrence, its endpoints are comparable by reachability: either the attempted edge was accepted or its reverse was already implied. The pair’s second occurrence therefore either inserts an already implied edge or is rejected. It does not change reachability.
After the zero stage, every pair of candidates is comparable by reachability. Every remaining negative-margin edge is therefore either already implied or rejected, so this stage also changes no reachability.
Conversely, any legal unordered schedule can be reproduced by ordering the positive edges accordingly and, within the zero tier, listing the attempted orientations in the prescribed order before their opposites. Such choices extend to a strict total order on all ordered pairs.
Thus the two procedures have the same set of possible final rankings, and the supplied unweighted hardness theorem applies.
Let \(P=(\rho_1,\ldots,\rho_n)\), with \(n\geq 1\), be an instance of the unweighted possible-winner problem, with candidate set \(A\) and target \(a\). Define its integer margins by
\[ D_P(x,y)=\sum_{i=1}^{n}\bigl(\mathbf{1}[x\succ_{\rho_i}y]-\mathbf{1}[y\succ_{\rho_i}x]\bigr). \]
Aggregate identical rankings. For each distinct ranking \(\rho\), let \(c_\rho\) be its multiplicity and assign mass
\[ \mu_\rho=\frac{c_\rho}{n}. \]
All listed masses are positive and sum to one. For every distinct \(x,y\),
\[ M_\mu(x,y)=\frac{D_P(x,y)}{n}. \]
Multiplication by the positive constant \(1/n\) preserves every strict comparison and equality between margins. Therefore, for each fixed tie-breaking order \(\sigma\), the two instances process exactly the same sequence of ordered pairs. Starting from the same empty graph, they make identical insertion decisions, by induction over that sequence. Hence
\[ a\text{ is a possible winner of }P \quad\Longleftrightarrow\quad a\text{ is a possible winner of }\mu. \]
There are at most \(n\) support types. Each mass has numerator and denominator of bit length \(O(\log(n+1))\), so the output length is
\[ O\!\left(\tau\bigl(m\log(m+1)+\log(n+1)\bigr)\right), \qquad \tau\leq n. \]
Grouping rankings and writing these fractions take polynomial time in the explicit source input length. This proves \(\mathrm{NP}\)-hardness.
If “binary rational” means specifically a dyadic rational, the reduction still works. Take two copies of \(P\), and let \(N\) be the least power of two satisfying \(N\geq 2n\). Pad with \((N-2n)/2\) pairs of mutually reversed rankings. Each padding pair contributes zero to every margin. The resulting profile has margins \(2D_P(x,y)\), and normalization gives dyadic masses and margins \(2D_P(x,y)/N\). Since \(N<4n\), this modification also has polynomial size and preserves all possible outcomes.
Write the input masses as \(\mu_i=p_i/q_i\), for \(1\leq i\leq\tau\), with positive integer denominators encoded in binary. Let
\[ Q=\prod_{i=1}^{\tau}q_i, \qquad w_i=p_i(Q/q_i). \]
The bit length of \(Q\) is \(O(L)\), because the total bit length of the input denominators is at most \(L\). Moreover, \(\sum_i w_i=Q\), so each \(w_i\) also has \(O(L)\) bits.
Compute the integer margins
\[ W(x,y)=\sum_{i=1}^{\tau} w_i\bigl(\mathbf{1}[x\succ_{\rho_i}y]-\mathbf{1}[y\succ_{\rho_i}x]\bigr). \]
Then \(M_\mu(x,y)=W(x,y)/Q\), and \(|W(x,y)|\leq Q\). Thus exact margin comparisons require only integers of \(O(L)\) bits; no expansion into individual voters is needed.
A certificate is a permutation \(\sigma\) of the \(m(m-1)\) ordered pairs, of length \(O(m^2\log(m+1))\) bits. The verifier checks the permutation, sorts the pairs by decreasing \(W(x,y)\) with \(\sigma\) as the secondary order, and simulates the procedure. Before inserting \(x\to y\), it searches for a path from \(y\) to \(x\).
Using schoolbook integer arithmetic and ordinary graph searches, a conservative bit-operation bound for this verification is
\[ O\!\left( \tau L^2+ \bigl(\tau m^2+m^2\log(m+1)\bigr)L+ m^4\log(m+1) \right). \]
Here the terms cover forming the common denominator and integer weights, computing and sorting margins, and performing at most \(m(m-1)\) reachability searches, respectively.
For completeness, the final graph is a strict total ranking. It remains acyclic by construction. For each unordered pair, if its first attempted direction is accepted, the opposite direction is subsequently rejected. If its first attempted direction is rejected, a reverse path already exists, so the opposite edge can subsequently be inserted without creating a cycle. Thus exactly one direction is present for every unordered pair. An acyclic tournament is transitive: \(x\to y\) and \(y\to z\) force \(x\to z\), since \(z\to x\) would create a cycle. The verifier can therefore check whether \(a\) is its top element.
The certificate has polynomial length and is verifiable in polynomial time in \(m,\tau,L\), establishing membership in \(\mathrm{NP}\). Combined with the reduction, this proves \(\mathrm{NP}\)-completeness for the rational-mass formulation.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the rational-mass formulation, with polynomial verification in \(m,\tau,L\). No major or minor mathematical gaps were found.
The cited result is correctly identified. Theorem 1 states that deciding whether a designated alternative is a ranked-pairs winner is \(\mathrm{NP}\)-complete. Its input consists of an explicit finite profile of strict rankings, and a winner is an alternative placed first under some tie-breaking order. Its procedure uses unordered pairs, ordered by absolute margin, and inserts the reverse direction when the attempted direction would create a cycle. These are the relevant hypotheses and procedural differences identified by the prover. [Brill and Fischer, definitions and Theorem 1](https://comsoc-community.org/assets/proceedings/comsoc-2012/Brill.pdf).
The prover does not merely assume that this variant coincides with the question’s variant; Section 1 supplies the necessary comparison.
Each step of the reachability argument is valid.
Consequently, the two procedures have the same possible final rankings. The argument establishes equality of outcome sets; it does not require the same literal tie-breaking order to implement both formulations.
The normalization reduction is correct.
Together with Section 1, this proves the required equivalence of possible-winner answers.
The stated output-length bound is valid under the usual indexed encoding of candidates. Numerators and denominators require \(O(\log(n+1))\) bits, and aggregation is polynomial in the explicit profile’s input length. The reduction does not expand a succinct input into exponentially many voters.
The optional dyadic construction is also correct. Because \(n\geq1\), the chosen power of two \(N\) is even, so \((N-2n)/2\) is a nonnegative integer. Mutually reversed rankings cancel every pairwise margin. The padded profile has exactly \(N\) voters and margins \(2D_P(x,y)\).
The bound \(N<4n\) holds, including when \(2n\) is already a power of two. Normalization therefore gives dyadic masses with polynomial encoding length and preserves all possible outcomes.
The arithmetic bounds are sound.
The certificate specifies the entire tie-breaking order and has polynomial length. Checking that it is a permutation, sorting by margin and certificate position, and performing the stated reachability searches implement the question’s procedure exactly.
The displayed verification bound is conservative but valid: schoolbook arithmetic fits the \(\tau L^2\) term, margin accumulation and sorting fit the stated arithmetic terms, and at most \(m(m-1)\) graph searches fit \(O(m^4\log(m+1))\) bit operations. Ordinary preprocessing of rankings and certificate validation fits within these bounds.
The final-graph argument is correct. Acyclicity is maintained throughout. For each unordered pair, acceptance of its first direction prevents acceptance of the opposite direction. Rejection of its first direction supplies a reverse path that persists, ensuring that the opposite direction can later be inserted.
Thus the final graph contains exactly one direction per unordered pair and is an acyclic tournament. The stated triangle argument correctly establishes transitivity, so checking whether \(a\) is its top element is sufficient.
The case \(m=1\) is explicitly handled. Positive total mass implies nonempty support, and the proof does not confuse support size with the number of possible rankings.
The conclusion is therefore justified. As usual, \(\mathrm{NP}\)-completeness does not unconditionally exclude a polynomial-time algorithm; it excludes one unless \(\mathrm{P}=\mathrm{NP}\).
⟨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.