Een paar weken geleden zat ik weer eens in de collegebanken omdat Matt Jackson (Stanford) de Tinbergen lectures gaf over netwerken. Dat kwam uitstekend uit omdat ik mij sinds kort realiseerde dat een deel van mijn eigen onderzoek raakvlakken heeft met netwerktheorie. Het was een erg interessante cursus maar het probleem waar Christian Holzner en ik mee worstelden werd helaas niet behandeld. Inmiddels hebben we wel vooruitgang geboekt. Het probleem heeft betrekking op de arbeidsmarkt maar het is leuker om het als dating probleem te presenteren.
Stel je een speeddate event voor met 100 mannen en 100 vrouwen. De mannen vinden alle vrouwen even leuk maar de vrouwen zijn kieskeurig. Elke vrouw kan aangeven met welke mannen ze een date zou willen. De vrouwen doen dus de aanzoeken en elke man en vrouw krijgen maximaal één date. De vraag is nu hoe de organisatoren er voor kunnen zorgen dat er zoveel mogelijk mannen en vrouwen een date krijgen. Dit hangt af van de realisatie van het netwerk. Stel bijvoorbeeld dat Anna, Barbara en Carla aangeven dat ze Jan leuk genoeg te vinden voor een date maar dat alleen Anna ook met Kees wel wil daten. Dan is het niet slim om Jan aan Anna te koppelen want dan heeft Kees niemand.
In netwerk termen zijn de aanzoeken de verbindingen in het netwerk tussen de mannen en de vrouwen. Het aantal mogelijke netwerken is enorm (een 1 met 101 nullen en dit is meer dan het geschatte aantal atomen in het heelal; een 1 met 82 nullen). Anna kan namelijk ,0, 1,2,3 …of 100 aanzoeken doen en hetzelfde geldt voor de andere dames.
Toch kun je een mechanisme ontwerpen dat het aantal dates maximaliseert. Het mechanisme komt er grofweg op neer dat je de mannen 10 muntjes geeft en laat bieden op elk aanzoek van de vrouwen. Stel in het bovenstaande voorbeeld dat Jan en Kees allebei in eerste instantie voor Anna kiezen. Kees zal in dat geval een extra muntje inzetten en Jan zal kijken of Barbara of Carla nog vrij zijn. Het voordeel van dit mechanisme is dat degene met de zwakste positie in het netwerk het agressiefst zal bieden en gematcht wordt.
Hoe kun je nou weten of dit mechanisme tot het maximaal mogelijke aantal dates leidt zonder alle mogelijke netwerken te beschouwen? Merk allereerst op dat elk aanzoek of tot een date leidt of niet. De Franse wiskundige Berge liet zien dat als er een pad bestaat over het netwerk waarbij je begint en eindigt met iemand zonder date en waarbij je afwisselt tussen aanzoeken die een date opleveren en aanzoeken die geen date opleveren dat je dan niet het maximaal mogelijke aantal dates hebt. Op dat pad kun je immers de date en geen date aanzoeken verwisselen en dat leidt altijd tot een extra date (één minder in het midden en twee meer aan de randen). Berge liet ook zien dat als je niet zo’n pad kunt vinden dat je dan de maximale hoeveelheid dates op het netwerk hebt (en dat allemaal zonder topsector subsidie!!). In ons paper laten we zien dat een mechanisme zoals hierboven beschreven, zo’n pad uitsluit. Er bestaan inmiddels allerlei algoritmen om het maximale aantal (gewogen) matches te vinden die market makers zoals dating bureaus kunnen toepassen. Het aardige is dat bovenstaand mechanisme ook werkt in gedecentraliseerde markten (zoals de arbeidsmarkt).
Tot slot. Kees en Anna hadden een leuke date en ze trouwden een jaar later. De wiskundige Claude Berge bewees nog vele mooie stellingen en schreef zelfs een wiskundige misdaadroman: Wie heeft de Hertog van Densmore vermoord? voor hij in 2002 overleed.
Auteur
Categorieën