| paper | d4-conf-aldt-2015-0012 |
| 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_with_minor_gaps
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given \(C\), \(p\in C\), and a binary-rational distribution \(\mu\) over the supported complete rankings of \(C\), decide whether \(C\) has a split \(C_1\sqcup C_2\) with \(\bigl||C_1|-|C_2|\bigr|\le 1\) such that each side advances its sole weak Condorcet winner, if one exists, according to \(q_\mu(a,b)=\sum_{t:\,a\succ_t b}\mu_t\), and \(p\) is the sole weak Condorcet winner among the candidates who advance.
The voter population is a distribution \(\mu\) over complete rankings, with each supported ranking carrying rational mass. The decision is a balanced partition of the finite candidate set; pairwise contest masses determine weak Condorcet winners in the preliminary elections and runoff, with ties eliminated.
The mirror covers only Theorem 4.4’s weakCondorcet-CCREPC-TP NP-completeness result; it does not cover the paper’s other equipartition, multipartition, or voter-group results.
My strongest case is a narrow mirror of the paper’s weakCondorcet candidate equipartition result. Imagine a large party or membership organization choosing among a sizable candidate slate: its members rank the candidates, the slate is split into two nearly equal sets, and only a unique winner of either preliminary election advances. A voter type is a complete ranking \(t\) of \(C\); \(\mu_t\) is the fraction of members with that ranking. This is a plausible high-multiplicity regime when the organization has \(N\) members but only \(\tau\) distinct rankings, with \(N\gg\tau\). Duplicating every ballot can make that ratio arbitrarily large without changing the society’s proportions or the election result.
Call the mirror Continuous WeakCondorcet-CCREPC-TP. Its input is a candidate set \(C\), a distinguished candidate \(p\), and a distribution \(\mu\) over the rankings of \(C\), given by its \(\tau\) positive-mass rankings and binary rational masses. For candidates \(a,b\), let
\[
q_\mu(a,b)=\sum_{t:\,a\succ_t b}\mu_t.
\]
For any candidate set \(S\), its weak Condorcet winners are the candidates \(a\in S\) with \(q_\mu(a,b)\ge\tfrac12\) for every \(b\in S\setminus\{a\}\). The question is whether \(C\) has a partition \(C_1\sqcup C_2\) with \(||C_1|-|C_2||\le1\) such that, in each subelection, only a sole weak Condorcet winner advances (ties-eliminate), and \(p\) is the sole weak Condorcet winner of the final election among the advancing candidates. A solution is such a candidate partition.
The anchor is Theorem 4.4, proved in this paper. In full, it says that weakCondorcet-CCRPC-TE and weakCondorcet-CCRPC-TP are in P, while weakCondorcet-CCREPC-TP is NP-complete. My anchor is the last claim: the paper proves the equipartition case NP-complete by a reduction from Cubic Vertex Cover, using McGarvey’s construction to realize the needed pairwise contests.
I expect hardness to transfer. Given a finite voter profile \(V\), form \(\mu_t\) by dividing the number of voters with ranking \(t\) by \(|V|\). This preserves every pairwise majority and tie, so it preserves the winners of every subelection and runoff, as well as the balanced candidate partition. Applying this translation to the paper’s reduction gives a yes/no-preserving reduction to the continuous problem. For binary rational masses, a candidate partition is a polynomial-size certificate and its pairwise masses can be checked exactly in polynomial time; so this mirror is NP-complete under the stated encoding. The hardness lies in the candidate agenda and its balanced split, not in having to track each voter individually. That makes it a Class B mirror: a legitimate continuous-population problem whose hardness survives.
The scope is deliberately limited to Theorem 4.4’s weakCondorcet candidate-equipartition result. It keeps the paper’s election rule, balanced candidate partition, tie-elimination rule, and runoff structure intact; only the voter population becomes a distribution. I would next ask whether hardness persists with restricted ranking support, how the problem behaves when parameterized by \(m\) or \(\tau\), and whether algorithms can exploit the fact that weak Condorcet outcomes depend only on aggregate pairwise masses.
The weakest point is that this is a conservative mirror: it compresses the electorate but does not show that continuous-optimization methods make the problem easier. The hardness reduction’s support may grow with the candidate set, so it does not establish hardness for fixed \(\tau\). Still, the paper’s problem is control over voter rankings, and representing repeated rankings by their population fractions preserves the authors’ actual question rather than simplifying it.
I can’t honestly defeat this anchor. Theorem 4.4 gives a named NP-completeness result for a computational control problem. Given any finite voter profile \(V\), setting \(\mu_t=|V_t|/|V|\) preserves every pairwise comparison, including ties. It therefore preserves the subelection winners and runoff outcome for every candidate partition. The continuous problem also has polynomially checkable certificates: a candidate partition, with pairwise masses computed exactly from the rational input. The large party or membership organization scenario is a plausible high-multiplicity regime.
The strongest negative point is about payoff: weak Condorcet outcomes depend only on the weighted pairwise contest matrix, so much of the ranking support is irrelevant to this particular question. The NP-hardness reduction encodes its combinatorics in the candidate agenda and balanced partition. That may make this a less rich example for continuous optimization methods, but it does not undermine the mirror: it still makes the society a distribution over voter types, and the programme explicitly allows hardness that survives continuization.
A more ambitious version could study how the problem behaves with restricted support or as \(\tau\) varies. Those extensions do not remove the original mirror. The honest negative case is weak; this anchor survives. I cannot support the claim that no worthwhile continuous mirror exists for this paper.
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.