Control 1421 Page 14 out of 35 Input: Iteration count iter, initial partition F Output: Final partition P while count iter do outscore←s(P) D← random district0 bestscore← outscore foreach Ma E 0U Mada(d) do foreach M,E OU Mremove(D)) do per formMove(Ma) per formMove(Mr) if is Contiguous(P)then if tmpscore> best score then bestscore← tempcore bestand←Ma bestremove←Mr end per Move(Ma) per formMove(M end nd if bestscore> curscore then per form Move(bestadd) per form Move(bestremove nd return P Algorithm 1- Stochastic domain hill-climbing algorithm for districtin Note that we guarantee that our solution will be contiguous by not even considering moves that would break contiguity, and that we only perform a move if it increases the score our ci 4.3 Achieving absolute equality US law mandates that the populations of each district be equal within a range of error of one person according to the census data(Karcher v. Daggett, 1983 ). Our problem dealt only with census tracts, and so exact equality of populations to the nearest integer was not possible. This last step of the algorithm must be implemented by splitting tracts between two districts To the knowledge of the authors, this problem beyond population unit level no smaller than block groups) has not been addressed in the literature. Clearly, the simplest way to
Control # 1421 Page 14 out of 35 Input: Iteration count iter, initial partition P. Output: Final partition P. count ← 0 while count < iter do curscore ← s(P) D ← randomDistrict() bestscore ← curscore foreach Ma ∈ {∅ ∪ Madd(D)} do foreach Mr ∈ {∅ ∪ Mremove(D)} do performMove(Ma) performMove(Mr) if isContiguous(P) then tmpscore ← s(P) if tmpscore > bestscore then bestscore ← tmpscore bestadd ← Ma bestremove ← Mr end end performMove(M−1 a ) performMove(M−1 r ) end end if bestscore > curscore then performMove(bestadd) performMove(bestremove) end count ← count + 1 end return P Algorithm 1 - Stochastic domain hill-climbing algorithm for districting Note that we guarantee that our solution will be contiguous by not even considering moves that would break contiguity, and that we only perform a move if it increases the score of our current state. 4.3 Achieving absolute equality US law mandates that the populations of each district be equal within a range of error of one person according to the census data (Karcher v. Daggett, 1983). Our problem dealt only with census tracts, and so exact equality of populations to the nearest integer was not possible. This last step of the algorithm must be implemented by splitting tracts between two districts. To the knowledge of the authors, this problem beyond population unit level (no smaller than block groups) has not been addressed in the literature. Clearly, the simplest way to
Control 1421 Page 15 out of 35 gorithm in the computer simulation. we describe the methodology for doing thus t of the do this is to split one of the border tracts. While we do not implement this pal Let g denote the graph whose vertices are given by the districts and whose edges are the pairs of bordering districts. The intuition for the algorithm is that if we can find a pair of districts such that splitting a border tract between them gives both districts a population of one within the mean population, then we would optimally do so and ignore those two districts for the remainder of the algorithm. However, to guarantee that the algorithm finishes, we require that the graph G remain connected (otherwise, G may divide into two or more connected components, such that the constituent districts cannot attain populations equal to the overall mean). Taking out two districts at a time by splitting only a single tract leaves the fewest possible tracts split, which we consider optimal, for the same reasons that number of counties split between districts is optimal Our algorithm works as follows. We search for an edge of G such that removal of its two vertices and all edges emanating from them leaves a new graph Gi C G that is connected We call the deletion of a single vertex from a graph that leaves the graph connected a paring If these two vertices have some special properties, we perform the double paring and then perform the algorithm on G1, and continue until all districts have equal population. If no such pair of districts exists, we then perform a single paring and ensure that the removed district has population p before removing it. Define tract splitting to be the process of splitting up a border tract into two disjoint areas and two disjoint populations allocated between two bordering district There always exists an edge on a connected graph g that permits a double paring of g, except for a very specialized set of connected graphs. However, all connected graphs permit a paring, as the next theorem shows Theorem 4.1 All connected graphs permit a paring A proof of this theorem is given in the Appendix b We recursively update the districts to get population equality. We iteratively pare the graph G of districts such that each time we pare a district or pair of districts, those districts ave populations which equal the population mean. By Theorem 4.1, this process always ends with all districts having equal population. Our algorithm works as follows 1. If the graph G contains only one district, its population must equal p. Stop the algorithm here. If not, search across all border tracts of the partition for a tract such that splitting it between two districts makes the population of the two border tract within 1 of the average p. If some pair of districts exists which is a double paring of G, then perform this double paring of G. For these two districts, take the tract on their border which, upon being split between the two districts, makes their population within 1 of the population mean. Split this tract to equalize their populations. If no such pair exists, go to Step 2 2. Search G for all possible double parings such that the two districts in the double paring have populations which sum to twice the average population. Perform the double paring of G among these double parings which has the property that the two removed districts can have equal populations with the minimal number of tract moves
Control # 1421 Page 15 out of 35 do this is to split one of the border tracts. While we do not implement this part of the algorithm in the computer simulation, we describe the methodology for doing this. Let G denote the graph whose vertices are given by the districts and whose edges are the pairs of bordering districts. The intuition for the algorithm is that if we can find a pair of districts such that splitting a border tract between them gives both districts a population of one within the mean population, then we would optimally do so and ignore those two districts for the remainder of the algorithm. However, to guarantee that the algorithm finishes, we require that the graph G remain connected (otherwise, G may divide into two or more connected components, such that the constituent districts cannot attain populations equal to the overall mean). Taking out two districts at a time by splitting only a single tract leaves the fewest possible tracts split, which we consider optimal, for the same reasons that number of counties split between districts is optimal. Our algorithm works as follows. We search for an edge of G such that removal of its two vertices and all edges emanating from them leaves a new graph G1 ⊂ G that is connected. We call the deletion of a single vertex from a graph that leaves the graph connected a paring. If these two vertices have some special properties, we perform the double paring and then perform the algorithm on G1, and continue until all districts have equal population. If no such pair of districts exists, we then perform a single paring and ensure that the removed district has population ¯p before removing it. Define tract splitting to be the process of splitting up a border tract into two disjoint areas and two disjoint populations allocated between two bordering districts. There always exists an edge on a connected graph G that permits a double paring of G, except for a very specialized set of connected graphs. However, all connected graphs permit a paring, as the next theorem shows. Theorem 4.1 All connected graphs permit a paring. A proof of this theorem is given in the Appendix B. We recursively update the districts to get population equality. We iteratively pare the graph G of districts such that each time we pare a district or pair of districts, those districts have populations which equal the population mean. By Theorem 4.1, this process always ends with all districts having equal population. Our algorithm works as follows: 1. If the graph G contains only one district, its population must equal ¯p. Stop the algorithm here. If not, search across all border tracts of the partition for a tract such that splitting it between two districts makes the population of the two border tracts within 1 of the average ¯p. If some pair of districts exists which is a double paring of G, then perform this double paring of G. For these two districts, take the tract on their border which, upon being split between the two districts, makes their populations within 1 of the population mean. Split this tract to equalize their populations. If no such pair exists, go to Step 2. 2. Search G for all possible double parings such that the two districts in the double paring have populations which sum to twice the average population. Perform the double paring of G among these double parings which has the property that the two removed districts can have equal populations with the minimal number of tract moves
Control 1421 Page 16 out of 35 and one tract splitting between the two. If such a pair exists, perform the double paring and go to Step 1. If no such pair exists, go to Step 3 3. Search all vertices of G for a paring of G such that a single tract splitting along the border of the district gives the district a population of barp, and perform this paring of G. If such a border tract and paring exist, perform the paring and the tract splitting, and go to Step 1. If no such tract splitting and paring exist, go to Step 4 4. Search all vertices of G for a paring of G such that the removed district Di borders a district which requires the minimum number of moves and one tract splitting to make the population of D; equal to p. Perform these moves, this tract splitting, and this aring, and return to Step 1 his entire algorithm removes at least one vertex from G at each steps, and the whole algorithm can therefore be performed with at most n-1 tract splittings, where n is the number of districts. The actual number of tract splittings equals n -d-l, where d is the number of double parings performed 5 Case Study: New York congressional districts 5.1 The data We began our inquiry by acquiring data from the 2000 census from the New York State Data Center. The downloaded data contained 4907 tracts. but a number of these were tracts have no population. These tracts represented water, inland lakes, or parks. We considered all of these tracts to be the equivalent of water, with the exception of only one of these tracts on Long Island which completely enclosed a populated"island"and was thus considered to be a tract of land with no population. These empty districts are the cause of the"holes"on our maps, particularly around the NYC Metro area Trimming these parts from our map left us with 4827 tracts to examine. It is worth noting that the possible number of partitions of these tracts is prohibitively high. Ignoring concerns such as contiguity, nonempty districts, or population equality, the number of allocations of 4827 tracts to 29 districts is approximately 1.1×107028 The data were delivered in ESRI shapefile format, which listed tract areas, populations, and unique county identifiers 5.2 Results Running the MSGM on our initial allocation left us with 29 haggard districts spanning the map from which to refine a solution Using this solution as a starting point, we optimized our result using swap moves in particular. Though our algorithmic process of refinement is stochastic, generally more than 90% of the moves in any run involved swaps. This was particularly the case for moves
Control # 1421 Page 16 out of 35 and one tract splitting between the two. If such a pair exists, perform the double paring and go to Step 1. If no such pair exists, go to Step 3. 3. Search all vertices of G for a paring of G such that a single tract splitting along the border of the district gives the district a population of barp, and perform this paring of G. If such a border tract and paring exist, perform the paring and the tract splitting, and go to Step 1. If no such tract splitting and paring exist, go to Step 4. 4. Search all vertices of G for a paring of G such that the removed district Di borders a district which requires the minimum number of moves and one tract splitting to make the population of Di equal to ¯p. Perform these moves, this tract splitting, and this paring, and return to Step 1. This entire algorithm removes at least one vertex from G at each steps, and the whole algorithm can therefore be performed with at most n − 1 tract splittings, where n is the number of districts. The actual number of tract splittings equals n − d − 1, where d is the number of double parings performed. 5 Case Study: New York congressional districts 5.1 The data We began our inquiry by acquiring data from the 2000 census from the New York State Data Center. The downloaded data contained 4907 tracts, but a number of these were tracts have no population. These tracts represented water, inland lakes, or parks. We considered all of these tracts to be the equivalent of water, with the exception of only one of these tracts on Long Island which completely enclosed a populated “island” and was thus considered to be a tract of land with no population. These empty districts are the cause of the “holes” on our maps, particularly around the NYC Metro area. Trimming these parts from our map left us with 4827 tracts to examine. It is worth noting that the possible number of partitions of these tracts is prohibitively high. Ignoring concerns such as contiguity, nonempty districts, or population equality, the number of allocations of 4827 tracts to 29 districts is approximately 1 29!294827 ≈ 1.1 × 107028 The data were delivered in ESRI shapefile format, which listed tract areas, populations, and unique county identifiers. 5.2 Results Running the MSGM on our initial allocation left us with 29 haggard districts spanning the map from which to refine a solution. Using this solution as a starting point, we optimized our result using swap moves in particular. Though our algorithmic process of refinement is stochastic, generally more than 90% of the moves in any run involved swaps. This was particularly the case for moves
Control 1421 Page 17 out of 35 Table 2: Values after the MSGM Value Heuristic Variance Score-3, 147 Largest District 969,511 Smallest District 280.945 County S cor Compactness Score 2.869 at the very end of a run, where population differences between districts were minute. As a result, swapping provided a way to adjust population smoothly. In addition swap operations particularly of side-by-side tracts exchanged between districts, provided an effective to"clean up"tattered fringes of districts, increasing their compactness even with vigorous population changes Table 3: Values after refinement Heuristic Variance Score-0277 655,760 Smallest District 652, 5 Compactness Score 2.906 The most difficult part of both steps was defining the optimal values for the scaling factors. It is important to note that it is not the magnitude of the scaling factors that is most crucial, but rather their relative marginal magnitudes. Since our algorithm operates on the changes that result from making a single first-or second-order move, selecting positions with the highest score, it is important that the changes in each of the heuristic variables are significant. In particular, a large or small multiple on some factor does not indicate that we wished to treat that variable severely or lightly, but rather that the marginal changes in that variable were relatively small or large he Appendix contains several informative tables and maps summarizing our results Images are produced using the amazing TatukGis Viewer software 6 Extension: The 4n Dimension It is entirely possible that a state's congressional districts could become populationally im- balanced between redistrictings, which usually occur every 10 years. Though current practice is to devise a districting with equal populations per district we suggest that this is subopti- mal. One could imagine an initial population allocation that maximizes district population equality not just in the first years but over the course of all 10 years between redistrictings
Control # 1421 Page 17 out of 35 Table 2: Values after the MSGM Variable Value Heuristic Variance Score -3,147 Largest District 969,511 Smallest District 280,945 County Score 37.48 Compactness Score 2,869 at the very end of a run, where population differences between districts were minute. As a result, swapping provided a way to adjust population smoothly. In addition swap operations, particularly of side-by-side tracts exchanged between districts, provided an effective to “clean up” tattered fringes of districts, increasing their compactness even with vigorous population changes. Table 3: Values after refinement Variable Value Heuristic Variance Score -.0277 Largest District 655,760 Smallest District 652,561 County Score 47.44 Compactness Score 2,906 The most difficult part of both steps was defining the optimal values for the scaling factors. It is important to note that it is not the magnitude of the scaling factors that is most crucial, but rather their relative marginal magnitudes. Since our algorithm operates on the changes that result from making a single first- or second-order move, selecting positions with the highest score, it is important that the changes in each of the heuristic variables are significant. In particular, a large or small multiple on some factor does not indicate that we wished to treat that variable severely or lightly, but rather that the marginal changes in that variable were relatively small or large. The Appendix contains several informative tables and maps summarizing our results. Images are produced using the amazing TatukGIS Viewer software. 6 Extension: The 4 th Dimension It is entirely possible that a state’s congressional districts could become populationally imbalanced between redistrictings, which usually occur every 10 years. Though current practice is to devise a districting with equal populations per district we suggest that this is suboptimal. One could imagine an initial population allocation that maximizes district population equality not just in the first years but over the course of all 10 years between redistrictings
Control 1421 Page 18 out of 35 For instance, if one district's population is growing 2% nothers is shrinking the growing district with a slightly lower population than that of the shrinking distri i a 1% a year then after ten years the two populations will differ by of elections occurring every two years it seems arbitary to privilege the population at the yea 2000 rather than at the years 2002, 2004, ete.. To improve this disparty we propose starting 6.1 A stitch in time For each tract, we can observe certain demographic characteristics, such as race. Based upon population growth estimates from the Census Bureau we can find optimal weighting of populations such that citizens do not have an"equal vote"today, but citizens have the most equal vote over the entire period between each redistrictings Let T denote the time between redistrictings; in our case T= 10 because the census is taken decenially in the United States. In this section we explore the effect of differential population growth rates by districts on optimal population weights for the districts Modern utility theory suggests that individuals favor present utility greater than future utility, and most often, for analytic al convenience. according to a constant time discount factor. Let us suppose that the time discount factor for utility of individuals in the United States is given by 8 We assume that societal utility is maximized by giving citizens an equal voting share in each period. (If this does not actually maximize utility then one could still argue that ideal politicians would prefer a scheme that promotes voting share equal. As we discussed in Section 4.1. 1, variance is the best measure for population inequality between districts Utility today is weighted greater than utility t units in the future by If we have a partition Q=Di,, Dn with populations pi, ...,pn, then the population penalty we found for such a partition is a constant multiple of Var(pi). Let pit denote the population of district i at time t. Then the discounted utility of the state at time t is e-otvar(pi). Suppose that we have forecast data on the population growth rates of different counties during the T-year period. Let the log-growth rate at time t for district i be given by nit. Then the population of district i at time t is given by Pit = exp nis ds) pi and total utility of the initial allocation Q2 with district populations p=(p1, P2, ..,Pn )is U0m1(2) e-of Var(pi.t)dt Expressing the variance in terms of the populations pit, we get Var(pi.t) Pi t ∑-∑m Dividing out by a constant factor, this gives the total utility as
Control # 1421 Page 18 out of 35 For instance, if one district’s population is growing 2% a year and another’s is shrinking 1% a year then after ten years the two populations will differ by over 33%. With congressional elections occurring every two years it seems arbitary to privilege the population at the year 2000 rather than at the years 2002, 2004, etc. . To improve this disparty we propose starting the growing district with a slightly lower population than that of the shrinking district. 6.1 A stitch in time For each tract, we can observe certain demographic characteristics, such as race. Based upon population growth estimates from the Census Bureau we can find optimal weighting of populations such that citizens do not have an “equal vote” today, but citizens have the most equal vote over the entire period between each redistrictings. Let T denote the time between redistrictings; in our case T = 10 because the census is taken decenially in the United States. In this section we explore the effect of differential population growth rates by districts on optimal population weights for the districts. Modern utility theory suggests that individuals favor present utility greater than future utility, and most often, for analytical convenience, according to a constant time discount factor. Let us suppose that the time discount factor for utility of individuals in the United States is given by δ. We assume that societal utility is maximized by giving citizens an equal voting share in each period. (If this does not actually maximize utility then one could still argue that ideal politicians would prefer a scheme that promotes voting share equal.) As we discussed in Section 4.1.1, variance is the best measure for population inequality between districts. Utility today is weighted greater than utility t units in the future by a factor of e δt . If we have a partition Ω = {D1, ..., Dn}, with populations p1, ..., pn, then the population penalty we found for such a partition is a constant multiple of V ar(pi). Let pi,t denote the population of district i at time t. Then the discounted utility of the state at time t is e −δtV ar(pi). Suppose that we have forecast data on the population growth rates of different counties during the T-year period. Let the log-growth rate at time t for district i be given by ηi,t. Then the population of district i at time t is given by: pi,t = exp Z t 0 ηi,sds pi,0 and total utility of the initial allocation Ω with district populations p = (p1, p2, ..., pn) 0 is U[0,T](Ω) = − Z T 0 e −δTVar(pi,t)dt Expressing the variance in terms of the populations pi,t, we get Var(pi,t) = 1 n Xn i=1 p 2 i,t − 1 n2 Xn i=1 pi,t!2 = n − 1 n2 Xn i=1 p 2 i,t − 1 n2 X i6=j pi,tpj,t Dividing out by a constant factor, this gives the total utility as