| paper | d4-conf-atal-2008-0318 |
| 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}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4.8
statement extracted from the paper’s text layer
Given registered candidates \(C\), addable candidates \(C'\), a target \(d\in C\), an addition limit \(r\), and a distribution \(\mu\) over complete rankings of \(C\cup C'\), does some \(A\subseteq C'\) with \(|A|\le r\) make \(d\) the unique highest-scoring candidate on the slate \(C\cup A\), where each type votes for its highest-ranked candidate on that slate?
Types are complete rankings of the potential slate \(C\cup C'\), with rational masses \(\mu_t\) summing to one. Choose binary variables \(x_a\) for \(a\in C'\), subject to \(\sum_{a\in C'}x_a\le r\); the resulting slate is \(C\cup\{a:x_a=1\}\). For each candidate \(c\), its score is the total mass ranking \(c\) first on that slate. The decision question is whether the chosen slate gives target \(d\) a strict score advantage over every other candidate, as required by adverse tie-breaking.
The mirror covers Proposition 4.8’s single-winner Bloc candidate-addition result, including its distinguished-candidate version. It leaves multi-winner candidate control, voter control, and the paper’s manipulation results outside this mirror.
My lead is continuous Bloc candidate-addition control at \(k=1\). It continuizes the electorate while preserving the paper’s candidate-control decision intact.
Anchor: Proposition 4.8, proved here by reducing to the cited candidate-control result of Bartholdi, Tovey, and Trick [3]. It states that control by adding or removing candidates in Bloc voting is NP-complete even in single-winner elections. The paper’s preceding discussion gives the stronger target-candidate version for SNTV: the chairman wants a distinguished candidate included among the winners. At \(k=1\), Bloc is SNTV, so that target version carries over too.
Here is the mirror. Let \(U=C\cup C'\) be the potential candidates, with registered candidates \(C\), addable candidates \(C'\), a target \(d\in C\), and addition limit \(r\). The society is a distribution \(\mu\) over complete rankings of \(U\), given by its \(\tau\) positive-mass rankings and binary-rational masses summing to one. For a chosen slate \(S=C\cup A\), where \(A\subseteq C'\) and \(|A|\le r\), define
\[
\operatorname{sc}_{\mu}(c;S)
=\sum_t \mu_t\,\mathbf{1}\!\left[c\text{ is the highest-ranked candidate in }S\text{ under }t\right].
\]
The question is whether some such \(A\) makes \(d\) the winner under the paper’s adverse tie-breaking convention. A solution is the set \(A\); its scores can be checked by exact rational arithmetic. Call this Continuous Bloc Candidate-Addition Control.
A plausible regime is a large public election in which many citizens share the same ranking over the possible slate: preference blocs may number far fewer than voters. A ranking of the full potential slate is a complete type because it determines each voter’s ballot whatever candidates are added. Mass is the fraction of the electorate in each bloc. The model keeps the paper’s actual choice—whether to add named candidates—and the consequence that adding one can change which candidate each voter ranks first. It does not simplify candidate control into a different objective.
I expect hardness to transfer (Class B). Given a discrete \(n\)-voter instance, set \(\mu_t=n_t/n\) for each ranking type \(t\), where \(n_t\) is its number of voters. On every possible slate, each continuous score is exactly the discrete vote count divided by \(n\), so the winner and every candidate-addition choice are preserved. Thus the cited NP-hard instances embed; the continuous problem is also in NP because a candidate subset is a certificate and its scores are computable from the explicit support. The resulting problem is NP-complete in the input parameters \(m,\tau,L\), even on societies obtained by normalizing discrete electorates.
This covers Proposition 4.8’s candidate-addition result for Bloc at \(k=1\), including its distinguished-candidate form. It does not claim that the voter-addition/removal hardness in Proposition 4.7 survives: there the action is over voters, and fractional mass choices may change the complexity. Natural follow-up questions include whether this problem is fixed-parameter tractable in \(\tau\) or \(r\), and whether the same transfer holds for multi-winner Bloc candidate control.
The weak point is that this is a comparatively direct Class B mirror: the hard choice is over the candidate slate, and the proof embeds discrete profiles exactly. It is less informative about whether continuizing the population dissolves hardness driven by selecting individual voters. I still think it is an honest mirror: the paper studies candidate control through aggregate electoral scores, and here those same scores are computed from a continuous society of ranking types.
The strongest skeptical case is that this mirror leaves the hard choice almost untouched: the chairman still selects an integral subset of named candidates, and the continuous population supplies only the scores used to evaluate that subset. The transfer from a discrete election is exact, so the mirror may look more like a new encoding of candidate control than a new algorithmic phenomenon.
That objection does not defeat the anchor under the programme’s criteria. The population is genuinely continuous: a large election can have many voters but relatively few distinct rankings, and the rational masses preserve every candidate’s score on every possible slate. The candidate identities remain discrete because candidates are not the population being continuized. The single-winner Bloc result in Proposition 4.8 is a named computational result, and the target-candidate version is a sensible mirror of it.
The proposed model also survives the best refinements I can see. Treating each ranking of the full potential slate as a complete type correctly accounts for how adding candidates changes voters’ first choices. Adverse tie-breaking can be expressed as a strict score advantage for the target. Normalizing a discrete electorate gives the same winners for every candidate subset, while arbitrary rational masses still admit polynomial-time verification of a proposed subset. So the discrete hardness transfers, and the decision problem is in NP.
One can say this is a Class B result whose hardness persists because the candidate-selection problem persists. But the programme explicitly counts identifying such boundaries as worthwhile. Calling the mirror an inert restatement, or dismissing it because the hardness lies in the candidate agenda, would rely on grounds the brief rules out. I cannot make a credible case against this anchor; the negative case here is weak.
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.