| paper | d4-conf-aaai-2006-0154 |
| 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: \(\text{NP-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a candidate set \(C\) and a finite support of strict rankings \(t\), each with positive binary-rational mass \(\mu_t\) summing to \(1\), and with no pair tied in the population, compute a ranking \(\succ\) minimizing the number of unordered candidate pairs that \(\succ\) orders opposite to their population pairwise-majority direction.
Types are complete rankings \(t\), carrying population mass \(\mu_t\). The input is the candidate set and the listed rational-mass support; the output is a ranking of candidates. The masses determine the pairwise-majority tournament, and the objective counts the tournament edges that the output ranking reverses.
The mirror covers Theorem 3’s tie-free NP-hardness result. It leaves the similar-candidate preprocessing results, the hierarchical-graph algorithm, and the experiments outside the stated question.
My lead is Continuous Slater Ranking. Its instance is a candidate set \(C\) and a list of \(\tau\) strict rankings \(t\), each with positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). The support list is the input; the full set of possible rankings need not be listed. Require that no pair is tied in the population: for all distinct \(a,b\), \(\sum_{t:a\succ_t b}\mu_t\ne \tfrac12\). Define \(a\to_\mu b\) when that sum is greater than \(\tfrac12\). The question is to output a ranking \(\succ\) of \(C\) minimizing
\[
\left|\left\{\{a,b\}: \succ \text{ orders }a,b\text{ opposite to }{\to_\mu}\right\}\right|.
\]
The decision variable is the aggregate ranking; the objective is the number of pairwise population majorities it contradicts. This preserves Slater’s objective. In particular, it does not replace it with total voter disagreement or Kemeny’s weighted margin objective.
The population has many agents grouped by complete rankings: agents of the same type have identical preferences in every respect this problem uses. A natural regime is a large election where most people share one of a moderate number of recurring ballots—for example, electorate segments choosing from the same set of platforms. The number of people can greatly exceed \(\tau\). The paper itself starts from voters with rankings and aggregates their pairwise contests, so this is a direct population-level form of its problem. The output candidates and ranking remain discrete; the society supplying the pairwise majorities is continuous.
My anchor is Theorem 3, proved in this paper: *computing a Slater ranking is NP-hard even in the absence of pairwise ties*. The proof reduces from MAXSAT. It constructs a pairwise election graph with variable-related candidate groups and clause candidates, so that reaching a specified Slater score is possible exactly when the MAXSAT instance has an assignment meeting its target. This is hardness in the paper’s own result, not a result merely cited from elsewhere.
The continuous problem inherits that hardness. The reduction’s tie-free tournament instances can be represented by polynomial-size profiles of strict rankings; putting mass \(1/n\) on each of \(n\) ballots gives exactly the same pairwise orientations and Slater scores. The resulting society has rational masses, and repeated ballot types can be combined into the support representation. Thus a polynomial algorithm for Continuous Slater Ranking would solve the paper’s NP-hard instances. I expect hardness transfers (Class B): the reduction’s combinatorics live in the alternatives and their cycles, not in the number of voters. Replicating voters preserves the population proportions and the support types while making the electorate arbitrarily large.
This mirror covers Theorem 3 only. Further questions include whether the problem becomes tractable when \(\tau\) is small, whether the hardness persists under restrictions on support or on the induced majority graph, and how the paper’s similar-candidate and hierarchical-graph reductions behave across such population regimes.
The weak point is that this mirror may look like a high-multiplicity reparameterization: empirical voter profiles already induce the same majority graph, and the theorem does not establish a new continuous-population phenomenon. It also says nothing about hardness when the support is especially small. That limits what the result establishes, but not whether the mirror is sensible: the paper’s Slater question is already defined by aggregating voters, and replacing voter counts with their exact population shares preserves the problem while making the high-multiplicity regime explicit.
The strongest case against this mirror is that Slater’s continuous population has no interior effect on the computation. For each pair \(a,b\), define the margin
\[
d_{ab}(\mu)=\sum_{t:\,a\succ_t b}\mu_t-\tfrac12.
\]
On the tie-free domain, the population simplex is divided by the boundaries \(d_{ab}(\mu)=0\) into regions. Within each region, every pairwise majority has the same direction, so the Slater problem and all its optimal rankings are identical. The masses matter only long enough to determine the majority tournament; after that, the entire distribution can be discarded. Replicating the electorate to make it arbitrarily large changes nothing once its proportions stay in the same region.
That makes this a weak fit for the programme’s continuous-optimization motivation. There is no mass-transfer decision, fractional objective, or pricing problem to exploit: the mass calculation is just a set of pairwise rational comparisons, followed by the original tournament-ranking problem. The paper already formulates that hard core directly on the pairwise graph. A stronger-sounding version based on moving mass until the Slater result changes would introduce a new robustness or control problem, rather than mirror Theorem 3’s computation problem.
But this does not defeat the anchor under ChoCo’s stated gate. Theorem 3 is a named computational result, and voters with complete rankings form a sensible type space for large electorates. The tie-free instances can be represented by rational masses over rankings, preserving the tournament and Slater objective exactly. The fact that the population collapses to a tournament after preprocessing limits what is novel about the mirror; it is not evidence that the high-multiplicity question is ill-posed. I cannot make a strong case that this anchor fails. The honest negative is that its continuous aspect may contribute little beyond an exact population-level input representation, and the reader may reasonably find that insufficient to justify the programme’s time.
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.