تخصیص کرسی های پارلمان اتحادیه اروپا از طریق برنامه ریزی خطی عدد صحیح و سهمیه بندی بازنگری شده

We deal with the problem of assigning seats to the European Parliament within the special requirements imposed by the rules of the EU. Since the usual rounding techniques, like in the divisor methods, may fail to satisfy these requirements, we propose to use integer linear programming (ILP) to provide at the same time rounding and satisfaction of the requirements. Using ILP makes central the choice of quotas to which the seats should be as close as possible. We investigate how the special requirements can affect the very definition of quotas, and define projective quotas. Finally we compare the various methods by using the EU Parliament data.

This note contains some reflections after reading the document Grimmett et al. (2011), also called ‘The Cambridge Compromise’. The allocation of seats to the constituencies of a state is a well studied problem (see for instance Balinski and Young, 2001) and seemingly there is little else to say. All methods are designed to satisfy the following obvious requirement: 1. a constituency, i.e., a country for the European Union, must not receive less seats than a smaller country. However, the rules for the EU Parliament introduce three new concepts which alter the usual framework (see Lamassoure and Severin, 2007): 2. no country can receive more seats than a stated upper bound; 3. no country can receive less seats than a stated lower bound; 4. seats must satisfy the so called ‘degressive proportionality’ requirement. Degressive proportionality means that the ratio of population/seats should be an increasing function of the population. In other words, in a larger country more people are needed to form a seat. Finding a simple method of assigning seats within these rules is the subject of Grimmett et al. (2011). The proposal is to first assign to each country a number of seats equal to the lower bound, and then to assign the remaining seats via a divisor method, by possibly capping the seats whenever they exceed the upper bound. As shown in Grimmett et al. (2011) the method may fail to satisfy the degressive proportionality rule. With regard to this point the authors suggest to weaken the rule by requiring degressive proportionality only before rounding. As a matter of fact it seems difficult to reconcile rounding schemes, like for instance the ones used in divisor methods or in largest remainders methods, with degressive proportionality. Here we take a different attitude in order to comply with these rules. As they are, they seem particularly suited to model the problem via an integer linear programming (ILP) problem. The rules become hard constraints that must be satisfied by the seat assignment. In addition an objective function has to be added to the problem to get proportionality (in a way still to be made more precise) as much as possible. It may be argued that using ILP is not transparent. A specific mathematical knowledge is required in order to model the problem and to solve it. However, in our opinion, a divisor method also requires some mathematical skills and is not amenable to the layman. Nowadays, linear programming packages are largely available (even on spreadsheets) and the model, given its modest size and simple structure, can be easily replicated in most governmental offices and university departments, so that educated people can check the result without any particular effort. This statement may look in contrast to the attitude taken in Simeone and Serafini (in press-b) where verifiability for the layman of a biproportional seat assignment is pursued, with seats assigned according to the method suggested in Simeone and Serafini (in press-a). We think that assigning seats to countries is indeed a delicate issue, but more at a governmental level, where tools to understand an approach and check a result are somehow available. On the contrary, assigning seats to parties on the basis of the votes expressed by the citizens requires some form of ‘understanding’ the method at the same level of the voters themselves. The proportionality issue can be approached by defining rational numbers, so called ‘quotas’, to which the integer numbers representing the seats should adhere as much as possible, for instance minimizing some form of deviation from the quotas. This way the problem of assigning the seats is split into two separate problems, namely first defining the quotas to deal with proportionality, and then solving an ILP model to deal with rounding. In order to define the quotas we may face the problem from two different points of view. On one hand we may consider the requirements 1–4 just as constraints and we try to minimize a measure of the deviation of the seats from the ‘natural’ quotas. On the other hand we may consider the constraints as directives which involve smoothly all countries and as a consequence the concept of quotas must be revised. The note is organized as follows. In Section 2 the problem is defined in mathematical terms. The integer linear programming problem is presented in Section 3. The concept of quotas is revised in Section 4 and projective quotas are defined. Simpler affine quotas are defined in Section 5 together with divisor quotas derived by the method proposed in Grimmett et al. (2011), and the modified quotas proposed in Balinski and Young (2001). The results are briefly discussed in Section 6 and some conclusions follow in Section 7. Finally all results are displayed in tables at the end of the note.

In this note we have proposed some different methods of computing the seats in the EU Parliament. All of them satisfy the requirements 1–4 exposed in the Introduction. The novelty of these methods is that they are based on integer linear programming models. This is not customary in problems of this type, for which rounding has been always taken care of in other ways. However, the usual rounding methods may fail to satisfy the degressive proportionality requirement, and it seems plausible to say that only ILP techniques can deal efficiently with this constraint. As already outlined in the Introduction we think that ILP models are, more or less, as transparent as other methods, and therefore they can be considered as possible ways of computing seats. The difference in seat assignments between different methods is due to the choice of quotas. The methods proposed in this note and the one proposed in Grimmett et al. (2011) are all mathematically sound. Looking at the figures in Table 2 the methods can be ‘ordered’ according to the seats given to large countries. Clearly the question of the choice of one particular method seems at this point more a political issue than a mathematical one.