Asymptotic Equivalence of Immediate and Deferred Acceptance

Stel je voor dat je de burgemeester bent van een bruisende stad waar elk kind een plek in een school nodig heeft, maar er zijn precies evenveel stoelen als er leerlingen zijn. Het probleem is niet alleen het vinden van een stoel; het is het vinden van de juiste stoel. Elk gezin heeft een lijst met scholen waar ze van houden, van "Mijn Droomschool" tot "De School Waar Ik Toch Wel Naartoe Zou Gaan Als Het Moet." De stad heeft ook regels, ook wel: misschien geeft een school voorrang aan kinderen die in de buurt wonen of broers of zussen hebben die er al zitten. De grote vraag voor de mensen die de leiding hebben is: Hoe koppelen we kinderen aan scholen zodat iedereen zo gelukkig mogelijk is?

Decennialang hebben experts gedebatteerd over twee belangrijke manieren om dit te doen. De eerste methode wordt Deferred Acceptance (DA) genoemd. Denk aan dit als een langzame, zorgvuldige dans. Studenten solliciteren naar hun favoriete keuze. Scholen houden hun favoriete kandidaten vast, maar zeggen niet definitief "ja"; ze zeggen slechts "misschien". Als er later een betere student verschijnt, kan de school deze uitwisselen. Dit proces herhaalt zich totdat iedereen is gevestigd. Het staat bekend als eerlijk en onmogelijk om te bedriegen, maar het kan een beetje rommelig en inefficiënt zijn.

De tweede methode is Immediate Acceptance (IA), ook wel bekend als de "Boston-methode". Dit is meer als een hectische race. Studenten staan in de rij en solliciteren naar hun eerste keuze. Scholen kijken naar de rij, kiezen hun favoriet op basis van prioriteit, en zeggen: "Je bent binnen!" Als je wordt afgewezen, ren je direct door naar je tweede keuze. Het nadeel is dat als je te laat solliciteert voor je eerste keuze, je je plek kunt verliezen aan iemand met een hogere prioriteit die eerder solliciteerde, zelfs als jij die school echt veel liever wilde. Vanwege dit punt wordt IA vaak bekritiseerd als oneerlijk of gemakkelijk te manipuleren. IA heeft echter een grote superkracht: als iedereen de waarheid spreeft over wat ze willen, garandeert IA een resultaat waarbij niemand gelukkiger kan worden zonder iemand anders ongelukkiger te maken. Dit wordt "Pareto-efficiëntie" genoemd.

Dus, hier is de miljoenenvraag: Maakt de superkracht van IA echt een groot verschil in het echte leven? Krijgen kinderen via IA scholen die ze veel beter vinden dan via de langzamere DA-methode? Of is het verschil slechts een minuscuul, onzichtbaar stipje? Dit is het puzzelstukje waar Josué Ortega zijn onderzoek naar doet.

---

De Grote Schoolrace: Een Verhaal van Twee Mechanismen

Josué Ortega, een onderzoeker van Queen's University Belfast, besloot dit debat te beslechten door een massaal gedachte-experiment uit te voeren. Hij keek niet naar echte steden met hun rommelige geschiedenis en politiek. In plaats daarvan stelde hij zich een "random markt" voor — een wereld waarin de lijst met favoriete scholen van elke student volledig willekeurig wordt getrokken, zoals het trekken van namen uit een hoed. In deze wereld zijn er $n$ studenten en $n$ scholen.

Ortega wilde de "gemiddelde rang" meten. Stel je voor dat elke student een score krijgt op basis van hoe hoog op hun lijst hun toegewezen school stond. Als je je #1 keuze krijgt, is je rang 1. Als je je #100 keuze krijgt, is je rang 100. Het doel is om dit getal zo laag mogelijk te houden.

Al een lange tijd weten we het antwoord voor de langzame, zorgvuldige dans (DA). Terug in de jaren '70 ontdekten wiskundigen dat in een random markt de gemiddelde student eindigt bij een school met een rang van ongeveer $\log n$ (logaritme van $n$). Als je 1.000 studenten hebt, is de gemiddelde rang ongeveer 7. Als je 100.000 studenten hebt, is het ongeveer 11. Het groeit, maar zeer langzaam.

Maar wat betreft de hectische race (IA)? Omdat IA anders werkt — waarbij de volgorde van solliciteren ertoe doet en studenten kunnen worden afgewezen simpelweg omdat ze "te laat" waren — dachten wiskundigen dat het veel complexer zou zijn. Sommige computerwetenschappers hadden geprobeerd het op te lossen, maar zij konden alleen de kans berekenen op het krijgen van een specifieke rang, niet de gemiddelde rang voor iedereen. Ze gokten dat het ook logaritmisch zou zijn, maar niemand kon het bewijzen.

Het "Coupon Collector"-geheim

Ortega's doorbraak was het besef dat beide mechanismen, ondanks dat ze er totaal anders uitzien, stiekem hetzelfde spel spelen. Hij gebruikte een klassieke puzzel genaamd het Coupon Collector Problem om het uit te leggen.

Stel je voor dat je probeert een complete set van $n$ verschillende ruilkaarten te verzamelen. Elke keer dat je een doos ontbijtgranen koopt, krijg je één willekeurige kaart. Hoeveel dozen moet je kopen om elke enkele kaart minstens één keer te hebben?
Het antwoord is ongeveer $n \times \log n$. Je besteedt veel tijd aan het kopen van dozen, alleen maar om de laatste paar zeldzame kaarten te vinden die je nog mist.

Ortega toonde aan dat Deferred Acceptance precies zoals dit is. Studenten blijven solliciteren naar scholen totdat elke school minstens één sollicitatie heeft ontvangen. Het totale aantal sollicitaties gedaan door iedereen is ongeveer hetzelfde als het aantal ontbijtgranendozen dat je nodig zou hebben om alle coupons te verzamelen. Aangezien de gemiddelde student ongeveer $\log n$ sollicitaties doet, is hun uiteindelijke schoolrang ook ongeveer $\log n$.

Toen richtte Ortega zijn blik op Immediate Acceptance. In eerste instantie leek het anders omdat studenten niet direct kunnen blijven solliciteren; ze moeten wachten tot een "ronde" is afgerond voordat ze opnieuw kunnen proberen. Maar Ortega realiseerde zich dat als je naar het proces op een specifieke manier kijkt, het ook een "coupon collector" is.

Hij stelde zich een iets "amnesische" versie van het spel voor. Stel dat een student willekeurig scholen blijft kiezen, zelfs als hij die school al eens geprobeerd heeft. Als hij een school kiest die hij al geprobeerd heeft, negeert hij deze gewoon (dat is een "verloren" poging). Ortega bewees dat zelfs met deze verloren pogingen, het aantal echte sollicitaties dat nodig is om elke school te vullen, nog steeds ongeveer hetzelfde is als het coupon collector-probleem.

De Grote Onthulling

Hier komt de clou: Het verschil tussen de twee methoden is verrassend klein.

Ortega bewees wiskundig dat naarmate de markt enorm wordt (wanneer $n$ heel groot wordt), de gemiddelde rang voor studenten in het Immediate Acceptance (IA) systeem ook ongeveer $\log n$ is.

Dit betekent dat hoewel IA "Pareto-efficiënt" is (wat betekent dat het theoretisch perfect is als iedereen de waarheid spreeft), het studenten niet een enorm voordeel geeft in termen van het krijgen van hun topkeuzes vergeleken met de tragere DA-methode. De "first-order" verbetering — de grote, merkbare winst — bestaat simpelweg niet.

Het artikel van Ortega sluit expliciet de gedachte uit dat IA een wondermiddel is dat de uitkomsten van studenten drastisch verbetert in grote, random markten. Hoewel IA in specifieke, kleine scenario's of met specifieke prioriteitsregels misschien iets beter is, laat het onderzoek zien dat in het algemene geval de twee mechanismen asymptotisch equivalent zijn. Ze brengen studenten beide in scholen die qua rang ongeveer logaritmisch zijn ten opzichte van de grootte van de markt.

Waarom dit ertoe doet

Deze bevinding is een beetje een teleurstelling voor fans van het "Immediate Acceptance"-systeem, maar een opluchting voor de wiskunde. Het vertelt ons dat de "Pareto-efficiëntie" van IA een beetje een fata morgana is als het gaat om gemiddelde geluk. Het mechanisme dat vaak wordt bekritiseerd als oneerlijk en manipuleerbaar, levert niet eens een significant beter resultaat op dan het mechanisme dat eerlijk en moeilijk te bedriegen is.

Ortega's werk breidt deze bevinding ook uit naar andere variaties. Of scholen nu meerdere plaatsen hebben (many-to-one matching) of of studenten scholen mogen overslaan (een variatie genaamd "IA met skips"), de uitkomst blijft hetzelfde: de gemiddelde rang blijft rond de $\log n$ liggen.

Dus, de volgende keer dat je iemand hoort beweren dat we de "Boston-methode" moeten gebruiken omdat deze efficiënter is, kun je glimlachen en zeggen: "Nou, misschien is hij wel efficiënt, maar hij zorgt er niet voor dat kinderen gemiddeld gezien betere scholen krijgen dan de andere manier." In de grote race van schoolkeuze halen beide hardlopers de finishlijn bijna op exact hetzelfde moment.