DRAWING POLITICAL DISTRICTS BY WEIGHTED VORONOI …



DRAWING POLITICAL DISTRICTS BY WEIGHTED VORONOI REGIONS AND LOCAL SEARCH

Federica Ricca, Andrea Scozzari, Bruno Simeone, Isabella Lari

University of Rome “La Sapienza”

Abstract

The design of electoral districts is one of the critical issues in political elections. Political districting can be modeled as multiobjective partitioning of a graph into connected components, where population equality and compactness must hold if a majority voting rule is adopted. This leads to the formulation of problems extremely hard to solve exactly. We propose a heuristic method which combines discrete weighted Voronoi regions and local search in order to obtain compact and balanced districts. The performance of the algorithm has been tested on real-life benchmarks and an experimental comparison with other heuristics, as well as with the actual district map adopted in the 1996 Italian political elections, is provided.

Keywords: political districting, weighted Voronoi regions, graph partitioning, heuristics.

1. INTRODUCTION

Soon after modern democracies were established, gerrymandering practices, consisting of partisan manipulation of electoral district boundaries, began to occur in several states and countries. In order to oppose such practices, researchers started thinking of automatic procedures for political districting, designed so as to be as neutral as possible. Commonly adopted criteria were, and still are: integrity, contiguity, population equality (or population balance), compactness.

A broad survey of political districting algorithms is given in [6]. Later work focuses on local search [3, 11]. Here, we propose combining local search with the computation of weighted Voronoi regions (or diagrams; WVR for short). The latter notion is not new in the literature, especially in the area of computational geometry [2]. The idea of using this tool in political districting was proposed for the first time in [12]. A novel feature of the procedure is the iterative updating of node weights to achieve population balance.

WVR procedures guarantee a flexible approach to the districting problem, since solutions with different trade-offs between compactness and population balance can be easily found: when population balance improves, compactness inevitably worsens; but, by stopping the procedure at different time points, one can always control the current trade-off between these two basic districting criteria. In order to improve the performance of our algorithms, we introduce an additional optimization phase at the end of our procedures. In this phase we keep the current solution, but drop the centers – which do not play any significant role – and consider them simply as ordinary sites. Relying on our previous results (see e.g., [11]), we use local search heuristics in order to find improved solutions with respect to both compactness and population equality. The Old Bachelor Acceptance (OBA) heuristic of Hu, Kahng, and Tsao [7] proves to be quite effective in this context.

In this paper both theoretical and experimental results are provided. In particular, in Sec. 2 we define some desirable properties to be met by WVR algorithms – or at least by some variants of them – and, with respect to these properties, we characterize different variants of such algorithms. We provide conditions under which key-properties, such as “geodesic consistency”, hold and give finite termination results relying on the theory of Majorization introduced in 1934 by Hardy, Littlewood and Pólya. In Sec. 3 we describe two alternative procedures (ADEN and RANDOM) for obtaining district maps, as well as the OBA heuristic for improving them. Finally, in Sec. 4, we present some preliminary computational experiments on a sample of five Italian Regions, where the three heuristics WVR, ADEN, and RANDOM, each followed by OBA, are compared between them and with the actual institutional district map adopted in the 1996 Italian political elections.

2. WEIGHTED VORONOI REGION PROCEDURES

The input to the weighted Voronoi procedures to be described in this section is the following: a contiguity graph G = (V,E), whose nodes represent the territorial units and where there is an edge between two nodes if the two corresponding units are neighbouring; a positive integer r, the number of districts; a subset S ( V of r nodes, called centers (all the remaining nodes will be called sites); positive integral node weights [pic], i(V, representing territorial unit populations; positive real distances [pic] for all pair of sites i and j. We denote by(P the mean district population ( = total population/r ). The integrity criterion dictates that a district must be a subset of nodes; according to the contiguity criterion, such subset must be connected. A district map is a partition of V into r connected subsets (the districts), each containing exactly one center. Given any district map, we denote by [pic] the unique district containing center s. We look for a district map such that, informally speaking, the district population imbalance is small and the districts are compact enough. According to our approach, we first locate the subset S ( V of r centers and then we design the district map by drawing on G the Voronoi diagram w.r.t. the distances [pic], ( i ( V\S, ( s ( S, which can be seen as the graph-theoretic counterpart of the ordinary Voronoi diagram in continuous space. The idea is that by taking as districts the Voronoi regions on G, a good compactness can be achieved. Notice that the compactness of the district map strongly depends on the location of the r centers. In order to get a good performance of the Voronoi approach w.r.t. compactness, we locate the r centers by solving an unweighted r-center location problem on G. In this way a good compactness level is usually achieved, but a poor population balance might ensue. In order to re-balance district populations, one would like to promote site migration out of “heavier” districts (population-wise) and into lighter ones. Then, the basic idea is to consider weighted distances [pic], where each weight [pic] is proportional to [pic], the population of district [pic], and to perform a Voronoi iteration w.r.t. the biased distances [pic]. Do this iteratively: at iteration k, [pic], two different recursions may be taken into consideration, namely, a static one,

[pic]

and a dynamic one,

[pic]

where, in both cases, [pic], [pic] is the population of the (unweighted) Voronoi region containing center s, and [pic] is the population of [pic] after iteration [pic]. Stop as soon as the districts become “stable”. The above sketched algorithm will be called a full transfer one. One may also consider a single transfer version of it, by letting sites migrate one at a time from one district to another; or a partial transfer version, in which only a particular subset of sites migrates at each iteration. Here too, one may adopt either the static or the dynamic recursion defined above. So one altogether gets six variants of the weighted Voronoi algorithm (static/dynamic recursion; full/partial/single transfer). Our implementation of the single transfer algorithm is the following. At iteration k, some district [pic] with minimum population, [pic], is selected as the destination district of the transfer. Then, a set M of candidate sites for migrating into [pic] is selected according to the following rule: site i is a candidate for migrating into [pic] if [pic]. Finally, site i is chosen for migrating from [pic] (the district it belongs to) to [pic] if the following two conditions hold: 1) [pic] ; 2) [pic]. Notice that if site i belongs to district [pic] and it is a candidate for migrating to [pic], then [pic]. The algorithm stops when the set of candidates is empty. One possible implementation of the partial transfer algorithm is called path transfer and is defined as follows. Initially, Voronoi regions are calculated. At each iteration an auxiliary network N is constructed whose nodes in N correspond to the current districts, while there is an arc between two nodes t and t’ of N if and only if there exists a site i which may be moved from t to t’. At each iteration a subset of sites moving from their own district to a new one is identified through the selection of one or more (vertex-disjoint) paths in N. Fig. 1 gives an idea of the shape of the districts obtained by a WVR procedure for a 20(20 grid. The grid is represented as a chessboard whose squares correspond to the grid nodes. In this case L1 – distances in the grid were adopted.

| |

|1. Select an initial feasible solution [pic]. |

|2. Define an initial threshold [pic]. |

|3. repeat: |

|select at random a feasible move producing a neighborhood |

|feasible solution [pic] of the current solution s |

|3.1. if [pic] |

|perform the move |

|3.1.1. decrease the threshold: [pic]; |

|3.2. otherwise [[pic]] |

|increase the threshold: [pic] |

|3.3. end if |

|4. until the stopping condition is met |

|5. The final solution is the best local optimum found [pic]. |

Figure 2

In our application [pic] and [pic] are linear functions of [pic], where i denotes the current iteration and M is the total number of iterations. More precisely, when the last steps of the algorithm are performed – that is, when the value of [pic] is low – both [pic] and [pic] become small. This corresponds to a strategy of maximum exploitation of the last iterations in order to find some additional local optima.

4. EXPERIMENTAL RESULTS

4.1 Experimental plan

The performance of the heuristics for political districting described in Sections 2 and 3 was studied over a sample of five Italian regions. These regions (Piedmont, Latium, Trentino Alto Adige, Abruzzi and Marches) differs in extension, characteristics and shape. The main features of the corresponding graphs are summarized in Table 1.

|Table 1: Graphs of the Italian regions |

| |Nodes |Edges |Density |Districts |

|Piedmont |1208 |3527 |2.92 |28 |

|Latium |374 |1006 |2.69 |19 |

|Trentino |339 |938 |2.78 |8 |

|Abruzzi |305 |847 |2.78 |11 |

|Marches |246 |674 |2.74 |12 |

Notice that they are all planar graphs since they are contiguity graphs. In Table 1 for each graph the number of nodes, edges, and districts are reported along with its density (ratio between the number of edges and the number of nodes). All our graphs have high densities (greater than 2). The number of nodes varies from a minimum of 246 (Marches) to a maximum of 1208 (Piedmont) and also the number of edges and the number of districts to be drawn are very different from region to region. Notice that the number of districts does not depend on the number of nodes of the graph. For example, Trentino has about one hundred nodes more than Marches and, however, the number of its districts is smaller (only 8 for Trentino and 12 for Marches).

The number of districts in each region was fixed according to the Italian electoral law of 1992. These values were adopted for the first time in the map drawn for the Italian political elections of 1994, 1996, and 2001. Therefore, it was taken as a benchmark in our experimental plan (institutional district map). Three additional initial district maps were considered for each region, namely, those generated by ADEN, by RANDOM, and by a dynamic single-transfer WVR procedure. Therefore, we have a set of three different initial solutions for each region. In total we have 15 different starting maps for our local search algorithms. The random solution was generated by selecting (at random) 50 spanning trees for the graph G and obtaining r subtrees by a random selection of their roots. The trees have been explored according to a breadth-first search technique.

The criteria values were averaged over the 50 spanning trees.

4.2 Criteria

The criteria we have employed are population equality (PE), compactness (C), and conformity to administrative boundaries (AC), but a mixture of the three (MT) was also considered. In this case the objective function is given by a convex combination of the objectives with weights equal to 0.5 for population equality, 0.3 for compactness and 0.2 for conformity to administrative boundaries (from now on we will refer to this objective function as mixed objective or mixed target).

All the objective functions adopted here measure the lack of fulfillment of the corresponding criterion, hence they must be minimized.

The PE index measures the lack of equality between district populations and it is defined as

[pic] .

We have adopted the compactness measure C proposed in [1], see also [6]. It may be thought of as a discrete weighted variant of the well-known Reock index [10], which measures how far is the district shape from a perfectly circular one. However, in this case there is no reference to the area but only to distances between the territorial units that form the district. Consider a district, its center and the farthest territorial unit, u, within the district. Among all the units that are no farther from the center than u, calculate the percentage of population of those units that are not in the district. The index is near to 0 for round districts and it is near to 1 for elongate or indented districts.

The last criterion is conformity to administrative boundaries (or simply administrative conformity), which requires district maps to take into account administrative boundaries that already exist, such as Regions, Provinces, Counties, and health-care districts. In this application, we adopt the administrative conformity index AC proposed in [6], which takes into account six different types of administrative areas.

4.3 Experimental results

The experimental results reported in this section refer to the application of local search to the 15 different combinations of the 5 territories with the 3 different initial solutions, namely, those generated by ADEN, RANDOM and Voronoi. For each region, Table 2 shows the values of PE, C, AC and the mixed target MT with respect to the given institutional solution. It can be easily checked that the institutional maps take into account PE and AC, but C is completely ignored (in fact, there was no provision on compactness in the Italian electoral law)

|Table 2: Institutional solution |

|Criteria |Trentino |Abruzzi |Marches |Latium |Piedmont |

|PE |0.04 |0.08 |0.05 |0.06 |0.10 |

|C |0.70 |0.63 |0.67 |0.68 |0.88 |

|AC |0.07 |0.21 |0.17 |0.20 |0.14 |

|MT |0.24 |0.27 |0.26 |0.27 |0.34 |

Tables 3-7 show the results obtained through each heuristic RANDOM, ADEN, and Voronoi, followed in any case by Old Bachelor Acceptance. First of all, notice that there is a general common behavior of the three initial solutions in all the different regions. Actually, the random solution has very bad values for PE and C and this implies also bad values for MT. On the other hand, ADEN and Voronoi solutions are already partially optimized with respect to the three criteria: they both show good values for PE, medium size values for AC, but C values are not satisfying even if in the Voronoi initial solution the values are much better than those of ADEN.

| |

|Table 3: Trentino |

|RANDOM solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.90 |-91% |0.081 |

|C |0.82 |-87% |0.107 |

|AC |0.32 |-75% |0.080 |

|MT |0.76 |-44% |0.426 |

| | | | |

|ADEN solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.13 |-99% |0.001 |

|C |0.74 |-56% |0.326 |

|AC |0.33 |-85% |0.049 |

|MT |0.36 |-35% |0.234 |

| | | | |

|Voronoi solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.306 |-96% |0.012 |

|C |0.462 |-72% |0.130 |

|AC |0.293 |-90% |0.030 |

|MT |0.350 |-34% |0.230 |

| |

|Table 4: Abruzzi |

|RANDOM solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.75 |-68% |0.240 |

|C |0.77 |-80% |0.154 |

|AC |0.34 |-78% |0.075 |

|MT |0.67 |-49% |0.341 |

| | | | |

|ADEN solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.08 |-83% |0.014 |

|C |0.72 |-79% |0.151 |

|AC |0.38 |-77% |0.087 |

|MT |0.34 |-28% |0.245 |

| | | | |

|Voronoi solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.216 |-93% |0.015 |

|C |0.460 |-60% |0.182 |

|AC |0.387 |-84% |0.063 |

|MT |0.323 |-29% |0.229 |

| |

|Table 5: Marches |

|RANDOM solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.76 |-58% |0.319 |

|C |0.79 |-68% |0.253 |

|AC |0.40 |-80% |0.080 |

|MT |0.70 |-38% |0.434 |

| | | | |

|ADEN solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.09 |-95% |0.004 |

|C |0.73 |-79% |0.153 |

|AC |0.47 |-90% |0.047 |

|MT |0.36 |-43% |0.205 |

| | | | |

|Voronoi solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.165 |-76% |0.040 |

|C |0.601 |-45% |0.332 |

|AC |0.358 |-86% |0.050 |

|MT |0.341 |-42% |0.209 |

| |

|Table 6: Latium |

|RANDOM solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.90 |-35% |0.585 |

|C |0.74 |-69% |0.229 |

|AC |0.36 |-72% |0.101 |

|MT |0.74 |-30% |0.518 |

| | | | |

|ADEN solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.10 |-88% |0.012 |

|C |0.73 |-56% |0.321 |

|AC |0.41 |-68% |0.131 |

|MT |0.35 |-31% |0.241 |

| | | | |

|Voronoi solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.199 |-85% |0.030 |

|C |0.707 |-67% |0.232 |

|AC |0.394 |-85% |0.057 |

|MT |0.390 |-27% |0.285 |

| |

|Table 7: Piedmont |

|RANDOM solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.87 |-81% |0.165 |

|C |0.94 |-53% |0.442 |

|AC |0.34 |-66% |0.116 |

|MT |0.78 |-47% |0.413 |

| | | | |

|ADEN solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.17 |-74% |0.044 |

|C |0.92 |-55% |0.414 |

|AC |0.35 |-69% |0.108 |

|MT |0.43 |-18% |0.353 |

| | | | |

|Voronoi solution |

|Criteria |Initial value |Per cent variation |Final value |

|PE |0.187 |-78% |0.041 |

|C |0.775 |-25% |0.584 |

|AC |0.423 |-75% |0.107 |

|MT |0.411 |-30% |0.289 |

A direct comparison between Table 2 and Tables 3 – 7 shows that the Institutional district map is dominated – with respect to all four criteria – by those produced either by the ADEN procedure or by the Voronoi one, when these are followed by OBA The latter two procedures are competitive: ADEN + OBA appears to do better w.r.t. PE and C, while Voronoi+OBA has a better performance w.r.t. AC and MT.

According to our results, a good performance is generally guaranteed for PE, even if the task is much harder when starting from a high initial value of the index. We have a good performance of local search also when AC is the objective, since in this case the improvement ranges between 66% and 90%. On the other hand, our results show that it is hard to reach good values of C, even when local search starts from the Voronoi solution. Actually, starting from this solution does not help except for the case of Trentino. However, the reader must not be surprised by this result, since the compactness of the initial Voronoi regions is partially lost when performing migrations during the Voronoi algorithm.

It should be emphasized that, whatever the initial map, Old Bachelor Acceptance has the ability to improve the PE, C, AC values both separately and all at the same time.

References

[1] F. Arcese, M.G. Battista, O. Biasi, M. Lucertini, B. Simeone, Un modello multicriterio per

la distrettizzazione elettorale: la metodologia C.A.P.I.R.E. A.D.E.N., Rome 1992

(unpublished manuscript, in Italian)

[2] F. Aurenhammer and H. Edelsbrunner (1984), An optimal algorithm for constructing the

weighted Voronoi diagram in the plane, Pattern Recognition 17, 251-257.

[3] B. Bozkaya, E. Erkut, and G. Laporte (2003), A tabu search heuristic and adaptive memory

procedure for political districting, European Journal of Operational Research 144, 12 – 26.

[4] L. Cooper, Location-allocation problems, Operations Research, 11 (1963), pp. 331-343.

[5] E. W. Forgy, Cluster analysis of multivariate data: efficiency vs. interpretability of

classification , Biometric Soc. Meetings, Riverside, CA, 1965.

[6] P. Grilli di Cortona, C. Manzi, A. Pennisi, F. Ricca, B. Simeone (1999) Evaluation and

Optimization of Electoral Systems, SIAM Monographs in Discrete Mathematics, SIAM,

Philadelphia.

[7] T. C. Hu, A. B. Kahng, and C. W. A. Tsao (1995), Old bachelor acceptance: a new class

of non-monotone threshold accepting methods, ORSA Journal on Computing, 7, 417- 425.

[8] A.A. Kuehn and M. Hamburger, A heuristic program for locating warehouses, Management

Science, 9 (1963), pp. 643-666.

[9] J. B. MacQueen (1967), Some methods for classification and analysis of multivariate

observations, Proc. Simp. Math. Stat. and Probability, 5th, Berkeley 1 pp. 281-297, AD

669871, University of California Press, Berkeley.

[10] Reock E.C. Jr. (1961), Measuring compactness as a requirement of legislative

apportionment, Midwest Journal of Political Science, vol.5. 70-74

[11] F. Ricca, B. Simeone (2000), Local search heuristics for political districting, Technical

Report A, n. 11- 2000, DSPSA, University of Rome "La Sapienza", submitted to European

Journal of Operational Research

[12] B. Simeone, I. Lari, F. Ricca (2004) A weighted Voronoi diagram approach to political

districting, in : M.L. Balinski, S. Brams, F. Pukelsheim (eds) Analysis and Design of

Electoral Systems , Mathematisches Institut Oberwolfach, Report 14/2004, 763-766

-----------------------

[1] Such procedure is well known in location theory (see, e.g., [4], [8]; as well as in cluster analysis [5], [9] where it is known under the name of k-means.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download