| paper | d4-conf-atal-2013-0126 |
| 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, even for \(\tau\leq 8\) with masses in \(\{1/8,2/8,\ldots,8/8\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite support \(T\) of complete rankings over candidates \(C\), with positive binary-rational masses \(\mu_t\) summing to \(1\), define \(M_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\). Include an edge \(a\to b\) of strength \(M_\mu(a,b)\) whenever this margin is positive. Given a target \(c^\star\), determine whether it is top-ranked in at least one outcome of neutral Ranked Pairs over all permitted tie-breakings.
Types are complete rankings, and each type carries rational mass \(\mu_t\); these masses induce the weighted majority graph through \(M_\mu\). The decision is whether some permitted ordering of tied edge strengths yields a Ranked Pairs outcome with \(c^\star\) top-ranked.
The distribution affects Ranked Pairs only through the induced weighted majority graph, so this mirror adds little computational structure; the proponent acknowledges its likely role as a hard-boundary result, and the limitation bounds novelty rather than validity.
fatal: False
Covers Theorem 4’s target-winner hardness and its 8-voter realizability construction; it leaves the Banks, TEQ, and Slater results and the majority-graph characterization results aside.
The strongest mirror is continuous Banks winner determination. Take \(m\) alternatives and a finite support of complete rankings \(t\), each with rational mass \(\mu_t>0\) summing to \(1\). Mass means the fraction of the population with that exact ranking. Define the majority relation by \(a\to b\) when the total mass ranking \(a\) above \(b\) exceeds \(1/2\); require no pairwise ties, so this relation is a tournament. Given a target \(c^\star\), ask whether \(c^\star\) belongs to the Banks set: the maximal elements of inclusion-maximal transitive subtournaments. The answer is yes or no; the decision variable is the target’s membership, and the underlying optimization is over transitive subtournaments.
This has a plausible high-multiplicity regime in a large preference-aggregation service where users choose among a small menu of ranking profiles over webpages or other alternatives. Millions of users may share at most seven such profiles, so \(N\gg\tau\). The paper’s search-aggregation motivation instead has few voters, but the mirror’s population can be the users of the service, grouped by their complete ranking. The common type description is exact: people of a type are indistinguishable for this problem.
The anchor is Theorem 1: “Computing the Banks set is NP-hard, if the number of voters is at least seven.” The paper proves the seven-voter restriction by showing that the tournaments in its hardness construction can be induced by a 7-voter profile; the underlying 3SAT-based Banks hardness is cited from Brandt et al. [3]. In that construction the target \(c_0\) is in the Banks set exactly when the formula is satisfiable. A 7-voter profile maps directly to a continuous society with masses equal to its ballot counts divided by \(7\). Thus the continuous decision problem is NP-hard already on instances with at most seven supported ranking types and masses on the \(1/7\) grid. I would classify this as Class B: hardness transfers. The reduction’s combinatorics live in the number and arrangement of alternatives, not in a large population.
Two other anchors make the case stronger, each for its own rule. Theorem 3 states that computing the Slater set is NP-hard if there are at least nine voters. The paper proves this by showing that the tournaments in Conitzer’s cited MAXSAT-based construction can be induced by a 9-voter profile. Its continuous counterpart takes the same rational distribution over complete rankings, requires strict pairwise majorities, and asks for the Slater set: the alternatives maximal among rankings minimizing the number of majority edges they reverse. The objective remains the paper’s count of discordant majority edges, not a mass-weighted substitute. This problem is likewise Class B, hard already with at most nine ranking types and masses on the \(1/9\) grid.
Theorem 4 states that deciding whether a given alternative is a ranked-pairs winner is NP-complete when the number of voters is even and at least eight. The paper proves the eight-voter restriction by representing Brill and Fischer’s cited SAT-based weighted-graph instances as 8-voter profiles. Its continuous counterpart uses rational ranking masses, forms the pairwise majority victories and their support strengths from those masses, and asks whether the target is top-ranked in some outcome of neutral Ranked Pairs, allowing its prescribed tie-breaking. A profile of eight voters gives exactly the same victories, strengths up to a common scale, and tie-breaking possibilities. This is also Class B, hard with at most eight ranking types on the \(1/8\) grid. Of these three, Banks is my lead: it gives the cleanest majority-tournament mirror and the smallest support bound; Ranked Pairs supplies the sharpest stated complexity result, NP-completeness for a specific winner query.
These are continuous-population questions because the input society is a distribution over voter types. Their outcomes remain discrete candidates, just as the mirror calls for. They do not continuize the outcome space or replace winner determination with an axiomatic or equilibrium question. Nor is the paper already studying a continuous society: it establishes hardness for profiles with a fixed small number of voters. Allowing arbitrarily large cohorts to share those ballots gives a distinct high-multiplicity interpretation, and the existing high-multiplicity literature would support the sensibility of that regime rather than collide with it.
The extensions raise useful boundary questions: what is the minimum support size \(\tau\) at which each rule remains hard; are the cases below these bounds tractable; and do arbitrary rational masses introduce additional complexity beyond the discrete-grid instances? Since hardness already holds at constant \(\tau\), parameterizing only by support size cannot give an FPT algorithm unless \(\mathrm{P}=\mathrm{NP}\).
The weakest point is that the paper’s stated motivation is almost the reverse regime: hardness with few voters and many alternatives. The high-multiplicity scenario requires many people to share a small set of exact complete rankings, and the paper does not study that population directly. Also, these anchors offer no reason to expect continuization to dissolve the hardness: they show that it survives even when the support is tiny. So this is a strong, recognizable mirror, but its likely contribution is to document a hard boundary of the continuous programme rather than uncover a tractability gain.
The strongest case against is that these are thin continuizations. For Banks, TEQ, and Slater, the distribution \(\mu\) matters only through the signs of the pairwise margins
\[
M_{ab}(\mu)=\sum_t \mu_t\bigl(\mathbf 1[a\succ_t b]-\mathbf 1[b\succ_t a]\bigr).
\]
Within any region of the mass simplex where those signs stay fixed, the winner output stays fixed too. Ranked Pairs also uses margin strengths, but its output is determined by their comparisons and ties. So the population distribution is mostly a way to represent a tournament or weighted majority graph; none of these questions uses continuous optimization over mass. That makes the mirrors less rich than the programme’s LP and mass-transfer examples. It does not, by itself, make them out of scope: the programme asks computational questions about a continuous society, and these still do that.
The Banks mirror is difficult to defeat. Theorem 1 gives NP-hard instances induced by seven rankings. Put mass \(1/7\) on each ranking and the continuous society has exactly the same majority tournament and Banks winners. Replicating those seven cohorts to any larger population preserves the proportions. A large preference-aggregation service with a small number of recurring ranking profiles is a plausible regime, even if it is not the paper’s search-engine scenario. The strongest criticism is that the continuum adds no new structure to the computation: it repackages the seven-voter instance as cohort proportions. But that is a limited novelty objection, not a reason the question is ill-posed, and the programme explicitly treats the high-multiplicity dictionary as a deliverable.
The Slater mirror survives the same test. Theorem 3’s nine-voter instances give mass \(1/9\) on each ranking, preserving the majority tournament and the paper’s objective of minimizing the number of majority edges reversed. One could instead define a population-weighted version that charges according to the margin of each reversed edge. That may be a better population-sensitive question, but it is a different rule; the exact Slater mirror already has a sensible formulation. Neither the unchanged objective nor the weighted alternative supplies a sound objection.
Ranked Pairs survives as well. In Theorem 4’s eight-voter construction, the mass distribution reproduces the pairwise margins up to a common scale, so it preserves their strength order and the neutral method’s tie-breaking possibilities. Using rational masses to compute those strengths directly is the better continuous formulation; it still contains the paper’s hard instances exactly.
I cannot honestly argue that all three anchors fail. The paper has named computational results, its winner questions do not track individual identities, and its constant-support reductions make the high-multiplicity regime especially clear. Nor can I use the fact that the hardness transfers as an objection: under the programme’s standard, that is a valuable boundary result. My negative case is therefore weak. At most, these mirrors look more like a clean Class B boundary and a formal bridge to cohort inputs than a source of new continuous-optimization techniques. Each anchor remains a worthwhile continuous question.
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.