All Politics is Local: Redistricting via Local Fairness
Authors: Shao-Heng Ko
Erin Taylor
Pankaj K Agarwal
Kamesh Munagala
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interest and in the minority of their respective districts;  such a set of individuals have a justified complaint with how the redistricting plan was drawn. A redistricting plan with no deviating groups is called locally fair. We show that the problem of auditing a given plan for local fairness is NP-complete. We present an MCMC approach for auditing as well as ranking redistricting plans. We also present a dynamic programming based algorithm for the auditing problem that we use to demonstrate the efficacy of our MCMC approach. Using these tools, we test local fairness on real-world election data, showing that it is indeed possible to find plans that are almost or exactly locally fair. Further, we show that such plans can be generated while sacrificing very little in terms of compactness and existing fairness measures such as competitiveness of the districts or seat shares of the plans. 

All Politics is Local: Redistricting via Local Fairness
Shao-Heng Ko"
Erin Taylor*
Pankaj K. Agarwal Department of Computer Science
Kamesh Munagala
Duke University
Durham, North Carolina 27708 USA
Email: {sk684, ect15 pankaj kamesh) duke, edu
Abstract
In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interest and the minority of their respective districts; such set individuals have a justified complaint with how the redistricting plan was drawn. A redistricting plan with no deviating groups is called locally fair. We show that the problem of auditing given plan for local fairness is NP-complete. We present an MCMC approach for auditing as well as ranking redistricting plans. We also present dynamic programming based algorithm for the auditing problem that we use to demonstrate the efficacy of our MCMC approach. Using these tools, we test local faimess weal-world election data, showing that it is indeed possible to find plans that are almost or exactly locally fair. Further, we show that such plans can be generated while sacrificing very little in terms of compactness and existing fairness measures such as competitiveness of the districts or seat shares of the plans.
Introduction
Redistricting in the United States is the process of partitioning state into districts, each of which elects one representative to the Congress, for the most part, via simple majority voting. 2022, one year after the US Census Bureau released the results of the 2020 decennial census, 41 out of the 50 states have finished redrawing the congressional redistricting plans for the next decade [29]. This process has triggered numerous debates and litigation along the way. Much of this debate centers on whether the plans are gerrymandered so that one of the two parties gets more representatives. Given its high-stakes impact and mathematical richness, there has been persistent interest in tackling redistricting as an algorithmic question since the early 1960s [7].
April
There is ongoing debate around what a "desirable" redistricting plan should be. It is commonly agreed that "desirable" plans should, minimum, produce population balanced, contiguous, and compact districts [1]. Beyond this basic agreement, there is still debate on richer notions of desirability, particularly notions related to the "fairness" of a plan. This has motivated a long line of recent work [14, 15, 23] as well software tools [4, 29] on auditing given redistricting plan against various fairness concepts. Some these concepts have since been adopted in Wisconsin's 's and Michigan's 'ss redistricting efforts [11]. It should be noted that under most notions of desirability proposed in literature, the problem of redistricting is computationally hard [27], leading to the study of heuristic approaches, which outline later.
Global versus Local Fairness. Zooming into fairness criteria, most extant notions of fairness focus on the global outcomes of the redistricting plans, e.g., whether the seat shares proportionally represent the demographics [41], or how competitive the districts drawn are [14]. However, it is argued [5]
Equal contributions.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

that global metrics do not always distinguish between natural gerrymandering when the distribution of voters unavoidably prohibits certain globally fair outcomes and artificial gerrymandering
when the plans are manipulated to favor demographic group. This issue is typically addressed via statistical tests [15]: a probabilistic method is used to generate an ensemble of population balanced, contiguous, and compact plans, and the global fairness score in question is computed for each of these plans, yielding a histogram of scores. The plan in question is deemed "fair" if its global fairness score is not outlier in this histogram.
Global fairness, such as proportional seat shares, despite being desirable and statistically testable, may not represent the local concerns of voters. For instance, imagine the blue party cares about rising sea levels and climate change, while the red party does not. In North Carolina, if at least one seat on the eastern coast has blue majority, that representative may advocate to mitigate the impacts of climate change to the coastal residents on the state or federal level. On the other hand, a better seat share may lead to plan in which all districts near the coast have red majority, while the districts in the western mountains have blue majority. However, the latter set of representatives may not advocate for issues impacting the coastal residents, since it is not of local concern to the geographic area. This motivates the need for local fairness as a separate fairness measure, capturing at some level the saying "all politics is local".
Borrowing the notion of core from cooperative game theory. the work of [5] defines local fairness notion as follows: given a redistricting plan, voter is unsatisfied if the majority demographic in her district does not match her own demographic. A redistricting plan is locally fair if no group of unsatisfied voters could deviate and draw different district such that this group of unsatisfied voters has a majority in the new district.
As in the scenario above, such a local notion of fairness has the advantage of capturing justified complaints of groups of voters, has happened in earlier court judgements [2]. It also provides a way of auditing enacted plans without resorting to statistical tests, making it more human interpretable and explainable.
Research Questions. The notion of local fairness is appealing; however, the analysis and results in [5] are theoretical and apply only to simplified one-dimensional model. In this paper. we develop algorithms to audit plans for local fairness, and systematically study this concept on real-world electoral data. In particular, we study the following questions:
Given redistricting plan, can efficiently test (or audit) whether the plan is locally fair?
Are locally fair plans achievable in real redistricting tasks? If not, can we quantify how far given plan is from being locally fair?
Is local fairness empirically compatible with other existing global fairness concepts?
1.1 Related Work
Redistricting as Optimization. We first focus on the task of drawing plans, or computational redistricting. The idea of using computational tools in redistricting dates back to the 1960s [24, 39]. Since then, an extensive line of work (see [7] for comprehensive survey) cast the redistricting task as an optimization problem, in which the input contains only spatial location of individuals, but not their political affiliations. The objective and constraints capture the population balance, contiguity, and compactness criteria of the districts. This problem is computationally intractable in the worst case [13], and multiple algorithmic approaches have been proposed, including Voronoi diagrams [20, 28), local search [26), simulated-annealiig and hill climbing [6], and spatial evolutionary algorithms [31]. On the flip side, it is argued in [10, 42] that such "neutral" districting plans as outputs of algorithms without political inputs may contain unintentional biases, well as unexpected outcomes such as "natural gerrymandering" [8. 19]. i.c., the geographic distributions of voters naturally lead to disproportionate seat shares. Therefore, fairness objectives such as partisan representativeness are typically incorporated into the redistricting problem as objectives; however, these additional requirements further add to the computational difficulty of the problem [27].
Ensemble Approaches to Redistricting, Instead of optimizing and finding a single best redistricting plan, another line of work focuses generating a large ensemble of districting plans, with the hope of some of these plans being fair. These methods include Flood Fill (2], Column Generation [21], and the widely adopted Markov Chain Monte Carlo (MCMC) approach [18, 30, 38). The latter

---

approach samples from the space of feasible plans with a bias towards "desirable" or faimess properties. For instance, provably biases towards compact plans. We provide more in-depth description of ReCom in Section 3. The work of [17] proposes a method for choosing one representative plan from such an ensemble based on defining distances between plans.
shown in [35] that the widely used ReCom MCMC method [15]
Auditing and Combating Gerrymandering. A somewhat different question from constructing a desirable plan is the question of auditing a given plan for desirability and fairness. As mentioned before, ensemble based approaches provide a natural, statistical way of auditing [22, 23]: The properties of the enacted plan is compared against the histogram of the corresponding property on the ensemble; if the plan statistical outlier. then it is considered more "gerrymandered and hence less desirable. The recent work of [30] instead uses plans in the ensemble as comparators to identify manipulation in redistricting plans. On the non-statistical side, numerous approaches to auditing have also been proposed via appropriate desirability scores. These are either scores based on compactness of the plan (such as the Reock [36] and Polsby-Popper [34] scores), or scores based on partisan outcomes generated by the plan (such as the efficiency gap [37], mean-median gap [40], partisan symmetry [41], and the GEO metric [9]), or scores based on competitiveness of the plan [14]. Many of these measures are used in publicly available tools [3, 4]. Finally, there is recent line of work that attempts to eliminate gerrymandering by completely revamping the winner-takes takes-all, single-member member district mechanism into multiwinner election [19].
1.2 Our Contribution
In this paper, we take the standard view of redistricting partitioning planar graph on precincts into population- ballnced, contiguous, and (in a heuristic sense) compact regions. We naturally extend the local fairness concept proposed in [5] this task.
We first focus on the question of auditing a given plan for local fairness, that is, the non-existence of a appulationbbalaneed contiguous region in which a majority of voters are of the same party and is minority in the given plan. We show that this problem is computationally intractable in the worst case. Our first contribution is two heuristics for the auditing problem. Our first approach, that is scalable and practical, extends existing ensemble-basee methods in a novel way: we assume the districts in the ensemble audited, we test each of these districts as a potential deviation on that plan. Our second approach drills deeper into plans where the ensemble based method finds no deviating group; indeed, if the method found deviating group, the plan was already deemed not locally fair. On the former set, we generate several random spanning trees, and devise a polynomial time dynamic programming algorithm that audits each tree for local fairness. If any of these audits finds a deviating group, the original plan was not locally fair. The dynamic program not as efficient as the ensemble-based method: however, we provide empirical evidence that the ensemble method suffices to deem a plan locally fair, and the dynamic program typically does not find additional compact deviating groups. Finally, for redistricting plans that are not locally fair, we propose a measure that quantifies the unfairness of the plans by the portion of population with justified complaint.
the only districts which voters can deviate, and given plan to be
As our second contribution, we empirically study the notion of local fairness on real data on recent elections in the US. We generate plans using the (by now) standard ReCom [15] ensemble method, and audit each plan for local fairness using the ensemble method, thereby producing an ordering of the plans via our unfaimesss measure. We empirically show that applying the criterion of local fairness prunes the space of candidate plans considerably, while still returning a set of potential candidates. Most global and statistical notions of fairness fail to do such pruning. since they are endogenously defined relative to the order statistics on the ensemble. We further show that not only is local fairness achievable on real redistricting tasks, but it is also compatible with extant global fairness properties. Indeed, when we compare locally fair plans and those with many deviating groups, the former tend to be just as compact, have comparable seat share outcomes, and sacrifice only small amount of competitiveness. Thus local fairness can be used as an additional faimess criterion in conjunction with a global fairness criterion. We also investigate robustness of the local fairness concept, and show that fair redistricting plans remain consistent across different elections used. We finally show visualizations of fair and unfair plans; in particular showing that the visualization of deviating groups makes the local fairness notion explainable.
3

---

Taken together, our results demonstrate local fairess as an effective pruning criterion for candidate redistricting plans while sacrificing little in other desired properties. We also note that practice, there could be other considerations when choosing the "best" plan even among many locally-fair plans; we leave the question of choosing these considerations to policy makers.
2 Model and Preliminaries
In keeping with recent literature [13, 15, 16, 21], the input to the redistricting problem is planar connected graph G = (V, E3) where each vertex v E V represents an indivisible geographic unit (a precinct or a census block),² 2 and an edge is placed between two vertices if they are geographically adjacent. Going forward, we refer to each U E V as precinct and G as the precinct graph.
Redistricting Plans. For each precinct
V. let p(v) 0 denote its population and let T(v)
[0, p(v)] denote the number of voters in v.?. We let (2)) E [o, 1] and B(u) = 1 ->(v) denote the fraction of r(v) who vote red and blue, respectively. Note that it is assumed each individual voter is exactly one of the two colors. For an arbitrary subset of precincts W C V, set p(W) = Σvew p(U),
r(W)= = Evew T(O), >(W)= == (ecw((())r7())) and ((W) = -WW.
r(W)
Definition (k-redistricting plan). A k-redistricting plan of = (V, E) is a partition V into pairwise-disjoin subsets D1, D2,...., Du S V, called districts. Each district assumes the color of the majority of its voters. For redistricting plan I1, let Bn (resp. BT) denote the set of precincts in blue (resp. red) districts in II.
In the following, we fix an error parameter 6 >> O, and the desired number of partitions k. Note that the average population per district is 2 We say a district D S V is e-feasible if: (1) D induces a connected subgraph, and (2) the population of D is at most s away from average, i.e., (1 - e) pVV2 e-fasiibl..
- K < p(D) S (1 +e) pfV) E
A redistricting plan II is s-feasible if each district D, E TI
We note that this definition of an e-fcasible plan is consistent with the general practice in the U.S, where the sizes of districts should be balanced in terms of their population, based on census information, not in terms of the number of eligible voters. Since & and l will be fixed throughout, we drop the prefixes and refer to k-redistritcting plans and e-feasible districts redistricting plans and feasible districts, respectively.
Local Fairness. We extend the notion of local fairness proposed by [5] to the graph-based redistrict- ing problem. We say that feasible district W C red-majority (red in short) if >WW) 2 3(W), and blue-majority (blue) otherwise. We call this majority color as the color of W. Given a redistrict- ing plan 11, any voter whose color agrees with the color of its assigned district in II is deemed happy with respect to 11, and the remaining voters are unhappy.
Definition 2 (c-locally fair). Given a feasible redistricting plan II of G and a constant e. E (1/2, 1). a feasible district W C V is a red e-deviating group with respect to if is red and least c-fraction of its voters are unhappy red voters in I1, or formally, Evewnna 7V) T(V) > c-T(W. A blue e-deviating group is defined analogously. We call a feasible redistricting plan Il of G c-locally fair if there are no red or blue c-deviating groups with respect to II.
When c = 1/2, only a simple majority of voters in a deviating group must be unhappy. In this special case, we omit the prefix e by referring to red deviating groups, blue deviating groups, and locally fair redistricting plans. Throughout, we refer to locally fair redistricting plans as fair plans.
We are thus interested in the following two problems.
LF AUDITING problem. Given feasible redistricting plan IT and parameter E (1/2, 1). decide whether 1I is c-locally fair.
LFP GENERATION problem. Given a precinct graph and parameters e, k and c, compute a feasible redistricting plan IT of G such that II is c-locally fair, or report that none exists.
TTyiccalyy precincts are not split by redistricting plans [15].
We assume that we know the exact number of people who cast vote in each precinet, along with which candidate they voted for, such as is available for historical elections

---

For redistricting plan II that is not locally fair, we quantify its degree of unfaimess as follows. Consider all deviating groups of II, and define the unfaimesss score of II as the fraction of all voters that are unhappy in some deviating group. Formally, let
W (T) = Ru n (U C W a blue deviating group of m
denote the set of red precincts that lie in some blue deviating group of IT. Similarly, define WR (TT). Then the unfaimess score of IT is defined as:
(II 3(WA (TT) (WW (TT) + (WF((I) (WWR
+(V)
This score captures the fraction of voters that are both (i) unhappy in II and (ii) in the majority color of some deviating group of II. Note that (II E [0, 1], and equals zero if II is locally fair.
Compactness. In addition to requiring that districts be contiguous and population balanced, many redistricting models also require that the districts be compact. However, in contrast to the former two criteria, there is universally agreed measure of compactness [7, 21J. For example, the Princeton Redistricting Report Cards* uses Reock [36] and Polshy-Popper [34] scores, both of which are derived from the and perimeter of the geographic districts drawn. It also uses the number of counties split into multiple districts. In the discrete model of precinct graphs, one common measure of compactness the number of edges formed by the plan, i.e., the number of edges whose endpoints lie in different districts of II [13, 15]. Though we do not enforce compactness in the generation and audit problems, the algorithms we use are biased towards compact plans, as we empirically demonstrate.
Organization. In Section 3, we present two algorithms for the LF AUDITING and LFP GENERATION problems. We then describe the experimental setup and empirical results in Section 4. Additional methodological and experimental results are presented in the Supplementary Material.
3 Heuristics for Efficiently Auditing Local Fairness
In Appendix A, prove that both the LF AUDITING and LFP GENERATION problem are NP- complete, thereby necessitating heuristic or approximately optimal approaches.
Our main contribution in this section is efficient heuristics for LF AUDITING. The methods trade off computational efficiency for accuracy in determining local fairness. We describe the types of inaccuracy (one-sided versus two-sided error) that arise after describing the methods. We also provide empirical evidence that the more computationally efficient of these methods suffices to deem plans as locally fair. For LFP GENERATION, we simply generate ensemble of feasible redistricting plans using existing MCMC approaches, and run the I.F AUDITING algorithm to find the unfairness score UTf((T] for each generated plan IT, thereby ranking the plans in the ensemble in terms of fairness.
3.1 Ensemble-based Auditing
The computationally more efficient approach makes use of ensembles in a novel way as follows:
1. Generation. Generate an ensemble of redistricting plans & (II, Ilg. I.).
2. Districts to test. Let A = - II be the collection of districts in the plans in E.
3. Audit. Treat A as the candidate set of deviating groups. For each plan IT E E, compute if each D E A a c-deviating group (either red or blue). This step yields, for each IT E E, the set W (II) S V of precincts in blue deviating groups E A (which we use as an approximation of Wi (II)), and similarly WR (II). We then use W3 (II) and W (II) to compute the unfairness score unI( for each 11 E.
For the first step of an ensemble of plans E, we use the ReCom algorithm [15]. This algorithm develops a Markov Chain whose state space the full set of (e- (easible (k- partitioss of G. In each step, it randomly combines two (or more in its general form) districts of the current redistricting plan,
wttprrymannner.ppinetoto.c.o wwwnceton.edii edu/
5

---

generates a random spanning tree of the subgraph induced by the combined districts, and re-partitions the subgraph into two parts by cutting edges in the spanning tree so that the new resulting districts remain population balanced. The random spanning tree step biases the Markov chain towards plans with compact districts, where compactness measured by number of cut edges [35].
In the remainder of the paper, we describe our auditing framework when ReCom is used as the ensemble generation technique. We note however that we can use any other method that produces compact plans, for instance, iterative-merging flood-fill algorithms [10].
3.2 Auditing via Dynamic Programming on Trees
The ensemble-based LF AUDITING method makes one-sided error - if it finds deviating group, then the plan is not fair, while the absence of a deviating group from A only means the plan is likely fair. Indeed, in experiments, there are often multiple redistricting plans that the ensemble-based audit deems likely fair, calling for more systematic method for further analyzing the candidate plans that are potentially fair. This motivates the approach now describe.
We show that the LF AUDITING problem efficiently solvable if G is a tree. We then exploit this fact and use this as a heuristic to solve LF AUDITING on a general planar graph G, given partition II, as follows:
1. Random spanning trees. First generate collection of random spanning trees T of G.
2. Audit each tree. For each tree T E TT, decide there exists a feasible deviating group with respect to II such that this district is connected subtree of T. Note that such district will also be a connected subgraph in G.
We implement step 2 for a tree T using dynamic programming. We check for the existence of blue deviating group for e = 1/2 in a tree 7 as follows; the case for red groups and larger e follows similarly. Note that the range for the size of a district is [(1 )o, (1 + s)o], where a = p(V) k. For each precinct u E V. let (vv) denote the district that contains in IT. Let the number of unhappy blue individuals in precinct v be denoted uhp(v) = 3(v)- if (vv) Rn, and zero otherwise. The task is to decide whether there is a connected subtree W C T such that Evew p(u) E [(1-s)o, [1+))
and Enew uhp(v)= > 1 Evew T(V).
For each v E V, let T, be the subtree of T rooted v. For vertex V and two parameters i.p S E)o, let A(u, i, p] denote the maximum number of unhappy blue voters in a subtree W C T. such that W, r(W) S i, and p(W) = p. To compute Aju, i, p). we take the best subset of children of such that unhappy blue voters are maximized subject to population and voter constraints.
For a leaf u of T, Alu, il = uhp(u) if 2 r(u) and p = p(v), and Afu, i, = 0 otherwise.
Next, let be an internal node of T. Let U = children(w) = {ui ........ Mag(()) denote the set of v's children in T. Let i' = --- (w)) and p' p p(v). We have
deg(v)
doR(v)
dog(u)
A(e, pl = uhp(v) + max
Alu, kp,
Σ
Σ (I)
(g
To compute the second term in Equation (1) efficiently, let B x. y) denote the maximum number of total unhappy blue voters in a union of subtrees rooted at {ur,-- Mg} with total voter count at most x and total population level y. The second term of the RHS in Equation (1) Be.i.p (deg(v), p'). We then have p v, yl = Alu1, y) for all xr y, and for all j 2 2 we have
Bo,kpii I, v] = max [Bu..pli - 1, x 2', y - v11 + Alu,. x' l
(2)
3'Ej0.=).v'E(0..
The algorithm thus proceeds by computing all A A/v, i in an outer loop in increasing order of i and p and in bottom-up order of v. Each computation of Alu, i, p) proceeds with an inner loop that computes B... j.. x. y) in increasing order of j. x, and For each u, after computing all A(E, é, p). we check if there is any p E [(1 =)o, (1 + e)o] such that A(v, i, >>
2. If so, there exists a blue deviating group rooted at with population p. total voter count at most i, and total number of unhappy blue voters A i).

---

Time complexity. The algorithm computes O σ²) values of Afe, pl, each computing (T) o²) values of Buss,pli æ, y). Computing each Bu,i,pli, x,yl requires O(o2)-time to loop through all values of x' and y', Hence the overall time complexity ((V] 0 de)( We conclude the following.
Theorem 1. LF AUDITING problem on a tree T(V, EV can be solved in time O deg(TT)) Here, (eg(T)) is the maximum degree of a node in T.
Ensemble-based Auditing is Approximately Sufficient The dynamic programming method is less desirable because of two significant limitations. The first is its running time, which is prohibitively high for practical use. The second limitation is the introduction of a different type of error from the unsemble-based method. Note that as with the sesemble-based method, the non-existence of deviating group in the DP only provides high confidence (but not absolute certainty) about the plan being locally fair. At the same time, there is more subtle type of error the DP can make in the other direction: even if it finds a deviating group on the tree, this may not be a compact deviating group in the original graph. Therefore, the algorithm can output "not locally fair" when the only deviating groups are non-compact. We therefore need a final step where we check the deviating group to see that it is both feasible and compact on the original graph.
In Appendix B.I, we first show approaches to speed up the running time of the dynamic program to make it practical. In Appendix B.2, we deseribe additional assumptions under which the dynamic program runs efficiently, we empirically show that fails to find compact c'-deviating groups in plans that the ensemble- beaeed audit method deems c-locally fair, for c' slightly larger than On the other hand, it easily finds such deviating groups in plans that the ensemble- In summary, the dynamic programming approach obviates its own use in practice, since we provide strong evidence that the ensemble-based auditing method suffices in order to deem redistricting plans as locally fair, assuming the strength e of the deviating group is relaxed slightly.
method deems unfair.
4 Experiments
In our experiments, we attempt to answer the following questions. First, is local fairness achievable on real redistricting tasks? Second, is it compatible with extant measures of global faimess? Finally, is the notion robust if the underlying data changes? Given the previous discussion, our experiments in this section focus exclusively on the ensemble based method. In Appendix B we discuss the experiments for auditing via dynamic programming.
4.1 Datasets and Methods
All data used in our experiments is obtained from the MGGG States open repository [33]. We obtain shapefiles and precinct graphs for Massachusetts (MA), Maryland (MD), Michigan (MI), North Carolina (NC), Pennsylvania (PA), Texas (TX), and Wisconsin (WT).5 5 We set p(v) to the 2010 census total population in each precinct v. The default election we use is the 2016 presidential election, while the 2012 presidential election is also used in the robustness tests. For each precinct v, we collect the number of total votes for the Republican party To and the total vote amount for the Democrat party b, in the 2016 presidential election from [33]. We set (v) r./ /r. + b,), 3(b) = 1 - Te. and T Tv)) = Tu + by so T(V) is the total number of red (Republican) and blue (Democrat) voters.
Using the ReCom algorithm, we generate an ensemble of redistricting plans for each state. 6 Each ensemble consists of 1, 000 redistricting plans, each being the outcome of an independent 10, 000- step Markov chain (with default population balance parameter = 0.02) seeded with recent congressional electoral plan of the state. We set to be the number of congressional districts the 2016 election in each state. We then obtain the collection A of candidate districts for each state by taking the union of the districts in each plan in the ensemble. The properties of input graphs of states and their corresponding ensembles are summarized in Table 1.
7

---

State
(V)
7(V)
A
MA
2.1K
5.9K
6.55M
5.13M
8.5K
MD
1.8K
4.7K
5.77M
4.42M
7.8K
MI
4.8K
12.5K
9.88M
7.54M
14
14.0K
NC
2.7K
7.6K
9.53M
7.25M
13
12.9K
TX
8.9K
24.7K
25.14M
18.28M
36
35.9K
PA
9.2K
25.7K
12.70M
9.91M
18
18.0K
WI
7.1K
19.5K
5.69M
4.35M
7.87K
Table 1: Properties of data and ensembles.
State
MA
MD
MI
NC
PA
TX
WI
c .5
100%
26.7%
0.3%
4.9%
12.0%
2.8%
76.9%
c = .51
100%
27.0%
1.6%
8.7%
28.6%
5.4%
83.6%
c .52
100%
28.0%
11.9%
14.8%
41.4%
8.7%
87.2%
.55
100%
31.5%
35.2%
63.9%
95.2%
26.0%
94.0%
Table Percent of plans without c-deviating groups for different c values.
(a) NC. Fair Plan
(b) NC. Plan with blue dev. group
(c) PA Fair Plan
(d) PA Plan with blue dev. group
Figure North Carolina and Pennsylvania plans without and with deviating groups. The blue deviating groups drawn with black outline. In these figures, the districts are coded by its color and the extent of partisanship: districts with a larger value of y (resp. 33) are colored in darker red (resp. blue).
4.2 Locally Fair Plans: Counts and Visualizations
We first use the ensemble-basee audit method audit each plan the ensemble against the set A of districts from the entire ensemble. For each E (0.5, 0.51, 0.52, 0.55). we count the number of plans the ensemble without c-deviating groups A. We present the results Table 2. For all values of there exists plans in the ensemble that admit c-deviating groups in A and thus are identified locally fair by the ensemble-based algorithm. Clearly, a larger value implies more plans identified as locally fair. With 1/2, very few (but non-zero number of) plans identified as fair in four of the seven states. Every plan the MA ensemble is identified as fair with all districts won by one party. Hence, omit MA from all subsequent experiments.
In Figures la and Ic, we present examples fair plans (with no 0.5-deviating groups) in NC and respectively, while in Figures 1 and 1d, we present "unfair" plans with many 0.5-deviating groups. We show visualizations for other states Appendix
We note that large fraction of plans are locally fair in some states (WI), while others have many deviating groups, even for large setting of (MI). To understand where deviating groups are located, in Figure 2, we plot a heat-map of the precincts, counting the number of 1/2-deviating groups (of either color) that contain that precinct, with yellow representing large counts and purple representing low counts. In every state except MD." we observe that precincts with highest counts are located either an urban area in proximity of one. This phenomenon consistent with the perceived correlation between voter distribution and type of residence [8, 42). In states with multiple dense urban areas (e.g., NC), there is sufficient flexibility the redistricting process "crack" a cighly-concentrated
'These are chosen to represent spectrum from states whose elections typically competitive (e.g., NC and WI) to states whose elections typically lopsided (e.g.. MA and TX). NNote that ReCom generates plans without taking into account electoral data. We discuss MD in more detail in Appendix E.

---

(a) MD
(b) MI
(c) NC
(d) PA
(c) TX
(f) WI
Figure 2: Precinets shaded in lighter color are contained in more deviating groups.
urban demographic into multiple districts. In this case, the urban area may form deviating group resulting in high numbers of unfair plans.
We note that visualizations in particular, the deviating groups in unfair plans, as well as the heat-map of likelihood of unhappiness of a precinct make the local fairness concept explainable.
(a) Seat shares as percent of districts with blue majority.
001100 cumppia distts
80%
40%
20%
MD-fai
ME-who
Ni-hir
Misandle
NC
NC-wheee
Rieeal
AM-tir
Sh.ehole
75/mm
TX-der
Trinhale
Wi-fiir
(b) Percentage of districts being competitive (having less than 53.5% voters majority).
0.15
0.10
0.05
MD-ee NE-whele M-rnal
Ni-ti
NC-er
NCwhhll
Rieeal
FA-ar
TXmma
TXider
Trinhele
W-mel
WHarr
Whatolle
(c) Minimurn Polsby-Popper score of districts in plan.
Figure 3: Distribution of fairness and compactness metrics among subsets of generated plans
4.3 Compatibility with Extant Fairness and Compactness Notions
The ensemble-base based auditing approach can be viewed a pruning method that identifies subset of plans as locally fair. We now ask: how do locally fair plans perform on extant global fairness and compactness criteria compared to average plans in the ensemble? Towards this end, for = 1/2, rank the plans in the ensemble by the unfairness score (II. We compare properties of the top 5% plans in the ranking (which most locally fair) against the entire ensemble, well recent enacted congressional redistricting plan.
Seat share outcomes. For each plan, compute Blue%, the percentage of seat shares claimed by the Democratic candidate. The resulting distribution is shown in Figure 3a. The seat share distributions of the top 5% locally fair plans comparable to the entire ensemble, sometimes achieving lower variance.
Number of competitive districts. The Princeton Gerrymandering Project [4] defines a district as competitive the majority color is at most 53.5% the total votes. Following this definition, in Figure 3b, we compare the percent of competitive districts in plan. The locally fair plans produce slightly fewer competitive districts: since larger majorities reduce the number of unhappy voters, finding deviating group becomes harder. However, there exist fair plans that produce the median
'If more than the 5% of the plans are locally fair, we take an arbitrary subset of the locally fair plans to serve the top 5%.

---

percentage of competitive districts in the ensemble in all but one state, and they are comparable with or better than the enacted plan in all states. We present results using different competitiveness metric in Appendix C.
Minimum compactness. Another measure of quality of districting plans is compactness non- compact district not only makes less geographic sense, but is also more likely to have been gerry- mandered to favor one party over another. Two commonly used metries to evaluate the compactness in redistricting plans are the average and minimum Polsby-Popper scores [34] of the districts in the plan [4]: For district D E II, the Polsby-Popper score is defined as 4 AT PDD),, where A(D) and P(D) are the area and the perimeter of the planar region D, respectively; a higher value implies a more compact district. In Figure 3c, we show that the minimum compactness of the locally fair plans remains comparable to that of the entire ensemble. We present results on the average Polsby-Poppe score in Appendix C.
Taken together, our results show that local fairness is compatible with fair seat share and compactness, while sacrificing only a small amount on number of competitive districts.
4.4 Actual Plans and Additional Results
We also compute the local fairness of plans actually enacted for previous elections. As it is relatively easy to find a locally fair plan in WI. its actual plan is indeed locally fair, while the actual plans for all other states are not locally fair. Using the unf ranks, the enacted plan falls in the 55th percentile (fairer than 45% of the plans) in MD, 73th percentile in MI, 84th percentile in NC, 29th percentile in PA, and 22nd percentile in TX. While the MI and NC plans are (somewhat surprisingly) above average in local fairness, they have very few (or no) competitive districts. In general, enacted plans that achieve above average local fairness compared to the ensemble (MD, MI, and NC) have fewer competitive districts, and enacted plans with more competitive districts perform below average in local fairnes.. On the other hand, our results demonstrate that it is possible to find locally fair plans with a comparable (to the ensemble) amount of districts remaining competitive.
In Appendix D, we show that the locally fair notion is also robust to voting patterns in the sense that there is large overlap between fair plans identified by auditing the ensemble using the voter data from the 2012 and the 2016 presidential elections for the states of NC, PA, and TX.
5 Conclusions
In summary, in contrast to extant global notions of fairness in redistricting such as seat distribution or district competitiveness, the notion of local fairness is an explainable notion that mitigates justified complaints of populations in compact geographic regions. Our experiments show that local fairness is not only possible to achieve in practice, but choosing locally fair plans also does not come at the expense of other global fairness properties.
Several open questions arise from our work. In terms of algorithm design, it is an open question of whether there is an approximation algorithm for either the LF AUDITING L.PP GENERATION problem, and whether such an algorithm could take into account compactness. It would also be interesting to extend our methods to capture additional real-world criteria used in redistricting, such as penalty for splitting up counties, or a requirement for a majority-minority district. In particular, can fair plans be locally modified so that they remain fair and such real-world criteria are satisfied?
Finally, our exploration of robustness of local faimess to voter turnout is preliminary, since it compares the outcomes between two election data in one state. It would be interesting to extend our work to stochastic setting, where each individual in the population has a "likely voter" score (or probability to vote), and we need high confidence in the non-existence of c-deviating group.
Acknowledgments and Disclosure of Funding
This work is supported by NSF grants
IIS- 118-181, CCF-2007556, and CCF-2223870.
Note that all experiments use the 2016 presidential election data, while the plans in use are mostly drawn in 2011 1, except the NC one that is drawn in 2019.
10

---

References
http://aaaaaaaa//////////aaa//a/ 1964. [2] Cooper v. Harris. https://suprrme.
[1] Reynolds v. Sims.
2017.
[3] GEO metric: A metric to detect gemymandering which uses both Geography and Election Outcomes. https://wwy http://wwwwttteeeeeeeeee thee-geometriccoomm com/,
[4] Princeton gerrymandering project. attps://gerrymmanee: http://maaneer....neeeeeeee wrwnceton..eeeeeee.e..........oe edu/, 2022.
[5] K. Agarwal, S. Ko, K. Munagala, and E. Taylor. Locally fair partitioning. In AAAI, pages
4752-4759, 2022.
[6] M. Altman and M. P. McDonald. BARD: Better automated redistricting. Journal of Statistical Software, 42:1 12:1-28, 2011.
[7] A. Becker and Solomon. Redistricting algorithms. In M. Duchin and O. Walch, editors, Political Geometry: Rethinking Redistricting in the US with Math, Law, and Everything In Between, chapter 16, pages 303-340. Springer, 2022.
[8] A. Borodin, O. Lev, N. Shah, and T. Strangway. Big city vs. the great outdoors: voter distribution and how it affects gerrymandering. In IJCAI, pages 98-104, 2018.
[9] M. Campisi, T. Ratliff, S. Somersille, and E. Veomett. Geography and election outcome metric: An introduction. Election Law Journal: Rules, Politics, and Policy, 2022.
[10] J. Chen, J. Rodden, et al. Unintentional genymandering: Political geography and electoral bias in legislatures. Quarterly Journal of Political Science, 8(3):239-266 2013.
[11] M. ing
with redistrict- tufts- jufts-research. siab-aidssttttes--eeeeeeeseseee- -aw.--aidd--satttssii---------e- wedtttrrddsttticccnnn--eeee
Chen.
Tufts
research
lab aids
states
process.
sttps://biee https://buftsdaaly> com wwwp///www////////////o/ 2021///0022/////////////
2021.
[12] C. Cirincione, T. A. Darling, and T. G. O'Rourke. Assessing South Carolina's 1990s congres- sional districting. Political Geography, 19(2):19-2211 2000.
[13] V. Cohen- P. N. Klein, D. Marx, A. Wheeler, and C. Wolfram. On the computational tractability of a geographic clustering problem arising in redistricting. In FORC, pages 3:1-3:18, 2021.
[14] D. DeFord, M. Duchin, and J. Solomon. A computational approach to measuring vote elasticity and competitiveness. Statistics and Public Policy, 7(1):69-86, 86, 2020.
[15] D. DeFord, M. Duchin, and J. Solomon. Recombination: A family of markov chains for redistricting. Harvard Data Science Review, 3(1), 3 2021. https://hdsr mitppress .iit edu/pub/1ds8pp 1dsttxx.
[16] M. Duchin and E. Tenner. Discrete geometry for electoral geography. arXiv preprint arXiv: /808. 1808.05000, 2018.
[17] S. A. Esmacili, H. Grape, and B. Brubach. Centralized fairness for redistricting, arXiv preprint arXiv:2203.000 00872, 2022.
[18] B. Fifield, M. Higgins, K. Imai, and A. Tarr. Automated redistricting simulation using Markov chain Monte Carlo. Journal of Computational and Graphical Statistics, 29(4):715-728, 2020,
[19] N. Garg, W. Gurnee, D. Rothschild, and D. B. Shmoys. Combatting gerrymandering with social choice: The design of multi-member districts. In EC, pages 560-561, 2022.
[20] P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann. Voronoi diagrams
planar graphs, and computing the diameter in deterministic Ö(n5/3) time. SIAM Journal on Computing, 50(2):509-554
2021.
[21] W. Gurnee and D. B. Shmoys. Fairmandering: column generation heuristic for faimesss- optimized political districting. In SIAM ACDA, pages 88 99,99991 2021.
[22] G. Herschlag, H. S. Kang, J. Luo, C. V. Graves, S. Bangia, R. Ravier, and J. C. Mattingly. Quantifying gerrymandering in North Carolina. Statistics and Public Policy, 711:330-38, 2020.
[23] G. Herschlag, R. Ravier, and C. Mattingly. Evaluating partisan gerrymandering in Wisconsin. arXiv preprint arXiv: 709.079999999 2017.

---

[24] S. W. Hess, J. Weaver, H. Siegfeldt, J. Whelan, and P. Zitlau. Nonpartisan political redistricting by computer. Operations Research, 13(6))998-1006 1965.
[25] D. S. Hochbaum and A. Pathria. Node-optimal connected k-subgraphs. University of California, Berkeley, 1994.
[26] D. M. King, S. H. Jacobson, and E. C. Sewell. Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning. Mathematical Programming. 149(1):425-457, 2015.
[27] R. Kueng, Mixon, and Villar. Fair redistricting is hard, Theoretical Computer Science, 791:28-31 2019.
[28] H. A. Levin and S. A. Friedler. Automated congressional redistricting. ACM Journal of Experimental Algorithmics. 24())11.1:111.110222 2019.
[29] J. Levitt. All about redistricting. https://rediitriccing 11s edu/,
[30] J. Lin, C. Chen, M. Chmielewski, S. Zaman, and B. Fain. Auditing for gerrymandering by identifying disenfranchised individuals. In 2022 ACM FAceT, pages 1 115-11335 2022.
[31] Y. Liu, W. K. T. Cho, and S. Wang. PEAR: A massively parallel evolutionary computa-
tion approach for political redistricting optimization and analysis. Swarm and Evolutionary
Computation, 30:78-92. 2016.
[32] D. B. Magleby and D. B. Mosesson. A approach for developing neutral redistricting plans. Political Analysis, 1672):147-167, 2018.
[33] MGGG. MGGG states. bettps//gitthe com/mggg- 2022.
[34] D. D. Polsby and D. Popper. The third criterion: Compactness as procedural safeguard against partisan gerrymandering. Yale Law & Policy Review, 9:301, 1991.
[35] A. D. Procaccia and J. Tucker-Fole Foltz. Compact redistricting plans have many spanning trees. In ACM-SIAM SODA, pages 3754-3771, 2022.
[36] E. C. Reock. A note: Measuring compactness as a requirement of legislative apportionment. Midwest Journal of Political Science, 5(1):70-74, 1961.
[37] N. O. Stephanopoulos and E. M. McGhee. Partisan gerrymandering and the efficiency gap. University of Chicago Law Review, 82:831,
[38] W. K. Tam Cho and Y. Y. Liu. Toward a talismanic redistricting tool: A computational method for identifying extreme redistricting plans. Election Law Journal, 15(4):351-366 2016.
[39] W. Vickrey. On the prevention of gerrymandering. Political Science Quarterly, 76(1): 76(1):105-110 1961.
[40] S. S.-H. Wang. Three tests for practical evaluation of partisan gerrymandering. Stanford Law Review, 68:126: 12:3, 2016.
[41] G. S. Warrington. Quantifying gerrymandering using the vote distribution. Election Law Journal, 17(1):39-53 57,399572200 2018.
[42] A. Wheeler and P. N. Klein. The impact of highly compact algorithmic redistricting on the mural-versus-urban balance. In SIGSPATIALJIIS, pages 397-400, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A] Datasets are publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zwtojYu-1W5", "reviewer": "Reviewer_LUyA", "summary": "The paper introduces a new measure for fairness in redistricting. Specifically, the paper introduces the notion of local fairness where a redistricting plan is considered to be locally fair if no feasible district exists that can includes at least 1/2 unhappy voters in the given redistricting plan (where unhappy means in the minority party). The problem of auditing and generating locally fair plans is shown to NP-complete and heuristics based on ensemble (sampling) approaches and dynamic programming are shown.  ", "questions": "My main points to authors are above. Please see points under Weaknesses in the above section. In particular, I think points 3 and 4 are the most important. ", "limitations": "Authors have adequately addressed the limitations and potential negative societal impact. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$\\textbf{Strengths}$:\n\n-I think the notion of local fairness is elegant and as the authors point out has the advantage of highlighting the individuals disadvantaged by the drawing of a given plan. \n\n\n\n$\\textbf{Weaknesses}$:\n\n1-The paper does not include many mathematical guarantees, but this is understandable given that the problem is difficult and generally forbidding to give guarantees to without significant assumptions. \n\n2-This is not very significant but it seems that compactness is de-emphasized as a requirement for a redistricting plan. Although it seems to be universal in the literature (acknowledging that there isn't an agreed upon definition). I would add compactness as a third point along with the connectedness and population balance in lines (149-153). \n\n3-Lines (368-373): the result on NC is a bit odd. One would certainly like local fairness to detected gerrymandering in a highly partisan plan. \n\n4-Following point 3, given a state is it possible that a locally fair redistricting does not even exist? More generally while the notion is interesting, the paper did not elaborate on where we would expect local fairness to help, etc. Perhaps even toy examples could help here. \n\n5-This is a very recent paper so it is acceptable that the authors don't point it out. But it introduces a fairness measure that is similar:\nhttps://dl.acm.org/doi/abs/10.1145/3531146.3533174  \n\n$\\textbf{Minor Issue}$:\n\nIn line (181), I think it is the case that unf(\\Pi)=0 if and only \\Pi is locally fair which is just more accurate than. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K-0AK9M5pVl", "reviewer": "Reviewer_hdtK", "summary": "The paper introduces a method of creating geographical voting districts composed of smaller precincts which are \"locally fair\". The focus is on two specific problems: determining whether a given redistricting plan is locally fair, and generating a redistricting plan that is locally fair. Both of these problems are shown to be NP-complete and a polynomial time dynamic programming algorithm is described that determines whether a plan is fair. They use this to solve the problem of generating a fair plan by generating many potential plans and ranking them all according to their fairness. Experiments on data from 4 US states show that this method can identify plans with local fairness. The authors also show empirically that they are able to find locally fair plans which meet other fairness and compactness criteria.", "questions": "Line 162 says a happy voter is one who agrees with the colour of their district. Definition 2 refers to a red district containing unhappy red voters which would seem to be impossible. Should line 162 say \"precinct\" rather than \"district\"? If not, could you attempt to explain this concept more clearly?\n\nWhy is WI not discussed in 4.4?\n\nThe checklist at the end of your paper says \"N/A\" in reference to whether you discussed potential negative social impacts of your work. I have trouble understanding this response. Does this mean you cannot imagine any potential negative impacts from a districting process that generate fair and unfair districts?", "limitations": "The authors have not done this. While quite a few readers are likely to be familiar with common ideas about the potential negative impacts of this work some discussion about how this specific process could be misused, either intentionally or not, is still rather important.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Generally, the paper is interesting and well written. The problem is well studied; this work provides a strong follow-up to a very related model (ref 6) and addresses some new dimensions of the local fairness issue. The paper is relevant to an ongoing process within the United States which does benefit from new research in this area. I can imagine the included empirical analysis making the work more approachable to non-technical audiences that might bring the results into practice.\n\nStrengths\n- the paper is logically structured and the results are discussed in appropriate detail at various locations (e.g. intro does a good job of highlighting the main points, reasonable choices about what is in appendix vs main paper)\n- the problem of redistricting remains a real issue in America and a great deal of people may benefit from new developments in the field\n- the concept of local fairness seems a reasonable one to include alongside other fairness concepts\n- I found the general idea relatively understandable which is important for practitioners\n\nWeaknesses/ways to improve\n- I think your definition of local fairness may have a small but significant typo; or I misunderstand. (see Questions, below)\n- the \"empirical evidence\" on lines 199/200 could be more explicitly connected to something in Section 4\nFigure 3(a) - unclear what is good here. Is the claim that the minority group should get 0% of seat share rather than an amount proportional to their size?\n3(c) - the large difference between NC/WI and TX/PA doesn't seem to be explained (is it to do with urban/rural divide?)\n- more discussion on how this could be misused is needed", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Gr9rUq8LGVr", "reviewer": "Reviewer_oFwU", "summary": "This paper studies local fairness for redistricting plans. The authors give 2 algorithms for auditing plans for local fairness. Both algorithms are approximate and make different types of errors. In experiments in the main text, the authors use the first (simpler) method to audit real and sampled redistricting plans for real data. They show that in many cases, there exist many locally-fair plans for a number of states. They also show that locally-fair plans tend to satisfy global notions of fairness.  Other statistics of the locally fair plans–like partisanship, compactness, and minority seat shares–-are also reported.", "questions": "- Footnote 2 was confusing. Is the issue one of double counting? In the construction where we care about unhappy voters as opposed to population is there still double counting? \n- Are there times when plan generation is less scalable than the DP? Are there any instances in which you’d recommend usage of the DP?\n- Why were the particular values of c in Table 1 chosen? Is 50% a meaningful choice of c? What other values should be considered?\n- In the seat shares result, why is a higher percentage of seat shares more desirable than a share that reflects the percentage of the minority? Why is lower variance an important criteria here?\n- For the partisanship result: is it a good thing for partisanship of a plan to decrease with respect to real plans? This confuses me since the text seems to say that the fair plans increase partisanship (over the ensemble), which leads to fewer unhappy voters (a good thing). \n- Related to the question of partisanship: Are all locally-fair plans for the same state equivalently good/bad? In more detail, is it possible to have two distinct, locally-fair plans that would yield different numbers of red/blue elected officials? If so, how should one choose between two locally fair plans?\n- Are plans used in practice locally fair?\n", "limitations": "- No ethical considerations addressed, but the problem area have high potential societal impact.\n- One question which is not directly addressed is whether their notion of local fairness should be a high priority consideration in real-world redistricting.\n- The algorithms presented are highly specialized. I’m not sure they are applicable for any other problem areas.\n- There is no discussion about selection among many locally-fair plans. Such selections could have significant ramifications.\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:**  This work combines and extends a handful of pieces from previous work rather than making a completely original contribution.\n- This work borrows a notion of local fairness from recent work [6].  However that work [6] the authors focus on a 1-dimensional problem setting whereas in this work, the authors focus on a 2-dimensional (planar graph) setting.\n- The generate-and-test algorithm proposed in this work relies on the ReCom [15] and is otherwise simple. In the proposed algorithm, first generate a number of redistricting plans using ReCom; then, for each district in each plan generated by ReCom, test whether that district is a c-deviating group in each other plan generated by ReCom.\n- The dynamic program proposed is somewhat more complex, but seems to be neither practical (i.e., it has a very high runtime) nor useful in that it does not lead to improvements over the simpler heuristic proposed.\n- The contributions are clear and as I can tell, relevant work has been cited.\n\n**Clarity:** \n- The paper is very well-written. Most of the ideas are explained clearly and I believe that it would be possible to reimplement the experiments form the description in the text (given access to the ReCom algorithm).\n- I found the definition of a deviating group to be confusing and required many re-reads. I would suggest including a Figure that shows: a) a small graph or portion of some graph, b) the districts according to $\\Pi$ and c) an alternative district–not in $\\Pi$--that shows a deviating group. Instead of (or in addition to) a visualization, it would be helpful to include a definition in words as well, for example: “In other words, a plan is unfair if a new feasible district, $W$, can be constructed such that a c-fraction of the voters in $W$ are unhappy under $\\Pi$ but would be happy in $W$.\n- 3.2.1 is complicated and at the end of the subsection, it seems like the approach is unnecessary. As written in 1.2 (contributions), the DP seems like it will be one of your proposed approaches. I would suggest a different framing where the DP is used to provide further evidence that the more efficient and simpler method doesn’t conclude that certain plans are fair when deviating groups can be found by a more costly and complicated method.\n- The word “properties” appears twice in a row in the last sentence of the first paragraph of the conclusion.\n\n**Quality:** this submission is of relatively high quality.\n- In the experiments, the authors goal is to determine whether plans that are locally fair are achievable, and whether these plans are compatible with notions of global fairness. By and large, both of these questions are answered affirmatively in a convincing manner.\n- At the same time, in my opinion, a discussion of whether local-fairness for redistricting is a good thing (and why) is missing and necessary. While reading, I lean towards thinking that local fairness is good: more people are “happy” (as the paper refers to them) and global fairness is respected. But looking at the results with respect to increased/decreased partisanship and seat shares, I found myself wondering if locally-fair plans are what we want in practice or not. More specific questions related to this thought are in the Questions for the Authors section of this review.\n- The theoretical results in this work are proofs of NP-completeness for the problems studied. No approximation results are proved with respect to the proposed algorithms. In my opinion, such proofs would add to the paper but are unnecessary since the application considered is very specific (i.e., redistricting in the United States) and the experimentation is performed with the relevant data.  It’s unclear whether the proposed algorithms could potentially be used in many other contexts. If so, having approximation guarantees becomes more important (so that practitioners would have some idea of how the algorithms are likely to perform).\n\n**Significance:** the results are important, and hold immediate real-world value, however they are limited to a specific problem area.\n- This work follows a small, yet well-established area of work on fair redistricting and gerrymandering.  If accepted, this work would likely be built upon.\n- Unlike previous work that focuses on global notions of fairness in districting plans, this work focuses on local fairness, which is conceptually different and requires distinct technical tools and algorithms. This paper gives a new method for applying ideas of locally fair partitioning to 2-dimensional (planar graph) redistricting problems.\n- Experimental results are new and constitute a new and interesting way at auditing redistricting plans for fairness.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6rmGlTgOETf", "reviewer": "Reviewer_mpC7", "summary": "This work defines a new notion of “local fairness” for redistricting. The main idea is that a plan is unfair if there are unhappy voters who lose in their current district, but could have been grouped together in an alternative district to elect a candidate from their party.\n\nDrawing locally fair maps and auditing for local fairness are shown to be NP-hard problems. The authors thus offer two heuristics for the auditing problem and evaluate them empirically.", "questions": "I have listed many questions and will not be offended if the authors choose to address only those they believe are most important or where I have made some mistake.\n\n\n1) Regarding the discussion of the dynamic programming method in Section 3.2.2, why does a deviating group need to be compact? First, compactness of deviating groups is not in the definition provided earlier in the paper. Second, I would argue that the deviating group should not need to be compact. Wouldn’t it be easier to gerrymander if non-compact deviating groups are not considered in defining local fairness? Put another way, suppose there exists a plan which is locally fair and satisfies the standard criteria including compactness. Wouldn’t we want to say that plan is more fair than another plan which has a non-compact deviating group?\n\n\n2) This fairness measure appears vulnerable to the gerrymandering practice of packing and may even encourage packing. Packing a district with mostly voters of the same party is one way to maximize the number of happy voters who cannot be part of a deviating group. This is mentioned briefly in Section 4.3, but can you speak to this more? In particular, I worry that it could be a lopsided fairness metric that favors rural parties packing urban centers. Could this be remedied by letting voters in packed districts be fractionally unhappy (e.g., a voter in a 75% partisan district is 1/3 unhappy)?\n\n\n3) Does this fairness metric risk invalidating a “fair” plan that voters prefer? There are a few plans that have been held up as fair such as the NC judges map considered in [22] or the 2018 PA map drawn by the PA supreme court? Have you checked whether these or similar maps are locally fair?\n\n\n4) Lines 127-129 state that locally fair plans “have comparable seat share outcomes” to those with many deviating groups. However, shouldn’t the fair plans have different seat share outcomes from those which represent partisan gerrymanders? Further, you also note that locally fair plans in your ensemble have similar compactness to those with deviating groups, but couldn’t this be an artifact of ReCom producing similarly compact maps as noted in [34]?\n\n\n5) In the worst case, there are maps that do not have any locally fair plan. How do we compare maps in this case considering that is intractable to compute how “almost fair” a map is and two similarly “almost fair” maps might make different groups unhappy?\n\n\n6) I’m aware of at least two recent papers which have some similarities to this one, although they are clearly different enough to co-exist. Can the authors can say more to place their work in context with them? I believe the first paper would not have been available to the authors at the time of submission. However, it is especially relevant because the metric is similar and also involves comparing against an ensemble.\n\nLin, Jerry, Carolyn Chen, Marc Chmielewski, Samia Zaman, and Brandon Fain. \"Auditing for Gerrymandering by Identifying Disenfranchised Individuals.\" In 2022 ACM Conference on Fairness, Accountability, and Transparency\n\nCampisi, Marion, Thomas Ratliff, Stephanie Somersille, and Ellen Veomett. \"The Geography and Election Outcome (GEO) Metric: An Introduction.\" arXiv preprint \n\n\n7) On lines 338-339, it says, “We compare properties of the top 5% plans in the ranking (which are most locally fair) against the entire ensemble.” How is this 5% chosen for states in which more than 5% of maps have no deviating groups?\n\n\n\nTypos:\nLine 52: accessing -> assessing\nLine 379: “properties properties”", "limitations": "I have noted several limitations above which are discussed somewhat to the paper’s credit, but could be discussed more. The only potential negative societal impact is raised in my question about this method being used to discredit “fair” or “good” maps.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper addresses and makes progress on a highly relevant and timely problem in society which is still open despite being well-studied. \n\nThe biggest contribution/strength is the new idea of how to measure fairness in redistricting. In my view, it’s a good idea, even though there are some flaws/weakness that I believe could make it unpractical in its current form. There is merit in publishing good ideas that may inspire future work as well as informative debate/criticism. So while I have listed many weaknesses and questions below, one could argue that it is worthwhile to publish the paper for its main idea and let the weaknesses be addressed in future work.\n\nI loved the analysis presented in Figure 2 and felt that was an undersold strength of the paper. These results offer useful insights into political geography in general and the urban/rural divide specifically. It could be of independent interest to areas such as the comparison between different electoral systems using districts. To me, this motivates the local fairness notion almost as much as the idea of using it to audit proposed plans.\n\nThe paper is written and presented clearly.\n\n\n\nWeaknesses:\n\nThe main weaknesses were potential flaws in the fairness metric, some questionable claims, lack of theoretical analysis of the auditing methods, and slightly limited experiments. Overall, I feel that the paper has some great ideas, but isn’t ready for publication. \n\n\nI have several concerns about the fairness metric which are mainly listed in the questions section of this review. \n\n\nI found the claims and analysis of the two auditing methods to be flawed as noted below. However, I hope the authors can correct me if I’ve misunderstood something. Overall, I would have liked a better theoretical analysis of the two auditing heuristics.\n\nFor the ensemble-based auditing method, there are unsubstantiated claims that the method is “likely” to find a deviating group if one exists or that it “provides high confidence”. However, there is no theoretical argument supporting these claims. On the contrary, it seems possible to produce a plan with a deviating group that the ensemble method is unlikely to find especially if non-compact deviating groups are allowed.\n\nFor the dynamic programming in trees audit, the analysis is incomplete. There is a description of how to solve the problem optimally in a tree, but no analysis of what solving the problem optimally in many random spanning trees can tell us about a given plan. It is possible that random spanning trees are very likely or very unlikely to contain deviating groups in their subtrees, but this crucial detail appears to be left out. Then, the dynamic programming approach is used to evaluate the ensemble-based approach, but it’s not clear to me that the dynamic programming approach is more accurate.\n\n\nThe experiments were not a major weakness, but adding some subset of the following would strengthen the paper.\n\nMore states. In the four states considered, only 2.8% of TX plans were fair at c = 0.5 and that’s using a fairness heuristic with an unknown false positive rate (positive being fair). This raises questions of whether some states do not admit locally fair plans.\n\nMore elections. Many of the ensemble papers use data from senate and gubernatorial elections in different years in addition to presidential election data.\n\nA better competitiveness metric. Average partisanship is not a good measure of competitiveness because it doesn’t tell us how many districts in a plan are meaningfully competitive. There are a number of competitiveness measures in the literature. A simple one to test here would be to pick a threshold (e.g. 55% or 53%) and count the number of districts in a plan with partisanship below\n\nA study using small grid graphs for which all possible districts can be enumerated. This could be used to evaluate the auditing heuristics and to gauge the frequency of maps that do not admit any locally fair plan.\n\n\nThis is a minor weakness, but many details are left to the appendix. For example, it would be good to include some sketch or intuition for the NP-completeness claims even just saying which NP-complete problem is used for the reduction. Many aspects of the dynamic programming approach are also in the appendix. While I enjoyed the introduction, I suggest the authors shorten it to make room for more content later in the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept