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 picturesimulates 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 particular group into one district to lessen their impact in nearby districts. Cracking: Spreading members of a group into several districts to reduce their impact in each of these districts. Forfeit district: A district where group A packs the members of group B so that group B wins this district but loses several surrounding districts that B might win with a different districting scheme. Wasted Vote: A vote cast by a member of group A in a district where A is already assured victory, so voting has no bearing on the result. In general, the group with more wasted votes is made worse off by a districting plan. Why Is It So Bad? Gerrymandering reduces electoral competition within districts, since cracking/packing makes elections uncompetitive. Further, incumbent representatives are in no real danger of losing elections, so they do not campaign vigorously, which can lead to lower voter turnout. Exacerbating the problem, incumbents increased advantage means that they have less incentive to govern based on their constituents interests, so democratic accountability and engagement mutually deteriorate.Gerrymandering also presents the practical problem that it is diffcult to explain to voters why district shapes are so labyrinthine. Some districts connect demographically-similar but geographically-distant regions using thin laments “Niceness” of district shape almost always takes a back seat to political and racial concerns. Example: In the 2000 California realignment, Democrats and Republicans united to design incumbent-favoring districts, which resulted in the re-election of all of the 153 incumbents in 2004. How can one argue that this is in voters best interests?However, gerrymandering can be considered appropriate in specic situations. For instance, the Arizona Legislature gerrymandered a division between the historically hostile Hopi and Navajo tribes even though the Hopi reservation is entirely surrounded by the Navajo reservation.The Legality of Gerrymandering Though gerrymandering is objectionable to many, it is legal. The Voting Rights Act of 1965, which eliminated poll taxes and other discriminatory voting policies, may have inadvertently increased gerrymandering. One interpretation of the Act is that it mandates nondiscriminatory election results, which has led to a strange reversal of vocabulary in which creating “majority-minority” districts is considered benecial. These gerrymandered districts are packedwith minorities to guarantee minority representation in Congress. However, in Shaw v. Reno (1993), and later in Miller v. Johnson (1995), the Supreme Court ruled that racial/ethnic gerrymanders are unconstitutional. Nevertheless, Hunt v. Cromartie (1999) approved of a seemingly racial gerrymandering because the motivation was mostly partisan rather than racial. The recent case League of United Latin American Citizens v. Perry (June 2006) held that states are free to redistrict