| paper | d4-conf-atal-2017-0105 |
| 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}\), even for dyadic rational masses; an exact deterministic algorithm runs in \(O(2^{\min\{m,\tau\}}m\tau L^2)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a distinguished candidate \(p\), and a society supported on \(\tau\) strict rankings \(\pi_t\) with rational masses \(\mu_t\ge 0\) summing to \(1\), decide whether there are split masses \(x_t\in[0,\mu_t]\) such that \(x_t\) goes to the first subelection and \(\mu_t-x_t\) to the second, and \(p\) is the unique winner of the runoff among the union of the two ties-promote veto winner sets. The runoff uses the original society restricted to those finalists; an empty subelection promotes all candidates.
A distribution over complete ranking types, with rational mass split variables \(x_t\); the question is feasibility of the same two-stage control and unique-winner condition, with no cost objective.
The discrete reduction does not by itself establish hardness when type mass can be split fractionally; its blocker argument still needs to be verified for every finalist set such splits can produce.
fatal: False
The mirror covers Theorem 1: constructive veto control by partition of voters under ties-promote in the unique-winner model. It leaves the other voter-partition variants, candidate-partition results, and voter-group theorems untouched.
The strongest mirror I see is the paper’s direct voter-partition result.
Anchor: Theorem 1, proved in this paper. In the unique-winner model, veto-CCPV-TP is NP-complete. Given a veto election and a distinguished candidate \(p\), the question is whether the voters can be partitioned into two subelections so that, under ties-promote, the winners of both subelections enter a runoff in which \(p\) is the unique winner. The paper proves hardness by reduction from ONE-IN-THREE-POSITIVE-3SAT.
My lead question is Continuous Veto-CCPV-TP. An instance consists of a candidate set \(C\), a distinguished candidate \(p\), and a list of \(\tau\) strict rankings \(\pi_t\) with rational masses \(\mu_t\ge 0\) summing to \(1\). A solution is a split \(x_t\in[0,\mu_t]\) for each type: mass \(x_t\) goes to the first subelection and \(\mu_t-x_t\) to the second. In each subelection, veto winners are the candidates with the fewest last-place votes by mass; ties-promote advances every winner. Let \(F\) be the union of the two winner sets. The runoff uses the whole original society, with each ranking restricted to \(F\), as in the paper. The question is whether some split makes \(p\) the unique runoff winner. If a side has zero mass, use the usual ties-promote convention that all candidates tie there.
A natural regime is a large platform or association election with millions of members but comparatively few recurring complete rankings. A chair routes population shares into two preliminary contests, then holds a runoff among the promoted candidates. The action and the veto rule are the paper’s; the continuation replaces person-by-person counts with mass by ranking type. That keeps the same strategic question and winner semantics, while allowing the resolution the programme is meant to study.
I expect this mirror to remain hard, likely NP-complete: the reduction’s combinatorics appear to live in the candidate set and the winner sets, rather than in the indivisibility of a large electorate. In the paper’s satisfiable case, the chosen partition sends one vote of a specified ranking type to one side. In the continuous instance, the corresponding one-vote-equivalent mass is available, so that witness remains feasible. On the no-instance side, the reduction uses a candidate \(w\) who is never ranked last and who prevails in the runoff against whoever joins it. That argument appears insensitive to fractional allocation, since the runoff depends on the original society and the finalists. This is a Class B-style expectation: agenda-driven hardness survives the move to population masses. It is not automatic from the discrete theorem, though; the no-instance argument must be checked for every finalist set that fractional splits can produce. With rational inputs, NP membership also looks plausible: once the two first-round winner sets are specified, the score conditions are linear, and feasible rational splits should have polynomial-size certificates.
The further questions are whether the continuous version is indeed NP-complete, and whether it becomes tractable under parameters such as the number of candidates \(m\) or support size \(\tau\). The mirror covers Theorem 1 only. The paper’s voter-group results need a separate model because their control action keeps each group intact; I would not fold those into this question.
The weakest point is that fractional splitting enlarges the chair’s options, so discrete hardness alone does not prove hardness of this mirror. The reduction gives a credible route around that objection, but its blocker argument needs to be made explicit for the continuous finalist sets. The question still seems worth asking: it preserves the election, the two-stage control action, and exact winner condition, while testing whether fractional population mass removes the paper’s SAT-based hardness.
The best case against is an argument about the setting, not the complexity result. Theorem 1 models an unconstrained split of voters, introduced as a simplified form of gerrymandering. In actual districting, location and contiguity matter; a type defined only by ranking would let the chair distribute fractions of a preference group between districts without regard to where those voters live. Add location and the relevant geographic constraints, and the low-support ranking model no longer captures the action. The voter-group results have a related tension: keeping each group intact preserves the paper’s atomic choice, while splitting mass across identical groups relaxes that choice.
But this does not defeat the strongest version of the mirror. The paper’s formal control problem has no geographic constraints, so a mass split by complete ranking is a direct population version of the stated problem. A large membership organization or platform could run two preliminary contests and a runoff, with many members sharing a small set of rankings. Then \(x_t\) is the share of type \(t\) sent to the first contest, and the runoff can use the original society restricted to the promoted candidates. Mass is meaningful, no voter identity is lost, and veto comparisons do not vanish under normalization. Theorem 1 is a named NP-completeness result; the paper’s group-control theorems provide further computational anchors.
The SAT reduction may lose its force when voter types can be split fractionally. That is not a reason to reject the question: discovering that the continuous version is easier would itself be a worthwhile result. I can make a credible objection to the gerrymandering story, and a weaker one to preserving indivisible voter groups, but neither rules out a plausible population-level mirror of Theorem 1. The negative case is therefore weak against the universal claim.
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.