💻 computer science

A General Theory of Proportionality with Additive Utilities

Dit artikel breidt de axioma's van proportionaliteit uit van approval-stembiljetten naar cardinale stembiljetten binnen een algemeen beperkt selectiemodel, waarbij nieuwe regels worden voorgesteld die proportionele uitkomsten waarborgen en proportionele rangschikkingen genereren voor toepassingen zoals participatieve budgettering en publieke besluitvorming.

Oorspronkelijke auteurs: Piotr Skowron

Gepubliceerd 2026-02-10

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Piotr Skowron

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een grootschalig gemeenschapsfestival organiseert. Je hebt een lijst met potentiële activiteiten (kandidaten), een groep buren (stemmers) en een beperkt budget (haalbaarheidsbeperkingen). Sommige activiteiten kosten meer dan andere, en sommige activiteiten kunnen simpelweg niet tegelijkertijd plaatsvinden (zoals een luid rockconcert en een rustige yogasessie in dezelfde tent).

Het doel is om een reeks activiteiten te kiezen die voor iedereen eerlijk voelt. Als een groep buren 20% van de menigte vertegenwoordigt en zij houden allemaal van een specifiek type muziek, dan zouden zij ook ongeveer 20% van de "muziektijd" van het festival moeten krijgen.

Dit artikel behandelt een zeer complexe versie van dit probleem: Wat als mensen niet alleen zeggen "Ik vind dit leuk" of "Ik vind dit niet leuk"? Wat als ze zeggen: "Ik vind dat rockconcert wel leuk, maar ik ben echt dol op dat jazzbandje"?

Hier is een uiteenzetting van de ideeën uit het artikel, uitgelegd met eenvoudige analogieën.

1. Het Probleen: De kloof tussen "Approval" en "Utility"

De meeste eerdere regels voor eerlijke selectie gingen ervan uit dat stemmers alleen een "Ja/Nee"-knop hadden (Approval).

Approval: "Ik vind het rockconcert leuk." (Waarde = 1)
Utility (de nieuwe uitdaging): "Ik vind het rockconcert een beetje leuk, maar de jazzband is mijn absolute favoriet." (Rock = 0,2; Jazz = 1,0).

Het artikel stelt dat het echte leven vol zit met deze "Utility"-voorkeuren. Zelfs als je voor een project stemt, kan het zijn dat je er meer om geeft als het $100 kost dan wanneer het $10 kost. De auteurs wilden regels bouwen die deze genuanceerde gevoelens kunnen verwerken, en niet alleen simpele "Ja/Nee"-stemmen.

2. Het Kernidee: Kandidaten kopen met "Virtueel Geld"

De auteurs stellen een systeem voor waarbij stemmers gedurende een bepaalde tijd virtueel geld verdienen, zoals een kraan die muntjes in hun zakken laat druppelen.

De Oude Manier (Phragmén's Regel): Zodra een groep mensen genoeg munten heeft om een kandidaat die zij leuk vinden te kopen, kopen ze deze onmiddellijk. Dit is een "hebzuchtige" (greedy) aanpak.
De Nieuwe Manier (PropRank & Equal Shares): De auteurs realiseerden zich dat het kopen van een kandidaat nu soms een slecht idee is. Misschien is het beter om 5 minuten te wachten, zodat je genoeg geld hebt om een betere kandidaat te kopen waar je nog veel meer van houdt.

De Analogie: Stel je voor dat je bij een all-you-can-eat buffet bent, maar dat je per minuut betaalt.

Greedy (Hebzuchtig): Je ziet een burger die je lekker vindt, dus je grijpt hem meteen.
Slim (De methode uit het artikel): Je ziet de burger, maar je weet dat er over 2 minuten een biefstuk wordt geserveerd. Je wacht. Je berekent: "Als ik mijn geld nu uitgeef aan de burger, mis ik misschien de biefstuk. Maar als ik wacht, kan ik de biefstuk krijgen, wat mij meer 'geluk' per dollar oplevert."

Het artikel introduceert een wiskundig mechanisme van "vooruitziendheid" (foresight). Het simuleert de toekomst om te beslissen: Is het de moeite waard om te wachten op een betere deal, of moet ik dit nu kopen?

3. De Twee Hoofdregels

A. PropRank (De "Tijdreizende" Selector)

Deze regel is ontworpen om een rangschikking te creëren (een lijst van de 1e plaats tot de laatste plaats) in plaats van alleen een definitieve lijst.

Hoe het werkt: Stemmers verdienen geld. Het algoritme kijkt naar elke kandidaft en vraagt: "Wie is bereid hiervoor te betalen, en tegen welke prijs?"
De Twist: Het koopt niet alleen het goedkoopste ding. Het berekent een "prijs per eenheid geluk". Als een kandidaat duur is maar een groep stemmers enorm veel vreugde geeft, kan het in termen van geluk "goedkoper" zijn dan een goedkope, saaie kandidaat.
Het Resultaat: Het produceert een eerlijke lijst waarbij elk bovenste deel van de lijst (de "prefix") op zichzelf een eerlijk comité vormt.

B. De Methode van Gelijke Delen (The Method of Equal Shares - De "Budgetallocator")

Dit is een agressievere versie. In plaats van het geld langzaam te laten druppelen, geeft het iedereen vooraf een groot deel van het virtuele geld en laat het hen dit uitgeven.

De Innovatie: De auteurs hebben deze methode, die voorheen alleen werd gebruikt voor eenvoudige budgettering, geleerd hoe het met complexe beperkingen moet omgaan (zoals "we kunnen niet zowel het rockconcert als de yogales hebben").
Hoe het met beperkingen omgaat: Als het algoritme probeert een set kandidaten te kopen die de regels overtreedt (bijv. het budget overschrijdt of de "geen rock/yoga samen"-regel schendt), stopt het, berekent het opnieuw en vindt het de beste haalbare deelverzameling om te kopen.

4. De "Heuristieken" (De Slimme Shortucts)

De auteurs ontdekten dat hun perfecte wiskundige regels soms geld "achterlieten" (stemmers hadden geld over dat ze niet hadden uitgegeven). Om dit op te lossen, creëerden ze "heuristiek" (slimme gok) versies:

PropRankRem: Als een kandidaat uit de lijst wordt verwijderd (omdat hij te duur is of conflicteert met anderen), drukt het algoritme op "Reset". Het zegt tegen de stemmers: "Oké, vergeet die kandidaat. Laten we het uitgavenplan zonder hem opnieuw starten." Dit voorkomt dat stemmers geld oppotten in afwachting van een kandidaat die nooit gekozen zal worden.
Backtracking: Dit is als het spelen van een videogame. Het algoritme probeert een pad. Als het vastloopt, gaat het een paar stappen terug, verandert van gedachten over voor welke kandidaten het zou moeten wachten, en probeert het opnieuw. Dit is langzamer, maar vindt vaak een veel perfectere oplossing.

5. Wat Hebben Ze Gevonden? (De Resultaten)

De auteurs hebben hun regels getest op echte gegevens uit Participatory Budgeting (waarbij echte steden burgers laten stemmen over hoe ze publiek geld kunnen uitgeven).

De "Wacht"-factor: Ze ontdekten dat het instellen van de "wacht"-parameter (genoemd $\kappa$ ) op 1 (wat betekent dat stemmers zeer bereid zijn te wachten op betere deals) het beste werkte voor de eerlijkheid.
Eerlijkheid vs. Geluk: Hun nieuwe regels waren ongelooflijk eerlijk. Ze overtraden zelden de eerlijkheidsregels (genaamd Extended Justified Representation).
Vergelijking:
- De Greedy methode (gewoon de populairste dingen kiezen) was efficiënt maar oneerlijk voor kleinere groepen.
- De Nieuwe Regels (PropRank en Equal Shares) waren veel eerlijker voor diverse groepen stemmers, waardoor de voorkeuren van minderheden daadwerkelijk werden vertegenwoordigd, in plaats van alleen de favorieten van de meerderheid.
- De Heuristische versies (met de "Reset" en "Backtrack" functies) presteerden bijna perfect, waarbij ze resultaten creëerden met bijna nul eerlijkheidsfouten.

Samenvatting

Het artikel zegt: "We hebben een nieuwe manier gebouwd om groepsbeslissingen te nemen die respect heeft voor hoeveel mensen iets echt leuk vinden, niet alleen of ze het leuk vinden of niet. Door een 'virtueel geld'-systeem te gebruiken dat stemmers aanmoedigt om te wachten op de beste 'geluk-per-dollar'-deals, kunnen we eerlijkere uitkomsten creëren voor complexe situaties, zoals gemeentelijke budgetten of commissie-selecties, waarbij niet alles gekozen kan worden."

Ze bewezen wiskundig dat deze regels eerlijk zijn, en testten ze op echte data om aan te tonen dat ze beter werken dan oudere methoden.

Technische Samenvatting: Een Algemene Theorie van Proportionaliteit met Additieve Nuten

1. Probleemstelling

Het artikel behandelt het probleem van het selecteren van een haalbare deelverzameling van kandidaten uit een verzameling $C$ op basis van kiezersvoorkeuren, onder algemene haalbaarheidsrestricties gedefinieerd door een familie van deelverzamelingen $\mathcal{F} \subseteq 2^C$ . Dit raamwerk generaliseert verschillende gevestigde modellen in de sociale keuzetheorie, waaronder:

Commissieverkiezingen: Het selecteren van een vast aantal kandidaten.
Participatieve budgettering (PB): Het selecteren van projecten binnen een totaal budget.
Publieke besluitvorming en oordeelsaggregatie: Beslissingen nemen over meerdere onafhankelijke kwesties.
Diversiteitsrestricties: Het waarborgen van specifieke structurele eigenschappen (bijv. genderbalans) in de geselecteerde set.

Hoewel axioma's van proportionaliteit (zoals Justified Representation) voor dit algemene model zijn gedefinieerd, zijn bestaande regels primair ontworpen voor goedkeuringsstembiljetten (waarbij kiezers een nut van 0 of 1 toekennen). Het artikel richt zich op de complexere setting van additieve nuten, waarbij elke kiezer $i$ een numeriek nut $u_i(c) \geq 0$ toekent aan elke kandidaat $c$ . Het doel is om regels te ontwerpen die zorgen voor eerlijke representatie van cohesieve groepen kiezers onder deze algemene restricties en kardinale nuten.

2. Methodologie

De auteurs stellen twee primaire algoritmische benaderingen voor, geïnspireerd door het concept van kiezers die kandidaten "kopen" met virtuele valuta.

2.1 De PropRank-regel

PropRank is een sequentiële regel, geïnspireerd door de Phragmén sequentiële regel, maar aangepast voor additieve nuten.

Mechanisme: Kiezers verdienen virtueel geld tegen een constante snelheid over de tijd. De regel simuleert een aankoopproces waarbij kiezers beslissen hoeveel ze aan kandidaten willen uitgeven.
Vooruitziend vermogen (Foresight Mechanism): In tegenstelling tot standaard hongerige (greedy) benaderingen, anticiperen kiezers in PropRank op toekomstige mogelijkheden. Ze berekenen een "schaalfactor" $\lambda_i$ op basis van de best mogelijke betaling-tot-nut ratio die zij zouden kunnen bereiken als zij zouden wachten op een meer wenselijke kandidaat die betaalbaar wordt.
Uitgavenfunctie: Een kiezer $i$ stemt ermee in om maximaal $x_i(c, r)$ uit te geven aan kandidaat $c$ in ronde $r$ , gedefinieerd door een formule die de huidige budget, het nut van de kandidaat en de schaalfactor bevat. Dit zorgt ervoor dat de betaling-tot-nut ratio niet de beste fractionele aankoop overschrijdt.
Rangschikking: Het algoritme construeert een volledige rangschikking van kandidaten op basis van hun aankoop-tijdstempels. Omdat onhaalbare kandidaten niet tijdens het proces worden verwijderd (alleen aan het einde van de constructie van de rangschikking voor specifieke commissiegroottes), voldoet elke prefix van de rangschikking aan de proportionaliteit.

2.2 Gegeneraliseerde Methode van Gelijke Delen (MES)

De auteurs breiden de Methode van Gelijke Delen (oorspronkelijk voor PB) uit naar algemene restricties.

Structuur: Het algoritme werkt in ronden. In elke ronde bepaalt het het maximale bedrag aan geld dat aan kiezers kan worden toegewezen zodat de "Equal Shares" subprocedure een set kandidaten kan kopen zonder de haalbaarheidsrestricties te schenden.
Vooruitzien in MES: Vergelijkbaar met PropRank bevat de gegeneraliseerde MES een mechanisme voor vooruitziend vermogen. Het berekent bovengrenzen voor uitgaven ($capi$) om te voorkomen dat kiezers te vroeg uitgeven aan kandidaten die minder efficiënt zouden kunnen zijn dan de kandidaten die in toekomstige iteraties beschikbaar komen.
Backtracking Heuristieken: Het artikel introduceert heuristische varianten (PropRankRem, PropRankBacktrack) die de procedure herstarten of terugkeren (backtrack) wanneer kandidaten worden verwijderd, met als doel ongebruikte budgetten te verminderen en de praktische prestaties te verbeteren, hoewel deze de theoretische garanties van de basisregels missen.
Bounded Overspending (BOS): Een adaptatie van de BOS-methode wordt voorgesteld voor algemene restricties, waarbij het algoritme de grootste geldige tijdstempel identificeert voor aankoop voordat de haalbaarheid wordt geschonden.

3. Belangrijkste Bijdragen

3.1 Theoretisch Raamwerk

Proportionaliteitsaxioma's voor Additieve Nuten: Het artikel generaliseert axioma's zoals Extended Justified Representation (EJR) en Proportional Justified Representation (PJR) naar de additieve nut-setting met algemene restricties.
Proportionaliteitsgraad: De auteurs definiëren en analyseren de "proportionaliteitsgraad", die de gemiddelde tevredenheid van een cohesieve groep kwantificeert. Ze stellen de relatie tussen EJR en de proportionaliteitsgraad vast, waarbij zij aantonen dat voor algemene restricties de garantie afhangt van de grootte van de cohesieve groep ( $\gamma = |S|/n$ ).

3.2 Theoretische Garanties

PropRank Garanties:
- Voor Participatieve Budgettering restricties, voldoet PropRank aan een proportionaliteitsgraad van $d(\alpha) = (\alpha - u_{max})/2$ .
- Voor Algemene restricties, voldoet het aan een graad van $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$ .
- Voor Matroïde restricties, voldoet het aan een zwakke proportionaliteitsgraad van $(\alpha - u_{max})/2$ .
PJR Garanties: De regels voldoen aan PJR-graad garanties van $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$ , waarbij $\kappa$ een parameter is die de flexibiliteit van de uitgaven controleert.

3.3 Algoritmische Uitbreidingen

Het artikel biedt de eerste generalisatie van de Methode van Gelijke Delen naar willekeurige haalbaarheidsrestricties met additieve nuten.
Het introduceert heuristieken (PropRankRem, PropRankBacktrack) om het probleem van ongebruikte budgetten in praktische scenario's aan te pakken.

4. Experimentele Resultaten

De auteurs evalueerden hun regels op meer dan 1.300 reële participatieve budgetteringsinstanties uit de Pabulib-dataset.

Metrieken: De evaluatie was gebaseerd op EJR+ schendingen (proportionaliteit), de Exclusieratio (fractie van kiezers met nul nut) en de Gemiddelde Kosten-Tevredenheid (utilitaire efficiëntie).
Bevindingen:
- $\kappa$ Parameter: De experimenten geven aan dat PropRank met $\kappa = 1$ (wat meer flexibele uitgaven toestaat) aanzienlijk beter presteert wat betreft proportionaliteit (minder EJR+ schendingen) dan $\kappa = 0$ .
- Heuristieken: De heuristische varianten (PropRankRem, PropRankBacktrack) gecombineerd met $\kappa = 0$ vertoonden zeer weinig EJR+ schendingen en gunstige exclusieratio's, en presteerden vaak beter dan de basisversie van PropRank op praktische metrieken, ondanks het gebrek aan formele bewijzen voor deze specifieke heuristieken.
- BOS Adaptatie: De aangepaste Methode van Gelijke Delen met Bounded Overspending presteerde uitzonderlijk goed, waarbij het de oorspronkelijke BOS-PB overtrof in EJR+ schendingen en er even goed naar was in exclusieratio en nut. Het werd ook opgemerkt als de meest computationeel efficiënte methode onder de voorgestelde technieken.
- Vergelijking: De voorgestelde regels bereikten over het algemeen een kosten-tevredenheid die vergelijkbaar met of beter is dan bestaande PB-specifieke regels (MES-PB, BOS-PB), terwijl ze algemene restricties afhandelden.

5. Betekenis en Claims

Het artikel claimt een algemene theorie van proportionaliteit te bieden die de kloof overbrugt tussen specifieke modellen (zoals commissieverkiezingen en PB) en het bredere landschap van beperkte selectieproblemen.

Generalisatie: Het toont aan dat gevestigde methoden (Phragmén en Equal Shares) kunnen worden uitgebreid naar willekeurige haalbaarheidsrestricties en additieve nuten zonder hun kernkenmerken van proportionaliteit te verliezen.
Rangschikking: Een belangrijke bijdrage is het vermogen om proportionele rangschikkingen te genereren (waarbij elke prefix een proportionele commissie is) in de setting van additieve nuten, waarmee een gat in de literatuur wordt gedicht.
Praktische toepasbaarheid: Hoewel de theoretische garanties sterk zijn, merken de auteurs bescheiden op dat heuristische varianten, die een deel van de theoretische traceerbaarheid opofferen voor betere praktische prestaties (het verminderen van ongebruikt budget), zeer effectief zijn in reële instanties.
Beperkingen: Het artikel erkent dat de bewijstechnieken voor de basisalgoritmen niet direct vertaalbaar zijn naar de heuristische varianten, en dat de computationele complexiteit van de backtracking-heuristieken exponentieel kan zijn (wat wordt getemperd door een parameter $\sigma$ ).

Samenvattend legt dit werk een robuuste theoretische basis voor proportionele representatie onder algemene restricties en additieve nuten, waarbij zowel bewijsbaar eerlijke algoritmen als praktische heuristieken worden aangeboden die goed presteren op reële data.