Game Theory deel 1

Game Theory deel 1 0001

Game theory (of speltheorie in het Nederlands) is een tak van de wiskunde waarin het nemen van beslissingen centraal staat. Het biedt een raamwerk waarmee strategische interacties tussen verschillende spelers bestudeerd worden. Het wordt gebruikt in de economie of in de biologie, maar ook voor poker kan het gebruikt worden. Om speltheorie uit te leggen zullen we simpel beginnen, en dat wil zeggen dat er weinig poker in dit artikel zal zitten. Dat zal pas voor een volgend deel zijn, wanneer de basis achter de rug is. Er zullen in deze serie waarschijnlijk drie delen verschijnen. Het bekendste voorbeeld van speltheorie is ongetwijfeld het prisoners dilemma. Velen van zullen dit alvast kennen maar ik zal het nog even uitleggen voor mensen die het nog niet kennen.

Er wordt ergens een ernstig misdrijf gepleegd en de politie pakt twee daders op. Ze zijn er zeker van dat deze mannen het misdrijf hebben gepleegd, maar het bewijs ontbreekt. Ze zitten met de handen in het haar en zoeken naar een manier om de twee daders zo lang mogelijk in de gevangenis te krijgen. Opeens komt er iemand met een briljant idee. De politie zet de twee gevangenen in verschillende kamers en geeft beide gevangenen het zelfde voorstel. Ze kunnen de andere verklikken en zo zelf minder lang de gevangenis in gaan, of ze kunnen zwijgen. Als beide gevangenen zwijgen, dan kan de politie hen niks maken en gaan ze allebei 1 jaar de cel in wegens wapenbezit. Als één gevangene klikt, en de andere zwijgt, dan krijgt de klikker de vrijspraak en de verklikte zal 10 jaar de cel in moeten. Als beide gevangenen verklikken, vliegen ze beiden 8 jaar de cel in (geen volle 10 jaar omdat ze beiden hebben meegewerkt).

Wel laten we deze situatie nu eens in een tabel gieten:

Game Theory deel 1 101

Deze tabel noemt met een payoff matrix. Hierin zien we de uitkomsten voor de twee spelers in dit spel. Eerst staat er de uitkomst voor gevangene 1 (G1) en na de komma staat de uitkomst voor gevangene 2 (G2). Als ze beiden zwijgen vliegen ze beide één jaar de gevangenis is. Als de ene klikt en de andere zwijgt krijgt de ene vrijspraak en de andere tien jaar cel. Tenslotte, als ze allebei klikken krijgen ze allebei acht jaar cel. De uitkomst die de politie prefereert is de situatie waar beiden gevangenen klikken, omdat de straten dan veilig zijn van beiden criminelen. En de politie heeft geluk, want door de manier waarop ze deze situatie hebben opgesteld, zullen beiden daders altijd klikken. Hoe komt dit?

Wel, stel je eens in de plaats van G1. Je zit in je cel na te denken over wat je gaat doen en je bent erg onzeker over wat G2 zal doen, je kunt namelijk geen contact met hem maken. Dus je denkt na over wat er allemaal kan gebeuren. Stel dat hij (G2) klikt, dan is het voor jou ook beter om te klikken, want dan zit je maar acht jaar en geen tien jaar. Stel dat G2 niet klikt, dan is het voor jou beter om te klikken omdat je dan helemaal niet de cel in moet, in tegenstelling tot wanneer je ook zou zwijgen, want dan moet je één jaar de cel in. Dus eigenlijk maakt het niet uit wat G2 zal doen, het is voor jou altijd beter om te klikken. Voor G2 is deze situatie net hetzelfde en voor hem zal klikken ook altijd de beste optie zijn. Misschien denkt G1 wel: "misschien kan ik toch maar beter zwijgen en hopen dat G2 zwijgt, dan zijn we er beide op een jaar vanaf". Maar als G2 dan toch besluit om te klikken moet G1 opeens tien jaar zitten! Wil hij dat risico nemen? Normaalgezien niet en dus zullen beide criminelen op het einde van dit "spel" acht jaar de cel in vliegen.

De situatie waar we in terecht komen noemt het Nash-equilibrium (Nash-evenwicht), genoemd naar de beroemde John Forbes Nash, een grote wiskundige. Meer over hem kan je zien in de prachtige film A Beautiful Mind. Zo'n evenwicht wil zeggen dat in een bepaalde situatie geen enkele speler zijn eigen strategie kan aanpassen en daar winst uit kan halen. En inderdaad, hier kan geen enkele speler van strategie veranderen en daar winst uit halen. Stel dat we in het Nash-evenwicht zitten en dat ze dus beiden klikken en dus beiden 8 jaar de cel in moeten. G1 kan van strategie veranderen en toch zwijgen, maar dan moet hij 10 jaar de cel in in plaats van 8 jaar. Hij wint dus niets. Hetzelfde geldt voor G2. Beide spelers kunnen niet winnen door hun strategie te veranderen.

Er zijn talloze andere voorbeelden te bedenken. Bijvoorbeeld een oorlog tussen twee landen. Een land kan kiezen om oorlog te voeren of geen oorlog te voeren. Het andere land kan dat ook. Als ze beiden geen oorlog voeren hebben ze beide hun oorspronkelijke land. Voert land A oorlog en land B niet, dan heeft A extra land en heeft B veel schade. Voert land B oorlog en land A niet, dan heeft B extra land en heeft A veel schade. Als ze beide oorlog voeren hebben ze beide een beetje schade. Stel dat we hier een payoff matrix van opstellen. Als een partij zijn oorspronkelijke land behoudt geven we die partij een score van 0. Extra land is een score van 10 en veel schade is een score van -10. Een beetje schade is een score van -5.

Game Theory deel 1 102

Ook hier kan je zien dat het voor beide partijen het beste is om oorlog te voeren, ongeacht de strategie van de tegenstander. Stel je in de plaats van land A. Als B aanvalt, kan je ofwel niets doen (-10) ofwel terug aanvallen (-5). Terug aanvallen is hier dus de beste optie want dan lijdt je de minste schade. Als B niet aanvalt kan A kiezen om voor vrede te gaan (0) of om oorlog te voeren (10). Dus ook hier is de beste optie oorlog voeren. Voor land B gaat dezelfde situatie op. Je zit dus dat deze twee landen altijd oorlog zullen voeren en dit is dus het Nash-evenwicht.

De NAVO wil natuurlijk de vrede bewaren op de wereld. Als oplossing voor dit probleem zou de NAVO bijvoorbeeld tegen beide landen kunnen zeggen: "Als je het andere land aanvalt bombarderen we jullie plat". Als de NAVO een land bombardeert heeft dat land uiteraard extra veel schade. Dan ontstaat er bijvoorbeeld de volgende payoff matrix:

Game Theory deel 1 103

Nu verandert de situatie voor beide landen. Stel je opnieuw in de plaats van land A. B kan aanvallen en dan kan je kiezen voor vrede (-10) of voor oorlog (-15). Dit maakt vrede de beste keuze. B kan ook voor vrede gaan en dan kan je ook kiezen voor vrede (0) of oorlog (-10). Ook hier is vrede de beste keuze. Het Nash-evenwicht in deze situatie zal dus vrede voor beide landen zijn. Het ingrijpen van de NAVO heeft effectief de payoffs voor beide landen veranderd waardoor er vrede ontstaat.

Laten we nu een voorbeeld nemen dat al meer aansluit bij poker. Het spelletje heet Odds and Evens en bestaat uit twee tegenstanders die tegelijk een beslissing moeten nemen. Elke speler krijgt een muntje in zijn hand en kan zelf bepalen of hij dit muntje in zijn hand houdt of niet. Op een bepaald moment openen beide spelers hun hand en als het totaal aantal muntjes gelijk is aan 0 of 2 wint speler A, en als het totaal aantal muntjes gelijk is aan 1, dan wint speler B. Iemand die wint krijgt de score +1, iemand die verliest krijgt de score -1. De volgende payoff matrix ontstaat (eerst uitkomst voor A, daarna B):

Game Theory deel 1 104

Dit spel noemt met een constant-sum game. Dat komt omdat de som van de uitkomsten in de tabel altijd gelijk is aan een constante, in dit voorbeeld is deze constante 0. Daarom noemt met dit ook wel eens een zero-sum game. In dit voorbeeld is het duidelijk dat speler A moet proberen om hetzelfde toen doen als B, dan zullen er namelijk altijd 0 of 2 muntjes tevoorschijn komen en zal A winnen. B zijn doel is om net het tegenovergestelde van A te doen, zodat er altijd maar 1 muntje tevoorschijn komt en B wint.

De twee tegenstanders kunnen proberen om elkaar te overtreffen door bijvoorbeeld patronen in het spel van je tegenstander te zoeken en daarop correct te reageren. In dat geval zal de speler die het best is in het vinden van dat soort patronen winnen. Maar er is een andere optie voorhanden. Stel dat je B bent en dat je van jezelf vind dat je slechter bent dan A in dit spel. Wat kan je hieraan doen?

Stel dat je besluit om X % van de tijd 0 muntjes om te draaien en (1-X) % van de tijd 1 muntje om te draaien. A is beter in het spel, kan onze patronen lezen en zal dus één bepaalde optie 100% van de tijd uitvoeren. Laten we even een voorbeeld bekijken. Stel dat we besluiten om 75% van de tijd 0 muntjes om te draaien en 25% van de tijd 1 muntje om te draaien, dus X = 0.75 en 1-X = 0.25. A zal dit patroon snel doorhebben en zal 100% van de tijd 0 muntjes omdraaien om zo zijn EV te maximaliseren. Hoezo? Wel, hieronder volgt de EV formule van A:

EV(A) = (1)(X)(Y) + (1)(1-X)(1-Y) + (-1)(X)(1-Y) + (-1)(X-1)(Y)

Waarbij Y het percentage van de tijd is dat A 0 muntjes omdraait en X zoals reeds besproken het percentage van de tijd is dat wij (speler B) 0 muntjes omdraaien. De formule lijkt nogal ingewikkeld maar is dit eigenlijk niet. Speler A krijgt altijd score +1 als hij dezelfde actie begaat als B, en krijgt altijd de score -1 als zijn actie verschilt van die van B. En omdat A beter is dan ons weet hij dat X = 0.75 en 1-X = 0.25 en dit vult hij dan ook in in zijn EV formule:

EV(A) = (1)(0.75)(Y) + (1)(0.25)(1-Y) + (-1)(0.75)(1-Y) + (-1)(0.25)(Y)

EV(A) = 0.75Y + 0.25 – 0.25 Y – 0.75 + 0.75Y – 0.25Y

EV(A) = Y – 0.5

Nu moet speler A enkel nog een waarde op Y plakken. Als we weten dat Y tussen 0 en 1 moet liggen (omdat het een percentage voorstelt), is deze formule duidelijk optimaal wanneer Y = 1. Zijn EV is dan gelijk aan 1 – 0.5 = 0.5. En inderdaad, dit klopt. Als A namelijk besluit om Y = 1 te spelen en 100% van de tijd 0 muntjes te draaien, zal hij 75% van de tijd winnen en een score krijgen van +1 en 25% van de tijd verliezen en een score krijgen van -1. Dit samen geeft: (0.75)(1) + (0.25)(-1) = 0.5.

Stel nu dat wij (speler B) het net omgekeerd doen, dus X = 0.25 en X-1 = 0.75. Als we dit weer invullen in de EV formule van A dan wordt dit:

EV(A) = (1)(0.25)(Y) + (1)(0.75)(1-Y) + (-1)(0.25)(1-Y) + (-1)(0.75)(Y)

EV(A) = 0.25Y + 0.75 – 0.75Y - 0.25 + 0.25Y -0.75Y

EV(A) = -Y + 0.5

Dit is de EV formule die speler A weet nadat hij ons patroon heeft ontdekt, en ook hier moet Y tussen 0 en 1 liggen. We zien dat nu zijn EV maximaal is als Y = 0, want dan is zijn EV gelijk aan 0.5.

Wat speler A dus doet is ten eerste onze strategie lezen (omdat hij beter is dan wij zijn) en dus onze X te weten komen en vervolgens deze X invullen in zijn EV formule. Vervolgens kiest hij de Y die zijn EV optimaliseert, en dit zal altijd 0 of 1 zijn, gegeven een bepaalde X die speler B kiest. Voor A is het dus duidelijk dat hij altijd een bepaalde actie 100% van de tijd zal uitvoeren, omdat hij onze strategie van tevoren kent wegens zijn skill-voordeel.

A zal door zijn betere skills dus altijd de optimale strategie tegen ons spelen. We noemen A dan de nemesis. De nemesis kent altijd onze strategie en speelt daartegen altijd de maximum EV counterstrategie. Wij als speler B hebben dit feit net ontdekt met al die berekeningen en wenen onszelf in slaap omdat we maar niet kunnen winnen. Maar de dag erna worden we wakker met verse moed! We proberen te zoeken naar de strategie die voor onszelf het beste is, wetende dat A altijd maxEV zal reageren op onze strategie.

Als wij (speler B) besluiten om meer dan 50% van de tijd 0 muntjes om te draaien is onze EV:

EV(B) = (-1)(X) + (1)(1-X)

EV(B) = 1 – 2X

Want we nemen namelijk aan dat A hier altijd 0 muntjes zal omdraaien, omdat hij beter is dan ons en ons patroon zal inzien. Als we dan X % van de tijd 0 muntjes omdraaien, dan draait A ook 0 muntjes om en wint A en is onze score gelijk aan -1. De andere (1-X) % van de tijd draaien we wel een muntje om, A zal geen muntje omdraaien omdat dit zijn optimale strategie is, en dus winnen we 1.

Als wij echter besluiten om meer dan 50% van de tijd 1 muntje om te draaien is onze EV:

EV(B) = (1)(X) + (-1)(1-X)

EV(B) = 2X – 1

Want we nemen namelijk aan dat A hier altijd 1 muntje zal omdraaien, omdat hij beter is dan ons en ons patroon zal inzien. Als we dan X % van de tijd 0 muntjes omdraaien, dan draait A 1 muntje om (wegens beste strategie voor A) en winnen we en is onze score gelijk aan +1. De andere (1-X) % van de tijd draaien we wel een muntje om, A zal ook een muntje omdraaien omdat dit zijn beste strategie is, en dan zal A winnen en is onze score -1.

Onze EV hangt dus af van X. Herinner je dat X gelijk is aan het percentage van de tijd dat we 0 muntjes draaien. Ook hebben we nu twee verschillende EV formules voor twee verschillende strategieën. Strategie 1 houdt in dat we 0 muntjes meer dan 50 % van de tijd zullen omdraaien en de EV formule is hierbij: EV = 1 – 2x. Strategie 2 houdt in dat we 1 muntje meer dan 50% van de tijd zullen omdraaien en de EV formule is hier: EV = 2x – 1.

Laten we deze twee formules eens in een grafiek gieten:

Game Theory deel 1 105

Uit deze tabel kan je opmaken dat het voor ons (speler B) optimaal is om 50% van de tijd een muntje te draaien, en 50% van de tijd geen muntje te draaien. Deze conclusie lijkt logisch voor velen van jullie, maar het kwantificeren van deze gegevens is vaak de moeilijkheid. Voor meer complexe problemen zal het dan ook handig zijn om een beetje ingewerkt te zijn in de hele manier van werken. Strategie 1 is mogelijk van X = 0.5 tot X = 1. Strategie 2 is mogelijk van X = 0 tot X = 0.5. Beide strategieën hebben hun optimum in X = 0.5 en daarbij geldt EV = 0. Aangezien bij elke andere X dan X = 0.5 onze EV negatief is, gaan we speler A counteren door elke actie 50 % van de tijd uit te voeren. Speler A is nu niet langer in staat zijn skill-voordeel te laten gelden. Hij kan nu doen wat hij wil, maar hij zal nooit een EV kunnen behalen die hoger dan 0 is en wij hebben succesvol zijn skill-voordeel kunnen neutraliseren.

Dit voorbeeld toont hoe speltheorie het skill-voordeel van je tegenstander kan neutraliseren. Ook voor poker kunnen we dit soort dingen toepassen, maar dat zal voor een volgende keer zijn.

Hopelijk vonden jullie het interessant. Vragen, opmerkingen, kritiek en dergelijke zijn zoals altijd welkom op het forum of per PM. Tot de volgende keer, waarbij er meer op de relatie tussen game theorie en poker wordt ingegaan.

LEES MEER

Comments

Nog geen reacties. Wees de eerste die post!

Wat denk jij?
Registreer je om een reactie achter te laten of login met facebook