| paper | d4-conf-aaai-2012-0119 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
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.
Types are complete candidate rankings \(\rho\); each type has mass \(\mu_\rho\). Pairwise margins are computed from those masses, and the decision variable is a tie-breaking order \(\sigma\) over ordered candidate pairs. The question is whether the target candidate can be the top-ranked alternative for some such order.
The mirror covers possible-winner and unique-winner determination from Theorems 1 and 2. It leaves manipulation, incomplete-profile winner questions, and the comparison with Kemeny’s rule aside.
The strongest mirror is the paper’s neutral, irresolute ranked pairs rule, \(RP\), where every tie-breaking order is considered. The type is a complete ranking \(\rho\) of the candidates. In a large electorate with recurring ballot patterns, \(\mu_\rho\) is the fraction of voters with ranking \(\rho\); the support lists the \(\tau\) rankings with positive mass. That is a credible regime for a large membership election or public ballot with a moderate candidate slate: the number of voters can greatly exceed the number of distinct rankings. For a hard family, the slate and support may grow too, but repeating every ballot any number of times preserves the distribution and the outcome.
For a distribution \(\mu\), define the pairwise margin
\[
M_\mu(x,y)=\sum_{\rho}\mu_\rho\,\mathbf{1}[x\succ_\rho y]
-\sum_{\rho}\mu_\rho\,\mathbf{1}[y\succ_\rho x].
\]
Process ordered candidate pairs in descending order of \(M_\mu\), using a total order \(\sigma\) to break ties, and lock a pair unless doing so creates a cycle. Let \(L_{\mu,\sigma}\) be the resulting ranking. The set of continuous ranked pairs winners is
\[
RP_\infty(\mu)=\{\operatorname{top}(L_{\mu,\sigma}):\sigma
\text{ is a total order of the ordered candidate pairs}\}.
\]
This is a decision problem, not an optimization problem: the variable is the admissible tie-breaking order, and the question is whether the target belongs to \(RP_\infty(\mu)\). A yes-instance has a witnessing \(\sigma\). The input is the candidate set, the explicitly listed support rankings and binary rational masses summing to one, and a target candidate.
The lead anchor is Theorem 1, proved in this paper: “Deciding whether a given alternative is a ranked pairs winner is NP-complete.” Its continuous mirror asks, given \(\mu\) and target \(a\), whether \(a\in RP_\infty(\mu)\). I expect NP-completeness, with the hardness transferring from the discrete problem. If a discrete profile has \(n_\rho\) voters of ranking \(\rho\), set \(\mu_\rho=n_\rho/n\), where \(n\) is the electorate size. Then \(M_\mu(x,y)=n_R(x,y)/n\), so every comparison and tie among pairwise margins is preserved, and the same tie-breaking orders produce the same outcomes. Converting an explicitly listed profile into these rational masses is polynomial time. Membership in NP also carries over: a total order of the \(O(m^2)\) pairs is a polynomial-size certificate, and the margins and resulting ranking can be computed using exact rational arithmetic in polynomial time. The paper’s SAT reduction builds variable, literal, and clause gadgets into the alternatives, so the hardness is driven by the agenda as well as the profile; it is a natural Class B case.
A second, worthwhile anchor is Theorem 2, also proved here: “Deciding whether a given alternative is the unique ranked pairs winner is coNP-complete.” Its continuous mirror asks whether \(RP_\infty(\mu)=\{a\}\)—equivalently, whether every other candidate is absent from the set of possible tops across tie-breakings. I expect coNP-completeness for the same embedding reason. A no-instance has a certificate consisting of another candidate \(b\ne a\) and a tie-breaking order that makes \(b\) the top-ranked candidate. This mirrors a distinct question in the paper: whether the outcome is forced to be the target, rather than merely whether the target can win. Theorem 2’s hardness reduction is proved by adapting the construction to a reduction from UNSAT.
These mirrors cover winner determination and unique-winner determination. They do not attempt to continuize manipulation, possible or necessary winners for incomplete profiles, or the paper’s comparison with Kemeny’s rule. Useful follow-up questions would be whether either problem is fixed-parameter tractable in the support size \(\tau\), and whether restrictions on the number or structure of tied pairwise margins yield tractable cases.
The soft spot is that this paper’s outcomes depend only on pairwise margins: every rational distribution in the mirror can be converted into some finite electorate by clearing denominators, although that electorate may be exponentially large relative to the binary encoding of the masses. So this mirror gives no new outcome rule, and the core hardness does not disappear under continuization. Its case is instead that the distribution over voter types is a sensible high-multiplicity input object, and complexity on that object is precisely the question the programme wants charted. The paper itself does not formulate that support-and-mass input, but its ranked pairs problem carries over exactly.
The strongest case against these mirrors is that they offer very little independent continuous structure. For a rational society \(\mu\), clear the denominators to obtain counts \(n_\rho=D\mu_\rho\). Then \(n_R(x,y)=D M_\mu(x,y)\), so every pair priority, tie, and possible ranked pairs outcome is preserved. Ranked pairs uses the population only through this finite margin matrix; changing the distribution while keeping its margins fixed changes nothing. Theorem 2 is less independent still: non-uniqueness has a witness consisting of another candidate and a tie-breaking order, so its continuous version largely repackages the complement of Theorem 1’s question. These are not two distinct continuous phenomena, and neither calls for the continuous-optimization machinery that motivates much of ChoCo.
That makes the proposed programme of work look unusually thin: define rational masses, transfer the existing results, and study a problem whose decisive structure remains the finite candidate agenda. But this is a case about research value, not a decisive objection to the mirrors. The brief explicitly rules out dismissing a question because its answer transfers or because its hardness lives in the alternatives. And clearing denominators can expand a binary-encoded mass input substantially, so the continuous input representation still poses a computational question of its own.
I therefore can’t honestly defeat Theorem 1. A population with many recurring ballot types is plausible, and the distribution-over-rankings model is well-posed. Theorem 2 adds little as a separate anchor, but the brief says one surviving anchor is enough. The negative case is weak; the proponent’s first mirror survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.