| paper | d4-conf-ijcai-2018-0283 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; belongs to \(\mathsf{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(A\), a finite support \(T\) of strict ranking types over \(A\), positive rational masses \(\mu_t\) summing to \(1\), a fixed tie-breaking order, and candidate \(c\), define \(\Delta_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\). Apply the paper’s Ranked Pairs rule to these margins; is \(c\) the resulting winner?
A society is a finite support \(T\) of strict ranking types over candidates \(A\), with rational mass \(\mu_t>0\) on each type and \(\sum_{t\in T}\mu_t=1\). Pairwise margins derived from these masses form the weighted majority graph used by Ranked Pairs; there are no optimization variables, and the output is whether the distinguished candidate wins.
The mirror covers Theorem 2’s Ranked Pairs winner determination and also supports Theorem 1’s Schulze winner question. It leaves the Pregel algorithm, runtime experiments, and computation of the full Schulze ranking outside the mirror.
The strongest mirror is Continuous Ranked Pairs Winner Determination. Its type is a complete ranking of the candidates, and its mass is the fraction of the electorate with that ranking. Given a candidate set \(A\), a finite list of ranking types \(T\), positive rational masses \(\mu_t\) summing to \(1\), a candidate \(c\), and the paper’s tie-breaking order \(T_{\mathrm{tie}}\), form the pairwise margins
\[ \Delta_\mu(a,b)=\sum_{t\in T}\mu_t\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr). \]
Apply Ranked Pairs to those margins, using the paper’s majority-margin ordering and tie-breaking convention. The question is whether \(c\) is the resulting top-ranked candidate; a solution is yes or no. This is a decision problem, not an optimization problem.
A plausible regime is a large online community or open-source project voting on a shared slate of proposals. If a million members rank six proposals, there are at most \(6!=720\) strict ranking types, so the population can be much larger than its support. Across instances, the slate size \(m\) can vary; the support size \(\tau\) records the distinct ballots actually present. Each type captures every preference feature this problem uses, exactly as high multiplicity requires.
The anchor is Theorem 2, proved in Section 3 of this paper: RANKED PAIRS WINNER DETERMINATION is P-complete. The instance is a weighted tournament graph and a candidate; the question is whether that candidate wins under Ranked Pairs with the fixed tie-breaking convention. The paper proves the result here: membership in P is known, and its P-hardness reduction is from the complement of Edge Maximal Acyclic Subgraph. The arXiv v2 text includes a corrected P-hardness proof.
This is a particularly direct population mirror. A finite profile with \(n_t\) voters of each ranking type gives masses \(\mu_t=n_t/n\). Normalizing every pairwise margin by the same positive factor \(n\) preserves the order of margins and ties, so it preserves the Ranked Pairs result. Conversely, rational masses can be cleared to integer multiplicities using a common denominator. That denominator may be exponentially large as a number, so the reverse conversion need not produce a polynomial-size *explicit voter list*; it is polynomial-size in the natural high-multiplicity representation of binary-encoded counts. For hardness, the paper notes that its weighted graphs can be realized by preference profiles using McGarvey’s theorem. Its reduction has polynomially bounded integer weights; scaling them uniformly if needed preserves the pair ordering. Thus the P-hardness survives in the rational-mass model. The reduction’s combinatorics lie in the candidate graph, not in fine-grained control of individual voters.
I expect this mirror to retain the paper’s P-hardness: it is a Class B case at the level of parallel complexity. P-completeness is not NP-hardness; it means the problem has a sequential polynomial-time algorithm, while efficient highly parallel algorithms would imply \(P=NC\). That distinction fits the paper’s central contrast about parallel computation.
A second credible mirror is Continuous Schulze Winner Determination. It has the same instance of candidates, ranking types, and rational masses, plus a distinguished candidate \(c\). From \(\Delta_\mu\), form a directed edge \(a\to b\) of weight \(\Delta_\mu(a,b)\) whenever that margin is positive. Let \(p_\mu(a,b)\) be the maximum, over paths from \(a\) to \(b\), of the minimum edge weight on the path. The question is whether \(c\) is a Schulze winner, meaning \(p_\mu(c,b)\ge p_\mu(b,c)\) for every candidate \(b\). A solution is again yes or no, with ties counting as winning.
Its anchor is Theorem 1, also proved in Section 3: SCHULZE WINNER DETERMINATION is NL-complete. Its instance is a weighted tournament graph and a candidate, and it asks whether that candidate is a Schulze winner. The paper proves NL membership using widest-path reachability and NL-hardness by reduction from Reachability. The hardness construction has even integer weights and, as the paper observes, can be realized by a profile of linear orders. Normalizing the corresponding voter counts gives rational masses and scales every path width uniformly, preserving the winner comparisons. So the continuous problem retains at least the graph problem’s NL-hardness. I would expect sequential tractability, but would not claim the full rational-mass encoding is NL-complete without analyzing the cost of aggregating binary-encoded rational masses. Whether that encoding remains in NL or adds arithmetic complexity is a further question.
These mirrors cover the paper’s two named winner-determination complexity results. They do not mirror the Pregel algorithm, its runtime experiments, or computation of the full Schulze ranking. The paper itself works with weighted majority graphs and explicitly says preference profiles are unnecessary as input. That is also the main weakness of the case: authors could regard a distribution over ballots as an upstream representation of their graph problem, rather than a new computational object. Still, the profile is the population in the ordinary voting model, and the paper establishes that such profiles realize the relevant graph instances. The mirror therefore preserves the authors’ winner questions while making the society a rational distribution over voter types.
The strongest case against both anchors is that the paper’s computational object is already the weighted majority graph, not a population. The authors say rankings are unnecessary as input; once pairwise margins are known, Ranked Pairs orders those margins and Schulze compares widest paths. A distribution over ranking types supplies those margins, but neither theorem asks what to do with voter mass. The continuous formulation therefore adds a population representation to a winner problem whose stated input has already discarded the population.
That objection applies to Theorem 2, Ranked Pairs Winner Determination, and Theorem 1, Schulze Winner Determination. Normalizing a finite electorate’s margins preserves their order and ties for Ranked Pairs, and scales all path widths uniformly for Schulze. So in each proposed mirror, the distribution can be collapsed to the same margin graph the paper already processes. If ChoCo requires a mirror to expose a computational role for population mass, these results offer little foothold: the paper studies graph computation as candidate count grows, not computation as voter multiplicities grow.
But this does not defeat either mirror by the programme’s stated standard. A distribution over ballot types is a sensible high-multiplicity society, and asking whether a candidate wins in that society is a well-posed computational question. The graph is a sufficient statistic for the rules, not evidence that the population model is incoherent. The paper’s realizability discussion also connects its graph instances back to voter profiles. Treating the graph formulation as disqualifying would mistake a compact representation for the absence of a population.
So the negative case is weak. I can argue that both mirrors are redundant at the level of the rules’ inputs, but I cannot honestly conclude that no worthwhile scenario exists. The open-source community example is plausible, and neither named theorem can be passed over: both survive as continuous winner-determination questions.
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.