When O.R. becomes Law

The Swiss Supreme Court ruled in 2002 that the parliamentary election in Zurich State violated the country’s constitution. The disputed old system allocated seats to the parties according to their vote counts in each district proportionally. As a result, small parties had basically no chance to ever gain a seat in any district, even though they might have gathered a respectable amount of votes at the state level. Thus, any vote cast for a small party – especially in a small district – could be considered lost. With enough “lost” votes, the voting procedure was deemed unfair and thus unconstitutional. Alternatively, counting all votes of a party at the state level, and only then allocating the seats to the parties, ensures that every vote makes a difference and that even small parties have a chance to gather some seats in parliament. The then prevailing injustice had to be revoked. In fact, it took the Supreme Court only nine months to rule, after a citizen filed a law suit citing the unfair system in the aftermath of the parliamentary election in 2002. 

The problem statement for the sought-after fair system can be stated as follows: The state has a given number of parliamentary seats (180 in Zurich State, for example), for which a certain number of parties (approximately 11 in Zurich State) run in a given number of districts (18 in Zurich State). On Election Day, the number of votes that have been cast for each party in each district are counted.While in the past, each district determined the parties’ seats for its own district, solely based on the district results; the new procedure allocates the seats based on the total statewide party votes. This gives small parties a chance to gather a seat given they do sufficiently well at the state level.

The new approach for seat allocation consists of three steps, each calling for an O.R. problem to be solved.

Step 1: Allocation of seats to election districts – the number of seats allocated to a district is based on the percentage of citizens living in that district.

Step 2: Allocation of seats to parties – the number of seats allocated to each party is based on the percentage of “voter-votes” that the parties receive. The voter-votes of a party in a district are the cast votes for that party in that district (party-votes), divided by the number of seats that were allocated to that district in Step 1.

Step 3: Allocation of seats to parties in each district – with the allocated seats to districts from Step 1 and the allocated seats to parties from Step 2, the allocation of seats to parties in each district can be done. It is based on the percentage of party-votes in each district. The O.R. challenge, for all three seat-allocation problems, is to transform the real-valued seat numbers into integer-valued seat numbers. The mathematical solution to this matrix apportionment problem, also referred to as bi-proportional scaling method, is based on work by Balinski et al. [1, 2, 3]. Pukelsheim et al. [4, 5] adapted these concepts to the Zurich State legal framework, which then was written into the State of Zurich Law of Political Rights.

Obviously, the mathematical formulation of an O.R. model, and much less the appropriate algorithms to solve it, cannot be written into a regulation, since most citizens would not be able to compute the correct allocation of seats in order to verify the proclaimed results. Therefore, an easily verifiable algorithmic instruction of how to compute the allocation of seats to parties in each district had to be devised. Alternatively, the problem can be solved by classical O.R. methods. In the following, both O.R. models and regulations are discussed with a simple numerical example for the three seat-allocation steps.

Step 1: Allocation of Seats to Election Districts

LET’S ASSUME, as a numerical example, the case of three parties running for a total of 12 parliamentary seats, for which three election districts have been defined. The hypothetical number of citizens residing in the three districts is 39,270, 52,300 and 27,500.

The number of seats to be allocated to the three districts would be the total number of seats,multiplied by the number of citizens in a district, divided by the total number of citizens in the state. These real-valued seat numbers must be transformed into integer values, with smallest possible deviations (least squares approach), subject to the sum of seats over all districts being equal to the total number of available seats (i.e., 12 for our example). The regulation for this seat allocation problem, which allows citizens to compute a solution using a trialand-error approach, is formulated in No. 88 of the Law of Political Rights.

For our numerical example, the allocation-divisor is 9,923, and we obtain the following number of seats for the three districts: 4, 5 and 3.

Step 2: Allocation of Seats to Parties

TO CONTINUE our numerical example, the hypothetical number of votes that a party received in a district, the so-called party-vote, is given in Table 1 on the left side.

The allocation of seats to parties is based on the percentage of votes received, similar to the previous allocation of seats to districts.However, in order to balance the voting weights, we must transform the party-votes to voter-votes (Table 1). This is done by dividing the party-votes by the number of seats allocated to each district. For example, the 6,200 party-votes for the first party in the first district must be divided by the four seats of the first district,which gives 1,550 voter-votes.As a result,we get the voter-votes as shown on the right of Table 1.

The allocation of seats to parties is formulated in No. 103. The decision variables of the O.R. model are the number of seats for each district (integers). The objective function is to minimize the deviations between real-valued and integer-valued number of seats (least squares). The real-valued number of seats is proportional to the voter-votes in each district.

The state election key for the numerical example is 1,240, providing the following number of total seats for the three parties: three, five and four, respectively. 

Step 3: Allocation of Seats to Parties in each District

THE FIRST TWO STEPS computed the number of seats for each district and each party. The last step, using the results obtained in Steps 1 and 2 as constraints, is to determine the number of seats for each party in each district. Three districts and three parties produce a total of nine decision variables, referring to the number of seats each party receives in each district.

The calculations are based on the partyvotes given in Table 1. Here, too, the objective function is to minimize the deviations between real-valued and integer-valued number of seats for each party in each district.

The regulation formulated in No. 104 requires identifying for each party a party-divisor and for each district a district-divisor, so that the rounded values of party-vote divided by party-divisor and district-divisor add up to the number of seats allocated to the districts and to the parties.

The initial values for the three district-divisors are computed as the total of district-votes divided by the number of allocated seats to that district. The initial values for the three partydivisors are set equal to 1. All initial values are shown in Table 2.

Table 2 illuminates two violations of the constraints. The first district has been allocated five seats overall (2+2+1), while it is only entitled to have four seats (Step 1), and first party has been allocated four sears overall (2+1+1), while it is only entitled to have three seats (Step 2). For the other districts and parties, the sums of allocated seats in Table 2 correspond to the numbers of available seats (i.e., the number of seats allocated in Steps 1 and 2).

The algorithmic iteration consists of changing, one-by-one (trial-and-error), the party-divisors or the district-divisors, until the sum of allocated seats equals the number of allocated seats to each district (Step 1) and to each party (Step 2). If too few seats have been allocated, the appropriate divisor must be decreased; if too many seats have been allocated, it must be increased. For the numerical example, the final allocation of seats can be achieved with just one iteration, namely by increasing the district-divisor of the first district from 4,100 to 4,200. The final seat allocation with the corresponding party and district divisors is shown in Table 3.

The focus switched from the districts to the central election office of the State (i.e., the Statistical Office), since it was there that the final assignment of seats was computed and announced.

All three O.R. problems can easily be solved, at least for this simple numerical example, with Excel’s Solver using the quadratic estimation procedure. The final seat allocation to the three parties in the three districts (Step 3) is shown in Figure 1 in the matrix referred to as “3. Decision Variables.”Obviously, the resulting Excel solution is identical to the solution obtained with the algorithmic approach in Table 3, which is defined in No. 104.

Practical Experiences

ZURICH STATEWAS KNOWN for its innovative election approach, including Internet-based voting [7]. It was therefore no surprise that this new seat-allocation method, mandated by the Swiss Supreme Court’s decision, could be put in place for the next city parliamentary election in 2006 and State parliamentary election in 2007. As a result, some quite remarkable operational changes took place. Within the old system, each district would announce the winners of the elections as soon as the vote count was done. The public attention was focused on the districts. Politicians and the press would gather at the corresponding district election offices to hear the results and to inform the public.

With the change to the new system, the focus switched from the districts to the central election office of the State (i.e., the Statistical Office), since it was there that the final assignment of seats was computed and announced. The election team checks and approves the community and district results. Only after the last district is finished counting its votes, a simple key stroke evokes the algorithm for seat-allocation. The distribution of parliamentary seats and the winners of the election are calculated in a fraction of a second. Eyes are focused on the Internet site of the Statistical Office, and skeptical citizens or parties can verify the results by simple hand calculations as described in this article. The Java code of the algorithm as it was used in Zurich State can be found at: www.statistik.zh.ch/themen/17/pukelsheim/nzz_js.txt. The original pseudo Java code can be found at: www.math.uni- ugsburg.de/stochastik/bazi/pseudoCode.html. 

REFERENCES

1. Balinski, M., Demange, G., 1989, “Algorithms for Proportional Matrices in Reals and Integers,” Mathematical Programming, Vol. 45, pp. 193-210.
2. Balinski, M., Rachev, S.T., 1997, “Rounding Proportions: Methods of Rounding,” Mathematical Scientist, Vol. 22, pp. 1-26.
3. Balinski, M., Young, H.P., 2001, “Fair Representation – Meeting the Ideal of One Man, One Vote,” 2nd ed., Washington, D.C.
4. Gaffkea, N. and Pukelsheim F., 2008, “Divisor Methods for Proportional Representation Systems: An Optimization Approach to Vector and Matrix Apportionment Problems,” Mathematical Social Sciences, Vol. 56, No. 2, pp. 166-184.
5. Pukelsheim, F., Schuhmacher, C., 2004, “Das neue Zürcher Zuteilungsverfahren für Parlamentswahlen,” Aktuelle Juristische Praxis – Pratique Juridique Actuelle, Vol. 5, pp. 505-522.
6. Beroggi, G.E.G., 2008, “Secure and Easy Internet Voting,” IEEE Computer, Vol. 41, No. 2, pp. 52-56.