Reducing the negative effects of random tie-breaking in student allocation mechanisms

Tom Demeulemeester
Deze scriptie introduceert twee nieuwe methoden om de negatieve effecten te verminderen die gepaard gaan met het gebruik van willekeur als een selectiecriterium voor toewijzingsproblemen van studenten aan scholen. Beide methodes bepalen de kans waarmee een bepaalde toewijzing geselecteerd zal worden als de finale toewijzing. De prestaties van beide methodes wordt beoordeeld op gegenereerde data en op data van Antwerpen en Gent.

Hoe controleer je willekeur in de toewijzing van leerlingen aan scholen?

Naar welke school een kind gaat heeft een grote invloed op diens leven. Goede leerkrachten kunnen de toekomst veranderen, goede vrienden zijn er om die toekomst mee te beleven. Kinderen willen daarom meestal niet zomaar naar eender welke school gaan, maar ze hebben vaak een duidelijk idee over welke scholen bij hen zouden passen en welke niet. Voor populaire scholen is het echter vaak zo dat er niet genoeg plaatsen zijn voor alle kinderen die er graag naartoe willen. Hoe bepaal je dan op een eerlijke manier welke kinderen volgend jaar op deze school mogen starten en welke niet?

Wat na kamperen aan de schoolpoort?

Tot voor kort was het gangbaar voor talloze Vlaamse ouders om dagenlang voor de schoolpoort van hun favoriete school te kamperen om hun kind er te kunnen inschrijven. Voor ouders met een drukke baan of een minder uitgebreid sociaal vangnet was het onder dit systeem van inschrijven echter heel lastig om een plaatsje te bemachtigen op hun school van voorkeur. Om zo’n toestanden te vermijden gebruiken grotere Vlaamse steden daarom sinds enkele jaren een algoritme om leerlingen toe te wijzen aan een school. In plaats van te kamperen, geven ouders in dit systeem simpelweg een lijstje op waarin ze de scholen ordenen volgens hun voorkeur en het algoritme doet de rest.

Over dit algoritme is er zowel in de academische literatuur als in de populaire media al veel inkt gevloeid. Er zijn namelijk een aantal zaken die een goed algoritme wil verwezenlijken. Ten eerste wil het natuurlijk zo veel mogelijk leerlingen toewijzen aan een school die hoog op hun voorkeurslijstje staat. Daarnaast wil het ervoor zorgen dat het voor leerlingen nooit mogelijk is om met een andere leerling van school te ruilen om zo allebei beter af te zijn. Ook de mogelijkheid om het algoritme te slim af te zijn door een vals voorkeurslijstje op te geven moet beperkt of zelfs uitgesloten worden. Tot slot is ook de transparantie van het algoritme enorm belangrijk. Ouders moeten namelijk het gevoel hebben dat de beslissing op een eerlijke manier gebeurt.

Doorheen de tijd zijn er verschillende toewijzingsalgoritmes ontworpen die aan een aantal van deze eigenschappen voldoen, maar geen enkel van deze algoritmes kan garanderen dat aan al deze eigenschappen wordt voldaan. Dit is geen toeval: wiskundigen en economen hebben aangetoond dat het simpelweg niet mogelijk is om al deze eigenschappen in één algoritme te combineren. Er moeten dus afwegingen gemaakt worden. De keuze van het uiteindelijke algoritme hangt hierdoor af van welke eigenschappen het belangrijkst zijn voor het stadsbestuur of voor de overheid.

Hoe kies je tussen leerlingen?

Maar hoe kies je nu tussen leerlingen als er niet voldoende plaats is op een school? In Vlaamse lagere scholen zal deze beslissing gebeuren op basis van de afstand tussen de school en de woonplaats van de leerling of de werkplaats van een van de ouders. Voor Vlaamse secundaire scholen is dit echter niet toegestaan, omdat dit op de lange termijn de huizenprijzen rond de populaire scholen zou verhogen. Hierdoor zouden leerlingen van een minder gegoede afkomst benadeeld worden.

Om alle leerlingen die een school op hun eerste plaats gezet hebben een gelijke kans te geven, wordt er aan elke leerling een willekeurig nummer toegekend. Vervolgens zal de leerling die via deze loting het laagste nummer heeft gekregen de resterende plaats mogen innemen.

Er bestaan echter betere en minder goede lotingen van deze willekeurige nummers. Het is bijvoorbeeld mogelijk dat een bepaalde loting van willekeurige nummers ervoor zal zorgen dat er een groter aantal leerlingen zonder school achterblijft. Door het gebruik van willekeurige nummers is er dus een grote onzekerheid over hoe goed de uiteindelijke toewijzing van leerlingen aan scholen zal zijn.

Een eerste idee om te vermijden dat er een slechte loting van deze willekeurige nummers plaatsvindt, is om simpelweg één loting van willekeurige nummers te selecteren. Dit is de loting die volgens het stadsbestuur of de overheid de beste toewijzing oplevert. Het probleem hiermee is dat ouders op die manier het algoritme te slim af zouden kunnen zijn door bijvoorbeeld maar één school op te geven. Om dit te voorkomen wordt er in mijn thesis een nieuwe manier voorgesteld om een groep van lotingen te selecteren, in plaats van één enkele. Zo kan je opnieuw de slechte lotingen van willekeurige nummers vermijden, maar bovendien kan je er zo ook voor zorgen dat het voor ouders niet langer mogelijk is om het algoritme te slim af te zijn door een ander voorkeurslijstje op te geven. Deze methode leidt dus op een eerlijke manier tot een betere verwachte toewijzing.

Omdat het toewijzingsalgoritme een belangrijke beslissing maakt, is elke verbetering de moeite waard. Al is het maar voor één kind. Daarom lijkt het me uiterst waardevol om er op voorhand voor te kunnen zorgen dat een slechte loting niet zal voorvallen. En dat is exact wat de methode die is ontwikkeld in mijn thesis doet.

Bibliografie
  • Abdulkadiroǧlu, A., Pathak, P. A. and Roth, A. E. (2009), ‘Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match’, The American Economic Review 99(5), 1954–1978.
  • Abdulkadiroǧlu, A. and Sönmez, T. (1998), ‘Random Serial Dictatorship and the core from random endowments in House Allocation problems’, Econometrica 66(3), 689– 701.
  • Abdulkadiroǧlu, A. and Sönmez, T. (2003), ‘School choice: A mechanism design approach’, American Economic Review 93(3), 729–747.
  • Ashlagi, I. and Nikzad, A. (2016), What Matters in School Choice Tie-breakings?: How Competition Guides Design, Proceedings of the 2016 ACM Conference on economics and computation, ACM, pp. 767–768.
  • Azevedo, E. M. and Budish, E. (2018), ‘Strategy-proofness in the Large’, The Review of Economic Studies 86(1), 81–116.
  • Balinski, M. and Sönmez, T. (1999), ‘A tale of two mechanisms: Student placement’, Journal of Economic Theory 84(1), 73–94.
  • Belga (2018), ‘Cocof dient belangenconflict in tegen vlaams inschrijvingsdecreet’, VRT NWS . URL: https://www.vrt.be/vrtnws/nl/2018/12/15/cocof-dient-belangenconflict-int…
  • Bertsimas, D. and Tsitsiklis, J. N. (1997), Introduction to linear optimization, Athena scientific series in optimization and neural computation 6, Athena scientific, Belmont.
  • Birkhoff, G. (1946), ‘Three observations on linear algebra’, Universidad Nacional de Tucuman Revista, Serie A 5, 147–151.
  • Black, S. E. and Machin, S. (2011), Housing valuations of school performance, in E. A. Hanushek, S. Machin and L. Woessmann, eds, ‘Handbook of the economics of education’, 1 edn, Vol. 3, Elsevier, chapter 10, pp. 485 – 519.
  • Bogomolnaia, A. and Moulin, H. (2001), ‘A new solution to the random assignment problem’, Journal of Economic Theory 100(2), 295–328.
  • Braeckman, K. (2019), ‘Kamperen voor de schoolpoort zal volgend schooljaar sterk verminderen’, VRT NWS . URL: https://www.vrt.be/vrtnws/nl/2019/01/31/kamperen-voor-de-schoolpoort-za…
  • Brualdi, R. A. (1982), ‘Notes on the Birkhoff algorithm for doubly stochastic matrices’, Canadian Mathematical Bulletin 25(2), 191–199.
  • Budish, E. and Cantillon, E. (2012), ‘The multi-unit assignment problem: Theory and evidence from course allocation at Harvard’, American Economic Review 102(5), 2237–2271.
  • Budish, E., Che, Y.-K., Kojima, F. and Milgrom, P. (2013), ‘Designing random allocation mechanisms: Theory and applications’, American Economic Review 103(2), 585–623.
  • Cantillon, E. (2009), ‘Regulating school choice in Brussels’, Brussels Studies .
  • Carroll, G. (2014), ‘A general equivalence theorem for allocation of indivisible objects’, Journal of Mathematical Economics 51(1), 163–177.
  • Che, Y.-K. and Kojima, F. (2010), ‘Asymptotic equivalence of Probabilistic Serial and Random Priority mechanisms’, Econometrica 78(5), 1625–1672.
  • Cools, S. (2018), ‘“Mijn zoon staat 56ste, 72ste en 73ste op de wachtlijsten”’, De Standaard . URL: http://www.standaard.be/cnt/dmf20180305 03391300
  • de Haan, M., Gautier, P., Oosterbeek, H. and van Der Klaauw, B. (2015), ‘The performance of school assignment mechanisms in practice’, IDEAS Working Paper Series from RePEc .
  • De Herdt, C. (2010), ‘Honderden ouders kamperen in turnzalen’, De Standaard . URL: http://www.standaard.be/cnt/v72n68hq
  • Debruyne, S. (2016), ‘Ouders omzeilen schoolkamperen met volmacht’, De Morgen . URL: https://www.demorgen.be/binnenland/ouders-omzeilen-schoolkamperen-metvo…
  • D’haeseleer, L. (2016), Centrale toewijzing van kinderen aan scholen, Master’s thesis, Universiteit Gent.
  • Doǧan, B. (2016), ‘Responsive affirmative action in school choice’, Journal of Economic Theory 165(C), 69–105.
  • Dubins, L. E. and Freedman, D. A. (1981), ‘Machiavelli and the Gale-Shapley algorithm’, The American Mathematical Monthly 88(7), 485–494.
  • Dufoss´e, F. and U¸car, B. (2016), ‘Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices’, Linear Algebra and Its Applications 497(C), 108–115.
  • Dur, U., Hammond, R. G. and Morrill, T. (2018), ‘Identifying the harm of manipulable school-choice mechanisms’, American Economic Journal: Economic Policy 10(1), 187–213.
  • Erdil, A. (2014), ‘Strategy-proof stochastic assignment’, Journal of Economic Theory 151(1), 146–162.
  • Erdil, A. and Ergin, H. (2008), ‘What’s the matter with tie-breaking? Improving efficiency in school choice’, American Economic Review 98(3), 669–689.
  • Ergin, H. and Sönmez, T. (2006), ‘Games of school choice under the Boston mechanism’, Journal of Public Economics 90(1), 215–237.
  • Gale, D. and Shapley, L. S. (1962), ‘College admissions and the stability of marriage’, The American Mathematical Monthly 69(1), 9–15.
  • Golub, G. H. and Van Loan, C. F. (1996), Matrix computations, Johns Hopkins studies in the mathematical sciences, 3rd ed. edn, Johns Hopkins university press, Baltimore.
  • Gordts, P. (2018), ‘Kritiek op gentse aanmeldsysteem blijft: “Plaatsen op scholen zijn geen Panini-stickers”’, De Morgen . URL: https://www.demorgen.be/binnenland/kritiek-op-gentse-aanmeldsysteem-bli…
  • Hafalir, I. E., Yenmez, M. B. and Yildirim, M. A. (2013), ‘Effective affirmative action in school choice’, Theoretical Economics 8(2), 325–363.
  • Hubo, B. (2017), ‘Loting vervangt voortaan tijdsregistratie bij inschrijving secundair’, Bruzz . URL: https://www.bruzz.be/video-loting-vervangt-voortaan-tijdsregistratie-bi…
  • Hylland, A. and Zeckhauser, R. (1979), ‘The efficient allocation of individuals to positions’, Journal of Political Economy 87(2), 293–314.
  • Inschrijven in Brussel (2019), ‘Aanmelden’. (Accessed on 2019/04/15). URL: http://www.inschrijveninbrussel.be/nl/secundair-onderwijs/aanmelden#pag…
  • Kesten, O. (2010), ‘School choice with consent’, Quarterly Journal of Economics 125(3), 1297–1348.
  • Kesten, O., Kurino, M. and Nesterov, A. (2017), ‘Efficient lottery design’, Social Choice and Welfare 48(1), 31–57.
  • Kesten, O. and Ünver, M. U. (2015), ‘A theory of school-choice lotteries’, Theoretical Economics 10(2), 543–595.
  • Kojima, F. (2012), ‘School choice: Impossibilities for affirmative action’, Games and Economic Behavior 75(2), 685–693.
  • Kojima, F. and Manea, M. (2010), ‘Incentives in the Probabilistic Serial mechanism’, Journal of Economic Theory 145(1), 106–123.
  • KSLeuven (2016), ‘Kiezen en inschrijven in KSLeuven: op weg naar 2017-2018’. (Accessed on 2019/04/15). URL: http://www.ksleuven.be/wp-content/uploads/2016/12/17-18-klein.pdf
  • KSLeuven (2019), ‘Op weg naar 2019-2020: Aanmelden en inschrijven in het eerste jaar in de Leuvense secundaire scholen van het officieel en het katholiek onderwijs’. (Accessed on 2019/04/15). URL: https://aanmeldensecundair.leuven.be/brochure.pdf
  • Liu, Q. and Pycia, M. (2016), ‘Ordinal efficiency, fairness and incentives in large markets’. Unpublished paper.
  • Manlove, D. (2013), Algorithmics of matching under preferences, Series on theoretical computer science 2, World scientific, Singapore.
  • Martini, G. (2016), ‘Strategy-proof and fair assignment is wasteful’, Games and Economic Behavior 98(C), 172–179.
  • Meld je aan Antwerpen (2019), ‘Veelgestelde vragen’. (Accessed on 2019/04/15). URL: https://meldjeaansecundair.antwerpen.be/faq
  • Meld je aan Gent (2019), ‘Veelgestelde vragen’. (Accessed on 2019/04/15). URL: https://meldjeaansecundair.gent.be/faq
  • Mennle, T. and Seuken, S. (2014), ‘Relaxing strategyproofness in one-sided matching’, ACM SIGecom Exchanges 13(1), 64–67.
  • Mouchalleh, A. (2019), ‘Middelbare scholen in Gent krijgen 1 online inschrijvingssysteem’, VRT NWS . URL: https://www.vrt.be/vrtnws/nl/2019/01/18/een-inschrijvingssysteem-voor-a…
  • Onderwijs Vlaanderen (2012a), ‘Inschrijvingsrecht en aanmeldingsprocedures in het basisonderwijs’. (Accessed on 2019/04/15). URL: https://data-onderwijs.vlaanderen.be/edulex/document.aspx?docid=14368
  • Onderwijs Vlaanderen (2012b), ‘Inschrijvingsrecht en aanmeldingsprocedures in het secundair onderwijs’. (Accessed on 2019/03/10). URL: https://data-onderwijs.vlaanderen.be/edulex/document.aspx?docid=14370 #13-5
  • Onderwijs Vlaanderen (2019), ‘Vlaams parlement keurt inschrijvingsdecreet definitief goed: gedaan met kamperen aan de schoolpoort’. (Accessed on 2019/05/13). URL: https://onderwijs.vlaanderen.be/nl/vlaams-parlement-keurt-inschrijvings decreet-definitief-goed-gedaan-met-kamperen-aan-de-schoolpoort
  • Pathak, P. A. and Sethuraman, J. (2011), ‘Lotteries in student assignment: An equivalence result’, Theoretical Economics 6(1), 1–17.
  • Pathak, P. A. and Sönmez, T. (2008), ‘Leveling the playing field: Sincere and sophisticated players in the Boston mechanism’, American Economic Review 98(4), 1636– 1652.
  • Pathak, P. A. and Sönmez, T. (2013), ‘School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation’, American Economic Review 103(1), 80–106.
  • Quartier, T. (2017), Hoe het lotingssysteem bij keuze van middelbare scholen optimaliseren?, Master’s thesis, KU Leuven.
  • Rawls, J. (1971), A theory of justice, Belknap Press of Harvard University Press.
  • Roth, A. (1982), ‘The economics of matching: Stability and incentives’, Mathematics of Operations Research 7, 617–628.
  • Sacerdote, B. (2011), Peer effects in education: How might they work, how big are they and how much do we know thus far?, in E. Hanushek, S. Machin and L. Woessmann, eds, ‘Handbook of the economics of education’, 1 edn, Vol. 3, Elsevier, chapter 4, pp. 249–277.
  • Salumu, T. (2017), ‘Computer beslist naar welke middelbare school uw kind mag’, De Standaard . URL: http://www.standaard.be/cnt/dmf20170901 03048848
  • Salumu, T. (2019), ‘“Chaos vermeden”: 96 procent leerlingen mag naar favoriete middelbare school’, Nieuwsblad . URL: https://m.nieuwsblad.be/cnt/dmf20190513 04397737?utm source=google
  • Shapley, L. and Scarf, H. (1974), ‘On cores and indivisibility’, Journal of Mathematical Economics 1(1), 23–37.
  • Snoekx, K. (2018), ‘Tweeling Tess en Lily (2) mag nu toch samen naar school: “We weten alleen nog niet in welke school ze terechtkunnen”’, Nieuwsblad . URL: https://www.nieuwsblad.be/cnt/dmf20180403 03443156
  • Stassijns, J. (2017), ‘Online aanmeldingssysteem secundair onderwijs actief’, De Standaard . URL: http://www.standaard.be/cnt/dmf20171218 03250911
  • Tarjan, R. (1972), ‘Depth-first search and linear graph algorithms’, SIAM Journal on Computing 1(2), 146–160.
  • The Royal Swedish Acadamy of Sciences (2012), ‘The prize in Economic Sciences 2012’. (Accessed on 2019/05/13). URL: https://www.nobelprize.org/prizes/economic-sciences/2012/press-release/
  • Thrupp, M., Lauder, H. and Robinson, T. (2002), ‘School composition and peer effects’, International Journal of Educational Research 37(5), 483–504.
  • van Campen, T., Hamers, H., Husslage, B. and Lindelauf, R. (2017), ‘A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack’, Social Network Analysis and Mining 8(1), 3. URL: https://doi.org/10.1007/s13278-017-0480-z
  • Vlaams Parlement (2018), ‘Voorstel van decreet houdende wijziging van het decreet basisonderwijs van 25 februari 1997 en de codex secundair onderwijs wat het inschrijvingsrecht betreft’. (Accessed on 2019/04/10). URL: http://docs.vlaamsparlement.be/pfile?id=1427944
  • Vlaamse overheid (2002), ‘Decreet betreffende gelijke onderwijskansen-I’. (Accessed on 2019/04/09). URL: https://codex.vlaanderen.be/Zoeken/Document.aspx?DID=1009657&param =informatie
  • von Neumann, J. (1953), ‘A certain zero-sum two-person game equivalent to the optimal assignment problem’, Contributions to the Theory of Games 2. edited by W. Kuhn and A.W. Tucker. Princeton: Princeton University Press, 1997.
  • Wouters, T. and Groenez, S. (2014a), ‘De evolutie van schoolse segregatie in het Nederlandstalige onderwijs in Belgi¨e’, Tijdschrift voor Sociologie 35(3), 185–211.
  • Wouters, T. and Groenez, S. (2014b), ‘School choice and segregation: explanatory models’. URL: https://lirias.kuleuven.be/retrieve/326250
  • Wouters, T. and Groenez, S. (2015), Overheidsbeleid en schoolse segregatie, Steunpunt Studie- en Schoolloopbanen, Leuven.
  • Zhou, L. (1990), ‘On a conjecture by Gale about one-sided matching problems’, Journal of Economic Theory 52(1), 123–135.

 

Universiteit of Hogeschool
Tom Demeulemeester
Publicatiejaar
2019
Promotor(en)
Prof. Roel Leus, Prof. Dries Goossens
Kernwoorden
Share this on: