| paper | Divide and Conquer: Using Geographic Manipulation to Win District-Based Elections |
| authors | Yoad Lewenberg, Omer Lev, J. Rosenschein |
| venue | ATAL 2017 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4 supplies the required named computational result. However, normalizing the paper's voter weights into masses \(\mu_t\) preserves every nearest-box assignment and district winner, while rational masses convert back to integer weights. The proposed mirror is therefore already the paper's weighted finite-support model, triggering \(b\text{-already}\).
fails bit b-already — the paper is already native to the continuum
The proposed continuous formulation is exactly equivalent to the paper's weighted-voter formulation, so it introduces no distinct continuous population object or bridge from a discrete model.
fatal: True
The formulation covers Theorem 4's NP-completeness as an exact weighted-model restatement; Algorithm 1 lacks a named approximation or complexity guarantee, and the empirical results are not independently anchored computational theorems.
My lead mirror is Continuous Geographical Gerrymandering\(_\infty\), the population-distribution version of the paper’s nearest-ballot-box manipulation problem.
The paper’s strongest anchor is Theorem 4, proved in this paper: “\( \text{gerrymandering}_{\text{plurality}} \) is NP-complete, even when the number of candidates is a constant.” The theorem concerns an election with candidates, weighted voters at locations in \( \mathbb{R}^2 \), possible ballot-box locations, integers \( \ell\le k\), and a target candidate \(p\). One must decide whether \(k\) ballot boxes can be selected so that every voter goes to their closest selected box and \(p\) wins in at least \( \ell \) of the resulting plurality districts. The authors prove this by reducing Planar X3C\(^*\), with their construction using only four candidates.
The continuous problem is as follows. An instance contains a finite set of voter types \(T\). A type \(t\in T\) consists of a geographic location \(z_t\in\mathbb{R}^2\) and a complete preference order \( \succ_t\) over the candidates. Its mass \( \mu_t\ge 0\) is the fraction of the population having that location and preference, with \( \sum_{t\in T}\mu_t=1\). The instance also contains a finite set \(B\) of possible ballot-box locations, a target \(p\), and integers \( \ell\le k\le |B|\).
The action is to choose \(B'\subseteq B\) with \( |B'|=k\). Each type is assigned wholly to its closest selected ballot box,
\[ a_{B'}(t)\in\arg\min_{b\in B'}\|z_t-b\|_2, \]
using a fixed tie-breaking convention. At each selected box \(b\), candidate \(c\)'s plurality mass is
\[ S_b(c)=\sum_{t:a_{B'}(t)=b}\mu_t \mathbf{1}\!\left[c=\operatorname{top}(\succ_t)\right]. \]
The question is whether some \(B'\) makes \(p\) win, under the paper’s plurality tie-breaking rule, in at least \( \ell\) selected districts. Equivalently, the optimization version maximizes the number of \(p\)-winning districts subject to selecting exactly \(k\) boxes. A solution is the selected set \(B'\); there is no fractional district assignment and no fractional ballot box.
This is a credible high-multiplicity regime. Think of millions of residents represented by census tracts, villages, apartment complexes, or other geographic–political cells. Residents in one cell have the same effective location for nearest-box purposes and the same relevant preference type, while the number of such cells \( \tau=|T|\) is much smaller than the population size \(N\). Ballot boxes are fixed possible sites, and an election authority or political actor chooses \(k\) of them. The paper’s geographic interpretation is preserved exactly: selecting boxes induces Voronoi-like districts, and the manipulation comes from how the population is spatially dispersed.
The mirror is not a softened surrogate. Given any instance of Theorem 4 with weighted voters \(v_i\), create a type for each distinct pair consisting of the voter’s location and preference order, with mass
\[ \mu_t=\frac{w_t}{\sum_{t'}w_{t'}}. \]
For every selected ballot-box set, the nearest-box assignment is unchanged, and all plurality scores are merely multiplied by the same positive constant. Thus the original instance is a yes-instance exactly when the continuous instance is a yes-instance. The strict margins in the proof, such as \(4\) versus \(3\) and \(6\) versus \(5\), survive normalization unchanged.
This places the mirror in Class B: hardness transfers. Under rational coordinates and rational masses, the problem is expected to remain NP-complete: a selected set \(B'\) is a polynomial certificate, and Theorem 4 embeds directly into it. The hardness is not caused by having many individually named voters. One may duplicate every resident of every type \(R\) times, making \(N/\tau\) arbitrarily large without changing the answer. The combinatorics live in the geographic arrangement of types and ballot-box sites, so continuization does not dissolve them.
The paper’s empirical and algorithmic material also makes the mirror recognizable to its authors. Their greedy algorithm can be run directly on masses by replacing voter counts with aggregate type mass, and their simulations already use very large populations generated from geographic and preference distributions. I would not treat Algorithm 1 as a second anchor, however, because the paper gives no named theorem establishing its approximation or complexity guarantee.
The weakest point is that the paper already permits weighted voters and explicitly says weights help represent multiple voters at the same location. Consequently, this mirror is mathematically close to a reformulation of part of their existing model. I would not present it as a dramatic new voting rule or as proof that the continuous model is tractable. Its defensible contribution is to make the population measure primary, separate \(N\) from the number of distinct types \( \tau\), and ask the corresponding high-multiplicity complexity questions. If that distinction is accepted, the authors should recognize Continuous Geographical Gerrymandering\(_\infty\) as their problem with the population continuized; if not, this particular mirror risks being judged a weighted-input restatement.
Natural follow-up questions are whether the problem becomes tractable for fixed \( \tau\), for one-dimensional geography, or with only two candidates; whether hardness survives smooth non-atomic geographic densities rather than atomic type masses; and whether the greedy method has approximation guarantees in the high-multiplicity model.
The proposed mirror does not clear the programme’s novelty gate, because Theorem 4 is already formulated over a finite weighted population. The paper’s voter is \((z_v,w_v,\succ_v)\): location, weight, and preference. That is already a mass-bearing type.
For any selected ballot-box set \(B'\), let \(a_{B'}(v)\) be the nearest selected box and define
\[ M_b(c)=\sum_{v:a_{B'}(v)=b} w_v\, \mathbf{1}\!\left[c=\operatorname{top}(\succ_v)\right]. \]
The proposed continuous instance sets \(\mu_t=w_t/W\), where \(W=\sum_t w_t\). Its district scores are exactly \(M_b(c)/W\). Hence every district winner, tie, and threshold condition is unchanged. Conversely, every rational continuous mass vector can be converted to integer weights using a common denominator. This is not merely a reduction preserving NP-hardness; it is an exact equivalence between the paper’s weighted model and the proposed atomic “continuous” model.
The proponent’s duplication argument therefore cuts against the mirror. If every voter type is replicated \(R\) times without changing anything, then total population was already irrelevant to the paper’s formal problem. Promoting those weights to normalized masses does not expose a new computational object; it renames the weighted input. If binary-encoded aggregate weights are the intended contribution, that is a high-multiplicity reformulation of the paper’s own weighted problem, not a population continuization discovered outside it.
The theorem’s reduction reinforces this point. Its hardness is carried by a carefully engineered arrangement of \(O(n+m)\) distinct geographic locations and ballot-box sites. The mass attached to each gadget point can be \(1\), \(2\), or \(3\), or normalized fractions, with no change. The continuous notation removes the names of the voters but leaves the entire geometric instance intact. The strict \(4\)-versus-\(3\) and \(6\)-versus-\(5\) margins show that normalization is harmless; they do not show that a new continuum problem has emerged.
A stronger rescue would replace atoms by a geographic density \(\rho(z,\sigma)\). But then the computational issue depends decisively on how that density is represented. With finite-support or finitely described piecewise densities, the problem is a weighted Voronoi-site selection problem with integrals replacing sums. With an oracle or arbitrary density, there is no ordinary finite-input complexity problem. With smooth blobs around the reduction points, strict separation can preserve the same gadget behavior, producing a geometric smoothing variant rather than a genuinely new population-level formulation. Allowing ballot-box locations themselves to vary continuously would be more substantial, but that continuizes the action space and district geometry as well; it is no longer the paper’s population mirror.
The continuous model is therefore perfectly well-defined, and the paper’s use of geography does provide a plausible aggregation story. But that is precisely why this is a collision rather than a worthwhile new mirror: the paper already has weights, repeated locations, and aggregate district scores. The suggested follow-up questions about fixed numbers of types or one-dimensional geography may be interesting parameterized studies, but they are refinements of the existing weighted problem, not consequences of continuizing its population.
I would not use Algorithm 1 as a second anchor either: the paper gives no theorem about its approximation quality. Thus the only serious anchor is Theorem 4, and its proposed continuous version is formally already present in the paper. The negative case is weakest if the programme is willing to count “binary-encoded weighted voters” or smooth density representations as sufficiently new input regimes; under that convention, a legitimate mirror survives. But on the programme’s stricter population-continuization criterion, this paper has already crossed the mass-representation bridge.
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.