Proportionality Degree in Participatory Budgeting

Dit artikel introduceert en analyseert het proportionaliteitsgraad-concept voor participatief budgetteren, waarbij het aantoont dat de Method of Equal Shares en Phragmen's Sequentiële Regel ondanks verschillende axioma's vergelijkbare kwantitatieve proportionaliteit bieden, een bevinding die wordt ondersteund door uitgebreide experimenten op real-world datasets.

De kern

De Gerechtelijke Verdeling van het Gemeentebudget: Een Verhaal over Twee Regels

Stel je voor dat een stad een grote pot met geld heeft (het gemeentebudget) en een lange lijst met wensen van de burgers: een nieuw park, een zwembad, een bibliotheekrenovatie, of een straatverlichting. De burgers moeten samen beslissen welk deel van dat geld naar welk project gaat. Dit heet Participatief Budgetteren.

Het probleem? Er is niet genoeg geld voor alles. En niet iedereen is het eens. Sommige mensen willen het park, anderen het zwembad. Hoe zorg je ervoor dat de beslissing eerlijk is? Dat is precies waar dit onderzoek over gaat. De auteurs kijken naar twee specifieke manieren (regels) om die beslissing te nemen en vragen zich af: "Hoe goed zorgen deze regels ervoor dat grote groepen mensen ook daadwerkelijk krijgen wat ze willen?"

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het Probleem: De "Grote Groep"

Stel je voor dat 60% van de inwoners van een wijk allemaal graag een nieuw zwembad wil. Als de regels slecht zijn, kan het gebeuren dat die 60% toch niets krijgt, terwijl de overige 40% wel een klein parkje krijgt. Dat voelt onrechtvaardig.

In de wiskunde noemen we zo'n groep die het eens is over een set projecten een "cohesieve groep". De auteurs willen weten: Hoeveel van hun wensen krijgt zo'n groep minimaal gegarandeerd? Dit noemen ze de "Proportionaliteitsgraad" (of eerlijkheidsgraad).

2. De Twee Kampioenen

De auteurs vergelijken twee bekende regels die vaak worden gebruikt:

• De Methode van Gelijke Aandelen (MES):

  • De Analogie: Stel je voor dat iedereen een identiek tegoed op zijn rekening krijgt (bijvoorbeeld €10). Als een groep mensen samen genoeg geld heeft om een project te betalen, dan wordt het project aangekocht en wordt het geld van hun rekeningen afgeschreven.
  • Het idee: Iedereen betaalt eerlijk mee. Als je een project wilt, moet je je portemonnee openen.
  • Sterke punt: Deze methode is bekend om zijn strenge regels voor eerlijkheid.

• De Sequentiële Regel van Phragmén:

  • De Analogie: Stel je voor dat iedereen een emmertje heeft dat langzaam volloopt met water (geld) terwijl de tijd verstrijkt. Zodra een groep mensen samen genoeg water in hun emmertjes heeft om een project te betalen, wordt dat project gekocht en worden hun emmertjes leeggemaakt.
  • Het idee: Het is een race in de tijd. Wie het snelst genoeg "water" heeft verzameld, wint het project.
  • Sterke punt: Het werkt heel dynamisch en reageert snel op wensen.

3. De Grote Verrassing: Ze zijn even goed!

Vroeger dachten experts dat de Methode van Gelijke Aandelen (MES) de koning was, omdat hij wiskundig gezien strengere regels volgt. De Phragmén-regel werd gezien als iets minder streng.

Maar wat ontdekten de auteurs in dit papier?
Ze zijn qua "eerlijkheid" (proportionaliteitsgraad) precies even goed!

Het is alsof je twee verschillende auto's hebt:

• Auto A (MES) heeft een dure, ingewikkelde navigatie die perfect routes berekent.
• Auto B (Phragmén) heeft een simpele, snelle GPS.
  De auteurs ontdekten dat, als je kijkt naar hoe ver je uiteindelijk komt (hoeveel eerlijkheid je krijgt), beide auto's op exact hetzelfde punt aankomen. Het maakt niet uit welke route je neemt; de bestemming is even rechtvaardig.

4. De Praktijktest: Het Rekenen met Echte Data

De auteurs waren niet tevreden met alleen wiskundige formules. Ze namen 100 echte datasets van steden die al participatief budgetteren (zoals Warschau of Parijs) en lieten de computers de regels uittesten.

• De Vergelijking: Ze vergeleken de twee eerlijke regels met een simpele, domme regel: de "Gierige Regel".

  • De Gierige Regel: "Kijk maar naar welk project het populairst is (meeste stemmen) en koop dat. Dan de volgende, enzovoort."
  • Het resultaat: De Gierige Regel is vaak onrechtvaardig. Hij negeert kleinere groepen en geeft alleen aan de grootste meerderheid. De twee eerlijke regels (MES en Phragmén) deden het veel beter.

• De Nuance: Soms deed Phragmén het net iets beter dan MES, en soms andersom. Maar over het algemeen waren ze beide superieur aan de simpele "meeste stemmen" methode.

5. Wat betekent dit voor de burger?

Dit onderzoek is belangrijk voor twee redenen:

1. Vertrouwen: Het bewijst dat je niet per se de meest complexe wiskundige methode nodig hebt om eerlijk te zijn. De iets simpelere Phragmén-regel werkt net zo goed als de zware MES-regel.
2. Keuze voor gemeenten: Gemeenten kunnen nu met een gerust hart kiezen voor een van deze twee regels. Ze hoeven niet bang te zijn dat ze "onrechtvaardig" zijn. Ze weten nu dat ze, in tegenstelling tot de simpele "meeste stemmen" methode, echt zorgen dat grote groepen burgers ook daadwerkelijk een stukje van het budget krijgen.

Kortom:
Stel je voor dat je een taart moet verdelen. De "Gierige Regel" geeft de hele taart aan de persoon die het hardst schreeuwt. De Methode van Gelijke Aandelen en de Phragmén-regel zijn twee verschillende manieren om de taart in stukken te snijden. Dit onderzoek zegt: "Gebruik maar welke van de twee je wilt, ze verdelen de taart beide even eerlijk onder de groepen die het eens zijn." En dat is een groot succes voor de democratie.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Proportionality Degree in Participatory Budgeting" in het Nederlands.

Titel: Proportionaliteitsgraad in Participatief Budgetteren

Auteurs: Aris Filos-Ratsikas, Sreedurga Gogulapati, en Georgios Kalantzis.

---

1. Probleemstelling

Participatief budgetteren (PB) is een democratisch proces waarbij burgers direct invloed uitoefenen op de toewijzing van publieke middelen. Een centraal doel in dit domein is het waarborgen van fairness (eerlijkheid) en proportionaliteit: cohesieve groepen kiezers (groepen die unaniem een set projecten steunen) zouden een budgetaandeel moeten ontvangen dat evenredig is aan hun grootte.

Hoewel er veel theoretisch werk is gedaan over axioma's voor proportionaliteit (zoals Justified Representation (JR), Proportional Justified Representation (PJR) en Extended Justified Representation (EJR)), zijn deze eigenschappen binair: een regel voldoet er wel of niet aan. Dit biedt geen kwantitatief inzicht in hoe goed een regel proportionaliteit bereikt in de praktijk.

Het paper introduceert en bestudeert het concept van de proportionaliteitsgraad (proportionality degree) voor PB-regels. Dit is een kwantitatieve maatstaf die de maximale ondergrens definieert van de gemiddelde tevredenheid die een cohesieve groep kiezers kan garanderen, uitgedrukt in termen van de grootte van de groep en de kosten van de projecten. De focus ligt op twee populaire regels:

1. Method of Equal Shares (MES): Bekend om het voldoen aan het sterke axioma EJR.
2. Phragmén's Sequential Rule: Voldoet aan het zwakkere axioma PJR, maar niet aan EJR.

De kernvraag is: Hoe verhoudt de kwantitatieve proportionaliteitsgraad van deze regels zich tot elkaar, gezien hun verschillende axioma's?

2. Methodologie

De auteurs hanteren een tweeledige aanpak: theoretische analyse en uitgebreide experimentele evaluatie.

A. Theoretische Analyse

• Definities:
  • Een groep kiezers $V$ is $T$-cohesief als ze unaniem een set projecten $T$ steunen en de totale kosten van $T$ in verhouding staan tot de groepsgrootte ($\frac{\text{cost}(T)}{B} \leq \frac{|V|}{n}$).
  • De proportionaliteitsgraad $d_f(T)$ van een regel $f$ voor een set $T$ is de grootste waarde $g(T)$ zodat de gemiddelde tevredenheid van elke cohesieve groep minstens $\min(|T|, g(T))$ is.
• Bewijstechnieken:
  • Voor MES: De auteurs gebruiken een lemma om de maximale betaling van kiezers binnen een cohesieve groep te begrenzen tijdens de uitvoering van de regel. Ze construeren een bestelling van kiezers en analyseren de uitputting van hun budgetten om een ondergrens af te leiden.
  • Voor Phragmén: Ze maken gebruik van een potentiaalfunctie (gebaseerd op werk van Skowron voor meerwinnaarsverkiezingen) om de variatie in kredietbalansen binnen een groep kiezers te analyseren. Dit stelt hen in staat de gemiddelde uitgaven en dus de tevredenheid te begrenzen.
  • Boven- en ondergrenzen: Voor beide regels worden strakke onder- en bovengrenzen afgeleid (tot op kleine constante factoren).

B. Experimentele Evaluatie

• Dataset: 100 real-world instances uit de Pabulib bibliotheek.
• Regels getest:
  1. MES (Method of Equal Shares)
  2. Phragmén's Sequential Rule
  3. MES met uitputting (exhaustion)
  4. Phragmén met uitputting
  5. Greedy Approval (selecteert projecten op basis van goedkeuringsscore; vaak gebruikt in de praktijk).
• Methode: Omdat het berekenen van de proportionaliteitsgraad voor alle mogelijke subsets exponentieel is, wordt er random sampling gebruikt. Voor elke subsetgrootte $k$ (van 1 tot 15) worden 5000 subsets willekeurig geselecteerd. De gemiddelde proportionaliteitsgraad wordt berekend over deze steekproeven.

3. Belangrijkste Bijdragen en Resultaten

Theoretische Bevindingen

1. Gelijke Proportionaliteitsgraad: Het meest verrassende resultaat is dat MES en Phragmén's Sequential Rule dezelfde proportionaliteitsgraad hebben, ondanks dat MES het sterkere axioma EJR voldoet en Phragmén dit niet doet.
   • De afgeleide ondergrens voor beide regels is ongeveer:
     $$d(T) \geq \frac{1}{2} \left( \frac{\text{cost}(T)}{\max_{t \in T} \text{cost}(t)} - 1 \right)$$
   • De bovengrens is asymptotisch gelijk aan deze waarde.
2. Structuurvergelijking: Dit resultaat suggereert een diepere structurele gelijkenis tussen de twee regels, ondanks hun verschillende axioma's. Het impliceert dat het voldoen aan EJR niet noodzakelijk leidt tot een hogere kwantitatieve proportionaliteit in de ergste gevallen.
3. Algemene Bound voor EJR: De auteurs tonen aan dat elke regel die EJR voldoet, een vergelijkbare proportionaliteitsgraad heeft als MES, mits de projectkosten niet extreem verschillend zijn (in "ordinary" instances).

Experimentele Bevindingen

1. Superioriteit boven Greedy: Zowel MES als Phragmén (met en zonder uitputting) presteren in alle 100 datasets significant beter dan de Greedy Approval-regel op het gebied van proportionaliteitsgraad.
2. Prestatie van MES vs. Phragmén:
   • In de praktijk vertonen beide regels vergelijkbare prestaties.
   • Phragmén met uitputting presteert in de meeste datasets iets beter dan MES met uitputting.
   • Zelfs zonder uitputting presteert Phragmén vaak beter dan MES.
3. Uitputting (Exhaustion): Het gebruik van uitputting (het toewijzen van restbudget via een greedy-methode) verbetert de proportionaliteitsgraad voor beide regels, maar verandert de relatieve rangorde niet fundamenteel.

4. Betekenis en Conclusie

• Kwantitatief Inzicht: Het paper vult een belangrijke lacune in de literatuur door de eerste systematische studie van de proportionaliteitsgraad in PB te presenteren. Het verschuift de focus van "voldoet aan een axioma?" naar "hoe goed werkt het in de praktijk?".
• Praktische Implicatie: Hoewel MES theoretisch "sterker" is (EJR), biedt Phragmén's regel in termen van kwantitatieve proportionaliteit een even goede, en in sommige experimentele scenario's zelfs betere, oplossing. Dit ondersteunt het gebruik van Phragmén als een robuust alternatief in echte PB-toepassingen.
• Optimaliteit: De auteurs concluderen dat beide regels waarschijnlijk optimaal zijn voor dit probleem, aangezien ze een ondergrens bereiken die dicht bij een theoretisch maximum ligt dat voor elke PB-regel geldt.

Samenvattend bewijst dit werk dat de keuze tussen MES en Phragmén in participatief budgetteren minder een kwestie is van fundamentele superioriteit in proportionaliteit, en meer een kwestie van specifieke implementatievoorkeuren, aangezien beide regels opvallend vergelijkbare kwantitatieve garanties bieden.