Proportionality Degree in Participatory Budgeting

Diese Arbeit untersucht den Proportionalitätsgrad von Partizipativen Budgetierungsverfahren, insbesondere der Methode des gleichen Anteils (MES) und Phragmén's sequentieller Regel, und zeigt durch theoretische Grenzen sowie experimentelle Evaluation auf realen Datensätzen, dass beide Regeln trotz unterschiedlicher axiomatischer Eigenschaften quantitativ denselben Proportionalitätsgrad aufweisen.

Das Wesentliche

Stellen Sie sich vor, eine ganze Stadt möchte gemeinsam entscheiden, wie sie ihr Budget für neue Projekte ausgeben soll. Vielleicht soll ein neuer Spielplatz gebaut werden, eine Bibliothek renoviert oder ein Fahrradweg angelegt werden. Jeder Bürger kann seine Lieblingsprojekte wählen. Das Problem: Das Geld ist begrenzt, und nicht alle Wünsche können erfüllt werden. Wie stellt man sicher, dass die Entscheidung fair ist und nicht nur die lauteste Minderheit gewinnt?

Dies ist das Thema des vorliegenden Forschungsartikels. Die Autoren untersuchen zwei beliebte mathematische Methoden, um solche Entscheidungen zu treffen: die „Methode der gleichen Anteile" (Method of Equal Shares) und die „Phragmén-Regel".

Hier ist eine einfache Erklärung der Kernpunkte, verpackt in anschauliche Bilder:

1. Das Problem: Gerechtigkeit messen

Stellen Sie sich vor, Sie haben eine große Gruppe von Freunden, die gemeinsam eine Pizza bestellen wollen.

• Die axiomatiche Sichtweise (Die alte Art): Man fragt: „Erfüllt diese Regel eine bestimmte Regel?" (Ja/Nein). Es ist wie ein Lichtschalter: Entweder die Regel ist fair, oder sie ist es nicht.
• Die neue Sichtweise (Proportionalitätsgrad): Die Autoren fragen: „Wie gut ist die Fairness eigentlich?" Sie wollen ein Maßstab, der zeigt, wie viel Pizza eine kleine Gruppe von Freunden bekommt, wenn sie sich alle einig sind. Es ist wie ein Thermometer, das nicht nur „heiß/kalt" anzeigt, sondern die genaue Temperatur misst.

2. Die beiden Helden: Zwei verschiedene Wege zum gleichen Ziel

Die Forscher haben zwei Hauptkandidaten verglichen:

• Der „Gerechte Verteiler" (Methode der gleichen Anteile / MES):

  • Das Bild: Jeder Bürger bekommt am Anfang einen gleichen Geldbeutel. Wenn ein Projekt gewählt wird, zahlen die Unterstützer aus ihrem Geldbeutel. Wer weniger Geld hat, zahlt weniger.
  • Der Ruf: Diese Methode gilt als der „Goldstandard" für Gerechtigkeit. Sie erfüllt strenge theoretische Regeln, die garantieren, dass große Gruppen immer ihren Teil bekommen.

• Der „Zeit-Verteiler" (Phragmén-Regel):

  • Das Bild: Stellen Sie sich vor, jeder Bürger hat einen Wasserhahn, aus dem langsam Geld fließt (wie Wasser in einem Eimer). Sobald die Eimer einer Gruppe zusammen genau genug Wasser haben, um ein Projekt zu kaufen, wird dieses Projekt gewählt und die Eimer werden geleert.
  • Der Ruf: Diese Methode ist etwas „schlanker" und erfüllt nicht alle strengen Regeln des ersten Kandidaten. Man dachte lange, sie sei daher weniger fair.

3. Die große Überraschung: Gleiche Leistung, unterschiedlicher Weg

Das überraschende Ergebnis des Artikels ist: Beide Methoden sind fast gleich gut!

Obwohl der „Gerechte Verteiler" (MES) in der Theorie strengere Regeln erfüllt, zeigt die genaue mathematische Analyse (der „Proportionalitätsgrad"), dass beide Methoden in der Praxis fast identisch fair sind.

• Die Metapher: Stellen Sie sich zwei Läufer vor. Läufer A (MES) trägt einen schweren Rucksack mit strengen Regeln, während Läufer B (Phragmén) leicht läuft. Man dachte, Läufer A würde gewinnen. Aber am Ende laufen beide genau gleich schnell und kommen gleichzeitig ins Ziel. Die „Stärke" der Regeln von Läufer A macht ihn nicht schneller in Bezug auf das Endergebnis.

4. Der Vergleich mit dem „Gierigen" (Greedy Rule)

Es gibt eine dritte, sehr einfache Methode, die oft in der echten Welt verwendet wird: „Der Gierige".

• Das Bild: Er zählt einfach, welche Projekte die meisten Stimmen haben, und kauft so lange die beliebtesten, bis das Geld aus ist.
• Das Ergebnis: In den Experimenten mit echten Daten aus Städten hat sich gezeigt, dass dieser „Gierige" deutlich schlechter abschneidet als die beiden anderen. Er ignoriert kleine, aber einigende Gruppen komplett. Wenn 40 % der Leute ein Projekt wollen und 60 % ein anderes, aber das andere Projekt viel teurer ist, könnte der „Gierige" das teure Projekt wählen und die 40 % völlig leer ausgehen lassen. Die beiden fairen Methoden (MES und Phragmén) sorgen dafür, dass auch die 40 % ihren Anteil bekommen.

5. Was bedeutet das für die Praxis?

Die Forscher haben nicht nur theoretische Formeln aufgestellt, sondern auch echte Daten aus 100 verschiedenen Städten getestet.

• Das Fazit: Die beiden komplexeren Methoden (MES und Phragmén) funktionieren in der echten Welt hervorragend und sind viel fairer als die einfache „Meinungsmehrheit"-Methode.
• Die Nuance: Manchmal ist die Phragmén-Methode (der Zeit-Verteiler) sogar ein winziges bisschen besser als die MES-Methode, besonders wenn man das Budget am Ende noch einmal nachjustiert („mit Erschöpfung"). Aber der Unterschied ist so klein, dass beide als hervorragende Wahl gelten.

Zusammenfassung in einem Satz

Dieser Artikel zeigt uns, dass es in der Welt der fairen Budgetverteilung zwei verschiedene, aber gleich starke Helden gibt, die beide viel besser sind als die einfache Methode, nur das „Beliebteste" auszuwählen – und dass man sich bei der Wahl zwischen ihnen nicht allzu viele Sorgen machen muss, da beide fast das gleiche faire Ergebnis liefern.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Proportionality Degree in Participatory Budgeting" auf Deutsch:

1. Problemstellung

Das Paper untersucht das Partizipatorische Budgeting (PB), ein demokratisches Verfahren, bei dem Bürgerinnen und Bürger direkt über die Vergabe öffentlicher Mittel entscheiden. Der Fokus liegt auf der quantitativen Bewertung von Fairness, speziell auf dem Proportionalitätsgrad (Proportionality Degree).

Während die axiomatiche Forschung in diesem Bereich etablierte Konzepte wie Extended Justified Representation (EJR) und Proportional Justified Representation (PJR) verwendet, sind diese Eigenschaften binär (eine Regel erfüllt sie oder nicht). Der Proportionalitätsgrad hingegen ist ein quantitatives Maß, das angibt, wie gut eine kohäsive Gruppe von Wählern (eine Gruppe, die eine Menge von Projekten gemeinsam unterstützt) proportional zu ihrer Größe einen Anteil am Budget erhält. Bisher war dieser Grad für PB-Regeln weitgehend unerforscht, obwohl er in der verwandten Literatur zur Mehrheitswahl (Multi-Winner Voting) gut verstanden ist.

Das Ziel der Autoren ist es, eine systematische Untersuchung des Proportionalitätsgrads für die beiden populärsten PB-Regeln durchzuführen:

1. Method of Equal Shares (MES)
2. Phragmén's Sequential Rule

2. Methodik

Die Autoren kombinieren theoretische Beweise mit einer umfangreichen experimentellen Evaluation.

Theoretischer Ansatz

• Definitionen: Basierend auf der Definition von T-kohäsiven Gruppen (eine Gruppe von Wählern $V$, die eine Projektmenge $T$ gemeinsam unterstützt und deren Größe $|V|$ im Verhältnis zur Gesamtzahl der Wähler $n$ mindestens dem Kostenanteil der Projekte $cost(T)/B$ entspricht).
• Zielgröße: Der Proportionalitätsgrad $d_f(T)$ einer Regel $f$ für eine Menge $T$ ist definiert als die größte untere Schranke für den durchschnittlichen Zufriedenheitswert (Anzahl unterstützter Projekte) aller $T$-kohäsiven Gruppen.
• Analyse: Die Autoren leiten für MES und Phragmén enge obere und untere Schranken für diesen Grad her. Sie nutzen dabei Lemmas zur Begrenzung der maximalen Zahlung, die von Wählern einer kohäsiven Gruppe während des Algorithmus verlangt werden kann.

Experimenteller Ansatz

• Datensatz: Es wurden 100 reale PB-Datensätze aus der Pabulib-Bibliothek verwendet.
• Vergleichsregeln:
  • Method of Equal Shares (MES)
  • Phragmén's Sequential Rule
  • Varianten mit „Exhaustion" (Restbudget wird am Ende gierig vergeben)
  • Greedy Approval Rule (Sortierung nach Zustimmungszahlen, weit verbreitet in der Praxis)
• Methode: Da die Berechnung des Proportionalitätsgrads für alle Teilmengen exponentiell ist, wurde eine Stichprobenmethode angewendet. Für jede Teilmengengröße $k$ (bis 15) wurden 5.000 zufällige Projektmengen gezogen, die kohäsiven Gruppen identifiziert und deren durchschnittliche Zufriedenheit berechnet.

3. Wichtige Beiträge und Ergebnisse

Theoretische Ergebnisse

1. Identische Proportionalitätsgrade: Das überraschendste Ergebnis ist, dass MES und Phragmén denselben Proportionalitätsgrad aufweisen, obwohl sie sich axiomatic unterscheiden.
   • MES erfüllt EJR (stärkere Garantie).
   • Phragmén erfüllt nur PJR (schwächere Garantie), aber nicht EJR.
   • Ergebnis: Beide Regeln erreichen einen Proportionalitätsgrad von ungefähr $\frac{1}{2} \cdot \left( \frac{cost(T)}{\max_{t \in T} cost(t)} - 1 \right)$.
2. Schranken: Die Autoren leiten enge untere und obere Schranken her (bis auf kleine konstante Faktoren).
   • Theorem 1 & 4: Beide Regeln haben eine untere Schranke von $\approx \frac{1}{2} (\frac{cost(T)}{\max cost} - 1)$.
   • Theorem 2 & 5: Es werden konstruierte Instanzen gezeigt, die eine obere Schranke von $\approx \frac{1}{2} \frac{cost(T)}{\max cost}$ beweisen.
3. Allgemeine Schranke für EJR: Es wird gezeigt, dass jede Regel, die EJR erfüllt (unter der Annahme „ordinärer" Instanzen, wo kein Projekt extrem billig ist), mindestens denselben Grad wie Phragmén erreicht.

Experimentelle Ergebnisse

1. Leistung im Vergleich:
   • Sowohl MES als auch Phragmén (insbesondere mit Exhaustion) schneiden in der Praxis deutlich besser ab als die Greedy Approval Rule.
   • Die Greedy-Regel ist in den meisten Fällen die schlechteste Wahl für die Proportionalität.
2. MES vs. Phragmén:
   • In der Praxis zeigen beide Regeln sehr ähnliche Leistung.
   • Phragmén (insbesondere mit Exhaustion) performt in vielen Datensätzen sogar leicht besser als MES, obwohl MES theoretisch stärkere axiomatiche Garantien hat.
   • Die Ergebnisse bestätigen die theoretische These, dass beide Regeln quantitativ gleichwertig sind.

4. Signifikanz und Implikationen

• Überbrückung von Theorie und Praxis: Die Arbeit schließt die Lücke zwischen der binären axiomaticchen Analyse und der quantitativen Bewertung von PB-Regeln. Sie zeigt, dass eine Regel ohne EJR (Phragmén) quantitativ genauso gut proportionale Ergebnisse liefern kann wie eine Regel mit EJR (MES).
• Praktische Empfehlung: Da beide Regeln theoretisch und empirisch ähnlich gut abschneiden, aber Phragmén oft einfacher zu implementieren oder zu verstehen sein kann (oder in bestimmten Szenarien leicht besser performt), sind beide als faire Alternativen zur gierigen (greedy) Verteilung zu empfehlen.
• Optimalitätsvermutung: Die Autoren vermuten, dass beide Regeln optimal für das Problem des Proportionalitätsgrads sind, da sie eine obere Schranke für jede mögliche Regel herleiten (Theorem 6), die fast mit den unteren Schranken der beiden Regeln übereinstimmt.

Fazit: Das Paper etabliert den Proportionalitätsgrad als neues, wichtiges Maß für die Fairness im Partizipatorischen Budgeting. Es widerlegt die intuitive Annahme, dass stärkere axiomatiche Eigenschaften (wie EJR bei MES) automatisch zu einem höheren quantitativen Proportionalitätsgrad führen müssen, und zeigt stattdessen eine tiefe strukturelle Ähnlichkeit zwischen MES und Phragmén auf.