Over fairness, algoritmes en schoolinschrijvingen (gastblog van Jo Devriendt)

Door mijn post gisteren die ook op VRTNWS verscheen als opinie kreeg ik gisteren nog meer mails over het aanmeldingssysteem in Gent (en Antwerpen). Een van de mails was een zeer constructieve van Jo Devriendt, postdoctoraal onderzoeker aan de universiteit van Leuven. Ik vroeg hem of hij zijn mail en uitleg niet wou omvormen tot een gastpost. Bij deze:

De problematiek van de inschrijvingen in scholen is een moeilijke zaak. In Gent en Antwerpen probeert men momenteel een centraal inschrijvingssysteem uit te werken, waar (ouders van) kinderen hun favoriete scholen kunnen opgeven. Een computeralgoritme verdeelt dan op een faire manier de scholen, zodanig dat geen voordeel wordt gegeven aan rang, stand of bereidheid om voor de schoolpoort te kamperen. En idealiter is die verdeling optimaal: zoveel mogelijk mensen krijgen een eerste keuze school.

Bij dit laatste punt knelt helaas het schoentje: het huidig algoritme slaagt er niet in om voldoende mensen hun eerste keuze te geven. Bijvoorbeeld, momenteel is het mogelijk dat Sam school A als eerste keuze had, Saïd school B, maar Sam wordt toegewezen aan school B en Saïd aan school A. Sam en Saïd zouden natuurlijk graag wisselen, zodat ze beiden hun eerste keuze school krijgen.

In het vakjargon noemen we dit het “stabiel huwelijk”-principe*. Het feit dat het huidige algoritme niet aan het “stabiel huwelijk”-principe voldoet, wijst op een fundamentele tekortkoming. Er bestaan immers algoritmes die hier wel aan voldoen. Meer nog, er zijn jaren van onderzoek naar dit soort “toekenningsproblemen” gegaan, die krachtige computertechnieken hebben opgeleverd.

Natuurlijk, zelfs de beste algoritmes zullen niet iedereen tevreden kunnen stellen. Ook een onbevooroordeelde computer zal sommigen een eerste keuze toekennen en anderen niet, bijvoorbeeld wanneer teveel mensen dezelfde school als eerste keuze opgeven. De vraag die dan rijst is: hoe doe je dit fair?

Het antwoord in het huidige algoritme is loting. En dit is inderdaad een fair principe, dat daarenboven in bijna elk toekenningsalgoritme kan worden verwerkt. Immers, een toekenningsalgoritme loopt typisch in een bepaalde volgorde over de lange lijst van alle keuzes die door ouders ingegeven zijn. Die volgorde bepaalt of het nu Sophie of Jos is die de laatst overblijvende plaats voor een felbegeerde school krijgt. Door die volgorde te loten, of meer technisch, door een “random shuffle” op die volgorde toe te passen, worden de knopen op een faire manier doorgehakt.

Die loting mag wel niet op voorhand bekend zijn. Immers, dan kan iemand het algoritme analyseren, en -in theorie- op exact het juiste moment zijn keuzes aan de lijst toevoegen, zodat ze na de loting bovenaan komen te staan. Daarom baseert men de loting vaak op een afgesproken maar onbekende variabele, die men pas te weten kan komen na het opstellen van de keuzes. Bijvoorbeeld het winnend lottonummer van de week na de deadline voor het opgeven van de keuzes zou een goede onbekende variabele zijn. Op basis van dat lottonummer kan de volgorde van de lijst keuzes finaal geloot worden.

Technisch is het dus perfect mogelijk om een fair toekenningsalgoritme te bouwen dat meer mensen een eerste keuze geeft én nog steeds fair is. In het ideale geval wordt dit algoritme openbaar gemaakt zodat experts kunnen checken of er geen gaten in zitten, of zelfs verbeteringen kunnen voorstellen. Bij deze een warme oproep om die experts effectief te raadplegen. Als Leuven iets te ver ligt, dan zijn er ongetwijfeld ook academici in Gent die de handschoen willen opnemen 🙂

* en.wikipedia.org/wiki/Stable_marriage_problem

Geef een reactie

Vul je gegevens in of klik op een icoon om in te loggen.

WordPress.com logo

Je reageert onder je WordPress.com account. Log uit /  Bijwerken )

Google+ photo

Je reageert onder je Google+ account. Log uit /  Bijwerken )

Twitter-afbeelding

Je reageert onder je Twitter account. Log uit /  Bijwerken )

Facebook foto

Je reageert onder je Facebook account. Log uit /  Bijwerken )

w

Verbinden met %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.