Mathematische Fairness-Garantien

Zusammenfassung: Die akademische Literatur hat dargelegt, dass die Methode der gleichen Anteile allen Wählergruppen eine angemessene Vertretung im Ergebnis garantiert. Sie garantiert auch, dass Projekte gewinnen, solange sie eine bestimmte Mindestanzahl an Unterstützern erhalten.

Die Methode der gleichen Anteile wurde von Mathematikern und Informatikern vorgeschlagen und entwickelt. Diese haben mathematische Theoreme bewiesen, die besagen, dass die Methode den Wählern in einem bestimmten Sinne Fairness garantiert. Auf dieser Seite werden wir einige ihrer Ergebnisse beschreiben, sowohl auf intuitiver Ebene als auch in technischer Hinsicht.

Für weitere Informationen konsultieren Sie bitte auch die folgenden Quellen (auf Englisch):

• Das Buch "Multi-Winner Voting with Approval Preferences" (2023) von Martin Lackner und Piotr Skowron, publiziert von Springer (kostenloses PDF erhältlich). Beachten Sie, dass sich dieses Buch hauptsächlich auf Wahlen mit mehreren Gewinnern konzentriert, bei denen letztenendes davon ausgegangen wird, dass alle Projekte die gleichen Kosten haben.
• Das Papier "Proportional Participatory Budgeting with Additive Utilities" von Dominik Peters, Grzegorz Pierczyński, und Piotr Skowron. Erhältlich auf arXiv.

Ein Projekt wird garantiert gewinnen, sobald es eine Anzahl von "eindeutigen" Stimmen erhält, die proportional zu seinen Kosten ist

Die erste mathematische Garantie betrifft einzelne Projekte: Sie werden garantiert finanziert, wenn sie mindestens eine bestimmte Mindestanzahl von Einzelstimmen erhalten.

Ein konkretes Beispiel ist ein Projektvorschlag, dessen Kosten 5 % des verfügbaren Gesamtbudgets in Anspruch nehmen würden. Wenn dann mindestens 5 % der Wähler für dieses Projekt und für kein anderes Projekt stimmen, gewinnt dieser Vorschlag mit der Methode der gleichen Anteile.

Im Folgenden wird diese Eigenschaft auf formale Weise beschrieben:

Satz. Sei $P$ ein Projekt und seien dessen Kosten $\text{Kosten}(P)$. Angenommen, $B$ sei das Gesamtbudget und $n$ sei die Gesamtzahl der Wähler. Wenn mindestens $n \cdot \text{Kosten}(P)/B$ Wähler für $P$ und keine anderen Projekte stimmen, dann gehört $P$ zu den Projekten, die von der Methode der gleichen Anteile ausgewählt werden.

Proof

Jeder der Wähler, der nur für $P$ gestimmt hat, bekommt zu Beginn der Berechnung der Methode einen Budgetanteil von mindestens $B/n$ zugewiesen. (Es könnte mehr als $B/n$ sein, weil wir die Methode vervollständigen.)

Daher ist der Gesamtbetrag des Budgets, der den Wählern zugewiesen wird, die nur für $P$ stimmen, mindestens

$$\underbrace{n \cdot \frac{\text{Kosten}(P)}{B}}_{\text{Anzahl der Wähler}} \cdot \underbrace{\frac{B}{n}}_{\text{Budgetanteil}} = \text{Kosten}(P).$$

Gemäß der Definition der Methode der gleichen Anteile endet sie erst dann, wenn keine Projekte mehr von ihren Befürwortern finanziert werden können. Das bedeutet aber, dass $P$ eines der ausgewählten Projekte sein muss, weil die Wähler, die nur für $P$ stimmen, ihr gesamtes Geld behalten, bis $P$ ausgewählt ist, und somit ist $P$ immer finanzierbar.

Bei der Standard-Abstimmungsmethode für Bürgerbudgets (bei der nur die beliebtesten Projekte ausgewählt werden, bis das Budget aufgebraucht ist) gibt es keine ähnliche Garantie. Selbst ein sehr kosteneffizientes Projekt (z. B. mit einem Anteil von 1 % des Budgets) kann eine große Anzahl von Wählern (z. B. mehr als 30 %) benötigen, um mit der Standardmethode zu gewinnen.

Damit die Garantie gilt, muss man davon ausgehen, dass die unterstützenden Wähler nur das betreffende Projekt und keine anderen Projekte unterstützen, da die Methode der gleichen Anteile andernfalls versuchen könnte, diese Wähler zufrieden zu stellen, indem sie einige der anderen Projekte, die sie unterstützen, auswählen.

Wählergruppen die ähnlich abstimmen werden im Ergebnis vertreten sein

Mit der Methode der gleichen Anteile kann jede Gruppe von Wählern, die für ähnliche Projekte gestimmt hat, davon ausgehen, dass sie im Ergebnis in einem Umfang vertreten ist, der proportional zur Gruppengröße ist. So kann beispielsweise eine Gruppe von 20 % der Wähler erwarten, dass sie 20 % des Budgets beeinflussen kann.

Beispiele für solche Wählergruppen sind die Eltern von Kindern in einer bestimmten Schule, die Bewohner eines bestimmten Stadtviertels, oder Fahrradfahrer. Die folgenden mathematischen Eigenschaften der Methode der gleichen Anteile stellen sicher, dass jede dieser Gruppen im Ergebnis vertreten ist (vorausgesetzt, sie haben genügend Mitglieder, um die Kosten der Projekte zu rechtfertigen, die sie gemeinsam unterstützen).

Wählergruppen die für die gleichen Projekte stimmen

Betrachten wir eine Bürgerbudget-Wahl, die auf einer Zustimmungswahl beruht. Nehmen wir an, dass $t$ der $n$ Wähler einen identischen Stimmzettel abgegeben haben, d.h. sie haben alle für genau dieselbe Gruppe von Projekten gestimmt. Der Einfachheit halber sagen wir, dass diese $t$ Wähler für die Projekte $P_1$, $P_2$ und $P_3$ stimmen. Da diese Gruppe einen Anteil von $t/n$ der Wähler ausmacht, sollte sie im Ergebnis mit einem Anteil von $t/n$ am Budget vertreten sein. Nehmen wir für den Moment an, dass

$$\text{Kosten}(P_1) + \text{Kosten}(P_2) + \text{Kosten}(P_3) \leqslant \frac{t}{n} \cdot B,$$

wobei $B$ der Gesamthaushalt ist. Mit anderen Worten: Die Gruppe der Wähler ist groß genug, um es zu "verdienen", dass alle Projekte, für die sie gestimmt haben, finanziert werden. In diesem Fall kann man beweisen, dass die Methode der gleichen Anteile alle drei Projekte auswählt.

Formal lässt sich diese Eigenschaft wie folgt ausdrücken:

Satz. Sei $\{P_1, P_2, \ldots, P_k\}$ eine Menge von Projekten, und nehmen wir an, dass $t$ der $n$ Wähler für alle diese Projekte (und nur diese) gestimmt haben. Nehmen wir an, dass die Gesamtkosten dieser Projekte höchstens $t/n \cdot B$ betragen. Dann wird die Methode der gleichen Anteile alle $k$ Projekte auswählen.

Informationen über den Fall, dass die Projekte mehr als das Gesamtbudget kosten

Eine ähnliche Garantie kann man auch beweisen, wenn die Wählergruppe für eine Menge von Projekten stimmt, die insgesamt mehr als $t/n \cdot B$ kosten. Angenommen, $t$ Wähler stimmen genau für die Projekte $P_1$, $P_2$, $P_3$ und $P_4$. Nehmen wir an, dass

$$\text{Kosten}(P_1) + \text{Kosten}(P_2) + \text{Kosten}(P_3) + \text{Kosten}(P_4) > \frac{t}{n} \cdot B.$$

Dann wird die Methode der gleichen Anteile einige dieser Projekte auswählen, die zusammen "ungefähr" $t/n \cdot B$ kosten.

Satz. Sei $T = \{P_1, P_2, \ldots, P_k\}$ eine Menge von Projekten, und nehmen wir an, dass $t$ der $n$ Wähler für alle diese Projekte (und nur diese) gestimmt haben. Dann wählt die Methode der gleichen Anteile eine Teilmenge $T' \subseteq T$ von Projekten so aus, dass für jedes Projekt $P^* \in T$, das nicht von der Methode ausgewählt wurde, gilt, dass $\sum_{P \in T'} \text{Kosten}(P) + \text{Kosten}(P^*) > t/n \cdot B$.

Wählergruppen mit sich überschneidenden Stimmen

Bei den oben beschriebenen mathematischen Garantie wurde davon ausgegangen, dass alle Mitglieder der Wählergruppe für genau dieselben Projekte gestimmt haben. In der Praxis werden jedoch selbst Gruppen von Wählern mit starker Übereinstimmung nicht immer für genau dieselbe Gruppe von Projekten stimmen. Daher ist es interessant zu sehen, ob die Methode der gleichen Anteile Projekte auswählt, die von einer Gruppe von Wählern mit hoher, aber nicht perfekter Übereinstimmung unterstützt werden. Die Antwort ist ja: Wenn sich die Stimmen einer Gruppe von Wählern hinreichend stark überschneiden, dann wird die Methode der gleichen Anteile diese Gruppe repräsentieren.

Details der mathematischen Garantie

Betrachten wir eine Bürgerbudget-Wahl, die auf einer Zustimmungswahl beruht. Für eine Menge $T = \{P_1, P_2, \ldots, P_k\}$ von Projekten, schreiben wir $\text{Kosten}(T) = \text{Kosten}(P_1) + \text{Kosten}(P_2) + \ldots + \text{Kosten}(P_k)$ für die Gesamtkosten der Projekte in $T$. Angenommen, eine Gruppe von $t$ Wählern stimmt für alle Projekte in der Menge $T$, aber einige der Wähler stimmen auch für einige andere Projekte, die nicht in $T$ enthalten sind. Nehmen wir an, dass $\text{Kosten}(T)\leqslant t/n \cdot B$ (so dass sich die Wählergruppe alle Projekte in $T$ "leisten" kann, selbst wenn wir nur die Budgetanteile der Mitglieder der Gruppe betrachten). Dann garantiert die Methode der gleichen Anteile, dass mindestens einer dieser $t$ Wähler im Ergebnis $W$ hinreichend vertreten ist: Das bedeutet, dass es ein Mitglied $i$ der Gruppe gibt für das folgendes gilt: Sei $A_i$ die Menge der Projekt, für die $i$ gestimmt hat (wegen unserer Annahme, muss gelten, dass $T \subseteq A_i$)). Dann gilt

$$\text{Kosten}(A_i \cap W) \geqslant \text{Kosten}(T) - \text{Kosten}(P_i) \qquad \text{für ein $P_i \in T$}.$$

In dieser Formel steht $A_i \cap W$ für die Menge der gewinnenden Projekte, für die der Wähler $i$ gestimmt hat.

Diese Eigenschaft der Methode der gleichen Anteile ist in der Literatur bekannt als "extended justified representation up to one project". Mehr Details finden sich im Papier von Peters et al. (2021).

Andere grundlegende Kriterien für Wahlmethoden

Es gibt noch weitere grundlegende Kriterien für Wahlmethoden, die zwar keine "Fairness-Garantien" im obigen Sinne sind, aber dennoch erwähnenswert sind. Die folgenden Kriterien werden von der Methode der gleichen Anteile erfüllt:

• Berechenbarkeit in Polnomialzeit: Das Ergebnis der Methode der gleichen Anteile kann durch einen einfachen Algorithmus in polynomialer Zeit berechnet werden. So können die Gewinnerprojekte schnell ermittelt werden, in der Regel in weniger als einer Minute, selbst bei Wahlen in großen Städten.
• Unabhängigkeit von Klonen: Ein "Klon" von einem Projekt ist eine so-gut-wie identische Kopie eines Projektes, das schon auf dem Stimmzettel steht. Wir nehmen an, dass jeder Wähler entweder alle oder keinen der Klone eines Projektes unterstützt. Mit der Methode der gleichen Anteile gilt: Wenn ein Verliererprojekt geklont wird, gewinnt keiner der Klone; und wenn ein Gewinnerprojekt geklont wird, gewinnt mindestens einer der Klone.
• Monotonie: Wenn ein Projekt gewinnt und ein Wähler seinen Stimmzettel ändert, indem er jetzt zusätzlich auch für dieses Projekt stimmet, dann gewinnt dieses Projekt weiterhin.
• Rabatt-Monotonie: Wenn ein Projekt gewinnt, und wir jetzt die Kosten dieses Projektes reduzieren, dann wird es weiterhin gewinnen. Wenn ein Projekt nicht gewinnt, und wir dessen Kosten erhöhen, wird es weiterhin nicht gewinnen.
• Unabhängigkeit zu leeren Stimmzetteln: Wenn wir einen Wähler zur Wahl hinzufügen, der keines der Projekte befürwortet, ändert sich das Ergebnis nicht (vorausgesetzt, wir vervollständigen die Methode auf die übliche Weise).
• Generalisiert das D'Hondt-Verfahren: Die Methode der gleichen Anteile (mit Standard-Vervollständigung) ist eine Generalisierung des D'Hondt-Verfahrens (auch bekannt als Hagenbach-Bischoff-Verfahren) was in vielen Ländern zur Wahl von Parlamenten mit Verhältniswahlsystemen genutzt wird (z. B. in Österreich und in der Schweiz für den Nationalrat, und in Deutschland für die Landesparlamente in Niedersachsen, Sachsen und im Saarland). Das D'Hondt-Verfahren ist ein Spezialfall der Methode der gleichen Anteile, bei der die "Projekte" die Parlamentskandidaten sind, die Kosten jedes "Projekts" gleich 1 sind, das Budget der verfügbaren Anzahl von Sitzen entspricht und jeder Wähler für alle Mitglieder von genau einer Partei stimmt.

Mehrere andere Kriterien sind jedoch nicht erfüllt, darunter:

• Pareto-Optimalität
• Monotonie der Budgetgrenze (ein gewinnendes Projekt sollte auch dann noch gewinnen sein, wenn das verfügbare Budget erhöht wird)
• Strategiesicherheit (ein Wähler sollte nicht in der Lage sein, das Ergebnis durch Änderung seines Stimmzettels zu verbessern)