| paper | d4-conf-ecai-2016-0060 |
| 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: All four fixed combinations—TE or TP, with the unique-winner or nonunique-winner model—are \(\mathrm{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), target \(c\), a finite support \(T\) of complete rankings of \(C\), and positive rational masses \(\mu_t\) summing to \(1\), is there a partition \(C=C_1\mathbin{\dot\cup}C_2\) such that the mass-based veto subelections, with the specified TE or TP rule, promote finalists who make \(c\) a winner of the runoff under the specified unique-winner or nonunique-winner model? In each subelection and the runoff, restrict rankings to the candidates present and compute veto scores from the original society’s mass.
The society is a distribution over complete ranking types, with each type carrying rational mass. The chair’s decision is a partition of candidates; the objective is to determine whether that partition succeeds under the paper’s tie-handling, finalist, and winner rules.
The mirror offers no new continuous-optimization route: the chair still chooses a discrete candidate partition, and the paper’s reduction already supplies the hardness. This limits its likely optimization payoff, but the proponent’s case establishes that a population mirror is within scope.
fatal: False
The mirror covers Theorems 3 and 5. It leaves the voter-partition results, Theorem 4, the maximin results, and the plurality candidate-addition result unaddressed.
The strongest mirror is to Theorem 3, proved in this paper. It says that veto constructive control by run-off partition of candidates is NP-complete under ties-eliminate (TE), in both the unique-winner and nonunique-winner models; under ties-promote (TP), it is NP-complete in the unique-winner model. The authors prove these claims by reduction from ONE-IN-THREE-POSITIVE-3SAT.
Call the mirror Continuous Veto-CCRPC. An instance is a candidate set \(C\), a target \(c\in C\), and a finite support \(T\) of complete rankings of \(C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). It also specifies one of the winner and tie-handling variants covered by Theorem 3. The question is whether there is a partition \(C=C_1\mathbin{\dot\cup}C_2\) such that, in each first-round subelection, rankings are restricted to that part and veto scores are computed by mass: a candidate receives \(1\) from each unit of mass unless it is ranked last in that restricted ranking. Apply TE or TP to determine which first-round winners advance; then rank the finalists using the original society, restricted to those finalists. A solution is the candidate partition itself, and it succeeds exactly when \(c\) is a winner of the final round, either uniquely or possibly tied according to the specified model.
This has a plausible high-multiplicity regime: a large ranked-ballot election with millions of voters but relatively few distinct ranking types, perhaps because many voters share preference patterns. A type is just a complete ranking, since that is the only voter information the problem uses; its mass is its fraction of the electorate. A chair arranging candidates into preliminary contests and a runoff is still asking the paper’s candidate-control question. The population is the object represented by masses; candidates and election rounds remain discrete.
The mirror is NP-complete for each of Theorem 3’s stated variants. Membership in NP follows because a candidate partition is a polynomial-size certificate and the rational scores can be compared exactly in polynomial time. For hardness, take a discrete election from the paper’s reduction and replace each ranking’s voter count \(n_t\) by mass \(n_t/N\), where \(N\) is the total number of voters. Every score is scaled by the same positive factor, so winners, ties, and successful partitions are preserved. The reduction’s combinatorics live in the candidate set and its partition, not in population multiplicity. This is a Class B case: the discrete hardness survives in the rational-mass model.
A second, compatible anchor is Theorem 5, also proved here. It establishes that veto destructive control by run-off partition of candidates under TE is NP-complete in both the unique-winner and nonunique-winner models. Its continuous mirror, Continuous Veto-DCRPC-TE, has the same mass-over-rankings input and candidate-partition process. It asks whether some partition prevents \(c\) from winning the runoff: in the unique-winner model, \(c\) must fail to be the sole winner; in the nonunique-winner model, \(c\) must not be a winner at all. The same count-to-mass construction preserves every outcome in the paper’s reduction, so these variants are NP-complete as well and also fall in Class B. Theorem 3 is my lead anchor; Theorem 5 extends the case to the destructive objective without changing the regime.
These questions are computationally meaningful in the programme’s terms: they ask whether the high-multiplicity version of a named problem admits an algorithm polynomial in \(m\), support size \(\tau\), and mass bit length \(L\). The reductions already rule that out unless \(\mathrm{P}=\mathrm{NP}\). Earlier high-multiplicity election and control work supports treating this regime as sensible; it does not make this mirror a novelty collision.
The mirror covers these two veto candidate-control results. It does not claim a mirror for the paper’s voter-partition results, maximin results, or plurality candidate-addition result. Useful follow-up questions include whether hardness persists for bounded \(\tau\), and what parameterized algorithms are possible in \(m\) or \(\tau\).
My weakest point is that the chair’s action remains a discrete partition of candidates; only the electorate is continuized. That is deliberate and within scope, but it means this is a strong high-multiplicity mirror rather than an example where continuity also reshapes the control action. The harder-to-dismiss point is that the authors’ underlying question is unchanged, and the paper’s own hardness reduction survives the change of population representation exactly.
The strongest case against is that Theorems 3 and 5 do not provide two independent reasons to continuize: both are veto candidate-partition problems, and their continuous versions use the electorate only through the mass of each ranking. For any rational society, a common denominator \(D\) turns each mass \(\mu_t\) into \(D\mu_t\) voters. Every veto score in every subelection and runoff is then multiplied by \(D\), preserving ties, winners, and successful candidate partitions. The chair’s action remains wholly discrete; no fractional control choice or continuous optimization appears.
That limits the conceptual novelty of these mirrors. The paper’s reductions already give hardness for them after this normalization, and verifying a proposed partition is straightforward. If ChoCo’s priority is finding problems where continuous-optimization tools create a new tractability route, these examples look less promising than problems whose intervention itself is naturally a mass transfer.
But that does not defeat either anchor under ChoCo’s stated scope. A large election with repeated ranking types is a sensible high-multiplicity regime, and neither problem tracks voter identities. Theorem 3’s stated variants and Theorem 5’s destructive variants both survive normalization exactly; the discrete candidate partition is allowed to remain discrete. The fact that their continuous answers are readily inherited from the paper is not, by itself, a reason to reject a well-posed mirror. I cannot make an honest case that defeats both anchors: the priority concern is real, but it does not establish that either mirror is unworthy of the programme.
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.