Wat mijn roeicursus met een algoritme te maken heeft

Door Sanne Blauw, 10 juli 2019

Beste John,

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.

Bron: de Correspondent.

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 )

Verbinden met %s

Deze site gebruikt Akismet om spam te bestrijden. Ontdek hoe de data van je reactie verwerkt wordt.