| paper | High-Multiplicity Election Problems |
| authors | Zack Fitzsimmons, E. Hemaspaandra |
| venue | ATAL 2018 |
| filed under | voting · bribery-control |
| 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: \(\Theta_2^p\)-complete, hence \(\mathrm{NP}\)-hard, even for four distinct orders with masses \(\mu_i=\frac14\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 20
statement extracted from the paper’s text layer
Given candidates \(C\), a target candidate \(p\), four complete ranking types \(t_1,\ldots,t_4\), and rational masses \(\mu_1,\ldots,\mu_4\) summing to \(1\), does some consensus order \(\pi\) minimizing \(\sum_i \mu_i d_{\mathrm{KT}}(\pi,t_i)\) rank \(p\) first?
A finite-support continuum of agents has ranking types \(t_i\) with rational masses \(\mu_i\); the decision variable is a discrete consensus order \(\pi\), and the objective is expected Kendall-tau loss \(\sum_i\mu_i d_{\mathrm{KT}}(\pi,t_i)\).
The mirrors cover Kemeny winner determination from Theorem 20 and Young winner determination from Theorem 22. They leave the paper’s control, manipulation, scheduling, and other winner-complexity results unmirrored.
The paper is unusually favorable to a continuous mirror because its high-multiplicity representation is already the natural finite encoding of a population distribution. I would use exact rational masses, encoded in binary; otherwise the computational problem has no finite input model. The candidates, rankings, consensus order, and control actions remain discrete. Only the population becomes continuous.
My lead mirror is a continuous four-type Kemeny winner problem. An instance consists of candidates \(C\), a distinguished candidate \(p\), four complete ranking types \(t_1,\dots,t_4\), and rational masses \(\mu_1,\dots,\mu_4>0\) summing to \(1\). A consensus ranking \(\pi\) has population loss \(K_\mu(\pi)=\sum_{i=1}^4\mu_i d_{\mathrm{KT}}(\pi,t_i)\), where \(d_{\mathrm{KT}}\) is Kendall tau distance. The question is whether some loss-minimizing consensus ranking places \(p\) first. A solution is therefore a yes/no answer, or a minimizing \(p\)-first order when the answer is yes.
This is a very natural high-multiplicity regime: millions of voters may belong to four large political, consumer, or online-preference blocs, with every member of a bloc sharing the same complete ranking. The number of agents can be enormous while the number of types is exactly four.
The anchor is Theorem 20, proved in this paper: “Kemeny-Weighted-Winner and Kemeny-High-Multiplicity-Winner for four votes are \(\Theta_2^p\)-complete.” In its high-multiplicity interpretation, the four votes are four distinct ranking types with binary multiplicities \(k_1,\dots,k_4\). The continuous mirror has exactly the same optimization after normalization: setting \(\mu_i=k_i/N\), where \(N=\sum_i k_i\), changes every Kemeny objective by the common factor \(1/N\), and hence does not change its minimizing orders. Conversely, rational masses can be cleared of denominators to produce integer multiplicities in polynomially many bits.
I therefore expect this mirror to be \(\Theta_2^p\)-complete: hardness transfers, rather than dissolves. Indeed, the paper’s four-voter hardness already embeds by taking four equal masses \(\mu_i=1/4\). The combinatorics live in the candidate agenda and the possible consensus rankings, not in the number of individually represented voters. This is precisely the programme’s Class B pattern. It is also a strong case that the population distribution is not merely decorative: the objective is an expected social disagreement over a continuum of agents, while the output remains a discrete consensus order.
The natural follow-up questions are whether approximate Kemeny optimization or winner margins become tractable under mass perturbations, and how the complexity changes when the distribution is given implicitly rather than by an explicit list of ranking types. The paper’s general Kemeny result, Theorem 18, suggests a broader \(\Delta_2^p\) continuous landscape beyond the four-type case.
A second, genuinely algorithmic mirror comes from Theorem 22, also proved here: “For a fixed number of votes, Young-High-Multiplicity-Winner is in \(\mathrm P\).” Its continuous version is as follows. Given ranking types \(t_1,\dots,t_r\) with masses \(\mu_1,\dots,\mu_r\), define the continuous Young score of candidate \(c\) by maximizing retained mass:
\[ Y_\mu(c)=\max \left\{\sum_{i=1}^r y_i: 0\le y_i\le \mu_i,\ \sum_{i:c>_{t_i}a}y_i\ge \sum_{i:a>_{t_i}c}y_i \text{ for every }a\ne c \right\}. \]
Here \(y_i\) is the mass of type \(t_i\) retained in a subpopulation on which \(c\) is a weak Condorcet winner. The continuous problem asks whether \(Y_\mu(p)\ge Y_\mu(c)\) for every candidate \(c\). This is a precise mass-selection problem: the action variable is the retained mass vector \(y\), and the objective is the largest surviving fraction of society.
The paper’s ILP proof replaces the \(y_i\) by integer counts \(k_i\) and uses Lenstra’s fixed-variable algorithm. In the continuous mirror, the same constraints form an LP. Thus, with explicitly listed support, the problem is in \(\mathrm P\), and the fixed-number-of-types restriction may disappear entirely: an LP with \(r\) variables and polynomially many pairwise constraints remains polynomial-time even when \(r\) is part of the input. This is a Class A mirror. The regime is plausible because the paper itself identifies fixed vote types with large political parties or social groups whose members vote identically.
These mirrors cover two concrete results—Theorem 20 on Kemeny winner determination and Theorem 22 on Young winner determination—not the paper’s entire collection of control, manipulation, and scheduling results. They also stay within scope: the population is continuous, but rankings, candidates, consensus orders, and retained/deleted-agent decisions remain discrete.
The weakest point is that, on exact rational inputs, the Kemeny mirror is polynomially interconvertible with the paper’s high-multiplicity problem by clearing denominators. A hostile reader could call that a change of units. I think that criticism identifies a real limitation rather than defeating the case: the paper’s HM results are precisely evidence that this population regime is meaningful, while the continuous formulation supplies the mass-based semantics and exposes which proofs become LP arguments. The Kemeny mirror is therefore not a claim that normalization alone creates a new theorem; it is a credible continuous computational problem with a natural four-bloc interpretation and a sharp hardness boundary.
I cannot make an honest universal negative case here. The paper is unusually well suited to continuization, and both anchors survive the strongest objections.
The Kemeny anchor is decisive. For four ranking types with integer multiplicities \(k_i\), let \(N=\sum_i k_i\) and \(\mu_i=k_i/N\). For every consensus order \(\pi\),
\[ \sum_i \mu_i d_{\mathrm{KT}}(\pi,t_i) = \frac{1}{N}\sum_i k_i d_{\mathrm{KT}}(\pi,t_i). \]
The common factor does not change the minimizing orders or whether \(p\) is a Kemeny winner. Conversely, any rational mass vector can be cleared to integer multiplicities with polynomially many bits. Thus Theorem 20 transfers exactly, including its \(\Theta_2^p\)-hardness, even with only four positive-measure blocs. The agents are interchangeable within each type, the objective depends on aggregate mass rather than identity, and the population does not disappear in the limit.
The obvious negative objection is that this is merely a change of units and that the high-multiplicity problem is already known. But the programme explicitly treats high multiplicity as supporting evidence, not as a collision; it also explicitly accepts a discrete-to-continuous identity as a worthwhile result. Kemeny is therefore almost the programme’s textbook Class B case. Theorem 18 gives the same conclusion for the broader high-multiplicity Kemeny problem.
The Young anchor is also sound, and the proposed version is stronger than the theorem stated in the paper. With listed ranking types and masses, the continuous Young score
\[ Y_\mu(c)= \max\left\{ \sum_i y_i: 0\le y_i\le \mu_i,\ \sum_{i:c>_{t_i}a}y_i \ge \sum_{i:a>_{t_i}c}y_i \ \forall a\ne c \right\} \]
is a linear program. Computing it for every candidate decides the continuous winner problem in polynomial time, even when the number of listed types is not fixed. Fractionally retaining mass is not an accidental relaxation: it is exactly what selecting a measurable subpopulation means in a continuum, and it preserves the paper’s substantive weak-Condorcet condition.
One might object that this changes Young’s integer score. That is not a valid objection under the programme: integral bundles for individual agents become masses at the population level, and this is precisely the intended continuization. Nor is the problem merely outcome-space continuity; the continuous object is the retained population itself.
The only defensible criticism is incremental: the Kemeny mirror adds little computational novelty beyond the paper’s existing high-multiplicity theorem, while the Young mirror turns the fixed-support ILP into a fairly direct LP. But that is a criticism of novelty or ambition, not evidence that no worthwhile continuous mirror exists. On the stated standard, the negative case fails: Theorem 20 alone is a strong green anchor, and Theorem 22 supplies a second, genuinely algorithmic one.
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.