没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
GETTING THE VOTES TO COUNT: A GENETIC ALGORITHM
FOR NON-PARTISAN LEGISLATIVE DISTRICTING
Abstract.
For decades, district gerrymandering has given incumbents an unfair advan-
tage over their opponents, resulting in artificially high reelection rates. This
gerrymandering has become so severe that Iowa [1] has implemented a non-
partisan district-drawing method, and other states are sure to follow. Such
efforts may have many different ob jectives in creating districts. In this paper
we describe a redistricting algorithm which is flexible enough to accommodate
a wide variety of district criteria. We use a genetic algorithm, wherein an arbi-
trary user-selected number of districts compete for population on a map of the
state region. By adjusting the probability formulae for district reassignment
events, we can tailor our algorithm to create districts satisfying a wide range of
criteria. This algorithm is then tested on the state of New York, by requiring
it to pro duce district shapes that maximize the interior regions of the districts
in prop ortion to their boundaries. The resulting district divisions produced by
the algorithm clearly exhibit this property.
After presenting the results of our tests, we will discuss the merits and defects
of our chosen algorithm, along with its possibility for extension.
Date: February 11, 2007.
1
Kyotaro Hemmi, Peter Mannisto, and Ting-You Wang
University of Washington
2007 Honorable Mention
数学中国提供
http://www.madio.net
Team 1035 2
Contents
1. Introduction 2
2. Specifications 3
2.1. Population Specifications 3
2.2. Geographic Simplicity 3
3. Our Method 4
3.1. Source for data 4
3.2. Other p ossibilities for district-drawing 6
4. Data 7
5. Evaluation of our Method 12
5.1. Defects 12
5.2. Merits 13
6. Appendix 1 - Probability factors 13
7. Appendix 2 - Other data 14
References 15
1. Introduction
Gerrymandering is one of the oldest and most successful methods of disenfran-
chisement available to Congress. This much-maligned practice is essential to main-
taining the 98% re-election rate currently enjoyed by incumbents
1
[5]. Obviously,
many people aren’t happy with the status quo, as it can render an individual’s
vote meaningless as his representation is determined not by popular sentiment, but
by the incumbents drawing up the districts. What is needed is a new method for
determining legislative districts, one out of the hands of incumbents.
What should an ideal district-drawing algorithm accomplish? This is certainly a
vexing p olitical question. Should it take the truly unbiased approach and ignore
any and all p olitical considerations? We can just randomly create districts, blind
to both political ambitions and political fairness. Others may feel that steps should
be taken to ensure that elected representatives fairly represent their constituents.
Should we set up the districts so that a 60% Republican state will likely have 60% of
its districts be majority Republican? Perhaps this just returns us to a different type
of gerrymandering, done for the cause of ‘fair representation’, but gerrymandering
nonetheless.
This dilemma can only be solved by political scientists, not mathematicians. How-
ever, a mathematician should be able to create a district-drawing algorithm which
can accomodate certain ‘preferences’ in drawing districts, whatever they may be.
It is then up to social scientists to ascertain what these preferences should be. Our
goal is to produce just such an algorithm. We will then test the algorithm by having
it select districts for New York that are ‘geographically simple’ in a specific sense
to be defined later.
1
Average re-election rate of House incumb ents over election cycles 2000, 2002, and 2004.
2
Team 1035 3
2. Specifications
We require our district-drawing algorithm to satisfy the following criteria:
2.1. Population Specifications.
In the 1962 decision of Baker v. Carr, the US Supreme Court asserted the abil-
ity to decide on the constitutionality of state district divisions [2]. Although the
Supreme Court has not specified the exact terms of what is acceptable, past rulings
have suggested the following: “congressional redistricting plans with overall range
percentage variances of up to .73 percent have been approved based upon identi-
fiable state objectives” [1]. Here, the overall range percentage variance is defined
by the maximum difference in population between any pair of districts, divided by
the ‘ideal’ district population (which is just the population of the state divided by
the number of districts). We would like to note, however, that a lower deviation
percentage of 0.69% has been rejected in the past [1]. Pending further legal clarifi-
cation, we set a range variance of less than or equal to 0.7 percent as our goal for
population range variance.
2.2. Geographic Simplicity.
We will require our districts to satisfy two criteria. The first requirement is ab-
solute: each district must be connected. We will later describe our method for
enforcing this. Our second requirement will b e to have each district contain as
many interior points as possible. Here, an interior point means a grid point which
does not neighbor a grid point of a different region on either the east, west, north,
or south. As with any notion of geometric simplicity, this one is motivated by
aesthetic reasons: intuitively, discretized versions of squares and circles contain a
large number of interior grid points.
The recognition that others may not agree with our particular definition of simplic-
ity is an important reason why we wish our algorithm to accommodate different
district division criteria easily.
Let us b e more specific about what a district-drawing algorithm should do. We will
be given a region (which represents the state map), along with a population density
function defined on the state. In our algorithm the region and density function will
be discretized, but a priori one thinks of them as approximately continuous. We
will discuss the validity of the discretization later.
In addition, the aforementioned so cial scientists may find other variables to be of
interest in drawing up districts. There are many ways in which such data can
be naturally presented. For example, we may wish to have our districts follow
county lines when possible. In this case, county lines should be included in our
state boundary map. On the other hand, information about political leanings is
naturally presented as a density function ρ
D
on the region (i.e., for each point x
on the state, ρ
D
(x)dA is the percentage of people living in differential area dA sur-
rounding x who are Demo crats, with analogous functions ρ
R
, ρ
I
for Republicans
and Independents). We will later show how these possibilities and others can be
3
剩余14页未读,继续阅读
资源评论
chenxs008
- 粉丝: 4
- 资源: 22
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功