Balinski and Young's impossibility theorem

According to the impossibility principle of Balinski and Young , no (whole-number) seat allocation process with a fixed total number of seats can simultaneously meet the quota condition and be free from the paradox of voter growth . It was proven in 1982 by Peyton Young and Michel Balinski .

interpretation

The sentence is interesting because both of the incompatible requirements can be seen as minimum requirements for a fair seat allocation process. So, in non-mathematical terms, the sentence means that a perfect seat allocation process is impossible. It also enables a division of the usual seat allocation procedures into the quota procedure which satisfies the quota conditions and the divisor procedure free from the voter growth paradox.

However, the rate only applies under certain conditions. The sentence does not make any statements about the seat allocation process with, for example, a variable number of seats or variable voting weight of the individual seats. Further exceptions are mentioned in the detailed description.

Mathematical formulation

The number of parties is the number of seats to be awarded . We name the number of votes cast , the number of votes from party 1, etc. ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle s_{1},s_{2},\dots ,s_{P}}$ ${\displaystyle s_{1}}$

If the total number of votes cast is calculated , the party would be entitled to seats, which of course usually does not initially result in a whole number. The is also called quotas. ${\displaystyle K}$ ${\displaystyle i}$ ${\displaystyle q_{i}={\frac {N\cdot s_{i}}{K}}}$ ${\displaystyle q_{i}}$

A seat allocation procedure assigns a seat allocation to each vote allocation , whereby the natural numbers are that result in the sum . The result is not the order of the dependent, ie with is reversed, then should the seats allocated to swap and otherwise the result change anything. ${\displaystyle \left(s_{1},s_{2},\dots ,s_{P}\right)}$ ${\displaystyle \left(m_{1},m_{2},\dots ,m_{P}\right)}$ ${\displaystyle m_{i}}$ ${\displaystyle N}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{j}}$ ${\displaystyle m_{i}}$ ${\displaystyle m_{j}}$

For a seat allocation process to be entirely fair, it would have to meet at least the following two conditions:

(Quot) The quota condition

${\displaystyle \forall i:\left|q_{i}-m_{i}\right|<1}$, d. H. the actually awarded number of seats may only deviate from the quota by less than 1.

(Mon) population monotony

If, with a different distribution of votes, the ratio of the new quotas and compared to the ratio of the old quotas and in favor of the party has changed or has at least remained the same, d. H. if ${\displaystyle q_{i}'}$ ${\displaystyle q_{j}'}$ ${\displaystyle q_{i}}$ ${\displaystyle q_{j}}$ ${\displaystyle i}$

${\displaystyle {\frac {q_{i}'}{q_{j}'}}\geq {\frac {q_{i}}{q_{j}}}}$ or , ${\displaystyle {\frac {s_{i}'}{s_{j}'}}\geq {\frac {s_{i}}{s_{j}}}}$

then party should get at least as many seats as before or party at most as many as before, so in total: ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle m_{i}'\geq m_{i}\lor m_{j}'\leq m_{j}}$.

Note: What is not taken into account is the case that two parties have exactly the same odds, so that a lot has to be drawn between them. However, this case does not play a role in the following proof.

The sentence is now:

There is no population-monotonous allocation procedure for and that meets the quota condition. ${\displaystyle P\geq 4}$ ${\displaystyle N\geq 7}$

proof

Assume that such a procedure exists.

We first start from the situation that the following quotas have resulted: where bis are natural numbers and a small positive real number (in fact necessarily rational). The specific distribution of votes that led to these quotas is not important here. You just have to realize that there is such a distribution of votes for these quotas. For noted later is Da to add up to 7, is . ${\displaystyle 5+\epsilon ,{\frac {2}{3}},{\frac {2}{3}},{\frac {2}{3}}-\epsilon ,q_{5},\dots ,q_{P}}$ ${\displaystyle q_{5}}$ ${\displaystyle q_{P}}$ ${\displaystyle \epsilon }$ ${\displaystyle \left(s_{1},s_{2},\dots ,s_{P}\right)}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{4}}$ ${\displaystyle \sum _{i=5}^{P}q_{i}=N-7}$

Since our method meets the quota condition, and and for . ${\displaystyle m_{1}\geq 5}$ ${\displaystyle 0\leq m_{2},m_{3},m_{4}\leq 1}$ ${\displaystyle m_{i}=q_{i}}$ ${\displaystyle i\geq 5}$

Then is , so at least one of the parties 2 to 4 must go home empty-handed. Due to the population monotony, only party 4 comes into question (reason for this: Swap the quotas of party 3 and party 4 - which means that the assigned seats also have to be swapped, as the result must not depend on the order and all parties must be treated equally and apply the population monotony criterion). Ie . ${\displaystyle m_{2}+m_{3}+m_{4}\leq N-5-(N-7)=2}$ ${\displaystyle m_{4}=0}$

Now let us consider another election outcome; the following quotas have resulted:, where again to are natural numbers; that is the same as above. ${\displaystyle 4-\epsilon ,2,{\frac {1}{2}},{\frac {1}{2}}+\epsilon ,q_{5}',\dots ,q_{P}'}$ ${\displaystyle q_{5}'}$ ${\displaystyle q_{P}'}$ ${\displaystyle \epsilon }$

According to the quota condition, and and , as well as for . ${\displaystyle m_{1}'\leq 4}$ ${\displaystyle m_{2}'=2}$ ${\displaystyle 0\leq m_{3}',m_{4}'\leq 1}$ ${\displaystyle m_{i}'=q_{i}'}$ ${\displaystyle i\geq 5}$

Then , so cannot and both be 0, i.e. H. at least one of the two numbers is 1. Again because of the population monotony must definitely be. ${\displaystyle m_{3}'+m_{4}'\geq N-4-2-(N-7)=1}$ ${\displaystyle m_{3}'}$ ${\displaystyle m_{4}'}$ ${\displaystyle m_{4}'=1}$

In comparison to the first election, Party 1 has deteriorated and Party 4 has improved. Because of the population monotony, it must not be possible that at the same time the quota of party 1 has improved or remained the same in relation to the quota of party 4 (because according to the population monotony, this would mean that party 1 must improve or party 4 must worsen) . It must apply: . ${\displaystyle {\frac {q_{1}'}{q_{4}'}}<{\frac {q_{1}}{q_{4}}}\Leftrightarrow {\frac {4-\epsilon }{{\frac {1}{2}}+\epsilon }}<{\frac {5+\epsilon }{{\frac {2}{3}}-\epsilon }}\Leftrightarrow \epsilon >{\frac {1}{61}}}$

However, since it is quite possible (with a sufficiently large total number of votes ) , the assumption that there is a procedure that meets the quota condition and population monotony at the same time leads to a contradiction. Thus the impossibility of such a procedure is proven. ${\displaystyle K}$ ${\displaystyle \epsilon \leq {\frac {1}{61}}}$

Note: The above proof does not apply in this form in the case . In addition, it implicitly demands that "sufficiently large" (thus also for is an integer) and that it is divisible by 3 (otherwise odds and could not occur). These difficulties can be eliminated through appropriate fine-tuning. ${\displaystyle P=4,N>7}$ ${\displaystyle K}$ ${\displaystyle K{\mathord {\cdot }}\epsilon }$ ${\displaystyle \epsilon \leq {\frac {1}{61}}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle {\tfrac {2}{3}}}$

literature

• Michel L. Balinski, H. Peyton Young: Fair Representation. Meeting the Ideal of One Man, One Vote . Yale University Press, New Haven CT et al. 1982, ISBN 0-300-02724-9 .