| paper | Nonparametric Detection of Gerrymandering in Multiparty Plurality Elections |
| authors | Dariusz Stolicki, Wojciech Słomczyński, Stanisław Szufa |
| venue | IJCAI 2024 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem, lemma, corollary, or proposition asserting a computational complexity or algorithmic result, so bit (a) fails under the explicit standard. Problem 4.1 is a reasonable districting optimization problem, but it is already formulated over aggregate geographic-cell votes and weights. Therefore the paper is red despite yielding a potentially worthwhile problem for future complexity analysis.
fails bit a — no named computational result to mirror
The proposed \( \mathrm{Continuum\ Advantageous\ Districting}_\infty \) is obtained by setting \( \mu_{u,p}=w_u v^u_p/W \), so its feasible districts, winner predicates, and objective are exactly the paper's existing weighted-cell problem rather than a new population continuization.
fatal: True
The candidate mirror covers only the experimental district-selection objective in Problem 4.1; it leaves the seats-votes functions, kernel regression, electoral-bias \(p\)-values, aggregation method, and empirical evaluations without computational mirrors.
Strictly, this paper has no qualifying anchor. It contains no theorem, lemma, corollary, or proposition asserting a complexity result. Its only numbered computational object is Problem 4.1, introduced and solved experimentally using an ILP formulation; it is not claimed to be in P, NP-hard, FPT, or otherwise classified. Theorem 1 in Remark 2.1 belongs to Boratyn et al. (2022), is cited from elsewhere, and is axiomatic rather than computational. Thus there are formally zero anchors and no per-anchor continuous problems to report.
The strongest honest positive case is nevertheless a mirror of Problem 4.1, if the evaluator accepts a numbered optimization problem as a weaker anchor.
Call it Continuum Advantageous Districting\(_\infty\). Let \(G=(U,E)\) be a geographic adjacency graph whose cells are census blocks or comparable units, and let \(\mathcal K\) be the family of admissible connected districts satisfying the paper’s population-balance constraint. There are \(m\) parties and a target party \(a\). A voter type is \(t=(u,p)\): residence in cell \(u\) and vote for party \(p\). This is complete for plurality elections. The society is a mass vector \(\mu=(\mu_{u,p})\), where \(\mu_{u,p}\) is the fraction of the whole electorate of type \((u,p)\), with \(\sum_{u,p}\mu_{u,p}=1\).
For \(K\in\mathcal K\), define the party mass \(V_p(K)=\sum_{u\in K}\mu_{u,p}\). With a fixed tie-breaking rule, \(a\) wins \(K\) exactly when \(V_a(K)\ge V_p(K)\) for every party contesting there. A feasible districting is a collection of \(d\) pairwise disjoint members \(K_1,\ldots,K_d\in\mathcal K\) covering \(U\). The problem is
\[ \max_{K_1,\ldots,K_d}\sum_{j=1}^{d} \mathbf 1\!\left[V_a(K_j)\ge V_p(K_j)\ \text{for all }p\in P(K_j)\right]. \]
Equivalently, given \(q\), decide whether a feasible districting gives \(a\) at least \(q\) seats; a solution is the districting itself. All masses may be rational and encoded in binary.
This is genuinely a population continuization: a national electorate may contain millions of voters but only \(\tau=m|U|\) location-party types. Many voters in one cell who support the same party are interchangeable, and only their mass matters. The regime is plausible for parliamentary redistricting: \(N\) may be in the millions, while the number of census cells and parties is orders of magnitude smaller. A discrete election with \(n_{u,p}\) voters is recovered by setting \(\mu_{u,p}=n_{u,p}/N\).
The mirror is close to the paper’s own question. In Problem 4.1, the quantity \(v^k w_k\) is already exactly party vote mass, and the objective \(s_i(\sum_{k\in K_j}v^k w_k)\) is the same winner predicate above. The continuous version preserves connected districts, population balance, varying party participation, and the target-party objective. It does not replace gerrymandering by proportional allocation or remove geography. It merely makes the electorate nonatomic and asks for the resulting computational complexity.
I would expect this problem to be Class B rather than Class A. The likely hardness lives in selecting connected, balanced districts and packing them into a partition, hence in geography and the number of districts—not in the multiplicity of voters. A discrete hardness construction using rational masses should therefore transfer. Restricted variants without connectivity, where population can be fractionally assigned freely, may instead admit LP or flow formulations; those would be useful Class A subproblems, but they should not be confused with the full mirror.
The weakest point is substantial: the paper already writes \(w_k\in\mathbb R_+\) and \(v^k\in\Delta_m\), so this proposal may look like a reinterpretation of its existing finite-cell input rather than a new continuous computational result. Moreover, the paper proves no complexity theorem for Problem 4.1. Consequently, this is a credible but modest mirror of the paper’s optimization core—not a fully anchored case under the programme’s strict standard.
The negative case is strongest at the formal level: this paper has no qualifying computational result to mirror. It contains no theorem, lemma, corollary, or proposition classifying the complexity of a problem. “Problem 4.1” is an optimization formulation used inside an experimental procedure; the authors do not claim that it is in \( \mathrm{P} \), NP-hard, fixed-parameter tractable, or otherwise computationally classified. The theorem mentioned in Remark 2.1 is imported from Boratyn et al. and is axiomatic, not computational. Under ChoCo’s stated standard, there are therefore no anchors.
Even if Problem 4.1 is accepted as a weak anchor, the proposed continuum is not actually a new continuization. Let \(W=\sum_u w_u\) and define \( \mu_{u,p}=w_u v^u_p/W \). Then for every candidate district \(K\), the proposed mass \(V_p(K)\) is simply the paper’s existing aggregate vote mass, up to the constant normalization \(W\). The feasible districtings, winning predicates, and objective are unchanged. The paper already takes \(v^u\) and \(w_u\) as aggregate real-valued inputs; it has already discarded individual voter identities. Replacing those symbols by \( \mu_{u,p} \) is a change of notation, not a high-multiplicity relaxation of a discrete voter-level problem.
This distinction matters. In a genuine ChoCo mirror, individual voters are replaced by masses of interchangeable types and that replacement changes the computational object or its parameterization. Here the relevant type is \( (u,p) \), where \(u\) is a geographic atom. Geography is indispensable: it determines connectedness, admissible districts, and which votes can be aggregated. Consequently, the number of complete types is essentially \(m|U|\), the number of party-labelled geographic cells. Making each cell contain millions of voters does not reduce the problem to a new population-level object; the cell-level weighted graph instance was already the primitive input.
The obvious repairs do not escape this. If voters within a cell may be split fractionally between districts, the districts cease to be the connected components used in the paper. If the geographic domain itself is made continuous, the continuization is of space and district boundaries, not of the population; it becomes a different geometric-measure partitioning problem. If location is removed from the type, the votes no longer determine which districts are won. Thus one gets either the same weighted districting problem, a different continuous-geography problem, or an under-specified model.
Nor does the paper’s actual main contribution provide a better population anchor. Its seats-votes function is a probability measure over elections or seat outcomes, and its kernel regression operates on aggregate party- and election-level observations. The statistical difficulty comes from learning a reference distribution over elections and distinguishing electoral bias from ordinary geographic variation. A continuum of voters does not address that issue: the method already works with vote shares, seat shares, effective competitor counts, and a training ensemble. Turning the underlying voters into a distribution merely supplies the same finite aggregates. To obtain a genuine computational question one would have to invent a new robustness, optimization, or adversarial-districting problem, rather than mirror a result of this paper.
The proposed construction may still describe a sensible weighted districting problem, and a complexity theorem for it could be valuable. The negative case is not that such a theorem would be uninteresting, nor that a high-multiplicity electoral regime is implausible. Its point is narrower but decisive under the programme’s rules: the paper supplies no computational theorem, and its only plausible optimization anchor is already formulated at the aggregate geographic-cell level. The continuous mirror therefore adds neither a new population object nor a named computational result worth continuizing.
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.