ESB Promotie
Promotie
I
uitkomst van een spel, die de kwaliteit
n dit proefschrift wordt een aanvan de uitkomst reflecteert. De coörtal onderwerpen in de algoritdinatieratio van een spel, gegeven een
mische speltheorie onderzocht
sociale-welvaartsfunctie, is de factor
met een gemeenschappelijk overkoewaarmee de sociale welvaart van een
pelend thema: samenwerking en exNash-evenwicht van een spel lager is
ternaliteiten tussen de verschillende
dan de optimale sociale welvaart. Een
betrokken partijen in een strategische
belangrijk voorbeeld van een socialesituatie, ofwel tussen de spelers van
welvaartsfunctie is de utilitaire sociale
een spel. Het proefschrift is theorewelvaart, gegeven door de som van de
tisch en analytisch van aard. Alle moindividuele welvaart van alle spelers.
dellen en resultaten zijn echter vanuit
Het is bijvoorbeeld uit eerder onderde praktijk gemotiveerd en hebben
zoek bekend dat de coördinatieratio
directe betrekking op verschillende
2,5 is voor de bovengenoemde klasse
realistische scenario’s.
bart de keijzer
congestiespellen, voor utilitaire sociaAlgoritmische speltheorie is een veld
Postdoctoraal onderzoeker aan de Sapienza
le welvaart. Dat betekent dat, gegeven
dat in de doorsnede van economie, wisUniversiteit van Rome
een congestiespel, de totale welvaart
kunde en informatica ligt. Dit ondervan de spelers in een Nash-evenwicht
zoeksgebied wordt steeds belangrijker
door de steeds groter wordende rol van computers in commer- ten hoogste 2,5 keer zo slecht is als de hoogst haalbare totale
cie en economie. Het gebied houdt zich bijvoorbeeld bezig met welvaart. De coördinatieratio geeft een garantie over de kwalihoe de verschillende uitkomsten van een spel op een efficiënte teit van de Nash-evenwichten van een spel.
In het proefschrift worden boven- en ondergrenzen op de
manier door een computer gevonden kunnen worden.
Een klassieke aanname in speltheorie is dat alle betrokken spe- coördinatieratio afgeleid voor verschillende klassen spellen,
lers onafhankelijk van anderen opereren, en volledig rationeel zowel onder klassieke aannames als onder alternatieve aannaen egoïstisch zijn. Dit leidt ertoe dat de spelers strategieën mes over het gedrag van de spelers. Een van zulke alternatieve
adopteren zonder met elkaar te coördineren, en wel op een aannames is altruïstisch gedrag. Een verrassende observatie
manier die enkel hun eigen welvaart zo hoog mogelijk maakt. is dat altruïstisch gedrag slecht is voor de coördinatieratio in
Er bestaan echter belangrijke scenario’s waarin deze aanname een aantal belangrijke klassen van spellen. Dit geldt al onder
onrealistisch is, en in dit proefschrift wordt onderzocht wat een zeer eenvoudig model van altruïsme. Voorbeeld: in conde impact is van verschillende vormen van ‘met-anderen-reke- gestiespellen gaat de coördinatieratio omhoog van 2,5 naar 3,
ninghoudend’-gedrag. Dit wordt gedaan voor verschillende naarmate de spelers zich altruïstischer gaan gedragen. Deze
belangrijke klassen van spellen. Ten eerste voor verschillende verslechtering van de coördinatieratio kan extreme vormen
soorten veilingen: multi-unit-veilingen, inkoopveilingen, aannemen, en treedt al op in een heel eenvoudige klasse van
GSP-veilingen (dat is het soort veiling dat ten grondslag ligt netwerkformatiespellen waarin de coördinatieratio oneindig
aan bijvoorbeeld het advertentiesysteem van Google). Ten hoog wordt naarmate het altruïsme toeneemt.
tweede voor verschillende soorten congestiespellen, die ver- Dit verslechteringsfenomeen blijkt op te treden in bijna alle
keersnetwerken modelleren, alsmede computernetwerken en klassen van spellen die in het proefschrift onderzocht zijn. Een
datanetwerken. Ten derde voor scheduling-spellen, die sche- intuïtieve verklaring voor het fenomeen is dat de spelers meer
duling-situaties modelleren waarbij meerdere spelers ieder een uitkomsten als ‘stabiel’ zien wanneer ze altruïstischer worden:
taak uit moeten voeren op een beperkte verzameling machines. een altruïstische speler wisselt minder snel van strategie omDe resultaten in het proefschrift zijn uiteenlopend. Een aan- dat hij er andere spelers mee schaadt wanneer hij dat doet, ontal conceptueel interessante bevindingen springen eruit. Om danks dat zijn eigen welvaart ermee omhoog zou kunnen gaan.
die in te zien is eerst enige uitleg nodig over speltheorie. Een Met toenemend altruïsme vergroot de verzameling Nashcentraal begrip in de speltheorie is het Nash-evenwicht. Dit evenwichten (‘stabiele’ uitkomsten) van het spel, en ontstaan
is een uitkomst van een spel die zodanig is dat niemand van er dus ook minder goede Nash-evenwichten, die ervoor zorstrategie kan veranderen om daarmee zijn welvaart te verbe- gen dat de coördinatieratio slechter wordt. Een beleidsmatige
teren. Gerelateerd aan het concept van het Nash-evenwicht, les van het proefschrift is dat het niet altijd goed is voor het
is de price of anarchy, ofwel de coördinatieratio van een spel. functioneren van een systeem om mensen te prikkelen om soDe analyse van de coördinatieratio van verschillende soorten ciaal en altruïstrisch te handelen. Onderzoek naar een formele
spellen vormt een heel belangrijk thema in dit proefschrift. verklaring en een karakterisering van het fenomeen loopt nog.
De coördinatieratio van een spel is gedefinieerd relatief ten
opzichte van een sociale-welvaartsfunctie. Deze fungeert als Keijzer, B. de (2014) Externalities and cooperation in algorithmic game theory.
een kwaliteitsfunctie die een getal toewijst aan elke mogelijke Proefschrift. Amsterdam: Vrije Universiteit Amsterdam, CWI.
556
De auteur heeft verklaard dit artikel alleen te publiceren in ESB en niet elders
te publiceren in wat voor medium dan ook. Het is wel toegestaan om het artikel voor eigen gebruik
en voor publicatie op een intranet van de werkgever van de auteur aan te wenden.
Jaargang 99 (4693) 11 september 2014