Unmöglichkeitssatz von Balinski und Young

Nach dem Unmöglichkeitssatz von Balinski und Young kann kein (ganzzahliges) Sitzzuteilungsverfahren bei fester Gesamtsitzzahl gleichzeitig die Quotenbedingung erfüllen und frei vom Wählerzuwachsparadoxon sein. Er wurde 1982 von Peyton Young und Michel Balinski bewiesen.

Interpretation

Der Satz ist interessant, weil beide damit unvereinbaren Forderungen als Mindestanforderungen an ein gerechtes Sitzzuteilungsverfahren gesehen werden können. Der Satz besagt also unmathematisch gesprochen, dass ein perfektes Sitzzuteilungsverfahren unmöglich ist. Er ermöglicht außerdem eine Einteilung der üblichen Sitzzuteilungsverfahren in die der Quotenbedingung genügenden Quotenverfahren und die vom Wählerzuwachsparadoxon freien Divisorenverfahren.

Der Satz gilt allerdings nur unter bestimmten Voraussetzungen. Über Sitzzuteilungsverfahren mit zum Beispiel variabler Anzahl der Sitze oder variierbarem Stimmgewicht der einzelnen Sitze macht der Satz keine Aussagen. Weitere Ausnahmen sind in der detaillierten Beschreibung genannt.

Mathematische Formulierung

Die Anzahl der Parteien sei $P$, die Anzahl der zu vergebenden Sitze $N$. Wir benennen die Zahlen der abgegebenen Stimmen mit $s_{1},s_{2},\dots ,s_{P}$, dabei ist $s_{1}$ die Stimmenzahl von Partei 1 usw.

Ist $K$ die Gesamtzahl der abgegebenen Stimmen, so stünden der Partei $i$ rechnerisch ${\textstyle q_{i}={\frac {N\cdot s_{i}}{K}}}$ Sitze zu, was natürlich in aller Regel zunächst keine ganze Zahl ergibt. Die $q_{i}$ nennt man auch Quoten.

Ein Sitzzuteilungsverfahren ordnet jeder Stimmenverteilung $\left(s_{1},s_{2},\dots ,s_{P}\right)$ eine Sitzverteilung $\left(m_{1},m_{2},\dots ,m_{P}\right)$ zu, wobei die $m_{i}$ natürliche Zahlen sind, die in der Summe $N$ ergeben. Das Ergebnis soll nicht von der Reihenfolge der $s_{i}$ abhängen, d. h. wenn $s_{i}$ mit $s_{j}$ vertauscht wird, dann sollen sich auch die zugeteilten Sitze $m_{i}$ mit $m_{j}$ vertauschen und sich sonst am Ergebnis nichts ändern.

Damit ein Sitzzuteilungsverfahren ganz gerecht wäre, müsste es mindestens die beiden folgenden Bedingungen erfüllen:

(Quot) Die Quotenbedingung

$\forall i:\left|q_{i}-m_{i}\right|<1$, d. h. die tatsächlich zugesprochene Sitzanzahl darf von der Quote nur um weniger als 1 abweichen.

(Mon) Populations-Monotonie

Wenn bei einer anderen Stimmenverteilung das Verhältnis der neuen Quoten $q_{i}'$ und $q_{j}'$ sich gegenüber dem Verhältnis der alten Quoten $q_{i}$ und $q_{j}$ zugunsten von Partei $i$ verändert hat oder zumindest gleich geblieben ist, d. h. wenn

${\frac {q_{i}'}{q_{j}'}}\geq {\frac {q_{i}}{q_{j}}}$ bzw. ${\frac {s_{i}'}{s_{j}'}}\geq {\frac {s_{i}}{s_{j}}}$,

dann soll Partei $i$ mindestens so viele Sitze wie zuvor bekommen oder Partei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} höchstens so viele wie vorher, insgesamt also:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_i'\geq m_i \lor m_j'\leq m_j} .

Anmerkung: Nicht berücksichtigt ist der Fall, dass zwei Parteien genau gleiche Quoten haben, so dass zwischen ihnen gelost werden müsste. Dieser Fall spielt aber für den folgenden Beweis keine Rolle.

Der Satz lautet nun:

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P\geq 4} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N\geq 7} existiert kein populationsmonotones Zuteilungsverfahren, das der Quotenbedingung genügt.

Beweis

Unterstellt, es gebe ein solches Verfahren.

Wir gehen zuerst von der Situation aus, dass sich folgende Quoten ergeben haben: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 5+\epsilon,\frac{2}{3},\frac{2}{3},\frac{2}{3}-\epsilon,q_5,\dots,q_P} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_5} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_P} natürliche Zahlen seien und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} eine kleine positive reelle Zahl (in der Tat notwendigerweise rational). Welche konkrete Stimmenverteilung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(s_1,s_2,\dots,s_P\right)} zu diesen Quoten geführt hat, ist hier nicht wichtig. Man muss sich nur klarmachen, dass es eine solche Stimmenverteilung zu diesen Quoten gibt. Für später anzumerken ist: Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_4} sich auf 7 addieren, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{i=5}^P q_i=N-7} .

Da unser Verfahren die Quotenbedingung erfüllt, gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1\geq 5} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0\leq m_2,m_3,m_4\leq 1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_i=q_i} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i\geq 5} .

Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2+m_3+m_4\leq N-5-(N-7)=2} , also muss mindestens eine der Parteien 2 bis 4 leer ausgehen. Aufgrund der Populationsmonotonie kommt nur Partei 4 in Frage (Begründung hierzu: Man vertausche die Quoten von Partei 3 und Partei 4 – wodurch sich auch die zugeordneten Sitze vertauschen müssen, da das Ergebnis nicht von der Reihenfolge abhängen darf und alle Parteien gleich behandelt werden müssen – und wende das Populationsmonotonie-Kriterium an). D.h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_4=0} .

Nun betrachten wir einen anderen Wahlausgang; als Quoten haben sich ergeben: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4-\epsilon,2,\frac{1}{2},\frac{1}{2}+\epsilon,q_5',\dots,q_P'} , wobei wieder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_5'} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_P'} natürliche Zahlen seien; das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} sei das gleiche wie oben.

Nach der Quotenbedingung gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_1'\leq 4} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_2'=2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0\leq m_3',m_4'\leq 1} , sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_i'=q_i'} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i\geq 5} .

Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_3'+m_4'\geq N-4-2-(N-7)=1} , also können nicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_3'} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_4'} beide 0 sein, d. h. mindestens eine der beiden Zahlen ist 1. Wieder wegen der Populationsmonotonie muss auf jeden Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_4'=1} sein.

Es hat sich also gegenüber der ersten Wahl Partei 1 verschlechtert und Partei 4 verbessert. Wegen der Populationsmonotonie darf es nicht möglich sein, dass sich zugleich die Quote von Partei 1 im Verhältnis zur Quote von Partei 4 verbessert hat oder gleich geblieben ist (denn daraus würde lt. Populationsmonotonie folgen, dass sich Partei 1 verbessern oder Partei 4 verschlechtern muss). Es muss also gelten: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}} .

Da jedoch (bei hinreichend großer Gesamtstimmenzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} ) durchaus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon\leq\frac{1}{61}} möglich ist, führt die Annahme, es gebe ein Verfahren, das Quotenbedingung und Populationsmonotonie zugleich erfüllt, zu einem Widerspruch. Somit ist die Unmöglichkeit eines solchen Verfahrens bewiesen.

Bemerkung: Der obige Beweis gilt in dieser Form nicht im Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P=4, N>7} . Außerdem verlangt er implizit, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} "hinreichend groß" (damit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K\mathord\cdot\epsilon} auch für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon\leq\frac{1}{61}} ganzzahlig ist) und durch 3 teilbar ist (sonst könnten Quoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac 12} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac 23} nicht auftreten). Diese Schwierigkeiten lassen sich durch entsprechende Feinarbeit aus dem Weg räumen.

Literatur

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