| paper | d4-conf-atal-2022-0154 |
| 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: \(\Sigma_2^P\)-complete with unrestricted party sizes; \(\mathrm{NP}\)-complete under every fixed positive upper bound on party size, including singleton parties. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given districts \(D\), parties with named candidate sets, a fixed tie-breaking order, and for each district either an empty electorate or a finite-support rational distribution over complete rankings of the candidates with total mass \(1\), does there exist a nomination profile in which each candidate is nominated in at most one district and no party can increase its number of elected candidates by unilaterally changing its nominations? Each nonempty district elects the plurality winner under its ranking distribution and the fixed tie-break.
Voter types are pairs \((d,t)\) of a district and a complete candidate ranking, carrying rational mass within that district. Parties retain the paper's discrete nomination strategies, and their utility is the number of their candidates elected; the decision is whether a pure Nash equilibrium exists.
The strategic choices remain discrete nominations of named candidates, so this mirror mainly compresses a large electorate and may make limited use of continuous-optimization machinery; that limits its potential payoff, not whether it is a well-posed population mirror.
fatal: False
The mirror covers Theorem 2's general Σ₂ᵖ-completeness result and, with the corrected restriction, Corollary 1's NP-completeness result for constant candidates per party. It leaves the restricted-instance equilibrium propositions and the paper's proposed extensions aside.
My lead is Continuous District Candidacy. In each district \(d\), let the voter types be complete rankings \(t\) of the candidates, with rational masses \(\mu_{d,t}\ge 0\) summing to \(1\). The input gives each district’s positive-mass types and binary-encoded masses, alongside the candidates, their party partition, and the paper’s fixed tie-breaking order. A party chooses where to nominate its candidates, with each candidate placed in at most one district. Under a nomination profile \(\nu\), candidate \(c\)’s plurality share in district \(d\) is
\[
\sum_{t:\,c\text{ is the highest-ranked nominee under }t}\mu_{d,t}.
\]
The district elects the candidate with the largest share, using the fixed tie-break; if nobody is nominated, it elects nobody. A party’s utility is the number of its candidates elected. The question is whether there exists a pure Nash equilibrium nomination profile: one in which no party can increase that number by changing its nominations alone. A witnessing nomination profile is a solution.
This is a credible high-multiplicity regime: a national or regional election may have very large electorates in each district, while preference types are shared by much smaller blocs—say, tens or hundreds of recurring ranking types among hundreds of thousands of voters. The parties remain a small set of strategic organizations with finite candidate pools, as in the paper; it is the electorate whose population becomes continuous. That fits the authors’ own motivation about parties influencing large electorates. Normalizing each district to mass \(1\) preserves every plurality winner and every party deviation, since only within-district vote shares matter.
Theorem 2 is the lead anchor. It states that deciding whether a district nomination game admits a pure Nash equilibrium is \(\Sigma_2^p\)-complete under the paper’s assumptions: one seat per district, plurality with fixed tie-breaking, and parties seeking to maximize the number of their elected candidates. The paper proves this result, including the hardness reduction from \(\exists\exists!\)-3sat; the cited work of Marx establishes the hardness of the source problem. Its continuous mirror is the problem just defined. I expect hardness to transfer: given a discrete electorate, set \(\mu_{d,t}\) to the fraction of district \(d\)’s voters with ranking \(t\). Every nomination profile then produces the same winners and party utilities as before, so the same profiles are equilibria. This conversion is exact and polynomial in the original input size. The mass version also remains in \(\Sigma_2^p\): guess a nomination profile, then universally check that no party deviation improves its payoff. The hard combinatorics lie in the parties’ choices across candidates and districts, not in representing a large population.
A second, useful anchor is Corollary 1. It states that district candidacy is NP-complete when every party has a constant number of candidates; the paper derives hardness from its 3sat construction and gives the NP upper bound by polynomially checking deviations. The corresponding Bounded-Party Continuous District Candidacy question is the same rational-mass equilibrium-existence problem, restricted to \(|P|\le q\) for a fixed constant \(q\). I again expect hardness to transfer, giving NP-completeness: profile guessing is polynomial, and with bounded party size each party has only polynomially many nomination deviations to check. This restriction is not needed for the main case, but it shows the mirror does not rely on parties having large candidate pools. In the paper’s NP-hardness construction each district has seven voters, so its ballots can be encoded as ranking masses in increments of \(1/7\), then replicated to represent an arbitrarily large electorate without changing any equilibrium.
The case covers the paper’s core district-candidacy complexity results, not its propositions about special preference structures or extensions to other voting rules and multiwinner districts. Natural follow-up questions include whether useful fixed-parameter algorithms exist in the number of candidate types, districts, or parties, and how sensitive equilibrium existence is to small changes in the mass vector.
The weakest point is that every rational mass profile can be expanded into a finite replicated electorate. So this mirror does not claim new strategic behavior arising only in a literal continuum. Its value is the high-multiplicity computational question: the masses give a compact description whose denominator may represent a very large electorate. That is still directly about the population, and the paper’s hardness survives even in that representation.
The strongest case against is that this paper offers little for the continuous optimization toolbox. Voters are a fixed environment; the strategic choices are parties’ discrete nominations of named candidates into named districts. A continuous mirror turns each district’s ballots into exact plurality shares, but it does not make nominations fractional or reveal an obvious LP or convex program. It may therefore be a less promising target for the programme’s optimization machinery than problems whose decisions themselves range over masses.
That concern does not defeat the better mirror. Use a distribution over district–ranking pairs, or conditional ranking distributions within each district. The district must be part of the type because voters in different districts affect different contests. Voter identity need not be: each ranking and district completely determine how a voter affects this game. Normalizing each district’s mass to \(1\) preserves every winner and party payoff. More generally, every rational mass profile is exactly realizable by a finite replicated electorate. That makes the mirror an exact high-multiplicity formulation, not an instance where the population axis is incoherent. Exact replicability is allowed by the programme’s brief, and the input can still describe a very large electorate compactly.
So Theorem 2 survives. Its \(\Sigma_2^p\)-complete question has a direct continuous version: does a rational distribution of voter types by district admit a pure-equilibrium nomination profile? The original electorate maps to those masses by dividing each district’s type counts by its population. This preserves all deviations and equilibria; the paper’s hardness construction, with seven voters per district, carries over using masses in increments of \(1/7\). The result may expose no new strategic behavior, but that is not a valid objection under the programme’s criteria. The formal question is well posed, computational, and about the population.
The second anchor is misstated. Corollary 1 bounds the number of candidates per party, not the number of parties. The paper’s hardness construction uses singleton parties but allows their number to grow, so it does not establish NP-completeness when \(|P|\) is fixed. But the corrected continuous mirror—constant party size, with the number of parties unrestricted—does survive: it is the same exact mass translation of the paper’s NP-complete restriction.
The remaining negative point is about payoff from the research time, not a fundamental flaw in the mirror: the input compression may be the main consequence of continuization, while the hard strategic structure stays discrete. That is a modest case against prioritizing this paper. I cannot honestly defeat the \(\Sigma_2^p\)-completeness anchor, and the corrected NP-completeness anchor survives too. The case against is therefore 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.