Justifiable Priority Violations

Deze paper introduceert een vraagloos, endogeen criterium voor rechtvaardige prioriteitschendingen in het Deferred Acceptance-mechanisme dat, in tegenstelling tot bestaande instemmingsmodellen, toelaatbare verbeteringen mogelijk maakt en een polynomiaal algoritme biedt om Pareto-optimale uitkomsten te benaderen, hoewel theoretische beperkingen en simulaties aantonen dat volledige efficiëntie niet altijd haalbaar is.

De kern

De Schoolkeuze: Hoe we eerlijkheid en geluk in balans brengen

Stel je voor dat er een grote schoolkeuze is. Elke leerling heeft een lijstje met favoriete scholen, en elke school heeft een lijstje met wie ze het liefst willen (bijvoorbeeld op basis van de afstand tot huis of een broer/zus die er al zit). De huidige standaardmethode, genaamd DA (Deferred Acceptance), werkt als een eerlijke maar soms saaie loterij. Het zorgt ervoor dat niemand een school krijgt waar een ander met een hogere prioriteit ook op zit, maar het kan leiden tot een situatie waarin veel leerlingen een school krijgen die ze niet echt willen, terwijl er elders nog plekken vrij zijn die ze wel leuker vinden.

De auteurs van dit paper, Josué en Pablo, vragen zich af: Hoe kunnen we dit verbeteren zonder de eerlijke regels te breken?

Het Dilemma: De "Vreemde" Prioriteit

Stel je voor dat je als leerling een plek op School A hebt gekregen, maar je vriendin zit op School B. Jij wilt School B, en zij wil School A. Als jullie van plek wisselen, zijn jullie allebei blij. Maar... wat als er een derde leerling, laten we hem Klaas noemen, is die een hogere prioriteit heeft op School B dan jij?

Als jullie van plek wisselen, wordt Klaas "ongelukkig" omdat hij zijn plek kwijtraakt aan jou, terwijl hij eigenlijk recht had op die plek. In de oude wereld was dit verboden. Maar de auteurs zeggen: "Wacht even, niet elke ongelukkige Klaas is hetzelfde."

Ze verdelen de leerlingen in drie groepen:

1. De Winnaars: Leerlingen die het beter krijgen dan voorheen.
2. De Onverbeterbaren: Leerlingen die het nooit beter kunnen krijgen, hoe je het ook draait of keert. Als zij een plek kwijtraken, is dat jammer, maar het kon toch niet anders.
3. De Potentiële Winnaars (maar niet nu): Leerlingen die wel beter hadden kunnen krijgen in een andere situatie, maar in jouw specifieke oplossing niet. Als zij een plek kwijtraken, is dat echt onterecht.

De Kernboodschap: Een "prioriteitsbreuk" (iemand van zijn plek stoten) is alleen gerechtvaardigd als het gebeurt ten koste van de Onverbeterbaren of de Winnaars. Het mag nooit ten koste gaan van de Potentiële Winnaars die in jouw oplossing niets winnen.

De Oplossing: Een Slimme Dans (SJBC+)

De auteurs hebben een nieuwe methode bedacht, een soort algoritme (een recept voor een computer), genaamd SJBC+.

De Analogie van de Dansvloer:
Stel je voor dat de leerlingen een dansvloer zijn.

1. De Eerste Ronde (JBC): De computer kijkt eerst naar de "Onverbeterbaren". Als een leerling die toch nooit een betere plek kan krijgen, zijn plek moet afstaan aan iemand die wél een betere plek krijgt, dan is dat toegestaan. Het is alsof iemand die toch al op de rand van de dansvloer staat, even opzij moet springen zodat iemand anders kan dansen. Dit noemen ze "Sterk Gerechtvaardigd".
2. De Volgende Rondes (De Uitbreiding): Nu hebben we een groepje "Winnaars" die blij zijn. De computer zegt: "Oké, omdat deze groepje nu blij is, mogen ze ook een beetje 'ruilen' met anderen, zelfs als dat betekent dat we de prioriteit van een andere 'Onverbeterbare' nog iets meer schelen." Het is alsof de winnaars nu een soort 'vergunning' hebben gekregen om de dansvloer wat meer te herschikken, zolang ze maar niemand lastigvallen die had kunnen winnen maar nu niets krijgt.

Dit proces herhaalt zich totdat er niets meer te verbeteren valt zonder iemand te benadelen die er recht op had.

Waarom is dit beter dan de oude manier?

Vroeger dachten we: "Vraag iedereen van tevoren: 'Mag ik je prioriteit negeren als het anderen helpt?'" Dit noemen ze EADA (met toestemming).

• Het probleem: Mensen zijn bang om toestemming te geven. Als je zegt "ja", ben je bang dat je zelf iets verliest. Als je "nee" zegt, blokkeer je misschien een oplossing die iedereen blij maakt.
• De nieuwe aanpak: De auteurs zeggen: "We hoeven niet te vragen. We kijken gewoon naar het resultaat. Als iemand erop vooruitgaat, is het gerechtvaardigd om de regels een beetje te buigen."

Het blijkt dat hun nieuwe methode (SJBC+) vaak meer leerlingen blij maakt dan de oude methode met toestemming, zelfs als iedereen toestemming zou geven.

Wat zeggen de cijfers?

De auteurs hebben dit getest met duizenden willekeurige situaties (simulaties).

• Resultaat: Hun nieuwe methode zorgt in meer dan 60% tot 85% van de gevallen voor een perfecte situatie (waar niemand het beter kan krijgen zonder dat iemand anders erop achteruitgaat).
• Vergelijking: De oude methode (EADA) faalt vaak als niet iedereen toestemming geeft. Zelfs als iedereen toestemming geeft, werkt de nieuwe methode vaak nog beter en is het eerlijker voor degenen die hun prioriteit kwijtraken.

Conclusie in één zin

Deze paper zegt: "We kunnen de schoolkeuze veel eerlijker en gelukkiger maken door niet blindelings te vragen om toestemming, maar door slimme regels te gebruiken die alleen 'onvermijdelijke' en 'wenselijke' prioriteitsbreuken toestaan, zodat meer kinderen op de school van hun dromen terechtkomen."

Technische samenvatting

1. Probleemstelling

Het paper adresseert een fundamenteel probleem in de schoolkeuzetheorie (school choice): het afwegen van twee vaak conflicterende doelen. Enerzijds moet een mechanisme wettelijk vastgestelde prioriteiten respecteren (bijv. op basis van afstand of broers/zussen), en anderzijds moet het schaarse schoolplekken efficiënt toewijzen om het welzijn van studenten te maximaliseren.

Het standaardmechanisme, Deferred Acceptance (DA), produceert een stabiele toewijzing die prioriteiten respecteert en student-optimaal is binnen de set van stabiele matchings. Echter, DA is vaak Pareto-inefficiënt: er bestaan andere toewijzingen waarbij sommige studenten beter af zijn zonder dat anderen erop achteruitgaan. Het realiseren van zo'n Pareto-verbetering vereist noodzakelijkerwijs het schenden van prioriteiten. De centrale vraag is: welke prioriteitsschendingen zijn moreel en normatief verdedigbaar ("justifiable")?

De huidige leidende aanpak is ex-ante toestemming: studenten worden vooraf gevraagd of ze hun prioriteit willen opgeven als dit anderen ten goede komt. Het paper toont aan dat deze aanpak beperkingen heeft en stelt een alternatief, vraagloos kader voor.

2. Methodologie en Conceptueel Kader

De auteurs introduceren een nieuw concept: Justifiable Priority Violations (Verdedigbare Prioriteitsschendingen).

Definitie van Justificatie

In plaats van vooraf toestemming te vragen, wordt bepaald of een schending verdedigbaar is op basis van het uiteindelijke resultaat van de verbetering. Studenten worden ingedeeld in drie categorieën:

1. Begunstigden (Beneficiaries): Studenten die door de verbetering een betere toewijzing krijgen dan onder DA.
2. Onverbeterbaren (Unimprovable): Studenten die onder geen enkele Pareto-verbetering van DA beter af zouden zijn; hun toewijzing blijft gelijk aan die onder DA.
3. Verbeterbare Niet-begunstigden (Improvable Non-beneficiaries): Studenten die kunnen profiteren van een verbetering, maar dat niet doen in de gekozen toewijzing.

Het criterium: Een prioriteitsschending is justifiable (verdedigbaar) als en slechts als deze plaatsvindt ten opzichte van studenten die tot categorie 1 of 2 behoren. Een schending ten opzichte van een student uit categorie 3 is onverdedigbaar, omdat deze student een reden heeft om te klagen: "Waarom werd mijn prioriteit genegeerd terwijl ik had kunnen profiteren?"

Dit criterium is endogeen: het hangt af van wat de verbetering bereikt, niet van vooraf gegeven toestemming.

Mechanismen

De auteurs ontwikkelen twee mechanismen om deze justifiable verbeteringen te vinden:

1. Just Below Cutoffs (JBC):

   • Dit mechanisme bouwt een graaf op basis van scholen die een "cutoff"-student (de laagst geprioriteerde toegelaten student onder DA) hebben toegewezen.
   • Het identificeert cycli waarbij de hoogst geprioriteerde student onder de cutoff (de "just below cutoff" student) een betere school krijgt.
   • Eigenschap: JBC produceert een sterk justifiable matching. Dit betekent dat er geen prioriteitsschendingen plaatsvinden ten opzichte van verbeterbare studenten; alleen de prioriteiten van onverbeterbaren worden geschonden. Het is uniek en vormt de basis voor verdere verbeteringen.

2. Sequential Just Below Cutoffs (SJBC+):

   • Dit is een polynomiale tijd-algoritme dat voortbouwt op JBC.
   • Het werkt iteratief:
     • Stap 1: Start met de JBC-matching en de set van begunstigden ($B_1$).
     • Stap 2: Zoek in een bipartiete graaf naar "augmenterende paden" die nieuwe studenten kunnen toevoegen aan de set van begunstigden. Schendingen zijn nu toegestaan ten opzichte van studenten die reeds in de set $B_t$ zitten (omdat zij er baat bij hebben).
     • Stap 3: Herhaal dit totdat geen nieuwe begunstigden meer kunnen worden gevonden.
     • Stap 4: Voer een verfijningsfase uit om cycli binnen de set van begunstigden te optimaliseren.
   • Resultaat: SJBC+ convergeert naar een matching die justifiable is en niet Pareto-gedomineerd kan worden door een andere justifiable matching zonder de set van begunstigden strikt te vergroten.

3. Belangrijkste Bijdragen en Theoretische Resultaten

• Bestaan van Justifiable Verbeteringen (Stelling 1): Als DA inefficiënt is, bestaat er altijd ten minste één sterk justifiable verbetering (geleverd door JBC).
• Incompatibiliteit met Volledige Efficiëntie (Propositie 1): Er bestaat geen matching die zowel justifiable is als volledig Pareto-efficiënt. Volledige efficiëntie vereist vaak het schenden van de prioriteiten van "verbeterbare niet-begunstigden", wat door het criterium wordt verboden.
• Vergelijking met Ex-Ante Toestemming (EADA):
  • Het paper vergelijkt justifiability met het bestaande Efficiency-Adjusted Deferred Acceptance (EADA) mechanisme, dat werkt op basis van vooraf gegeven toestemming.
  • Stelling 3: Er bestaan situaties waar EADA (zelfs met volledige toestemming) een matching produceert die niet justifiable is. Omgekeerd zijn er justifiable en Pareto-efficiënte matchings die door EADA onder geen enkele toestemmingsset kunnen worden gegenereerd.
  • Stelling 4 (Onmogelijkheid): Er bestaat geen toestemmingsmechanisme dat tegelijkertijd: (i) efficiënt is wanneer mogelijk, (ii) beperkt efficiënt is, en (iii) studenten prikkelt om toestemming te geven zonder hen te schaden. Dit toont fundamentele beperkingen van ex-ante toestemming aan.
• Polynomiale Complexiteit: Het SJBC+ algoritme kan in polynomiale tijd worden uitgevoerd, wat het praktisch toepasbaar maakt.

4. Resultaten uit Simulaties

De auteurs voeren simulaties uit op willekeurige schoolkeuze-problemen (met $n=50$ en $n=100$ studenten) en vergelijken SJBC+ met DA en EADA (met 50% en 100% toestemming).

• Pareto-efficiëntie: SJBC+ bereikt in 63% tot 85% van de gevallen een volledig Pareto-efficiënte uitkomst, afhankelijk van de voorkeursstructuur. Dit is significant hoger dan EADA met beperkte toestemming (vaak <10% efficiëntie bij 50% toestemming).
• Aantal Begunstigden: SJBC+ genereert gemiddeld meer begunstigden dan EADA, zelfs wanneer EADA werkt met volledige toestemming.
• Justificatie: SJBC+ is per constructie altijd justifiable (100%). De justificeerbaarheid van EADA daalt drastisch naarmate de markt groter wordt en voorkeuren gecorreleerd zijn (bijv. slechts 0,3% in gecorreleerde markten met $n=100$).
• Conclusie: Hoewel theorie aangeeft dat justifiability en volledige efficiëntie onverenigbaar zijn, blijkt dat in de praktijk SJBC+ zeer vaak toch tot een volledig efficiënte uitkomst leidt, terwijl het de prioriteitsschendingen beperkt tot de verdedigbare categorie.

5. Betekenis en Conclusie

Dit paper biedt een nieuwe normatieve richting voor schoolkeuzemechanismen.

1. Nieuwe Filosofie: Het verschuift de focus van "vooraf toestemming vragen" naar "endogene rechtvaardiging". Een schending is acceptabel als de getroffen student er uiteindelijk baat bij heeft of er nooit baat bij had kunnen hebben.
2. Praktische Toepasbaarheid: Het SJBC+ algoritme biedt een concrete, rekenkrachtige methode voor onderwijsautoriteiten om de inefficiëntie van DA te verminderen zonder willekeurige prioriteitsschendingen.
3. Theoretische Grenzen: Het paper toont aan dat zowel ex-ante toestemming als endogene justifiability fundamentele grenzen hebben in het bereiken van volledige efficiëntie, maar dat SJBC+ in de praktijk zeer dicht bij die grenzen komt.

Kortom, het paper bewijst dat het mogelijk is om substantiële welvaartswinsten te behalen ten opzichte van DA, zolang men strikt vasthoudt aan het principe dat prioriteitsschendingen alleen gerechtvaardigd zijn voor degenen die er profijt van hebben of die er nooit profijt van zouden kunnen hebben.