211service.com
De opkomende revolutie in speltheorie
De wereld van de speltheorie staat momenteel in brand. In mei kondigden Freeman Dyson van de Princeton University en William Press van de University of Texas aan dat ze een voorheen onbekende strategie hadden ontdekt voor het spel van prisoner's dilemma die de ene speler een beter resultaat garandeert dan de andere.
Dat is een monumentale verrassing. Theoretici hebben het Prisoner's Dilemma decennialang bestudeerd en gebruikten het als een model voor het ontstaan van samenwerking in de natuur. Dit werk heeft een diepgaande invloed gehad op disciplines als economie, evolutionaire biologie en natuurlijk de speltheorie zelf. Het nieuwe resultaat zal impact hebben op al deze gebieden en meer.
Het spel is dit: stel je voor dat Alice en Bob een misdaad hebben begaan en worden gearresteerd. De politie biedt iedereen een deal aan - verklikker en jij gaat vrijuit terwijl je vriend 6 maanden in de gevangenis zit. Als zowel Alice als Bob verklikt, krijgen ze allebei 3 maanden cel. Als ze allebei zwijgen, krijgen ze allebei een maand cel voor een lichter misdrijf.
Wat moeten Alice en Bob doen?
Als ze meewerken, zitten ze allebei maar een maand in de gevangenis. Desalniettemin is de beste strategie in een enkel spel om te snaaien, omdat het garandeert dat je niet de maximale gevangenisstraf krijgt.
Het spel wordt echter interessanter wanneer het in herhaalde rondes wordt gespeeld, omdat spelers die in de ene ronde zijn verraden, de kans hebben om hun eigen terug te krijgen in de volgende iteratie.
Tot nu toe dacht iedereen dat de beste strategie in iteratief prisoner's dilemma was om het gedrag van je tegenstanders in de vorige ronde te kopiëren. Deze tit-for-tat-aanpak garandeert dat jullie allebei dezelfde tijd in de gevangenis doorbrengen.
Die conclusie was gebaseerd op tientallen jaren computersimulaties en een zeker blind vertrouwen in de symmetrie van de oplossing.
Dus het nieuws dat er andere strategieën zijn waarmee de ene speler niet alleen de andere kan verslaan, maar ook hun tijd in de gevangenis kan bepalen, is ronduit revolutionair.
De nieuwe benadering wordt de nuldeterminantstrategie genoemd (omdat het het proces omvat waarbij een wiskundig object, een determinant genaamd, op nul wordt gezet).
Het blijkt dat de tit-for-tat-benadering een speciaal geval is van de zero-determinant-strategie: de speler die deze strategie gebruikt, bepaalt dat de tijd van de andere speler in de gevangenis gelijk is aan die van hen. Maar er is een hele reeks andere strategieën die ervoor zorgen dat de andere speler veel meer tijd in de gevangenis doorbrengt (of veel minder als je vrijgevig bent).
Het enige voorbehoud is dat de andere speler zich er niet van bewust moet zijn dat ze worden gemanipuleerd. Als ze de list ontdekken, kunnen ze een strategie spelen die resulteert in de maximale gevangenisstraf voor beide spelers: dwz beide lijden.
Speltheoretici noemen dit het Ultimatum-spel. Het komt overeen met het geven van 100 pond aan Alice en haar vragen om het tussen haar en Bob te verdelen. Bob kan de verdeling accepteren of weigeren als hij denkt dat de verdeling oneerlijk is, in welk geval beide spelers niets krijgen. De weigering is Bobs manier om Alice te straffen voor haar hebzucht.
Het interessante hier is dat wanneer beide spelers zich bewust zijn van de nulbepalende list, het dilemma van de gevangene in een ander spel verandert.
De ontdekking van Press en Dyson heeft gametheoretici ertoe aangezet om de implicaties uit te werken. Ze hebben het prisoner's dilemma gebruikt om inzicht te krijgen in alles, van Koude Oorlog-politiek en onderhandelingen over klimaatverandering tot psychologie en natuurlijk de evolutionaire oorsprong van samenwerking zelf.
Vandaag zien we een van de eerste papers waarin deze implicaties in detail worden bestudeerd. Christoph Adami en Arend Hintze van de Michigan State University in East Lansing onderzoeken of de nuldeterminantenstrategieën evolutionair stabiel zijn.
Dat is een interessante vraag. Het vraagt het volgende: als een hele populatie van individuen allemaal nuldeterminantenstrategieën speelt, zou een andere strategie zich dan door de populatie kunnen verspreiden en het overnemen? Zo niet, dan zijn nuldeterminantenstrategieën evolutionair stabiel.
Adami en Hintze laten zien dat nuldeterminantenstrategieën niet evolutionair stabiel zijn. De reden is dat ze het niet goed tegen elkaar doen en dat laat de deur open voor andere strategieën om binnen te sluipen en het over te nemen.
Nul-determinantenstrategieën zijn op een andere manier niet stabiel. Adami en Hintze laten zien dat als de strategieën van de speler evolueren, de veranderingen die plaatsvinden tussen de ene generatie en de volgende ervoor zorgen dat de nieuwe strategie over het algemeen niet nulbepalend is. Dus de strategie kan niet overleven.
Er is echter één scenario waarin Adami en Hintze zeggen dat de nieuwe strategie stabiel moet zijn. Dat is wanneer de nulbepalende spelers kunnen bepalen of andere spelers dezelfde strategie gebruiken of niet. In dat geval kunnen ze de verliezen vermijden die optreden wanneer ze tegen hun eigen spelers spelen terwijl ze onwetende spelers uitbuiten.
Dus om stabiel te zijn, hebben nulbepalende strategieën aanvullende informatie over hun tegenstanders nodig. Deze informatie geeft hen een duidelijk voordeel, maar waarschijnlijk slechts een tijdelijk voordeel. Zo'n voordeel zal ongetwijfeld van korte duur zijn, aangezien tegengestelde strategieën zich ontwikkelen om de herkenning tegen te gaan, zeggen ze.
Met andere woorden, de andere spelers moeten een soort camouflage ontwikkelen om te voorkomen dat ze worden opgemerkt en uitgebuit.
Dat zou kunnen verklaren waarom niemand in de natuur voorbeelden van nuldeterminante strategieën heeft gevonden: in de meeste gevallen zullen ze niet stabiel zijn en zelfs als ze dat wel zijn, is de situatie waarschijnlijk van korte duur. Zoals Adami en Hintze het in de titel van hun krant zeiden: winnen is niet alles.
Dat wil niet zeggen dat er geen voorbeelden zijn die klaar zijn om gevonden te worden. Integendeel. Dit type evolutionaire wapenwedloop is en zal in de hele biosfeer worden waargenomen, zeggen Adami en Hintze.
Dit is natuurlijk nog maar het begin van een geheel nieuwe benadering van speltheorie die ingrijpende implicaties heeft. Suggesties voor waar dit de meeste impact kan hebben, kunt u vinden in het opmerkingengedeelte.
Referentie: arxiv.org/abs/1208.2666 : Winnen is niet alles: Evolutionaire stabiliteit van Zero Determinant-strategieën