| paper | Possible Winners in Noisy Elections |
| authors | K. Wojtas, Krzysztof Magiera, Tomasz Miąsko, Piotr Faliszewski |
| venue | AAAI 2012 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.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}\)-hard; indeed, \(\#\mathrm{P}\)-complete under polynomial-time parsimonious reductions for every fixed \(k\ge 2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.5
statement extracted from the paper’s text layer
Given \(C,A,p,\ell\), fixed \(k\ge 2\), and complete ranking types \(T\) over \(C\cup A\) with rational masses \(\mu_t\) summing to \(1\), compute the number of sets \(A'\subseteq A\) with \(|A'|\le\ell\) for which \(p\) is the unique \(k\)-Approval winner after restricting each type to \(C\cup A'\), where \(\operatorname{score}_{\mu,A'}(c)=\sum_{t\in T}\mu_t\mathbf{1}[c\text{ is top-}k].\)
High-multiplicity \(k\)-Approval candidate-control counting: types are complete rankings, \(\mu\) is population mass, \(A'\) is an integral candidate-addition decision, and the objective is the exact number of successful \(A'\).
The mirror may be only a weighted-election sufficient-statistic reformulation, and the hardness transfer does not establish a genuinely compressed fixed-small-\(\tau\) regime.
fatal: False
It covers the constructive candidate-addition component \(k\)-Approval-\(\#\mathrm{CCAC}\) of Theorem 4.5. It leaves candidate deletion, destructive candidate control, voter-control results, and single-peaked results untouched.
The strongest honest case is a single-anchor, Class B mirror of the paper’s candidate-control problem.
My lead anchor is Theorem 4.5, proved in this paper. In the unrestricted case, it states that, for every fixed \(k\ge2\), \(k\)-Approval-\(\#\mathrm{CCAC}\) and \(k\)-Approval-\(\#\mathrm{CCDC}\) are \(\#\mathrm{P}\)-complete, while their destructive variants are \(\#\mathrm{P}\)-metric-complete. I use the constructive candidate-addition result \(k\)-Approval-\(\#\mathrm{CCAC}\). The paper proves the theorem using the parsimonious \(\#\mathrm{X3C}\) reductions of Faliszewski, Hemaspaandra, and Hemaspaandra, together with its own Theorem 3.2 for the destructive cases; it is therefore a result established here, not merely a literature summary.
The continuous mirror is Continuous \(k\)-Approval Candidate-Control Counting.
An instance consists of:
The mass \(\mu_t\) is the fraction of the electorate having ranking type \(t\). For a proposed added-candidate set \(A'\subseteq A\), every type’s ranking is restricted to \(C\cup A'\). Let
\[ \mathrm{sc}_{\mu,A'}(c) = \sum_{t\in T}\mu_t\, \mathbf{1}\!\left[c\text{ is among the top }k\text{ candidates of }t \text{ in }C\cup A'\right]. \]
The question is to compute
\[ Z= \left| \left\{ A'\subseteq A: |A'|\le\ell,\; \mathrm{sc}_{\mu,A'}(p)> \mathrm{sc}_{\mu,A'}(c) \text{ for every }c\in(C\cup A')\setminus\{p\} \right\} \right|. \]
Thus a solution is an admissible candidate set \(A'\), and the required output is the exact number \(Z\) of successful control plans. If all admissible \(A'\) are equally likely to register, \(Z\) immediately gives the designated candidate’s winning probability after normalization by \(\sum_{i=0}^{\ell}\binom{|A|}{i}\). The uncertainty over candidate registration remains discrete; only the voter population has been continuized.
This is a plausible high-multiplicity regime. Imagine a large electorate of millions of voters divided into demographic, organizational, or behavioural cohorts. All members of a cohort have the same ranking over the currently possible and potentially registering candidates. The relevant instance is then a distribution over \(\tau=|T|\) ranking types, with \(N\gg\tau\) actual voters. The types are complete descriptions: agents with the same type are indistinguishable for every operation in the problem.
The paper’s problem is preserved exactly. Candidate addition remains an integral control action, the committee of candidates is not fractionalized, and the winner condition is unchanged. Only the list of individually named voters is replaced by their population distribution. If \(\mu_t=N_t/N\), the continuous scores are the corresponding discrete scores divided by \(N\), so unique-winner comparisons are identical.
I would expect this mirror to be Class B: hardness transfers. Take any hard instance from the proof of Theorem 4.5 and let each distinct voter preference become a type. Then duplicate every voter \(M\) times. The resulting electorate has \(MN\) voters but exactly the same type distribution, and every candidate score is multiplied by \(M\). Consequently, every candidate subset \(A'\) succeeds in the continuous instance exactly when it succeeds in the original discrete instance, so \(Z\) is unchanged. The population can therefore have arbitrarily high multiplicity without weakening the \(\#\mathrm{P}\)-hardness.
The reason is also conceptually important: the reduction’s combinatorics live in the possible subsets of candidates, not in the identities of voters. Continuization removes redundant population identities, but it does not remove the combinatorial candidate-selection problem. Under ordinary binary encoding of the rational masses, the mirrored problem remains in \(\#\mathrm{P}\), since one can guess \(A'\) and compare the resulting rational scores in polynomial time; the transfer gives \(\#\mathrm{P}\)-hardness.
This mirror covers only the unrestricted constructive candidate-addition result in Theorem 4.5. It deliberately does not claim to mirror every result in the paper. In particular, I would not force the voter-control results such as Theorem 4.8 into the same framework: their output counts subsets of individual voters, and there is no equally canonical notion of “counting” subsets of a divisible population. That would risk changing the paper’s question rather than continuizing it.
The weakest point is that the resulting problem may look like a weighted-election reformulation rather than a dramatic new continuous theory. Candidate actions remain discrete, and the hard reduction can retain many distinct types before multiplying their populations. So this is not a claim that continuization makes the problem tractable. Its positive case is narrower: the paper studies finite named electorates, while a natural high-multiplicity version studies a rational distribution over repeated voter types, and that version exposes a meaningful Class B boundary—population continuity does not dissolve hardness when the obstruction lies in candidate control. Whether the problem becomes easier when \(\tau\) is fixed or genuinely small, or when candidate-subset probabilities are approximated rather than counted exactly, are natural follow-up questions.
The strongest negative case is that Theorem 4.5 does not really need continuization. In \(k\)-Approval-\(\#\mathrm{CCAC}\), voters are never individually manipulated or counted. Their identities matter only through the score vector. Grouping voters with identical rankings into types is therefore an exact sufficient-statistic transformation already available in the discrete problem:
\[ \mathrm{score}(c)=\sum_t n_t\, \mathbf{1}[c\text{ is top-}k\text{ after }A'] \]
and replacing \(n_t\) by \(\mu_t=n_t/N\) merely divides every score by \(N\). No feasible control action, winner comparison, or counted object changes. The proposed “continuous” problem is thus weighted candidate control with a different encoding, not a genuinely new population-level model.
The proponent’s hardness transfer also does not demonstrate a specifically high-multiplicity phenomenon. The reduction preserves one type for essentially every source voter, so \(\tau\) grows with the instance. Replicating every voter \(M\) times only pads multiplicities; it does not compress the hard instance into a small or structurally meaningful type space. A genuinely compressed mirror would need to study the regime where \(\tau\) is fixed or substantially smaller than the population, but that is a new parameterized question, not what the proposed reduction establishes.
The natural repairs do not improve the case much. One could introduce a probability distribution over candidate subsets, but that adds candidate-side uncertainty rather than making the population continuous. One could ask for an expected winning probability, but this is still a weighted-election calculation over the same discrete candidate subsets. One could allow fractional candidate participation, but then the candidate-control problem—and hence the paper’s theorem being mirrored—has been replaced.
This is not an objection that the continuous answer remains hard; hardness would be a legitimate Class B result. The objection is more basic: the population distribution is passive input, and the paper’s anchor already factors through that distribution exactly. Unlike mass-transfer bribery, no fractional population operation or continuous optimization object appears. The mirror therefore supplies little beyond a high-multiplicity encoding of an existing weighted problem.
That said, this negative case is not airtight. A large electorate partitioned into demographic cohorts with common rankings is plainly plausible, and the programme explicitly permits Class B mirrors whose hardness survives continuization. Nothing here defeats that well-posed question outright. The honest conclusion is that the proposed anchor is weaker and less novel than advertised, but it probably survives the universal claim that no worthwhile continuous mirror exists.
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.