Matching-markten
Een aantal belangrijke markten hebben de eigenschap dat je niet simpelweg kunt kiezen wat je wilt, zelfs als je budget het toe zou laten: je moet zelf ook gekozen worden. Een belangrijk voorbeeld is de toewijzing van studenten aan universiteiten. Universiteiten verhogen in de regel niet simpelweg hun collegegeld totdat het aanbod gelijk is aan de vraag maar kiezen een voldoende laag niveau voor het collegegeld zodat een groot aantal studenten geïnteresseerd is.Vervolgens laten ze slechts een fractie van deze studenten toe tot de universiteit of studierichtingen.
Een ander voorbeeld van een matching-markt is de arbeidsmarkt voor economische promovendi en academische posities in de Verenigde Staten. Prijzen spelen hier een andere rol dan in (veel) goederenmarkten. Dit soort (tweezijdige) matching-markten lijken een beetje op een huwelijksmarkt: er wordt gezocht aan beide zijden, en er is hofmakerij vanuit beide zijden.
Stabiele koppelingen
Laten we voor het gemak eens kijken naar een (vereenvoudigde) huwelijksmarkt tussen mannen en vrouwen. Ieder man heeft een ranking (geordende lijst) over de vrouwen, en iedere vrouw heeft een soortgelijke ranking over de mannen. Met deze informatie in de hand moet de vraag over de minimale vereisten van een “goede” matching (koppeling) te beantwoorden zijn. Een eerste vereiste is dat niemand getrouwd is met een onacceptabele partner. Een tweede conditie is dat de matching niet tot echtscheidingen leidt: er is geen paar dat bestaat uit een man en een vrouw die liever bij elkaar zijn dan bij hun huidige partners. Deze twee vereisten tezamen vormen het stabiliteitsconcept geïntroduceerd door David Gale en Lloyd Shapley (1962).
In hun artikel laten Gale en Shapley zien dat er voor elke huwelijksmarkt een stabiele matching is. Ze ontwikkelden een algoritme om een stabiele matching te vinden. Hun zogeheten herhaalde-aanzoek algoritme werkt als volgt. Veronderstel dat iedere man eerst een aanzoek doet aan zijn favoriete vrouw. Iedere vrouw accepteert voorlopig het beste aanzoek en wijst alle andere (aan haar gedane) aanzoeken af. De mannen die afgewezen worden doen nu een aanzoek aan hun één-na-beste vrouw. Iedere vrouw beschouwt nu alle nieuwe aanzoeken én het beste aanzoek dat overbleef in de vorige ronde, en ze accepteert voorlopig het beste aanzoek en wijst alle andere af. Dit proces herhaalt zich totdat geen enkele man een nieuw aanzoek doet (we nemen aan dat het aantal mannen en vrouwen eindig is). Op dat moment wordt de “voorlopige” matching “definitief”. Met heel elegante argumenten bewezen Gale en Shapley dat deze matching (onder meer) stabiel is. De literatuur die stabiele matchings bestudeert is in de afgelopen decennia enorm gegroeid. Het handboek van Roth en Sotomayor (1990) is in de afgelopen jaren aangevuld door nieuwe literatuuroverzichten voornamelijk dankzij de ontwikkeling van nieuwe theorieën gebaseerd op interessante toepassingen.
Empirische relevantie
Gale en Shapley (1962, p.14) geven aan dat met betrekking tot hun algoritme “... some of the ideas introduced here might usefully be applied to certain phases of the admissions problem.” Dit bleek inderdaad het geval, en niet alleen voor het studenten-universiteiten toewijzingsprobleem. Sterker nog, in 1984 ontdekte Alvin Roth dat het algoritme van Gale en Shapley sinds 1952 gebruikt werd door een clearinginstituut om artsen in opleiding toe te wijzen aan ziekenhuizen. Voor 1952 was er geen centraal mechanisme en de hevige concurrentie tussen de ziekenhuizen uitte zich onder andere in een steeds vroegere (inefficiënte) onderschrijving van de aanstellingen. In 1945 was het bijvoorbeeld heel normaal dat door potentiële kandidaten meer dan twee jaar voor de feitelijke aanstelling een contract werd ondertekend. Dit probleem werd tijdelijk opgelost door het niet doorsturen van academische resultaten (de ziekenhuizen werden in het ongewisse gelaten). Dit bleek geen goede oplossing te zijn, omdat op het moment dat die informatie beschikbaar kwam en een ziekenhuis een kandidaat een aanbod deed, kwam het geregeld voor dat de kandidaat het ziekenhuis afwees en het ziekenhuis geen aanbod meer kon doen aan hun tweede favoriete kandidaat (omdat hij/zij het aanbod van een ander ziekenhuis inmiddels had geaccepteerd). Een gevolg van deze congestie was een chaotische en inefficiënte situatie waarin aanbod en acceptatie/afwijzing in een zeer korte periode gedaan werden. De oplossing in 1952 was een systeem waarin artsen interviews hadden met ziekenhuizen en vervolgens beide zijden hun rankings doorstuurden naar een clearinginstituut. Dit clearinginstituut gebruikte het (later!) door Gale en Shapley gepubliceerde algoritme voor de matching tussen artsen en ziekenhuizen.
Marktontwerp: de economische ingenieur
Roth (1990, 1991) analyseerde de clearinginstituten die in gebruik waren genomen nadat gedecentraliseerde medische arbeidsmarkten in Groot-Brittannië soortgelijke “ontrafeling” hadden vertoond. Iedere regio in Groot-Brittannië koos voor een verschillend algoritme om rankings om te zetten in een matching. Roth zag toen in dat de meeste onstabiele mechanismen na een aantal jaar opgegeven werden, terwijl de meeste stabiele mechanismen succesvol waren. Een laboratoriumexperiment van Kagel en Roth (2000) versterkte de hypothese van Roth dat het succes van bepaalde mechanismen te danken was aan de stabiliteit van de matchings die ze produceerden.
Deze en andere inzichten leidden tot het ontstaan van een nieuwe discipline: marktontwerp. Het idee is dat economen niet alleen markten kunnen analyseren, maar ook een actieve rol kunnen spelen in het ontwerp en herontwerp van specifieke markten. Het National Resident Matching Program (NRMP) verzocht Alvin Roth in 1995 het mechanisme voor de eerder beschreven medische arbeidsmarkt te herontwerpen. Er waren verschillende redenen hiervoor. Ten eerste was er onrust onder de medische studenten vanwege het vermoeden dat de matching van het NRMP de ziekenhuizen bevoordeelden (ten koste van de studenten). Ten tweede waren er in de loop van de jaren verschillende complicaties de markt binnengeslopen. Een belangrijke complicatie was de aanwezigheid van (echt)paren van studenten. Het mechanisme voor 1995 maakte het praktisch onmogelijk voor studentenparen om (gewenste) posities te vinden in het dezelfde geografisch gebied/ziekenhuis. Roth en Peranson (1999) en Roth (2002) beschreven de “ingenieursaanpak” die ze gebruikten voor het herontwerp van het mechanisme voor het NRMP. Roth (2002) gaf een heldere illustratie van de rol van een ingenieur in dit soort praktische problemen. Beschouw het ontwerp van een hangbrug. Het (relatief) eenvoudige theoretische model neemt aan dat de zwaartekracht de enige relevante kracht is, dat de balken perfect stijf zijn, etc. Een fatsoenlijk ontwerp van een brug moet echter ook rekening houden met kwesties zoals metallurgie, grondmechanica, en zijwaartse krachten van water en wind. Deze complicaties kunnen doorgaans niet analytisch worden bestudeerd, maar moeten worden onderzocht met behulp van fysieke of computationele modellen. Engineering is misschien minder elegant dan de eenvoudige onderliggende fysica, maar staat ons toe om (op langere termijn) de complicaties te begrijpen, en dus uiteindelijk betere en duurzame bruggen te ontwerpen. Voor het ontwerp van een degelijk toewijzingsmechanisme (zoals dat voor het NRMP) is het daarom noodzakelijk om niet alleen gebruik maken van pure speltheorie, maar ook van laboratoriumexperimenten en computermodelsimulaties. Deze visie en aanpak hebben ook hun vruchten afgeworpen in een aantal andere toepassingen.
Andere toepassingen: openbare scholen, niertransplantaties, …
In een groot aantal landen is er een alsmaar groeiende wachtlijst van patiënten voor een niertransplantatie. Vanwege uiteenlopende redenen zijn er onvoldoende geschikte donors van mensen die overlijden. Een levende donor kan één nier doneren (de verkoop is vrijwel overal illegaal) mits er geen incompatibiliteitsproblemen zijn. Zo kan het gebeuren dat Anton wel een nier zou willen geven aan zijn vrouw Bianca, maar dat dit niet mogelijk is vanwege incompatibele bloedgroepen of immuniteitssystemen. Veronderstel dat een ander echtpaar (Aart en Babette) hetzelfde probleem heeft. Normaal gesproken zouden de artsen beide echtparen naar huis sturen met een teleurstelling. Maar waarom zouden we de echtparen niet de kans geven voor een “nierenuitwisseling”? Dus: Anton geeft een geschikte nier aan Babette en tegelijkertijd (letterlijk!) geeft Aart een geschikte nier aan Bianca. Deze mogelijkheid werd voor het eerst beschreven in Roth et al. (2004). Ook heeft Alvin Roth een belangrijke rol gespeeld in het opzetten van een systeem in New England om zoveel mogelijk nierpatiënten en geschikte donors bij elkaar te brengen. De beperkingen hier zijn duidelijk: naast het verbod op de (ver)koop van nieren en de mogelijke incompatibiliteit, moeten – vanwege strategische kwesties – alle operaties tegelijkertijd uitgevoerd worden. Ziekenhuizen moeten dus voldoende operatiezalen en teams hebben.
Een andere toepassing is de toewijzing van kinderen aan openbare scholen in bepaalde schooldistricten in de VS (Abdulkadiroglu en Sönmez, 2003). Lokale wetten bepalen de prioriteit van ieder kind op iedere school. Een kind met een broer of zus op een bepaalde school heeft bijvoorbeeld een hogere prioriteit op deze school dan andere kinderen. In het geval van Boston was er een gecentraliseerd systeem om de kinderen aan de scholen toe te wijzen. Ieder kind (ouders) stuurde een (voorkeur)ranking naar de lokale overheidsinstantie en deze bepaalde een matching op basis van de rankings en de prioriteiten. In het oude systeem zou een kind zijn/haar (daadwerkelijke) eerste keus A bovenaan kunnen plaatsen. Veronderstel nu dat school A “populair” was. In dat geval kon het kind misschien (door een te lage prioriteit) niet op die school terecht. Het grotere en uiteindelijke probleem was dat na de afwijzing door school A er geen beschikbare plaats was op de tweede school B, omdat deze school alle plaatsen al gevuld had met kinderen die B als eerste keus hadden opgegeven. Als gevolg hiervan belandden vaak de “eerlijke” kinderen (ouders) in hun minst gewenste scholen. Alleen strategische ouders waren in staat om hun kinderen in de gewenste scholen te krijgen. Abdulkadiroglu en Sönmez (2003) beschreven rechtszaken die sommige ouders aanspanden omdat hun kind in een ongewenste school C was beland, terwijl het kind een hogere prioriteit had voor school B dan vele andere kinderen die een plaats hadden verworven in school B. Deze problematiek werd veroorzaakt door het feit dat het mechanisme in Boston manipuleerbaar en onstabiel was. Alvin Roth en zijn medewerkers overtuigden de autoriteiten om het mechanisme te vervangen door een mechanisme gebaseerd op het herhaalde-aanzoek algoritme (zie Abdulkadiroglu et al., 2005). Dit mechanisme is nog steeds in (succesvol) gebruik.
Het belang van de theoretische bijdrage van Lloyd Shapley en de toepassingen van Alvin Roth is duidelijk. Het enthousiasme en de energieke aanpak van Alvin Roth hebben geleid tot het ontstaan van een inmiddels grote groep onderzoekers (economen, wiskundigen, computerwetenschappers, etc.) die actief werken aan verbeteringen van inefficiënte of problematische matching-markten in verschillende landen. Marktontwerp mag dan misschien niet in staat zijn om grote financiële crises op te lossen, het is wel zeer bruikbaar voor vele “kleine” maar zeer belangrijke markten. Zelfs levens kunnen worden gered!
Tot slot een persoonlijke noot, Alvin Roth is niet alleen een toponderzoeker. Tijdens mijn verblijf op Harvard Business School heb ik ook gezien dat hij een heel inspirerende docent en begeleider is voor zijn Master en Ph.D. studenten. Daarnaast is Alvin Roth een actieve blogger over marktontwerp. Zijn dagelijks bijgehouden blog houdt ons op de hoogte van recente ontwikkelingen en interessante nieuwtjes of mogelijkheden voor toekomstig onderzoek. Alvin is een heel charmante gastheer met een on-Amerikaans gevoel voor humor. Mocht je hem in deze drukke mediaperiode willen spreken dan is het goed om te weten dat hij dol is op chocolade en Italiaanse espresso…
Referenties
Abdulkadiroglu, A., P.A. Pathak, A.E. Roth, en T. Sönmez (2005) “The Boston Public School Match,” American Economic Review, Papers and Proceedings, 95, 368-371.
Abdulkadiroglu, A. en T. Sönmez (2003) “School Choice: A Mechanism Design Approach,” American Economic Review, 93, 729-747.
Gale D. en L.S. Shapley (1962) “College Admissions and the Stability of Marriage,” American Mathematical Monthly, 69, 9-15.
Kagel, J.H. en A.E. Roth (2000) “The Dynamics of Reorganization in Matching Markets: A Laboratory Experiment Motivated by a Natural Experiment,” Quarterly Journal of Economics, 115, 201-235.
Roth, A.E. (1984) “The Evolution of the Labor Market for Medical Interns and Residents: a Case Study in Game Theory,” Journal of Political Economy, 92, 991-1016.
Roth, A.E. (1990) “New Physicians: A Natural Experiment in Market Organization,” Science, 250, 1524-1528.
Roth, A.E. (1991) “A Natural Experiment in the Organization of Entry Level Labor Markets: Regional Markets for New Physicians and Surgeons in the U.K.,” American Economic Review, 81, 415-440.
Roth, A.E. (2002) “The Economist as Engineer: Game Theory, Experimental Economics and Computation as Tools of Design Economics,” Fisher Schultz lecture, Econometrica, 70, 1341-1378.
Roth, A.E. en E. Peranson (1999) “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review, 89, 748-780.
Roth, A.E., T. Sönmez en U. Ünver (2004) “Kidney Exchange,” Quarterly Journal of Economics, 119, 457-488.
Roth, A.E. and M. Sotomayor (1990) Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Econometric Society Monograph Series, Cambridge University Press.