/dc-useruploads-images/c0d04d84203744a89ad3739570fa0981.png)
Beste,
Kort geleden schreef ik me in voor een roeicursus. Ik was op zoek naar een nieuwe hobby en ik zag mezelf al sereen over het water zoeven op een mooie zomeravond.
Op het inschrijfformulier moest ik aangeven welke dag ik het liefst wilde roeien. Ik moest ook invullen welke van de veertien tijdstippen – negen op dagen in het weekend – mijn voorkeur genoot én wat mijn tweede keus was.
Elke cursist kon dus kiezen uit 74 mogelijke starttijden (2*9 + 4*14 - op vrijdag wordt niet geroeid) en moest uiteindelijk in een bootje met vier terechtkomen. Dat handmatig indelen zou een helse klus zijn. Ik hoopte maar dat ze er een slim algoritme voor hadden...
Deze week moest mijn cursus beginnen. Maar op maandag had ik nog steeds niets gehoord. Tot ik een mailtje kreeg: sorry, we zijn nog niet klaar, dus we kunnen nog niet zeggen of je kunt starten met de cursus.
Het stabiele huwelijk
Op allerlei plekken zie je dit soort problemen met ‘matching’ opduiken. Een gedoneerd orgaan moet zo snel mogelijk naar de juiste patiënt. Een scholier moet ingedeeld worden op een geschikte school. En een online datingsite wil mensen zo goed mogelijk aan elkaar koppelen.
Het zijn lastige problemen, maar ze zijn niet onoplosbaar. In 2012 wonnen Alvin Roth en Lloyd Shapley de Nobelprijs voor de Economie (of, tsja, de Prijs van de Zweedse Rijksbank voor Economische Wetenschappen, maar dat bekt toch minder lekker) voor hun onderzoek naar matching.
In 1962 bedacht Shapley met zijn collega David Gale een oplossing voor het ‘stabiele huwelijksprobleem’. De vraag: hoe match je mannen en vrouwen (in de puzzel is iedereen heteroseksueel) op zo’n manier dat er geen koppel te maken is dat liever samen is?
Misschien wil Julia wel liever met de man van Sophie, maar blijft hij liever bij zijn eigen vrouw. Dit is wat wordt bedoeld met ‘stabiel’. Ook al eindigt Julia niet met haar eerste keus, er is geen risico dat ze ervandoor gaat met een ander.
Het algoritme
Er blijkt een vrij eenvoudig stappenplan te bestaan zijn om dit probleem op te lossen. In het ‘Gale-Shapley-algoritme’ – ook wel het deferred acceptance algoritme genoemd – maken mannen en vrouwen eerst een rangschikking van potentiële partners.
Vervolgens doet elke man een huwelijksaanzoek aan zijn favoriete vrouw. Een populaire vrouw kan dus zomaar een paar aanzoeken krijgen, terwijl een andere met nul achterblijft. Er ontstaat nu een aantal voorlopige koppels, want de vrouwen met een aanzoek zeggen ‘misschien’ tegen de man die ze het hoogst hebben staan en ‘nee’ tegen de rest.
In de volgende stap doen de overgebleven mannen een aanzoek aan de vrouw die ze nu het hoogst hebben staan (en waar ze nog geen aanzoek aan hebben gedaan). Het maakt niet uit of die vrouw al in een koppel zit, als het nieuwe aanzoek haar meer bekoort, dan kan ze switchen.
En zo gaat het alsmaar door, totdat iedereen verloofd is. Op Numberphile, mijn favoriete wiskundekanaal op YouTube, legt wiskundige Emily Riehl het algoritme uit aan de hand van een eenvoudig voorbeeld.
Het nut
Al heeft mijn ‘roeiprobleem’ iets weg van het huwelijksprobleem, het is net wat anders. Want nu is de poule niet ingedeeld in twee groepen (man en vrouw) én moeten er teams van vier worden gemaakt. Het lijkt dan ook wat meer op het ‘stable roommate problem’ (zie Wikipedia voor een uitleg).
Het leuke van dit soort algoritmes is dat ze ontzettend nuttig zijn in de ‘echte wereld’. Roth, de andere Nobelprijswinnaar, gebruikte de theoretische ideeën om ziekenhuizen aan nieuwe doktoren te helpen, om nierdonoren aan patiënten te koppelen en om scholieren in te delen op scholen.
Ik weet niet of mijn roeischool een dergelijk algoritme heeft gebruikt, maar gisteren had ik mijn eerste roeiles. Erg sereen was het niet. Maar ik zat wel op mijn lievelingstijdstip.
#NerdAlert
Wil je meer snappen van de wiskunde achter het stabiele huwelijksprobleem? Riehl heeft een extra video waarin ze wat verder de diepte ingaat.
Tot slot...
...kreeg ik veel reacties op mijn oproep voor AI-experts, veel dank! Met een aantal ga ik volgende week al in gesprek, ik kijk ernaar uit.
Deze nieuwsbrief liever in je inbox?
Als correspondent Ontcijferen onderzoek ik de getallenwereld. In mijn wekelijkse mail houd ik je op de hoogte van wat ik schrijf, hoor en lees. Een vast onderdeel: #NerdAlert, voor de getallenliefhebbers.
Dit verhaal heb je gratis gelezen, maar het maken van dit verhaal kost tijd en geld. Steun ons en maak meer verhalen mogelijk voorbij de waan van de dag.
Al vanaf het begin worden we gefinancierd door onze leden en zijn we volledig advertentievrij en onafhankelijk. We maken diepgravende, verbindende en optimistische verhalen die inzicht geven in hoe de wereld werkt. Zodat je niet alleen begrijpt wat er gebeurt, maar ook waarom het gebeurt.
Juist nu in tijden van toenemende onzekerheid en wantrouwen is er grote behoefte aan verhalen die voorbij de waan van de dag gaan. Verhalen die verdieping en verbinding brengen. Verhalen niet gericht op het sensationele, maar op het fundamentele. Dankzij onze leden kunnen wij verhalen blijven maken voor zoveel mogelijk mensen. Word ook lid!
