| paper | d4-conf-ijcai-2018-0489 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The continuous-mass districting problem is coherent, but Theorem 2 establishes that a favorable partition exists rather than giving a computational result. The paper’s heuristic and experiments do not supply the required numbered computational anchor, so the proposed optimization problem would be a new computational study rather than a mirror of a qualifying result.
fails bit a — no named computational result to mirror
Theorem 2 makes no computational claim, and its threshold argument extends to fractional precinct masses without producing an algorithm or complexity result.
fatal: True
The proposed model draws on Theorem 2’s two-district threshold and the paper’s broader district-win objective; it leaves the urban-rural simulations and the heuristic’s empirical performance outside the mirror.
The strongest mirror I would defend is Continuous-Mass Gerrymandering. The paper has no numbered result that classifies a problem as NP-hard, in P, FPT, or similar. Its closest named anchor is Theorem 2, proved in this paper: for an even \(n\), an \(n\times n\) grid, and \(K=2\) equal-population connected districts, a party controlling the districting can win both districts whenever its vote share is at least \(1/2+1/n\). The theorem covers the worst case over how that party’s voters are distributed across the grid. It is a structural result about districting feasibility, rather than a complexity classification.
In the mirror, each type is a pair \((v,P)\): precinct \(v\) and party \(P\). A large precinct population has mass \(1/n^2\); if \(q_v\in[0,1]\) is the fraction supporting the target party, set
\[
\mu_{(v,P)}=\frac{q_v}{n^2},
\qquad
\mu_{(v,\bar P)}=\frac{1-q_v}{n^2}.
\]
The \(q_v\) are binary rationals, and the support has at most \(2n^2\) types. The scenario is a large election with many voters grouped into a much smaller number of precinct-party types. For example, millions of voters may be represented by a few hundred precincts, with each precinct’s party proportions recorded as masses.
Given this distribution and \(K\mid n^2\), the problem is to partition the grid’s vertices into \(K\) connected districts of \(n^2/K\) vertices each, maximizing the number won by the target party. A district counts as won when its target-party mass is at least \(1/(2K)\), using the paper’s tie-breaking convention. The solution is the partition and its win count; the associated gerrymandering power is the maximum win fraction minus the party’s population share. The map and the assignment of precincts to districts remain those in the paper. Only voter counts within each precinct become fractional.
Theorem 2 anchors the \(K=2\) case: in this model, it suggests that the same \(1/2+1/n\) guarantee holds even when the precinct-party masses are rational. The authors’ proof uses the grid’s structure and exchanges between strips, so this is a close match to their districting question. For the full optimization problem, I would expect hardness to transfer: the connected-partition choices remain, and discrete instances with equal precinct populations embed by setting each \(q_v\) to the corresponding fraction of party voters. This is a prediction, not a result established by the paper; a transfer claim would need hardness for the matching discrete grid model. Further questions include the exact worst-case vote-share threshold for each \(n\), and the complexity of maximizing wins for general \(K\).
The scope is the paper’s worst-case districting analysis and its gerrymandering-power objective. It does not claim a mirror for the empirical urban-rural simulation or the heuristic algorithm’s performance. Its weakest point is that continuity leaves the main graph-partition choices intact, so this mirror may not yield a tractability gain. That does not make the population model implausible: precinct and party are complete types for the paper’s purposes, and many voters can share each type.
The case is therefore positive about the mirror’s plausibility, with one important limit: Theorem 2 is the closest named anchor, but the paper supplies no named complexity-classification result of the kind your anchor rule asks for.
The strongest negative case is that this paper gives no named computational result to mirror. Its Theorem 1, Proposition 1, and Theorem 2 are structural guarantees about which districtings exist; the algorithmic contribution is a heuristic evaluated on experiments, not a complexity or approximation theorem. That matters here because the proposed mirror of Theorem 2 is another existence claim, not a computational question.
The proposed type \((v,P)\) is sensible: many voters can share a precinct and party, and their mass can be a rational proportion. But for fixed \(n\), Theorem 2’s strip-exchange proof uses inequalities, not integrality, so it extends directly to those fractional masses. And the paper already gives a continuous-measure treatment in Theorem 1 for the large-grid limit. Neither result classifies an algorithmic problem. Theorem 2 therefore does not supply the missing computational anchor.
The stronger alternative is to ask for the complexity of maximizing the number of districts won when precincts carry rational party masses. That is a coherent weighted graph-partition problem, and related computational work already studies graph districting with aggregated voter weights. That literature supports the plausibility of the high-multiplicity regime; it is not a reason to reject the mirror. But this optimization question is a new computational study, not a continuous version of a computational theorem in this paper. [A related weighted graph-gerrymandering model](https://arxiv.org/abs/2102.09889) illustrates that distinction.
So I would reject Theorem 2 as a surviving computational anchor. The negative case is weaker against the broader optimization question: the precinct-party masses are a plausible population model, and I cannot honestly rule out that studying its algorithms would be worthwhile. My case against is narrower: this paper’s named results do not establish that it has a computational result for ChoCo to continuize.
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.