All Politics is Local Redistricting via Local Fairness Shao-Heng KoErin TaylorPankaj K. Agarwal Kamesh Munagala Department of Computer Science
2025-04-30
0
0
3.47MB
20 页
10玖币
侵权投诉
All Politics is Local: Redistricting via Local Fairness∗
Shao-Heng Ko†Erin Taylor†Pankaj K. Agarwal Kamesh Munagala
Department of Computer Science
Duke University
Durham, North Carolina 27708 USA
Email: {sk684,ect15,pankaj,kamesh}@cs.duke.edu
November 22, 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.
1 Introduction
Redistricting in the United States is the process of partitioning a state into districts, each of which elects one
representative to the Congress, for the most part, via simple majority voting. As of April 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].
There is ongoing debate around what a “desirable” redistricting plan should be. It is commonly agreed that
“desirable” plans should, at 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 as software
tools [4,29] on auditing a given redistricting plan against various fairness concepts. Some of these concepts
have since been adopted in Wisconsin’s and Michigan’s 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 we 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 in [5] 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
∗This work is supported by NSF grants CCF-2113798, IIS-1814493, CCF-2007556, and CCF-2223870.
†Equal contributions.
1
arXiv:2210.11643v2 [cs.GT] 19 Nov 2022
manipulated to favor a 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 an 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 a 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, a 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 a 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, as 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 a 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 a redistricting plan, can we 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 a 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 a 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-annealing 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, as well as unexpected
outcomes such as “natural gerrymandering” [8,19], i.e., 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 on generating a large ensemble of districting plans, with the hope of some
of these plans being fair. These methods include Flood Fill [12,32], 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 fairness properties. For instance, it is shown in [35]
that the widely used ReCom MCMC method [15] provably biases towards compact plans. We provide a
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.
2
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 is a 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 a recent line of work that
attempts to eliminate gerrymandering by completely revamping the winner-takes-all, single-member district
mechanism into a multiwinner election [19].
1.2 Our Contribution
In this paper, we take the standard view of redistricting as partitioning a planar graph on precincts into
population-balanced, contiguous, and (in a heuristic sense) compact regions. We naturally extend the local
fairness concept proposed in [5] to this task.
We first focus on the question of auditing a given plan for local fairness, that is, the non-existence of a
population-balanced 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-based methods in a novel way: we assume the districts in the ensemble are the
only districts to which voters can deviate, and given a plan to be 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 a 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 is 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 a justified complaint.
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
unfairness 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 a small amount of competitiveness. Thus local fairness can be used as an additional fairness
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.
Taken together, our results demonstrate local fairness as an effective pruning criterion for candidate
redistricting plans while sacrificing little in other desired properties. We also note that in 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.
3
2 Model and Preliminaries
In keeping with recent literature [13,15,16,21], the input to the redistricting problem is a planar connected
graph
G
= (
V, E
)where each vertex
v∈V
represents an indivisible geographic unit (a precinct or a census
block),
1
and an edge is placed between two vertices if they are geographically adjacent. Going forward, we
refer to each v∈Vas a precinct and Gas the precinct graph.
Redistricting Plans.
For each precinct
v∈V
, let
ρ
(
v
)
>
0denote its population and let
τ
(
v
)
∈
[0
, ρ
(
v
)]
denote the number of voters in
v
.
2
. We let
γ
(
v
)
∈
[0
,
1] and
β
(
v
) = 1
−γ
(
v
)denote the fraction of
τ
(
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⊆V
, set
ρ
(
W
)
:
=
Pv∈Wρ
(
v
),
τ
(
W
)
:
=
Pv∈Wτ
(
v
),
γ(W):=Pv∈W(γ(v)·τ(v))
τ(W), and β(W):= 1 −γ(W).
Definition 1
(
k
-redistricting plan)
.
A
k
-redistricting plan of
G
= (
V, E
)is a partition of
V
into
k
pairwise-
disjoint subsets
D1, D2, . . . , Dk⊆V
, called districts. Each district assumes the color of the majority of its
voters. For a redistricting plan Π, let BΠ(resp. RΠ) denote the set of precincts in blue (resp. red) districts
in Π.
In the following, we fix an error parameter
ε >
0, and the desired number of partitions
k
. Note that the
average population per district is
ρ(V)
k
. We say a district
D⊆V
is
ε
-feasible if: (1)
D
induces a connected
subgraph, and (2) the population of
D
is at most
ε
away from average, i.e.,(1
−ε
)
·ρ(V)
k≤ρ
(
D
)
≤
(1+
ε
)
·ρ(V)
k
.
A redistricting plan Πis ε-feasible if each district Di∈Πis ε-feasible.
We note that this definition of an
ε
-feasible 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
k
will be fixed throughout, we drop the prefixes and refer
to k-redistritcting plans and ε-feasible districts as redistricting plans and feasible districts, respectively.
Local Fairness.
We extend the notion of local fairness proposed by [5] to the graph-based redistricting
problem. We say that a feasible district
W⊆V
is red-majority (red in short) if
γ
(
W
)
≥β
(
W
), and
blue-majority (blue) otherwise. We call this majority color as the color of
W
. Given a redistricting plan Π,
any voter whose color agrees with the color of its assigned district in Πis deemed happy with respect to Π,
and the remaining voters are unhappy.
Definition 2
(
c
-locally fair)
.
Given a feasible redistricting plan Πof
G
and a constant
c∈
[1
/
2
,
1], a feasible
district
W⊆V
is a red
c
-deviating group with respect to Πif
W
is red and at least a
c
-fraction of its voters
are unhappy red voters in Π, or formally,
Pv∈W∩BΠγ
(
v
)
·τ
(
v
)
> c ·τ
(
W
)
.
Ablue
c
-deviating group is defined
analogously. We call a feasible redistricting plan Πof
G c
-locally fair if there are no red or blue
c
-deviating
groups with respect to Π.
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
c
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 a feasible redistricting plan Πand a parameter
c∈
[1
/
2
,
1], decide whether
Πis c-locally fair.
LFP Generation problem.
Given a precinct graph
G
and parameters
ε, k
and
c
, compute a feasible
redistricting plan Πof Gsuch that Πis c-locally fair, or report that none exists.
For a redistricting plan Πthat is not locally fair, we quantify its degree of unfairness as follows. Consider
all deviating groups of Π, and define the unfairness score of Πas the fraction of all voters that are unhappy
in some deviating group. Formally, let
W∗
B(Π) :=RΠ∩[W⊆V|Wis a blue deviating group of Π
1Typically, precincts are not split by redistricting plans [15].
2
We assume that we know the exact number of people who cast a vote in each precinct, along with which candidate they voted
for, such as is available for historical elections
4
摘要：
展开>>
收起<<
AllPoliticsisLocal:RedistrictingviaLocalFairness*Shao-HengKoErinTaylorPankajK.AgarwalKameshMunagalaDepartmentofComputerScienceDukeUniversityDurham,NorthCarolina27708USAEmail:{sk684,ect15,pankaj,kamesh}@cs.duke.eduNovember22,2022AbstractInthispaper,weproposetousetheconceptoflocalfairnessforauditing...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
【词汇变形总汇】2025高考词汇变形总汇 - 教师版VIP免费
2024-12-06 3 -
【超简37页】新课标高考英语考纲3500词汇VIP免费
2024-12-06 4 -
《高考英语3500词详解》（WORD版）VIP免费
2024-12-06 18 -
《高考英语3500词详解》VIP免费
2024-12-06 14 -
高中英语-[教师版]80天通关高考3500词汇VIP免费
2024-12-06 16 -
高中人教选修7课文逐句翻译VIP免费
2024-12-06 8 -
高中人教选修7课文原文及翻译VIP免费
2024-12-06 19 -
高中人教必修4课文逐句翻译VIP免费
2024-12-06 8 -
高中人教必修4课文原文及翻译VIP免费
2024-12-06 22 -
高考英语核心高频688词汇VIP免费
2024-12-06 11
分类：图书资源
价格：10玖币
属性：20 页
大小：3.47MB
格式：PDF
时间：2025-04-30
作者详情
相关内容
-
主题班会：责任与我同行(1)
分类：中学教育
时间：2025-06-01
标签：无
格式：PPT
价格：10 玖币
-
主题班会：责任——我们共同的需要ppt
分类：中学教育
时间：2025-06-01
标签：无
格式：PPT
价格：10 玖币
-
主题班会：预防爱滋病
分类：中学教育
时间：2025-06-01
标签：无
格式：PPT
价格：10 玖币
-
主题班会：远离毒品，珍爱生命ppt1
分类：中学教育
时间：2025-06-01
标签：无
格式：PPT
价格：10 玖币
-
韶关市2024届高三综合测试（一）英语答案
分类：中学教育
时间：2025-06-05
标签：无
格式：PDF
价格：10 玖币
渝公网安备50010702506394
