李银杰小组第一次讨论论文.doc

Summary Gerrymandering, the practice of dividing political districts into winding and unfair geometries, has a deleterious effect on democratic accountability and participation. Incumbent politicians have an incentive to create districts to their advantage (California in 2000, Texas in 2003); so one proposed remedy for gerrymandering is to adopt an objective, possibly computerized, methodology for districting. We present two efficient algorithms for solving the districting problem by modeling it as a Markov decision process that rewards traditional measures of district “goodness”: equality of population, continuity, preservation of county lines, and compactness of shape. Our Electoral District-dividing Model basing on the voronoi picture simulates the creation of a xed number of districts for an arbitrary geography for districts and specifying particular growth rules. The result of this process is refined in our Partition Optimization Model, which uses stochastic domain hill-climbing to make small changes in district lines to improve goodness. We include as an extension an optimization to minimize projected inequality in district populations between redistrictings. As a case study, we implement our models to create an unbiased, geographically simple districting of New York using tract-level data from the 2000 Census. What is Gerrymandering? Gerrymandering is division of an area into political districts that give advantage to one group. Frequently, this involves concentrating “unfavorable” voters in a few districts to ensure that “favorable” voters will win in many more districts. To squeeze unfavorable voters into a few districts, gerrymandering creates snaky and odd shaped regions. The eponymous label was created when politician Elbridge Gerry pioneered this technique in early 19th century and his opponents claimed that the districts resembled salamanders. Basic Terminology ?Packing: Forcing a disproportionately high concentration of a