Technische Samenvatting: Proportionele Representatie in Rangorde-aggregatie

Probleemdefinitie

Het artikel behandelt het probleem van rangorde-aggregatie (rank aggregation), waarbij het doel is om een profiel van gewogen invoerrangordes samen te voegen tot één enkele uitvoerrangorde. In deze context bestaat een profiel $R$ uit een verzameling kandidaten $C$ en een functie die elke mogelijke rangorde $\succ$ koppelt aan een gewicht $R(\succ) \in [0, 1]$, zodanig dat de som van alle gewichten gelijk is aan 1. Deze gewichten vertegenwoordigen de belangrijkheid van verschillende criteria (bijv. prijs versus beoordeling bij een hotelboeking) of het aandeel stemmers dat een specifieke rangorde ondersteunt.

De centrale uitdaging is dat klassieke sociale welvaartsfuncties (Social Welfare Functions, SWFs), zoals de Kemeny-regel, Borda-telling en Condorcet-type regels, inherent majoritair zijn. Ze hebben de neiging om de uitvoerrangorde te selecteren die de afstand minimaliseert tot de hoogst gewogen invoerrangorde, waardoor minderheidsvoorkeuren effectief worden genegeerd. Bijvoorbeeld, als twee inverse rangordes gewichten hebben van 51% en 49%, geven standaard SWF's vaak simpelweg de 51%-rangorde terug, waardoor de 49%-groep niet wordt vertegenwoordigd. Het artikel streeft ernaar om SWF's te ontwerpen die proportionele representatie garanderen, waarbij elke invoerrangorde in verhouding tot zijn gewicht invloed heeft op de uitvoerrangorde.

Methodologie en Raamwerk

De auteurs formaliseren proportionaliteit door de utiliteit van een invoerrangorde $\succ$ voor een uitvoerrangorde $\triangleright$ te definiëren als het aantal paarwijze overeenkomsten tussen hen:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ en } x \triangleright y\}|$$
Aangezien er $\binom{m}{2}$ totale paarwijze vergelijkingen zijn voor $m$ kandidaten, zou een invoerrangorde met gewicht $\alpha$ idealiter een utiliteit moeten verkrijgen van ten minste $\lfloor \alpha \binom{m}{2} \rfloor$.

Het artikel introduceert een hiërarchie van proportionaliteitsaxioma's geïnspireerd door goedkeuringsgebaseerde commissieverkiezingen (approval-based committee voting) en participatieve budgettering:

1. Unanimous Justified Representation (uJR): Een verzwakking die vereist dat elke invoerrangorde met een gewicht $\ge 1/\binom{m}{2}$ ten minste één paarwijze overeenkomst verkrijgt.
2. Unanimous Proportional Justified Representation (uPJR): Het kernaxioma dat vereist dat een invoerrangorde met gewicht $\alpha$ een utiliteit verkrijgt van ten minste $\lfloor \alpha \binom{m}{2} \rfloor$.
3. Strong Proportional Justified Representation (sPJR): Een versterking die de garantie uitbreidt naar groepen van rangordes. Als een subprofiel $S$ een totaal gewicht $\alpha$ heeft, moet de uitvoer overeenkomen met ten minste $\lfloor \alpha \binom{m}{2} \rfloor$ paarwijze vergelijkingen uit de unie van de rangordes in $S$.

Om deze axioma's te bereiken, passen de auteurs het concept van prijsbaarheid (priceability) uit de participatieve budgettering aan. Ze modelleren de constructie van de uitvoerrangorde als een sequentieel aankoopproces waarbij kandidaten (of paren van kandidaten) worden "gekocht" met de budgetten van de invoerrangordes.

Belangrijkste Bijdragen en Resultaten

1. Beperkingen van Bestaande Methoden

Het artikel analyseert eerst de Gekwadrateerde Kemeny-regel (Squared Kemeny rule) (voorgesteld door Lederer et al. [2024] voor proportionele rangorde). De auteurs bewijzen dat de Gekwadrateerde Kemeny-regel voor $m \ge 5$ zelfs het zwakste axioma, uJR, faalt. Specifiek construeren zij profielen waar een invoerrangorde met een aanzienlijk gewicht nul utiliteit ontvangt van de Gekwadrateerde Kemeny-uitvoer, wat de noodzaak voor nieuwe mechanismen aantoont.

2. De Proportional Sequential Borda Rule (PSB)

Om uPJR te voldoen, stellen de auteurs de Proportional Sequential Borda rule (PSB) voor.

• Mechanisme: PSB werkt sequentieel. In elke ronde selecteert het de kandidaat die de gewogen Borda-score maximaliseert op basis van de huidige budgetten. Vervolgens wordt het budget van de invoerrangordes proportioneel bijgewerkt aan hun bijdrage aan de score van de geselecteerde kandidaat, waardoor effectief wordt "betaald" voor de plaatsing van de kandidaat.
• Theoretische Garantie: De auteurs introduceren een gestructureerd axioma genaamd rank-priceability, dat de prijsbaarheid in participatieve budgettering weerspiegelt. Zij bewijzen dat rank-priceability uPJR impliceert.
• Resultaat: Stelling 4.5 stelt vast dat PSB voldoet aan rank-priceability en daarmee ook aan uPJR.
• Kwantitatieve Garantie: Naast de axiomatische voldoening, bewijst Stelling 4.6 dat PSB voor elk subprofiel $S$ een gemiddelde utiliteit garandeert van ten minste $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$. Dit biedt een lineaire ondergrens voor de utiliteit relatief aan het gewicht van de groep.

3. De Flow-adjusting Borda Rule (FB)

De auteurs tonen aan dat PSB faalt voor sPJR omdat het betalingsschema niet adequaat bescherming biedt aan groepen rangordes die gezamenlijk optreden. Om dit aan te pakken, introduceren zij pair-priceability, een verfijnd axioma waarbij betalingen worden gedaan voor specifieke paren kandidaten in plaats van alleen voor rangen.

• Mechanisme: De Flow-adjusting Borda rule (FB) is een verfijning van PSB. Net als PSB selecteert FB de Borda-winnaar sequentieel. Echter, in plaats van een eenvoudige proportionele betaling, bepaalt FB de betalingen door een maximum flow probleem op te lossen in een geconstrueerd netwerk. Dit netwerk zorgt ervoor dat de kosten per utiliteitsratio worden geminimaliseerd, terwijl aan budgettaire en paarwijze beperkingen wordt voldaan.
• Resultaat: Stelling 5.5 bewijst dat FB voldoet aan pair-priceability, wat op zijn beurt sPJR impliceert (Stelling 5.3).
• Kwantitatieve Garantie: Stelling 5.6 laat zien dat FB dezelfde lineaire gemiddelde utiliteitsgarantie biedt als PSB ($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$), wat sterke eerlijkheid garandeert voor zowel individuen als groepen.

4. Aanvullende Varianten

In de appendix bespreken de auteurs de Ranked Method of Equal Shares (RMES), een variant geïnspireerd door de Method of Equal Shares (MES) uit de participatieve budgettering. Zij tonen aan dat RMES voldoet aan rank-priceability (en dus uPJR) en een iets ander utilitair profiel biedt, waarbij de eerste $\lfloor m/4 \rfloor$ kandidaten puur op basis van de initiële Borda-scores worden geselecteerd.

Betekenis en Claims

Het artikel claimt de eerste werkelijk proportionele sociale welvaartsfuncties voor rangorde-aggregatie te presenteren. De primaire betekenis ligt in:

• Bruggen Slaan Tussen Vakgebieden: Het slaagt erin diepe resultaten uit de goedkeuringsgebaseerde commissieverkiezingen en de participatieve budgettering (specifiek PJR en priceability) over te dragen naar het domein van rangorde-aggregatie.
• Een Openstaand Probleem Oplossen: Het lost het openstaande probleem op van het ontwerpen van SWF's die uPJR en sPJR voldoen, waar eerdere pogingen (zoals de Gekwadrateerde Kemeny-regel) in faalden.
• Axiomatische en Kwantitatieve Kracht: De voorgestelde regels (PSB en FB) voldoen niet alleen aan sterke axiomatische eerlijkheidscondities, maar bieden ook robuuste kwantitatieve garanties op de gemiddelde utiliteit voor elke groep stemmers, waardoor wordt gewaarborgd dat minderheidsvoorkeuren niet systematisch worden genegeerd.

De auteurs merken op dat hoewel hun werk zich richt op het aantal paarwijze overeenkomsten als de utiliteitsmetriek, dit een standaardbenadering is in de literatuur. Zij suggereren dat toekomstig onderzoek sterkere eerlijkheidsbegrippen (zoals EJR of core-stability) en algemenere utiliteitsfuncties kan verkennen die rekening houden met de variërende waarde van verschillende rangorde-posities.