Waarom wiskunde? Omdat je het spel strategisch wilt spelen

In een strategisch spel zijn alle spelers egoïsten. Iedereen speelt voor zichzelf. De uitkomst kan slecht zijn voor de maatschappij. Hoe slecht? Wiskundigen kunnen dat berekenen, doceert Marc Uetz. 

Illustratie Roel Venderbosch Illustratie Roel VeNdeRbosch

Het zijn er niet veel, maar elk jaar komen er wel een paar jongens of meisjes Wiskunde studeren die een bijzondere ‘sport’ beoefenen: schaken. Dezelfde club mensen houdt zich vaak ook bezig met ‘nerdy’ games als Risk, Weerwolven of Magic. Zelf heb ik dat eigenlijk nooit excessief gedaan – met uitzondering van Risk misschien. En als ik nu aan sport denk, heb ik het over voetballen (met de kinderen), of hardlopen (lekker tussendoor of in de middagpauze).

Toch klopt het wel, hard denken is ook een sport, en wie weet, misschien helpt het later voor jouw studie of zelfs een wetenschappelijke carrière. Dat geldt tenminste voor één van onze PhD-studenten, want voor het soort onderzoek waar wij nu mee bezig zijn komt het goed uit dat hij goed in schaken is. En ook in Magic trouwens; hij is recent vicekampioen van de wereld geworden op het Magic Online-kampioenschap.

Maar dat terzijde. Ons onderzoek heeft te maken met optimalisatie en speltheorie, en daar wil ik het over hebben. En in het bijzonder ook over het verkeer.

Om te beginnen een simpel spel

Laat ik beginnen met het simpelste en bekendste voorbeeld van een strategisch spel, het zogenaamde prisoner’s dilemma. Twee misdadigers worden apart van elkaar verhoord. Ze hebben twee opties, namelijk zwijgen of de ander beschuldigen. De sancties zijn als volgt: de veroordeelde moet één jaar naar de gevangenis. Als beiden zwijgen, volgt voor beiden maar één maand opsluiting, vanwege gebrek aan bewijs. Maar je krijgt in elk geval één maand strafvermindering als je helpt de ander te veroordelen.

Waarom dit een dilemma wordt genoemd? Omdat voor elke speler ‘beschuldigen’ de betere optie is, onafhankelijk van wat de ander doet.

Laat het me uitleggen. Stel de ander zwijgt. Doe ik dat ook dan krijg ik één maand, maar als ik hem beschuldig, mag ik meteen naar huis. Stel de ander beschuldigt mij. Als ik zwijg, dan krijg ik één jaar, terwijl ik maar elf maanden krijg als ik hem ook beschuldig. Het dilemma is dus dat de enig logische uitkomst van dit spel is: beschuldigen terwijl het veel beter zou zijn om beiden te zwijgen. Omdat ze niet (kunnen) coöpereren, zit het egoïstisch gedrag ze in de weg, met als resultaat een oplossing die slecht is voor allebei.

De uitkomst waar ze elkaar beschuldigen is een evenwicht van het spel. Een evenwicht is een uitkomst waar geen enkele speler zijn positie kan verbeteren door alleen zijn eigen beslissing aan te passen. Misschien is de naam John Nash wel bekend uit de Hollywoodproductie A Beautiful Mind. Nash heeft in 1994 de Nobelprijs voor economie ontvangen, onder andere voor zijn bewijs uit 1950 dat elk eindig strategisch spel een evenwicht bezit, nu gewoon bekend als Nash-evenwicht.

Wat heeft dit nu met verkeer te maken? Daarvoor gaan we terug naar 1920 en bekijken een voorbeeld van de econoom Arthur Pigou – hier voor het gemak in een wat simpele versie met twee personen. Stel, er zijn twee manieren om van Enschede naar Amsterdam te reizen. Met de auto, dat duurt iets meer dan twee uur, of met een jetpack (raketrugzak). Dat gaat sneller, in maar één uur, maar alleen als de ander de auto neemt. Als beiden dezelfde jetpack willen gebruiken, dan duurt het twee uur. Wat is in deze situatie een Nash-evenwicht? Dat is als beiden de jetpack nemen. Denk daar maar eens over na. En wat is nu maatschappelijk van belang? Dat is de totale hoeveelheid tijd die mensen kwijt zijn. Maar als iedereen maar doet wat voor hem het beste lijkt, is dat niet de beste oplossing voor de maatschappij. Inderdaad, in ons voorbeeld is de totale reistijd in het Nash-evenwicht 2+2=4 uur. Natuurlijk was het beter geweest dat één de auto en de ander de jetpack neemt, want dan is de totale reistijd maar iets meer dan drie uur. Maar dat is geen evenwicht.

Hoe werkt de price of anarchy?

In Pigou’s voorbeeld is de totale reistijd in het Nash-evenwicht precies 33 procent hoger dan de totale reistijd in de optimale oplossing. De Griekse informatici Christos Papadimitriou en Elias Koutsoupias noemden dat in 1999 de price of anarchy: vanwege het gebrek aan centrale coördinatie (een soort van anarchie) kan het resultaat slecht zijn voor de maatschappij. En soms ook voor iedereen. In dit geval 33 procent slechter. Je zou kunnen zeggen dat dit belachelijke voorbeelden zijn… En dat klopt. Maar de jetpack is natuurlijk wel een analogie voor het feit dat de reistijd op een weg toeneemt als er meer mensen gebruik van maken. Zulke modellen worden overal in de wereld gebruikt waar verkeer gemodelleerd wordt.

Daarom is het volgende nu misschien interessant. Zo’n vijftien jaar geleden hebben Tim Roughgarden en Éva Tardos Nash-evenwichten in verkeersnetwerken geanalyseerd. Zij toonden aan dat, als er heel veel reizigers zijn, de totale reistijd in elk evenwicht nooit groter kan zijn dan 33 procent boven het optimum. Ofwel, de price of anarchy is hooguit 33 procent. Met andere woorden, anarchie heeft wel een prijs – maar die is gelukkig niet al te hoog.

Als iedereen maar doet wat goed voor hem of voor haar is, dan komen we tenminste niet in een dilemma terecht zoals de twee misdadigers. Voor hun resultaten over network congestion games hebben Roughgarden en Tardos in 2012 de prestigieuze Gödelprijs ontvangen.

De price of anarchy werd vervolgens voor veel andere situaties geanalyseerd, en niet alleen in verkeersnetwerken. Wat overigens nog wel interessant is om te weten, is dat als het aantal reizigers niet heel groot is, dan kan de price of anarchy in verkeersnetwerken wel groter zijn dan 33 procent. Maar ook weer niet al te slecht: hooguit 100 procent in het geval van twee spelers, en hooguit 150 procent voor drie of meer spelers. Dat werd in 2005 bewezen.

Hoe oplossingen tot stand komen

Wat heeft dit verhaal nu eigenlijk met schaken te maken? Een Nash-evenwicht beschrijft een enigszins stabiele uitkomst in een situatie waar de keuzes van individuen elkaar onderling beïnvloeden. Maar er wordt niet gevraagd hoe deze oplossing tot stand is gekomen. Wat gebeurt er bijvoorbeeld als we individuen opeenvolgende beslissingen laten nemen, net zoals bij het schaken? Alleen met meer dan twee spelers. Dus éérst kiest de eerste, dan de tweede, vervolgens de derde, et cetera. Een mogelijke uitkomst van zo’n spel met volgorde staat bekend als subgame perfect evenwicht. Dit werd in 1965 door Reinhard Selten beschreven, trouwens ook Nobelprijswinnaar in 1994, samen met John Nash.

Enfin, de schaakspeler in de file. Samen met onze PhD-student Jasper onderzoeken wij de effecten als individuen opeenvolgend beslissingen nemen. Net zoals een schaakspeler: uitgaande van vorige beslissingen, beredeneert hij of zij wat de consequenties van de eigen zet voor de volgende spelers zullen zijn. De slimme schaakspeler kan zo voorspellen wat de beste beslissing voor zichzelf is. Toegepast op problemen in verkeersnetwerken hebben wij onlangs aangetoond dat, in het geval van twee spelers, subgame perfect evenwichten hooguit 50 procent boven het minimum kunnen liggen. Spelers opeenvolgend laten beslissen helpt dus, zo lijkt het.

Lang in de file

Een paar maanden lang probeerden wij vervolgens te bewijzen dat de uitkomst van subgame perfect evenwichten – voor meer dan 3 spelers – nooit slechter kan zijn dan 100 procent boven het minimum. Maar dat vermoeden bleek onjuist: In december 2014 hebben wij een tegenvoorbeeld kunnen construeren met 3 spelers dat 113 procent boven het minimum uitkwam. En in mei 2015, dus nog geen twee maanden geleden, hebben wij samen met twee wetenschappers uit Italië en Chili, aangetoond dat – voor heel veel spelers – opeenvolgende beslissingen zelfs tot onbegrensd slechte oplossingen kunnen leiden. Althans, dat kan gebeuren als iedereen slim genoeg is om te beredeneren wat in zo’n spel voor hem- of haarzelf het beste is.

Met andere woorden, de slimme schaakspeler staat mogelijk bijzonder lang in de file! Voor ons was deze ontdekking een grote verrassing. Bovendien is de betekenis van dit soort inzichten ook voor de praktijk van belang, want uiteindelijk streven we, bijvoorbeeld door slimme heffingen, naar een situatie waar strategisch gedrag van individuen – ook schaakspelers – nooit tot situaties leidt die slecht zijn voor de maatschappij.