📈 economics

The Distribution of Envy in Matching Markets

Dit artikel analyseert de verdeling van jaloezie in willekeurige toewijzingsmarkten onder het Deferred Acceptance-algoritme en vergelijkt deze met Random Serial Dictatorship, waarbij wordt vastgesteld dat het verwachte aantal agenten dat niet wordt benijd in beide gevallen gelijk is aan het n-de harmonische getal, maar dat dit een verwaarloosbaar klein deel van de markt uitmaakt.

Oorspronkelijke auteurs: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

Gepubliceerd 2026-03-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

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

De Verdeling van Jaloezie in een Willekeurige Matchingsmarkt: Een Simpele Uitleg

Stel je voor dat je een grote schoolkeuze organiseert. Je hebt duizenden leerlingen en duizenden scholen. Iedere leerling heeft een lijstje met hun favoriete scholen, en elke school heeft een lijstje met de leerlingen die ze het liefst willen (hun prioriteiten). De vraag is: hoe verdelen we de leerlingen eerlijk over de scholen zonder dat er te veel jaloezie ontstaat?

In dit onderzoek kijken de auteurs naar twee specifieke soorten "gelukkige" leerlingen in een willekeurige situatie, waarbij ze een beroemde methode gebruiken genaamd Deferred Acceptance (DA). Laten we dit uitleggen met een paar alledaagse vergelijkingen.

1. Wat is "Jaloezie" in dit verhaal?

In de wereld van schoolkeuzes betekent jaloezie het volgende:

Leerlingen die niemand benijdt: Dit zijn leerlingen die op een school zitten waar niemand anders graag zou willen zitten. Niemand kijkt naar hen en denkt: "Ik wil daar ook zitten." Ze zijn als het ware "onbelangrijk" voor de rest.
Leerlingen die niemand benijdt: Dit zijn leerlingen die precies op hun favoriete school zitten. Zij kijken naar niemand anders en denken: "Ik ben blij met wat ik heb."

De auteurs willen weten: hoeveel van deze leerlingen zijn er eigenlijk?

2. De Grote Vergelijking: De "Couponverzamelaar"

Om te begrijpen hoeveel leerlingen op een school zitten waar niemand anders wil, gebruiken de auteurs een slimme vergelijking met het Couponverzamelaarsprobleem.

De Analogie: Stel je voor dat je een verzameling van $n$ verschillende stickers (scholen) probeert te verzamelen. Je krijgt willekeurige stickers uit een doos. Hoeveel keer moet je trekken voordat je elke sticker hebt?
De Koppeling: Het blijkt dat het aantal scholen dat "niet populair" is (waar maar één leerling op zit en niemand anders om geeft), precies overeenkomt met het aantal stickers dat je in het laatste stadium van verzamelen nog maar één keer hebt gezien.
Het Resultaat: Wiskundig gezien is dit aantal heel klein. Het groeit heel langzaam naarmate de markt groter wordt. Voor een markt van 10.000 leerlingen zijn er gemiddeld minder dan 10 leerlingen die door niemand worden benijd.
- Kortom: In een grote markt zijn er bijna geen leerlingen die "niet belangrijk" zijn. Iedereen zit op een school waar minstens iemand anders ook graag zou willen zitten.

3. De Gelukkigen: Leerlingen die hun Topkeuze Krijgen

Nu kijken we naar de leerlingen die hun allerbeste keuze krijgen (zij die niemand benijden).

De Wiskunde: De auteurs ontdekken dat het aantal gelukkigen ongeveer gelijk is aan het totale aantal leerlingen ( $n$ ) gedeeld door een getal dat heel langzaam groeit (de "Harmonische reeks", ongeveer gelijk aan de natuurlijke logaritme van $n$ ).
De Vergelijking: Als je 10.000 leerlingen hebt, krijgt ongeveer 1.100 van hen hun topkeuze. Dat klinkt als veel, maar het is nog steeds maar een klein deel van de totale groep (ongeveer 11%).
De Conclusie: De meeste leerlingen krijgen niet hun favoriete school, maar wel een school die redelijk goed is.

4. De Verrassende Vergelijking: DA vs. "Willekeurige Loterij"

De auteurs vergelijken hun methode (DA) met een heel andere methode: Random Serial Dictatorship (RSD).

RSD (De Loterij): Stel je voor dat je een willekeurige volgorde trekt. De eerste leerling mag zijn favoriete school kiezen, de tweede de volgende beste, enzovoort.
Het Verschil: Bij de loterij (RSD) krijgt ongeveer de helft van de leerlingen (50%) hun topkeuze. Bij de DA-methode is dat maar ongeveer 11%. De DA-methode is dus veel slechter voor het aantal "topkeuzes".

Maar hier komt de verrassing:
Hoewel DA veel minder leerlingen hun topkeuze geeft, is het aantal leerlingen die door niemand worden benijd bij beide methoden exact hetzelfde!

Bij DA: ongeveer $\log(n)$ leerlingen.
Bij RSD: ook ongeveer $\log(n)$ leerlingen.

Dit is als twee verschillende bakkers die heel verschillend brood bakken (de ene heeft veel boter, de andere weinig), maar beide bakkers hebben precies hetzelfde aantal broden dat "niet verkocht wordt" omdat niemand er zin in heeft. Dit suggereert dat dit kleine aantal "onbelangrijke" plekken een fundamenteel kenmerk is van elke willekeurige markt, en niet per se een fout van de methode.

Samenvatting in Eenvoudige Taal

Weinig onbelangrijke plekken: In een grote markt zijn er bijna geen scholen die niemand wil. Iedere school heeft minstens één leerling die er graag zou willen zitten.
Weinig topkeuzes: De meeste leerlingen krijgen niet hun favoriete school, maar een goede tweede of derde keuze.
De verrassing: Of je nu een slim algoritme gebruikt (DA) of een simpele loterij (RSD), het aantal leerlingen dat door niemand wordt benijd is altijd even klein. Het is een onvermijdelijk gevolg van de wiskunde van grote groepen.

De Les:
Hoewel we hopen dat iedereen zijn droomschool krijgt, laat dit onderzoek zien dat in een grote, willekeurige markt, het onmogelijk is om iedereen tevreden te stellen. Maar goed nieuws: er zijn ook bijna geen leerlingen die op een school zitten waar "niemand anders" wil. Iedereen zit op een plek waar minstens iemand anders ook graag zou willen zijn.

Titel: De Distributie van Afgunst in Matching Markten

Auteurs: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao.

1. Probleemstelling

Het artikel onderzoekt de verdeling van "afgunst" (envy) in willekeurige tweezijdige matching markten (zoals schoolkeuzesystemen) onder het Deferred Acceptance (DA) algoritme.

Hoewel stabiele matchings per definitie geen "gebaseerde afgunst" (justified envy) kennen, is het minder duidelijk hoe vaak studenten überhaupt afgunstig zijn op anderen, ofwel of ze zelf door niemand worden benijd. De auteurs richten zich op twee specifieke groepen studenten:

Studenten die door niemand worden benijd: Studenten die toegewezen zijn aan een school die door geen enkele andere student wordt geprefereerd boven hun eigen toewijzing (in de context van de DA-uitkomst).
Studenten die niemand benijden: Studenten die toegewezen zijn aan hun absolute topkeuze.

Het begrijpen van de grootte van deze groepen is cruciaal voor drie redenen:

Efficiëntie: DA produceert niet per se een Pareto-efficiënte uitkomst. Het is belangrijk om te weten hoeveel studenten "onverbeterbaar" zijn (d.w.z. ze kunnen niet beter worden gemaakt door ruil).
Welvaart: Studenten die niemand benijden, hebben hun topkeuze gekregen. Dit is een belangrijke welvaartsmaatstaf voor beleidsmakers.
Pareto-verbeteringen: Studenten die in een van deze twee categorieën vallen, vormen een ondergrens voor het aantal studenten dat niet kan worden verbeterd vanuit de DA-uitkomst.

De analyse vindt plaats in een model met $n$ studenten en $n$ scholen, waarbij voorkeuren en prioriteiten onafhankelijk en uniform willekeurig zijn getrokken.

2. Methodologie

De auteurs combineren toegepaste waarschijnlijkheidstheorie met specifieke eigenschappen van het DA-algoritme.

Sequentiële Implementatie: Ze gebruiken de sequentiële implementatie van DA zoals beschreven door McVitie en Wilson (1971), waarbij ongehuwde studenten één voor één hun volgende voorkeurschool aanvragen.
Principe van Uitgestelde Beslissingen (Principle of Deferred Decisions): In plaats van alle voorkeurslijsten vooraf te genereren, worden de voorkeuren "on the fly" gegenereerd tijdens de uitvoering van het algoritme. Dit wordt gemodelleerd als een oneindige reeks willekeurige trekkingen uit de set scholen.
Koppeling met het "Coupon Collector Problem":
- Voor de groep "door niemand benijd" maken ze een directe link met het klassieke probleem van het verzamelen van coupons. Een school wordt "onder-vraag" (under-demanded) als deze slechts één keer wordt aangevraagd in de reeks van alle trekkingen tot het algoritme stopt.
- Voor de groep "die niemand benijden" gebruiken ze asymptotische benaderingen gebaseerd op de verdeling van het aantal aanvragen per student, wat leidt tot een geometrische verdeling.
Vergelijking met RSD: De resultaten worden vergeleken met Random Serial Dictatorship (RSD), een mechanisme waarbij studenten in een willekeurige volgorde hun favoriete beschikbare school kiezen.

3. Belangrijkste Resultaten

A. Studenten die door niemand worden benijd (Under-demanded schools)

Exacte Formule: De verwachte aantallen studenten die door niemand worden benijd, wordt gegeven door het $n$ -de harmonische getal:
$NEn = H_n = \sum_{k=1}^n \frac{1}{k}$
Asymptotisch Gedrag: Omdat $H_n \approx \ln(n) + \gamma$ , groeit dit aantal slechts logaritmisch met de marktgrootte $n$ .
Conclusie: Het aandeel van deze studenten in de totale markt ( $H_n / n$ ) nadert 0 als $n \to \infty$ . Voor een markt van 10.000 studenten wordt er bijvoorbeeld verwacht dat er minder dan 10 studenten zijn die door niemand worden benijd.
Uniciteit: Dit resultaat is exact voor elke eindige $n$ , niet alleen asymptotisch.

B. Studenten die niemand benijden (Top-choice assignments)

Asymptotische Benadering: De kans dat een student bij de $k$ -de poging wordt toegewezen, volgt een geometrische verdeling met parameter $1/H_n$ .
Verwacht Aantal: Het verwachte aantal studenten dat zijn topkeuze krijgt, wordt benaderd door:
$EN_n \approx \frac{n}{H_n}$
Conclusie: Hoewel dit aantal veel groter is dan het aantal "onbenijde" studenten, is het nog steeds een klein fractie van de totale markt. Voor $n=10.000$ wordt dit geschat op ongeveer 1.100 studenten.

C. Vergelijking met Random Serial Dictatorship (RSD)

De auteurs vergelijken DA met RSD om de resultaten te contextualiseren:

Topkeuzes: RSD kent een constante fractie studenten toe aan hun topkeuze ( $\approx n/2$ ), terwijl DA dit slechts doet voor een fractie van $\approx n/\ln(n)$ . DA presteert dus aanzienlijk slechter op dit punt.
Onbenijde studenten: Surprendent genoeg is het verwachte aantal studenten dat door niemand wordt benijd onder RSD exact gelijk aan dat van DA:
$NEn^{RSD} = H_n$
Betekenis: Dit suggereert dat het aantal onbenijde studenten een fundamentele eigenschap is van willekeurige markten, en niet specifiek een tekortkoming van het DA-mechanisme.

4. Significatie en Discussie

Onverbeterbaarheid: De studie toont aan dat studenten die gegarandeerd "onverbeterbaar" zijn (ofwel door niemand benijd, ofwel hun topkeuze hebben), een verdwijnend klein fractie vormen van de markt naarmate deze groeit.
Fundamentele Eigenschap: Het feit dat zowel DA als RSD exact $H_n$ onbenijde studenten opleveren, wijst erop dat dit een intrinsieke eigenschap is van willekeurige matching-problemen, ongeacht het specifieke mechanisme (zolang het stabiel of strategisch veilig is).
Beleid en Theorie: De resultaten bieden inzicht in de beperkingen van stabiele mechanismen qua Pareto-efficiëntie. Hoewel DA stabiel is, is het voor de meeste studenten mogelijk om hun situatie te verbeteren via ruil, omdat de groep "onverbeterbare" studenten verwaarloosbaar klein is in grote markten.
Toekomstig Onderzoek: De auteurs wijzen op open vragen, zoals de uitbreiding naar veel-op-een markten (many-to-one) en de invloed van gecorreleerde voorkeuren. Simulaties suggereren dat onverbeterbare studenten zelfs nog zeldzamer zijn in deze complexere scenario's.

Samenvattend: Het artikel kwantificeert dat in grote, willekeurige markten bijna geen enkele student volledig "veilig" is tegen verbetering via ruil, en dat het aantal studenten dat door niemand wordt benijd, beperkt blijft tot een logaritmische schaal ( $H_n$ ), ongeacht of het DA of RSD wordt gebruikt.