| paper | d4-conf-ijcai-2007-0179 |
| 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}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(|C|=2^k\), a finite support \(S\) of complete rankings over \(C\), positive binary-rational masses \(\mu_t\) summing to \(1\), with a strict majority for one candidate in every pair, and a target \(A\), decide whether there is a balanced binary voting tree with one leaf per candidate in which \(A\) wins under the majority relation induced by \(\mu\).
The society consists of ranking types \(t\in S\) with mass \(\mu_t\). The decision certificate is a balanced voting tree; each match is resolved by the strict majority under \(\mu\). The induced tournament preserves the paper's winner question, and polynomial-size profile realizations of hard tournaments give rational-mass instances.
The mirror covers Theorem 4's NP-completeness result for fair possible winners on complete tournaments; it leaves the arbitrary-tree results, imbalance bounds, and incomplete-preference results unmirrored.
My lead is Fair Possible Winner over a Rational Society. A type is a complete ranking \(t\) of the candidates. The input is a finite support \(S\) with positive rational masses \(\mu_t\) summing to \(1\), and a target candidate \(A\). Require that every pair has a strict majority under \(\mu\), so the society induces a complete majority tournament. The question is whether there is a balanced binary voting tree, with each candidate at exactly one leaf, whose winner is \(A\). A solution is such a tree; each internal match is resolved by the majority relation induced by \(\mu\). This keeps the paper’s rule and the chair’s choice of tree intact while making the population a distribution over voter types.
The regime is a large electorate with repeated ballot rankings: for example, many voters share one of a relatively small set of complete rankings. Here \(N\), the number of voters, can be far larger than the support size \(\tau\). Even the hard instances can fit this regime: a tournament can be realized by a polynomial-size voter profile, and replicating those voters increases \(N\) without increasing \(\tau\). Normalizing the type counts gives the rational masses \(\mu_t=n_t/N\).
The anchor is Theorem 4, proved in this paper. It states that, given a complete oriented weighted majority graph \(G\) and candidate \(A\), deciding whether \(A\) is a fair possible winner for \(G\) is NP-complete. Here “fair possible winner” means that \(A\) wins in some balanced voting tree. The paper’s proof reduces Exact Cover to the graph problem. This is the strongest anchor because it is a hardness result, and its underlying question transfers directly to the distribution model.
I expect this continuous problem to be Class B: hardness transfers, and likely NP-complete. Given a rational society, its pairwise majority graph can be computed in polynomial time, and a balanced tree is a polynomial-size certificate. For hardness, Theorem 4’s hard tournaments can be represented by polynomial-size profiles of rankings; grouping identical rankings and normalizing their counts gives an instance of the stated problem with the same tournament and therefore the same answer. The graph weights’ magnitudes do not affect which candidate wins a match; their directions do.
The authors would likely recognize this as their fair-winner problem with the voter population represented by type masses. It does not continuize the outcome or the voting rule. The scope is specifically Theorem 4’s chair-control question for balanced trees. It does not claim a mirror for the paper’s results on arbitrary trees or incomplete preferences.
The weak point is that the continuous representation may add little computationally here: the question can be compressed to a majority tournament, and the hardness comes from the number of candidates and bracket structure rather than population multiplicity. This is a thinner continuation than one that unlocks a new optimization method. Still, it is a precise population-distribution problem, and it gives a useful boundary result: for this paper’s fair-winner question, representing voters by rational type masses does not remove the hardness. It also raises natural follow-ups, such as whether the problem is tractable when parameterized by \(\tau\), or under restrictions on the number and structure of ranking types.
The strongest objection is that the proposed mirror makes the population a redundant input. For each pair \(a,b\), define
\[
d_{ab}(\mu)=\sum_t\mu_t\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr).
\]
The fair-winner answer depends only on the signs of these margins: once they determine the majority tournament \(G_\mu\), the masses and support no longer matter. The computation is therefore to build \(G_\mu\) and apply Theorem 4’s graph problem. Theorem 4 already studies fair possible winners on weighted majority graphs, and the tournament instances can be represented by rational distributions over rankings. This gives a particularly thin continuation: no population-sensitive objective, mass-transfer optimization, or continuous-optimization method appears.
A stronger population-centered variant might ask for the minimum mass that must change rankings before \(A\) can win a balanced tree. That would make the distribution matter, but it adds a voter-intervention problem and a cost model that Theorem 4 does not study. It is less clearly a mirror of this paper’s chair-control result.
That is the best case against prioritizing the anchor, but it does not defeat it under ChoCo’s stated criteria. The graph in the paper is not itself a distribution over voter types; the society-based question is well posed, and the authors could recognize it as their fair-winner problem with a population representation. The fact that the answer is already known, or that the mirror adds little computational structure, is explicitly not enough to rule it out. Since ChoCo values Class B results and boundaries too, I cannot honestly support the universal claim that no worthwhile continuous mirror exists here. The fair-winner anchor survives the negative case.
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.