Making Serial Dictatorships Fair

Dit artikel toont aan dat het gebruik van een Kemeny-rangschikking van prioriteiten de verwachte hoeveelheid gerechtvaardigde afgunst in een seriële dictatuur minimaliseert, en dat bij het versoepelen van bepaalde aannames een gewogen variant van deze rangschikking optimaal is.

De kern

Hier is een uitleg van het onderzoek van Adam Hamdan in simpel, alledaags Nederlands, met behulp van creatieve vergelijkingen.

De Kern: Een eerlijke rij opstellen voor een populaire feest

Stel je voor dat er een groot feest is met een beperkt aantal populaire cadeaus (bijvoorbeeld de beste stoelen, de coolste cadeaus of plekken in een populaire school). Er zijn veel mensen die deze cadeaus willen, maar er zijn er niet genoeg voor iedereen.

Om dit eerlijk te verdelen, gebruiken organisaties vaak een methode die "Seriale Dictatuur" (of Serial Dictatorship) heet. Het werkt als volgt:

1. Je maakt een lijst met de mensen in een willekeurige volgorde.
2. De eerste persoon op de lijst mag zijn favoriete cadeau kiezen.
3. De tweede persoon mag kiezen uit wat er nog over is.
4. Enzovoort, tot iedereen iets heeft.

Het probleem:
Deze methode is heel eerlijk in de zin dat niemand kan bedriegen (je zegt gewoon wat je wilt) en het is efficiënt (niemand krijgt iets dat hij niet wil, terwijl er nog iets beters over was). Maar het is niet altijd rechtvaardig in de ogen van de mensen.

Stel je voor dat Jan een heel hoge prioriteit heeft voor de beste stoel (bijvoorbeeld omdat hij ouder is of een speciale status heeft), maar hij staat als laatste op de lijst. Als de eerste persoon op de lijst die stoel kiest, is Jan boos. En dat is niet zomaar boosheid; het is "gerechtvaardigde jaloezie". Jan heeft namelijk het recht om die stoel te krijgen, maar hij heeft hem niet gekregen omdat hij te laat aan de beurt was.

De vraag die deze paper beantwoordt is: Hoe stellen we die lijst op, zodat er zo min mogelijk gerechtvaardigde jaloezie ontstaat?

De Oplossing: De "Kemeny-Regel" als een super-rekenmachine

De auteur zegt: "Als we de lijst willekeurig maken, is dat niet slim. We moeten de lijst opstellen op basis van de prioriteiten die er al zijn."

Hij gebruikt een slimme wiskundige methode uit de sociale keuzetheorie, genaamd de Kemeny-regel.

De analogie van de jury:
Stel je voor dat er 5 verschillende rechters zijn (de verschillende objecten/scholen) en ze moeten allemaal een ranglijst maken van de kandidaten (de mensen).

• Rechter A vindt dat Jan het best is.
• Rechter B vindt dat Piet het best is.
• Rechter C vindt dat Jan weer het best is, maar Piet minder.

Deze rechters zijn het niet eens. De Kemeny-regel is als een super-rekenmachine die probeert één enkele "hoofdlijst" te maken die het minst in strijd is met alle individuele lijsten van de rechters. Het zoekt de volgorde waarbij de meeste rechters het minst vaak moeten knikken en zeggen: "Nee, die persoon hoort eigenlijk hoger."

Het belangrijkste resultaat van het papier:
Als iedereen ongeveer dezelfde voorkeur heeft (bijvoorbeeld: iedereen wil de beste school, de tweede beste, enz.) en de objecten maar één plek hebben, dan is de Kemeny-regel de perfecte manier om de volgorde te bepalen. Het is de volgorde die de minste "gerechtvaardigde jaloezie" genereert.

Wat als de situatie ingewikkelder is?

Het papier gaat verder en zegt: "Oké, maar wat als het niet zo simpel is?"

1. Sommige cadeaus zijn populairder dan anderen:
   Stel dat er één super-cool cadeau is dat iedereen als eerste wil, en een saaie doos die niemand wil.

   • De oplossing: De volgorde moet dan zwaarder wegen voor de prioriteiten van dat populaire cadeau. Het is alsof je in de jury de mening van de rechter over het populaire cadeau meer laat meetellen dan die over de saaie doos. Dit noemt de auteur een "gewogen Kemeny-regel".

2. Iedereen heeft verschillende wensen:
   Stel dat niet iedereen hetzelfde wil. De ene wil de stoel, de ander wil de tafel.

   • De oplossing: Dan moet je de volgorde zo maken dat je rekening houdt met hoe groot de kans is dat iemand jaloers wordt. Als iemand heel laat aan de beurt komt, is de kans groter dat hij jaloers is op iemand die veel eerder was. De "gewichten" in de berekening passen zich hieraan aan.

3. Er zijn meerdere plekken (geen een-op-een):
   Stel dat de school niet 1 plek heeft, maar 10.

   • De oplossing: Als er veel plekken zijn, is de kans kleiner dat iemand jaloers is, omdat er nog ruimte is. De berekening moet dan weten hoeveel plekken er nog over zijn op het moment dat iemand aan de beurt komt.

Waarom is dit belangrijk?

In het echte leven gebruiken scholen, huisvestingsinstanties en ziekenhuizen vaak simpele, willekeurige lijsten of loterijen om plekken te verdelen. Dit is makkelijk, maar het zorgt voor veel onrechtvaardigheid (gerechtvaardigde jaloezie).

Deze paper zegt: "Je kunt de simpele, eerlijke methode (Seriale Dictatuur) behouden, maar door de volgorde slim te kiezen op basis van de bestaande regels (prioriteiten), kun je het systeem veel eerlijker maken zonder dat mensen kunnen bedriegen."

Samenvattend in één zin:
Het papier leert ons hoe we een lijst moeten maken voor het verdelen van knelpunten (zoals schoolplekken) door de mening van alle betrokkenen (de prioriteiten) te combineren tot één perfecte volgorde, zodat niemand zich onterecht benadeeld voelt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Making Serial Dictatorships Fair" van Adam Hamdan, geschreven in het Nederlands.

Titel: Het Fair Maken van Serial Dictatorships

Auteur: Adam Hamdan
Datum: 9 maart 2026

---

1. Probleemstelling

Het paper behandelt het probleem van prioriteitsgebaseerde toewijzing (bijvoorbeeld bij schoolkeuze, huisvesting of orgaandistributie). In deze context moeten objecten (scholen) worden toegewezen aan agenten (studenten) op basis van twee normatieve principes:

1. Efficiëntie: Geen enkele agent kan erop vooruitgaan zonder dat een ander erop achteruitgaat (Pareto-efficiëntie).
2. Fairness (Rechtvaardigheid): Het elimineren van "gerechtvaardigde jaloezie" (justified envy). Gerechtvaardigde jaloezie treedt op wanneer een agent $i$ een object $s$ prefereert boven zijn eigen toewijzing, maar een andere agent $j$ die $s$ heeft toegewezen gekregen, een lagere prioriteit heeft voor $s$ dan $i$.

Het centrale dilemma is dat er geen mechanisme bestaat dat zowel Pareto-efficiënt, strategiebestendig (strategyproof) en vrij van gerechtvaardigde jaloezie is. Serial Dictatorship (SD) is een populair mechanisme dat efficiënt en strategiebestendig is, maar vaak faalt in het elimineren van gerechtvaardigde jaloezie omdat de volgorde waarin agenten kiezen vaak arbitrair is en de object-prioriteiten negeert.

De onderzoeksvraag: Hoe kan een planner de volgorde van agenten in een SD-mechanisme optimaliseren, uitsluitend gebaseerd op de object-prioriteiten (die door wetgeving vastliggen en niet manipuleerbaar zijn), om de verwachte hoeveelheid gerechtvaardigde jaloezie te minimaliseren?

---

2. Methodologie en Model

Het paper gebruikt een standaard model voor prioriteitsgebaseerde matching:

• Agenten ($I$) en Objecten ($S$): Agenten hebben strikte voorkeuren over objecten; objecten hebben strikte prioriteitsordeningen over agenten.
• Serial Dictatorship (SD): Agenten worden in een specifieke volgorde $\rho$ geplaatst. De eerste agent kiest zijn favoriete beschikbare object, de tweede kiest uit de resterende, enzovoort.
• Doelfunctie: De planner kiest een volgorde $\rho$ die de verwachte waarde $E_P[N(\mu^{SD}_\rho)]$ minimaliseert, waarbij $N$ het aantal gevallen van gerechtvaardigde jaloezie is. De verwachting wordt genomen over de verdeling van de voorkeursprofielen $P$.
• Beperking: Om strategiebestendigheid te behouden, mag de keuze van $\rho$ niet afhangen van de gerapporteerde voorkeuren van de agenten, maar alleen van de bekende prioriteiten en de aannames over de verdeling van voorkeuren.

De kern van de analyse is het vertalen van het minimaliseren van jaloezie naar een rank aggregation probleem (rangschikking aggregatie), specifiek het vinden van een consensusrangschikking die het beste past bij de verschillende prioriteitslijsten van de objecten.

---

3. Belangrijkste Resultaten

A. Basisscenario: Identieke en Uniforme Voorkeuren

Stelling 1 (Theorem 1): Als alle agenten identieke voorkeuren hebben (die uniform willekeurig worden getrokken) en objecten een eenheidscapaciteit hebben (één plek per object), dan is de optimale volgorde voor SD de Kemeny-rangschikking van de agent-prioriteiten.

• Redenering: Bij identieke voorkeuren is jaloezie gegarandeerd. De enige variabele is of de jaloezie "gerechtvaardigd" is. Omdat elke object-prioriteit even waarschijnlijk is om een rol te spelen, moet elke schending van een paar-prioriteit ($i \succ_s j$) even zwaar wegen.
• Kemeny's Regel: De Kemeny-rangschikking is de rangschikking die de som van de paarwise onenigheden (Kendall tau-afstand) met de input-rangschikkingen minimaliseert. Hier betekent dit dat de planner de prioriteiten van alle objecten zo eerlijk mogelijk samenvoegt tot één ranglijst.

B. Uitbreidingen (Gewogen Kemeny-rangschikking)

Het paper toont aan dat als de aannames worden versoepeld, de optimale oplossing een gewogen Kemeny-rangschikking wordt, waarbij prioriteitsschendingen zwaarder wegen afhankelijk van de kans dat ze jaloezie veroorzaken.

1. Niet-uniforme verdeling van voorkeuren (Propositie 1):

   • Als sommige objecten systematisch populairder zijn (hogere kans om bovenaan de voorkeurslijst te staan), dan worden schendingen van de prioriteiten voor deze objecten zwaarder gewogen.
   • Het gewicht voor een schending $\rho(t') \succ_s \rho(t)$ is evenredig met de kans $p(s, t)$ dat object $s$ op positie $t$ in de voorkeursrangschikking verschijnt.

2. Onafhankelijke voorkeuren (Propositie 2):

   • Als agenten onafhankelijke voorkeuren hebben, is jaloezie niet langer gegarandeerd, maar neemt de kans op jaloezie toe naarmate het tijdsverschil tussen twee agenten in de SD-volgorde groter is.
   • De optimale gewichten $p(t', t)$ hangen af van het verschil in positie ($t' - t$) en de grootte van de resterende keuzeopties. Schendingen tussen agenten die ver uit elkaar staan in de volgorde wegen zwaarder.

3. Niet-eenheidscapaciteiten (Propositie 3):

   • Wanneer objecten meerdere plekken hebben (bijv. scholen met meerdere plaatsen), is de kans dat een latere agent jaloezie voelt afhankelijk van of het object al vol zit.
   • De gewichten worden complexer en houden rekening met: (i) de kans dat agent $\rho(t)$ object $s$ krijgt, en (ii) de kans dat object $s$ tussen stap $t$ en $t'$ vol raakt.

---

4. Kernbijdragen

1. Nieuwe Link tussen Matching en Social Choice: Het paper vestigt voor het eerst een directe theoretische link tussen het minimaliseren van gerechtvaardigde jaloezie in matching-problemen en de Kemeny-regel uit de sociale keuzetheorie.
2. Optimalisatie van SD: Het biedt een concrete, wiskundig onderbouwde methode om de "zwakke plek" van Serial Dictatorship (het gebrek aan fairness) te verhelpen zonder de voordelen (efficiëntie, strategiebestendigheid, eenvoud) op te offeren.
3. Gewogen Aggregatie: Het generaliseert de Kemeny-regel naar een context met ongelijke kansen en capaciteiten, wat resulteert in een flexibele "gewogen Kemeny-rangschikking" die adaptief is aan de specifieke context (prioriteiten, capaciteit, voorkeursverdeling).
4. Verband met Random Serial Dictatorship (RSD): Het paper toont aan dat RSD een speciaal geval is van de hier voorgestelde methode wanneer objecten geen prioriteiten hebben (alle prioriteiten zijn indifferent). In dat geval is elke volgorde een Kemeny-rangschikking, en wordt een willekeurige keuze gemaakt.

---

5. Significantie en Implicaties

• Praktische Toepasbaarheid: Het paper biedt een oplossing voor een langdurig probleem in het onderwijs en de publieke sector. Planners kunnen nu een SD-mechanisme gebruiken dat wettelijk verplichte prioriteiten respecteert en tegelijkertijd de kans op gerechtvaardigde jaloezie minimaliseert, zonder dat agenten hun voorkeuren hoeven te verdraaien.
• Theoretische Inzicht: Het illustreert hoe inzichten uit de rank aggregation literatuur (social choice) direct kunnen worden toegepast op mechanisme-design in de economie.
• Strategiebestendigheid: Door de volgorde te baseren op de verdeling van voorkeuren en niet op de gerapporteerde voorkeuren zelf, blijft het mechanisme strategiebestendig. Agenten hebben geen prikkel om hun voorkeuren te manipuleren om een betere plek in de SD-volgorde te krijgen.

Conclusie: Adam Hamdan demonstreert dat Serial Dictatorship, vaak gezien als een "ruwe" methode die prioriteiten negeert, kan worden geoptimaliseerd tot een zeer eerlijk mechanisme door de volgorde van keuzes slim af te stemmen op de onderliggende prioriteitsstructuren via de Kemeny-rangschikking.