| paper | How Hard Is It for a Party to Nominate an Election Winner? |
| authors | Piotr Faliszewski, L. Gourvès, J. Lang, Julien Lesca, J. Monnot |
| venue | IJCAI 2016 |
| 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: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given candidates \(C\) partitioned into parties \(P_1,\ldots,P_t\), target party \(P_w\), a societal axis \(B\), and rational masses \(\mu_\rho\) over complete rankings \(\rho\) that are single-peaked with respect to \(B\), decide whether there exists \(q\in P_1\times\cdots\times P_t\) such that some \(q_w\) maximizes \(\operatorname{score}_{\mu,q}(c)=\sum_{\rho\in T:\,c\text{ is top-ranked among }q\text{ under }\rho}\mu_\rho\), with ties accepted.
A high-multiplicity Plurality nomination model with finite-support ranking types, rational population masses \(\mu\), an indivisible nomination vector \(q\) as the decision variable, and the objective of making \(P_w\) a Plurality co-winner.
The mirror covers Theorem 3, Corollary 1, and both possible and necessary variants of Theorem 1. It leaves Proposition 1, Theorem 2, and Theorem 4 outside its main claim, although Theorem 2 suggests a tractable restricted extension.
The strongest case is a high-multiplicity, population-weighted version of the paper’s Plurality-POSSIBLE PRESIDENT problem under single-peaked preferences. I would call it Single-Peaked Possible President\(_\infty\).
The candidates \(C\) are partitioned into parties \(P_1,\ldots,P_t\), and \(P_w\) is the target party. The society is not a list of \(n\) named voters. It is a finite-support distribution \(\mu\) over complete ranking types \(T\), where \(\mu_\rho\in\mathbb Q_{\ge 0}\) is the fraction of the population with ranking \(\rho\), and \(\sum_{\rho\in T}\mu_\rho=1\). The instance also supplies a societal axis \(B\), and every ranking in \(T\) must be single-peaked with respect to \(B\).
A nomination vector is \(q=(q_1,\ldots,q_t)\in P_1\times\cdots\times P_t\). For a nominee \(c\), its Plurality score is
\[ \operatorname{score}_{\mu,q}(c) = \sum_{\rho\in T:\,c\text{ is top-ranked among }q\text{ under }\rho} \mu_\rho . \]
The question is whether there exists a nomination vector \(q\) such that some \(q_w\in P_w\) maximizes this score. The solution is a yes/no answer, with \(q\) as a witness in the yes case. Nomination remains completely indivisible: each party still chooses exactly one candidate, and the winner is still a candidate, not a fractional outcome.
The regime is quite natural for a large political or organizational election. There may be millions of voters but only hundreds or thousands of recurring preference profiles, obtained from ideological, demographic, regional, or polling segments. Thus the electorate size \(N\) can be vastly larger than the number \(\tau=|T|\) of types. A type is precisely a complete ranking, since that is the only voter attribute used by the paper. A rational society is also a genuine high-multiplicity representation: if \(\mu_\rho=a_\rho/D\), it corresponds to \(a_\rho\) copies of type \(\rho\) in an electorate of size \(D\). The denominator \(D\) may be exponentially larger than the encoded input.
My lead anchor is Theorem 3, proved in this paper. It states that Plurality-POSSIBLE PRESIDENT is NP-complete even when the voters’ preferences are single-peaked. The reduction is from VERTEX COVER. Importantly, the theorem does not require candidates belonging to each party to form consecutive blocks on the societal axis; that additional restriction is what enables the polynomial-time result in Theorem 2.
The continuous problem above is therefore a direct mirror of Theorem 3. A finite hard election becomes a rational population distribution by setting \(\mu_\rho\) equal to the fraction of voters with ranking \(\rho\). Conversely, clearing denominators recovers a finite election with exactly the same Plurality comparisons. Hence NP-hardness transfers: the combinatorics live in the nomination choices and the party structure, not in the identities of individual voters. I would expect this mirror to be Class B, not continuum-specifically hard.
This is not merely a claim that “scores can be fractional.” The input society is compressed by type multiplicity, while the party nomination problem remains discrete. The continuous question asks whether an atomless population distribution changes the computational status of a strategic nomination problem; Theorem 3 gives strong evidence that it does not, even under a geometrically meaningful preference domain.
The paper’s Corollary 1 strengthens the same case: Plurality-POSSIBLE PRESIDENT remains NP-complete even when preferences are 1D-Euclidean single-peaked, and therefore also single-crossing. A more structured version of the mirror would represent each voter type by a location \(z_\rho\) and each candidate by a position \(x_c\), with rankings induced by increasing distance \(|z_\rho-x_c|\). This is an especially plausible continuous population for a left–right political axis. I would treat Corollary 1 as a strengthening of the lead anchor rather than as a separate problem: the only additional obligation is to make the paper’s omitted coordinate implementation explicit and polynomially encoded.
A second, broader anchor is Theorem 1, also proved in this paper. It states that Plurality-POSSIBLE PRESIDENT is NP-complete and Plurality-NECESSARY PRESIDENT is coNP-complete for unrestricted elections, even when every party has at most two candidates. The theorem proves the possible result by reduction from 3-SAT and the necessary result by a reduction from the complement of 3-SAT.
For this anchor I would use the same population model without the single-peakedness promise. It gives two closely related continuous decision problems:
The nonunique-winner convention is preserved exactly: ties count as victories. The possible variant has a nomination vector as its certificate. The complement of the necessary variant has a nomination vector and a candidate that strictly outscores the proposed necessary president as its certificate.
Both hardness results transfer through rational masses. The continuous problem is therefore again Class B. The fact that every party can have only two candidates is useful: the mirror does not rely on large or divisible party-level action spaces. What remains combinatorial is the simultaneous selection of nominees, exactly as in the paper’s reductions.
The mirror covers only these results: Theorem 3 as the lead, Corollary 1 as its stronger geometric version, and Theorem 1’s possible and necessary variants. It does not claim to continuize every result in the paper. Theorem 2 suggests an attractive boundary question: when parties form consecutive blocks on the single-peaked axis, the paper’s dynamic programme should extend to rational Plurality masses because it uses only score comparisons. That would give a tractable restricted continuous problem, but I would present it as a follow-up rather than overclaim it as an additional anchor.
The main further questions are whether hardness persists when the number of ranking types is bounded, whether the problem becomes fixed-parameter tractable in \(\tau\), how much approximation error in the population masses can be tolerated, and how the gap between possible and necessary presidents behaves under uncertain polling data. One could also study the transition between interleaved party candidates, where Theorem 3 gives hardness, and consecutive party blocks, where Theorem 2 gives tractability.
The weakest point is that these mirrors may look like exact weighted restatements of the finite problems. The existing reductions also use a type per logical gadget, so they do not by themselves prove hardness with a constant number of types. I would not pretend that this is a continuum-specific discovery. The honest positive claim is narrower: the paper’s nomination problem has a well-motivated high-multiplicity population regime, the continuous formulation is precise and computationally distinct in its input size, and the paper’s strongest hardness results survive it. That is already a meaningful Class B boundary for the continuization programme: population continuity does not dissolve the difficulty when the reduction’s combinatorics live in party nominations rather than voter multiplicity.
The strongest negative case is that the proposed mirror is scientifically thin: population mass is only a coefficient, never a decision variable. For a nomination vector \(q\), the entire society enters through
\[ \operatorname{score}_{\mu,q}(c) = \sum_{\rho}\mu_\rho \mathbf{1}\!\left[c\text{ is top-ranked among }q\text{ under }\rho\right]. \]
The feasible set remains the finite product \(P_1\times\cdots\times P_t\). Splitting or aggregating mass changes no feasible action, creates no integrality issue, and exposes no pricing problem. If \(\mu_\rho=a_\rho/D\), clearing denominators produces exactly the original finite election with \(a_\rho\) copies of type \(\rho\). Thus the proposed problem is a weighted, succinctly encoded election problem, not a population-continuous computational mechanism. The paper’s reductions use essentially one ranking type per gadget, so they do not even exploit compression by high multiplicity.
That objection applies to every anchor. Theorem 3 survives normalization exactly: its single-peaked rankings become rational type masses, and the interleaved party structure still carries the Vertex Cover reduction. Corollary 1 is no weaker; the same holds with 1D-Euclidean types, and replacing locations by a density would merely provide another representation of the same score calculation. Theorem 1’s possible and necessary variants also transfer exactly, including the strict inequality used for the complement of the necessary problem. Party sizes of two do not change this.
One might therefore argue that none of these results opens a genuinely continuous research direction: the population is passive, the nomination choices remain entirely discrete, and the continuous model has a finite sufficient statistic consisting of the candidate scores for each nomination vector. Questions about bounded \(\tau\), mass perturbations, or succinct input would be worthwhile weighted-election questions, but not evidence that this paper contributes to the programme’s continuous optimization or population-level complexity agenda.
That is the best case against the paper. It is not enough to support the requested universal verdict, however. The programme explicitly treats rational high-multiplicity representations as legitimate, and explicitly allows Class B results whose hardness remains in candidates, parties, or agendas. A voter type here is a complete description of everything the problem uses; no voter identity, history, network relation, or individual cost is lost. Plurality comparisons remain meaningful after normalization, and large electorates with recurring ranking segments are an entirely credible regime. Nor does the continuum degenerate: the score fractions still determine possible and necessary winners.
So I cannot honestly defeat any of the proposed anchors. The correct criticism is “valid but modest direct Class B mirror”: it should not be advertised as a new LP, pricing problem, or continuum-specific hardness result. But under the stated programme, that limitation does not make the mirror unworthy. The proponent’s case survives.
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.