Evenwichten in de speltheorie Eva Groenewoud, 27 juni 2011 Bachelorscriptie Begeleiding: Prof. Dr. Krzysztof Apt
Korteweg de Vries Instituut voor Wiskunde Faculteit der Natuurwetenschappen, Wiskunde en Informatica Universiteit van Amsterdam
Samenvatting In deze bachelorscriptie wordt een kijkje genomen in de wereld van de speltheorie. Er wordt gekeken naar verschillende spellen, de strategische spellen en de uitgebreide spellen met perfecte en inperfecte informatie. Veel van deze spellen hebben evenwichten. Er zijn verschillende evenwichten in de speltheorie. In deze bachelorscriptie wordt een aantal van deze evenwichten bestudeerd. Bij de strategische spellen komen het Nash evenwicht, het strikte Nash evenwicht en het correlated evenwicht aan bod. Er zal bewezen worden dat de gemengde uitbreiding van een strategisch spel altijd een Nash evenwicht heeft en dat ieder Nash evenwicht een correlated evenwicht is. Bij de uitgebreide spellen met perfecte en inperfecte informatie zien we het Nash evenwicht terug. Daarnaast wordt het deelspelperfecte evenwicht besproken en zien we dat ieder deelspelperfect evenwicht een Nash evenwicht is.
Gegevens Titel: Evenwichten in de speltheorie Auteurs: Eva Groenewoud,
[email protected], 5732441 Begeleider: Prof. Dr. Krzysztof Apt Einddatum: 27 juni 2011 Korteweg de Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 904, 1098 XH Amsterdam http://www.science.uva.nl/math
Inhoudsopgave 1 Inleiding 1.1 Speltheorie . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Strategische spellen . . . . . . . . . . . . . . . . . . . 1.3 Gemengde strategie¨en . . . . . . . . . . . . . . . . . 1.4 Spellen in uitgebreide vorm . . . . . . . . . . . . . . 1.4.1 Uitgebreide spellen met perfecte informatie . . 1.4.2 Uitgebreide spellen met imperfecte informatie 1.5 Benodigde stellingen . . . . . . . . . . . . . . . . . . 2 Evenwichten in strategische spellen 2.1 Het Nash evenwicht . . . . . . . . . 2.2 Andere evenwichten . . . . . . . . . 2.2.1 Strikte Nash evenwicht . . . 2.2.2 Correlated evenwicht . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . . . .
. . . .
. . . . . . .
. . . .
. . . . . . .
. . . .
. . . . . . .
. . . .
. . . . . . .
2 2 2 6 6 7 9 11
. . . .
12 12 17 17 18
3 Evenwichten in uitgebreide spellen met perfecte informatie 22 3.1 Het Nash evenwicht . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Het deelspelperfecte evenwicht . . . . . . . . . . . . . . . . . . 24 4 Evenwichten in uitgebreide spellen met imperfecte informatie 31 4.1 Het Nash evenwicht . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Het deelspelperfecte evenwicht . . . . . . . . . . . . . . . . . . 31 5 Literatuur analyse
35
6 Populaire samenvatting
38
1
Hoofdstuk 1 Inleiding 1.1
Speltheorie
Het doel van de speltheorie is het begrijpen van situaties waarin besluitvormers op elkaar in werken. De speltheorie houdt zich maar voor een klein gedeelte bezig met de spellen zoals wij die kennen, een competatieve activiteit waarin spelers met elkaar strijden waarbij ze zich moeten houden aan een aantal regels. De speltheorie houdt zich grotendeels bezig met het belichten van economische, politieke en biologische verschijnselen. Een groot gebied binnen de speltheorie zijn de strategische spellen. Deze worden ook wel niet-co¨operatieve spellen genoemd. Strategische spellen zijn modellen van interactie van winst maximaliserende spelers. In zo een spel heeft iedere speler een uitbetaalfunctie en zijn doel is om deze functie te maximaliseren. De waarde van deze functie hangt af van de beslissingen van alle spelers die tegelijkertijd worden genomen.
1.2
Strategische spellen
Definitie 1.1. We beschouwen een verzameling van n spelers {1, . . . , n} met n > 1. Een strategisch spel voor n spelers, geschreven als ((Si )ni=1 , (pi )ni=1 ) bestaat voor elke speler i uit: • een niet lege (mogelijk oneindige) verzameling Si van strategie¨ en, • een uitbetaalfunctie pi : S1 × · · · × Sn −→ R.
2
Aannames 1.2. In deze scriptie worden strategische spellen bestudeerd onder de volgende aannames: • de spelers maken tegelijkertijd hun beslissing, elke speler ontvangt een bepaalde uitbetaling afhankelijk van de gezamelijke strategie, • elke speler is rationaal, dat wil zeggen dat iedere speler als doel heeft om zijn winst te maximaliseren, • alle spelers hebben gemeenschappelijke kennis van het spel en van iedere speler zijn rationaliteit. Voorbeeld 1.3. Een bekend voorbeeld in de speltheorie is het gevangenen dilemma. We beschouwen hierbij twee verdachten van een zware misdaad die opgesloten zijn in twee aparte cellen. Er is alleen genoeg bewijs om beide verdachten te veroordelen voor een lichte misdaad, tenzij ze gaan praten. Wanneer ze beide zwijgen worden ze beide veroordeeld voor de lichte misdaad en moeten ze ´e´en jaar doorbrengen in de gevangenis. Als ze beide praten moeten ze beide drie jaar doorbrengen in de gevangenis. Wanneer ´e´en van de twee praat, wordt degene die praat vrijgesproken en degene die zwijgt veroordeeld tot vier jaar gevangenisstraf. We noteren in het vervolg praten met P en zwijgen met Z. We hebben hier te maken met een strategisch spel bestaande uit twee spelers. Beide spelers hebben de verzameling strategie¨en: S1 = S2 = {P, Z}. We defini¨eren nu de uitbetaalfuncties voor beide spelers: • p1 (P, Z) = 3, p1 (Z, Z) = 2, p1 (P, P ) = 1, p1 (Z, P ) = 0. • p2 (Z, P ) = 3, p2 (Z, Z) = 2, p2 (P, P ) = 1, p2 (P, Z) = 0.
3
We kunnen dit samenvatten in de volgende tabel: Z P
Z 2, 2 3, 0
P 0, 3 1, 1
Figuur 1.1: Gevangenen dilemma Voorbeeld 1.4. Een ander voorbeeld uit de speltheorie is het spel Matching Pennies. Hierbij kiezen twee spelers tegelijkertijd of ze kop of munt van een munt laten zien. Als ze dezelfde kant laten zien, dan betaalt speler 2 aan speler 1 een euro. Als beiden een verschillende kant laten zien, dan betaalt speler 1 een euro aan speler 2. De spelers houden zich alleen bezig met de hoeveelheid geld ze ontvangen en willen natuurlijk het liefst zo veel mogelijk geld ontvangen. Beide spelers hebben de volgende verzameling strategie¨en: S1 = S2 = {Kop, M unt}. We defini¨eren nu de uitbetaalfuncties voor beide spelers: • p1 (Kop, Kop) = 1, p1 (M unt, M unt) = 1, p1 (Kop, M unt) = −1, p1 (M unt, Kop) = −1. • p2 (Kop, Kop) = −1, p2 (M unt, M unt) = −1, p2 (Kop, M unt) = 1, p2 (M unt, Kop) = 1. We kunnen deze gegevens nu samenvatten in de volgende tabel: Kop M unt
Kop 1, −1 −1, 1
M unt −1, 1 1, −1
Figuur 1.2: Matching Pennies 4
Voorbeeld 1.5. Een derde voorbeeld uit de speltheorie is het spel Battle of the Sexes. Hierbij moet een stel beslissen of ze uit gaan naar een voetbalwedstrijd (V ) of naar een balletvoorstelling (B). De man (speler 1) prefereert de voetbalwedstrijd boven de balletvoorstelling en de vrouw (speler 2) prefereert de balletvoorstelling boven de voetbalwedstrijd. Wel prefereren beiden samen uit te gaan boven apart. Beide spelers hebben de volgende verzameling strategie¨en: S1 = S2 = {V, B}. We defini¨eren nu de uitbetaalfuncties voor beide spelers: • p1 (V, V ) = 2, p1 (B, B) = 1, p1 (V, B) = 0, p1 (B, V ) = 0. • p2 (B, B) = 2, p2 (V, V ) = 1, p2 (V, B) = 0, p2 (B, V ) = 0. We kunnen deze gegevens nu samenvatten in de volgende tabel:
V B
V 2, 1 0, 0
B 0, 0 1, 2
Figuur 1.3: Battle of the Sexes Notatie 1.6. We duiden S1 × · · · × Sn aan met S. Ieder element s ∈ S noemen we een gezamelijke strategie of strategie profiel. Het i-de element uit s schrijven we als si . De rij (sj )j6=i korten we af tot s−i . We schrijven voor s ook wel (si , s−i ). Tenslotte korten we ×j6=i Sj af tot S−i . Definitie 1.7. We noemen een strategie si de beste reactie van speler i op een gezamelijke strategie s−i van zijn tegenstanders als ∀s0i ∈ Si : pi (si , s−i ) ≥ pi (s0i , s−i ). 5
1.3
Gemengde strategie¨ en
We gaan nu verder met het bestuderen van oneindige strategische spellen, die worden verkregen uit de reeds bekende eindige strategische spellen door het toestaan van gemengde strategie¨en. Om een definitie te kunnen geven van gemengde strategie¨en, moeten we eerst een kansverdeling defini¨eren die we los laten op de verzameling van strategie¨en Si van speler i. Definitie 1.8. Met een kansverdeling op een eindige niet-lege verzameling A bedoelen we: π : A −→ [0, 1], P waarvoor geldt: a∈A π(a) = 1. We noteren de kansverdeling op A met ∆A. Definitie 1.9. We beschouwen een eindig strategisch spel G := ((Si )ni=1 , (pi )ni=1 ). Een gemengde strategie van speler i in G is de kansverdeling over Si . Dus ∆Si is de verzameling van gemengde strategie¨en van speler i. Notatie 1.10. In het vervolg noteren we een gemengde strategie van speler i met mi en de verzameling van gemengde strategie¨en van speler i noteren we met ∆Si . De gezamelijke gemengde strategie noteren we met m. Definitie 1.11. Wanneer we ook gemengde strategie¨en toestaan in een strategisch spel G := ((Si )ni=1 , (pi )ni=1 ), dan spreken we van de gemengde uitbreiding van het strategische spel. Definitie 1.12. Gegeven een gemengde strategie mi van speler i defini¨eren we: support(mi ) := {a ∈ Si | mi (a) > 0}, deze verzamelingen noemen we de support van mi .
1.4
Spellen in uitgebreide vorm
In de voorgaande paragrafen hebben we kennis gemaakt met strategische spellen. Hier maken de spelers tegelijkertijd hun keus en kunnen dus niet anticiperen op voorgaande gebeurtenissen. In deze paragraaf zullen we kijken naar spellen in uitgebreide vorm. Deze spellen beschrijven een reeks van beslissingen. Waarbij de spelers steeds opnieuw een keuze maken. Ze kunnen hierbij hun keuze maken op basis van de beslissingen van voorgaande spelers. Dit kan alleen wanneer de spelers geinformeerd zijn over de keuzes van de voorgaande spelers, we spreken hierbij van spellen met perfecte informatie. Hierbij kun je denken aan de bekende spellen dammen, schaken en kaarspellen zoals bridge. 6
1.4.1
Uitgebreide spellen met perfecte informatie
Wanneer elke speler op de hoogte is van alle voorafgaande beslissingen van de andere spelers, spreken we van een spel met perfecte informatie. Om de precieze definitie van een uitgebreid spel met perfecte informatie te kunnen geven moeten we eerst een aantal definities geven. Opmerking. Als we in het vervolg spreken over acties bedoelen we de mogelijke of reeds gemaakte keuzes van spelers. Definitie 1.13. Een historie h = (a1 , . . . , ak ) is een rij van acties. Een deelhistorie φ = (a1 , . . . , am ) met 1 ≤ m ≤ k is een deelrij van acties. Een echte deelhistorie is de rij (a1 , . . . , am ) met 1 ≤ m < k. En tenslotte is een complete historie een verzameling van histories die geen echte deelhistorie zijn. Met deze definities kunnen we nu een uitgebreid spel met perfecte informatie defini¨eren. Definitie 1.14. Een spel in uitgebreide vorm met perfecte informatie schrijven we als Γ = (N, T, P, (i )i∈N ). Met • N de verzameling spelers, • T de verzameling van complete histories, • P de spelersfunctie, P (h) ∈ N is de speler die aan zet is na een echte deelhistorie h, • voor iedere i ∈ N is i de preferentie over T . Definitie 1.15. De mogelijke acties voor speler P (h) na geschiedenis h defini¨eren we als A(h) := {a | (h, a) is een historie}. Voorbeeld 1.16. Hieronder een voorbeeld van een spel in uitgebreide vorm met perfecte informatie. Hiervoor geldt: • N = {U, V }. • T = {N ee, (Ja, S), (Ja, F )}. • P (∅) = U en P (Ja) = V . 7
• A(∅) = {Ja, N ee}, A(Ja) = {S, F }, A(N ee) = ∅ en A((Ja, S)) = A((Ja, F )) = ∅.
{{ S {{ { { { }{
V
l U NNN NNN lll l l NNNNee Jalll l NNN l ll l N' l l l l v (1, 2) CC CC F CC CC !
(2, 1)
(0, 0)
Figuur 1.4: Een spel in uitgebreide vorm met perfecte informatie Definitie 1.17. Een strategie si van speler i in Γ = (N, T, P, (i )i∈N ) geeft voor iedere h ∈ H met P (h) = i een actie A(h) aan. Definitie 1.18. Een strategieprofiel s is de reeks van gekozen strategie¨en van een spel. We merken hierbij op dat een strategieprofiel dus niet hetzelfde is als de strategie¨en van een speler. Definitie 1.19. Laat s een strategieprofiel zijn. Dan is O(s) de uitkomst van het strategieprofiel s. Voorbeeld 1.20. In het onderstaande spel in uitgebreide vorm geldt: • N = {Jan, P iet}. • T = {(Ja, C), (Ja, D), (N ee, E), (N ee, F )}. • P (h) = Jan ⇐⇒ h = ∅. • P (h) = P iet ⇐⇒ h = Ja of h = N ee. • Jan heeft de strategie¨en A(∅) = {Ja, N ee}. • P iet heeft de strategie¨en A(Ja)×A(N ee) = {(E, G), (E, H), (F, G), (F, H)}. • O(Ja, C) = (2, 1) en O(N ee, F ) = (1, 2). 8
j Jan TTTT jjj TTT N ee TTT TTT TTT T)
Jajjjjj
jj jjj ujjj P ietGG w GG D w w C ww GG GG w w G# {w w
(2, 1)
P ietGG
ww E www w w w{ w
(3, 0)
(3, 4)
GG F GG GG G#
(1, 2)
Figuur 1.5: Een spel in uitgebreide vorm met perfecte informatie
1.4.2
Uitgebreide spellen met imperfecte informatie
Een andere variant van de uitgebreide spellen zijn de uitgebreide spellen met imperfecte informatie. Hierbij is de speler op het moment dat hij zijn keuze maakt niet op de hoogte van de beslissingen die de voorgaande spelers hebben gemaakt (dit in tegenstelling tot de uitgebreide spellen met perfecte informatie). Om de definitie van een uitgebreid spel met imperfecte informatie te kunnen geven hebben we de definitie van een informatieverzameling nodig. Definitie 1.21. Een informatieverzameling Ii van speler i is een element uit de verzameling Ii = {h ∈ H | P (h) = i}, zodat h, h0 ∈ Ii ∈ Ii =⇒ A(h) = A(h0 ). Definitie 1.22. Een spel in uitgebreide vorm met imperfecte informatie schrijven we als Γ = (N, T, P, fk , (Ii )i∈N , (i )i∈N ). Met • N de verzameling spelers, • T de verzameling van complete histories, • P de spelersfunctie, P (h) ∈ N is de speler die aan zet is na historie h, • als P (h) = k (kanszet), dan is er een kansverdeling fk (h) over de acties A(h) gegeven, 9
• voor iedere i ∈ N is Ii de verzameling van informatieverzamlingen van speler i, • voor iedere i ∈ N is i de preferentie over T . Voorbeeld 1.23. We bekijken een variant van het voorbeeld uit de voorgaande paragraaf. In dit geval weet P iet niet of Jan Ja of N ee gekozen heeft. Dat P iet dat niet weet wordt aangegeven met een stippellijn tussen de twee punten. In dit geval geldt het volgende: • N = {Jan, P iet}. • T = {(Ja, C), (Ja, D), (N ee, C), (N ee, D)}. • P (h) = Jan ⇐⇒ h = ∅. • P (h) = P iet ⇐⇒ h = Ja of h = N ee. • Jan heeft de strategie¨en A(I1 ) = {Ja, N ee}. • P iet heeft de strategie¨en A(I2 ) = {(C, E), (D, F )}. • O(Ja, C) = (2, 1) en O(N ee, C) = (3, 4). • De informatieverzameling van Jan is I1 = ∅. • De informatieverzameling van P iet is I2 = {(Ja, N ee))}.
j Jan TTTT jjj TTT N ee TTT TTT TTT T) / P iet GG w GG F w E www GG GG w w G# w {w
Jajjjjj
jj jjj ujjj P ietGGo w GG D w C www GG GG w w G# w {w
(2, 1)
(3, 0)
(3, 4)
(1, 2)
Figuur 1.6: Een spel in uitgebreide vorm met imperfecte informatie
10
De definities voor een pure en gemengde strategie van speler i in een uitgebreid spel met imperfecte informatie lijken erg op de definitie van een strategie van speler i in een uitgebreid spel met perfecte informatie. Definitie 1.24. Een pure strategie van speler i in een uitgebreid spel met imperfecte informatie is een functie die aan elke informatie verzameling Ii van speler i een actie uit A(Ii ) toekent. Definitie 1.25. Een gemengde strategie van speler i in een uitgebreid spel met imperfecte informatie is een kansverdeling over de pure strategie¨en van speler i.
1.5
Benodigde stellingen
In het vervolg van het stuk is, om een aantal stellingen te kunnen bewijzen, een aantal andere stellingen nodig. Deze zullen we hier benoemen. Ze zullen verder echter niet bewezen worden. Voor het bewijs van de stelling van Nash hebben we de volgende drie stellingen nodig, de topologische stelling van Kakutani, de stelling van het bestaan van extreme waarden van Weierstrass en Brouwers dekpuntstelling. Stelling 1.26. (Kakutani). Laat A een niet lege compacte en convexe deelverzameling van Rn en φ : A −→ P (A) zo dat • φ(x) is niet leeg en convex ∀x ∈ A, • de grafiek van φ, dus de verzameling {(x, y)|y ∈ φ(x)}, is gesloten. Dan bestaat er een x∗ ∈ φ(x∗ ). Stelling 1.27. (Weierstrass). Laat f : S −→ R een continue re¨eelwaardige functie. Waarbij S een niet lege, compacte deelverzameling van Rn is. Dan bestaat er een vector x∗ ∈ S en een vector x˜ ∈ S zo dat f (˜ x) ≤ f (x) ≤ f (x∗ ) voor alle x ∈ S. Stelling 1.28. (Brouwer). Laat S ⊂ Rn een niet lege compacte en convexe verzameling. Laat f : S −→ S een continue functie. Dan bestaat er minstens een dekpunt van f in S. Dat betekent dat er minstens een x∗ ∈ S is waarvoor geldt x∗ = f (x∗ ).
11
Hoofdstuk 2 Evenwichten in strategische spellen 2.1
Het Nash evenwicht
In een spel hangt de beste strategie van een speler i af van de strategie¨en van de andere spelers. Dus wanneer speler i voor een bepaalde strategie si kiest moet hij een idee hebben over de keuze van de andere spelers. Vanwege de eerder genoemde gemeenschappelijke kennis van het spel en de rationaliteit van alle spelers, heeft iedere speler een idee over de keuze van de strategie van de andere spelers. Als het spel is afgelopen en geen enkele speler een hogere uitbetaling kan ontvangen gezien de keuze van de strategie van de andere spelers door van strategie te verwisselen, noemen we deze gezamelijke strategie een Nash evenwicht. Definitie 2.1. We noemen een gezamelijke strategie s∗ een Nash evenwicht als elke s∗i de beste reactie is op s∗−i . Dus wanneer ∀i ∈ {1, . . . , n}, ∀s0i ∈ Si \{s∗i } : p(s∗ ) = pi (s∗i , s∗−i ) ≥ pi (s0i , s∗−i ). Voorbeeld 2.2. Wanneer we nu terug kijken naar het gevangenen dilemma uit hoofdstuk 1, zien we dat dit spel een uniek Nash evenwicht heeft.
Z P
Z 2, 2 3, 0
P 0, 3 1, 1
Figuur 2.1: Gevangenen dilemma
12
De gezamelijke strategie (P, P ) is een Nash evenwicht. In dit punt zou zowel speler 1 als speler 2 niet willen wisselen van strategie gezien de strategiekeuze van zijn tegenstander. Namelijk, stel dat speler 1 toch besluit te zijgen, dan zou zijn uitbetaling van 1 veranderen in 0. Hetzelfde geldt voor speler 2. Het Nash evenwicht (P, P ) is uniek, het is het enige Nash evenwicht. Bekijk het de uitkomst (Z, Z). Wanneer gegeven is dat speler 1 voor Z kiest, had speler 2 liever gekozen voor P . De uitbetaling aan speler 2 zou dan 3 zijn, in plaats van 2. Andersom geldt hetzelfde voor speler 1. Dus (Z, Z) is geen Nash evenwicht. Bekijk nu (Z, P ). Gegeven dat speler 1 voor Z kiest, had speler 2 liever P gekozen. De uitbetaling van speler 2 zou dan 1 zijn, in plaats van 0. Dus (Z, P ) is geen Nash evenwicht. Op analoge wijze volgt ook dat (P, Z) geen Nash evenwicht is. We concluderen dat bij het gevangenen dilemma (P, P ) het enige Nash evenwicht is en daarmee heeft het gevangen dilemma een uniek Nash evenwicht. Wanneer we dit spel bekijken in gemengde strategie¨en komt er geen Nash evenwicht bij. Voorbeeld 2.3. We bekijken nu nogmaals het spel Matching Pennies uit hoofdstuk 1. Kop M unt
Kop 1, −1 −1, 1
M unt −1, 1 1, −1
Figuur 2.2: Matching Pennies Dit is een voorbeeld van een spel met geen Nash evenwicht. Immers bij de uitkomsten (Kop, Kop) en (M unt, M unt) zou speler 2 liever hebben gekozen voor de andere strategie en bij de uitkomsten (Kop, M unt) en (M unt, Kop) zou speler 1 liever hebben gekozen voor een andere strategie. Wanneer we dit spel nu bekijken in gemengde strategie¨en zien we dat wel een evenwicht is, namelijk (( 12 , 12 ), ( 12 , 12 )). Dat dit een Nash evenwicht is volgt uit het feit dat de volgende twee gelijkheden gelden: 1 1 1 1 p1 (Kop, ( , )) = p1 (M unt, ( , )), 2 2 2 2 1 1 1 1 p2 (( , ), Kop) = p2 (( , ), M unt). 2 2 2 2 13
Voorbeeld 2.4. Het spel Battle of the Sexes, ge¨ıntroduceerd in hoofdstuk 1, is een voorbeeld van een spel met twee Nash evenwichten.
V B
V 2, 1 0, 0
B 0, 0 1, 2
Figuur 2.3: Battle of the Sexes In dit voorbeeld is zowel (V, V ) als (B, B) een Nash evenwicht. Het is eenvoudig na te gaan dat deze twee uitkomsten Nash evenwichten zijn. Wanneer we dit spel nu bekijken in gemengde strategie¨en zien we dat er een evenwicht bij komt, namelijk (( 23 , 13 ), ( 13 , 23 )). Dat dit een Nash evenwicht is volgt uit het feit dat de volgende twee gelijkheden gelden: 1 2 1 2 p1 (V, ( , )) = p1 (B, ( , )), 3 3 3 3 2 1 2 1 p2 (( , ), V ) = p2 (( , ), B). 3 3 3 3 Stelling 2.5. (Nash). Elke gemengde uitbreiding van een eindig strategisch spel heeft een Nash evenwicht. Er zijn twee manieren om deze stelling te bewijzen. Voor het eerste bewijs dat we zullen bespreken hebben we de volgende topologische stelling van Kakutani nodig. Deze is terug te vinden in paragraaf 1.4. Bewijs. (Nash 1). Beschouw het eindige strategische spel ((Si )ni=1 , (pi )ni=1 ). We defini¨eren nu de volgende functie: besti (m−i ) := {mi ∈ ∆Si : mi is de beste reactie op m−i }. Nu defini¨eren we de functie: best : ∆S1 × · · · × ∆Sn −→ P (∆S1 × · · · × ∆Sn ), met best(m) := best1 (m−1 ) × · · · × bestn (m−n ). Het is nu eenvoudig in te zien dan m een Nash evenwicht is dan en slechts dan als m ∈ best(m). We kunnen bovendien nagaan dat de functie best(·) voldoet aan de voorwaarden van de stelling van Kakutani. Dat voor alle gezamelijke gemengde strategie¨en m geldt dat best(m) niet leeg is volgt uit de extreme waarden stelling. Deze stelling zegt dat elke continue re¨eelwaardige functie op een compacte deelverzameling van Rn een maximum aanneemt. 14
Een ander bewijs van de stelling van Nash gaat met Brouwers dekpunststelling. Deze is ge¨ıntroduceerd in paragraaf 1.4. Bewijs. (Nash 2). Beschouw het eindige strategische spel G := ((Si )ni=1 , (pi )ni=1 ). We zullen in dit bewijs de existentie van een Nash evenwicht van het spel G aantonen door het bestaan van een dekpunt van een functie f , waarvan de dekpunten Nash evenwichten van G zijn. Het bewijs verloopt in drie stappen: (1) het maken van de functie f , (2) het bewijzen dat f een dekpunt heeft en (3) het laten zien dat dit dekpunt een Nash evenwicht is. We nemen in dit bewijs aan dat i ∈ {1, . . . , n} en dat j ∈ {1, . . . , k}. Stap 1: We defini¨eren de functie f : ∆S −→ ∆S als volgt. Voor elke m ∈ ∆S, elke speler i en zijn pure strategie sji geldt: mi,sj + max{0, pi (sji , m−i ) − pi (m)} . fi,sj (m) = Pi k 0 i 1 + j 0 =1 max{0, pi (sji , m−i ) − pi (m)} Laat nu fi (m) = (fi,s1i (m), . . . , fi,ski (m)) met i ∈ {1, . . . , n} en laat f (m) = P (f1 (m), . . . , fn (m)). Merk op dat voor elke speler i geldt dat kj=1 fi,sj (m) = 1 i
en dat fi,sj ≥ 0 voor alle sji . Daarom geldt dat fi (m) ∈ ∆Si voor elke i, en i dus geldt f (m) ∈ ∆S. Stap 2: De teller van fi,sj is continu in m en de noemer is zowel continu i in m als van onder begrensd (hij wordt nooit minder dan 1). Hieruit kunnen we concluderen dat fi,sj is een continue functie van m voor alle i en sji . Nu i volgt dat f een continue functie is die de niet-lege, compacte en convexe verzameling ∆S naar zichzelf stuurt. We kunnen nu op f de stelling van Brouwer toepassen en concluderen dat f een dekpunt m∗ heeft. Stap 3: Omdat f (m∗ ) = m∗ geldt dat fi,sj (m∗ ) = m∗i,sj voor alle spelers i
sji .
i
i en hun bijbehorende pure strategie Nu volgt uit de definitie van fi,sj i dat m∗i,sj + max{0, pi (sji , m∗−i ) − pi (m∗ )} , m∗i,sj = Pi 0 i 1 + kj0 =1 max{0, pi (sji , m∗−i ) − pi (m∗ )} ofwel m∗i,sj i
k X
0
max{0, pi (sji , m∗−i ) − pi (m∗ )} = max{0, pi (sji , m∗−i ) − pi (m∗ )}.
j 0 =1
15
Wanneer we nu beide kanten vermenigvuldigen met pi (sji , m∗−i ) − pi (m∗ ) en we over sji sommeren geeft dit ons: k X j=1
m∗i,sj [pi (sji , m∗−i ) i
=
k X
∗
− pi (m )]
k X
0
max{0, pi (sji ), m∗−i − pi (m∗ )}
j 0 =1
[pi (sji , m∗−i ) − pi (m∗ )]max{0, pi (sji , m∗−i ) − pi (m∗ )}.
j=1
Wanneer we nu de linkerkant van de gelijkheid nader bekijken, zien we dat deze gelijk is aan nul: k X j=1
m∗i,sj [pi (sji , m∗−i ) i
∗
− pi (m )] =
k X j=1
m∗i,sj pi (sji , m∗−i ) − pi (m∗ ) i
= pi (m∗ ) − pi (m∗ ) = 0. De eerste gelijkheid volgt uit het feit dat mi,sj sommeert tot 1 over j. Nu i volgt dat: 0=
k X
[pi (sji , m∗−i ) − pi (m∗ )]max{0, pi (sji , m∗−i ) − pi (m∗ )}.
j=1
De som over de rechterkant van de gelijkheid kan alleen nul zijn dan en slechts dan als pi (sji , m∗−i ) − pi (m∗ ) ≤ 0 voor alle j. Wanneer zou gelden dat pi (sji , m∗−i ) − pi (m∗ ) > 0 voor een i0 , dan zou de i0 -de term van de som strikt positief zijn en omdat er geen enkele term van de som negatief is zou hiermee de hele som strikt positief zijn. Nu volgt omdat pi (sji , m∗−i ) − pi (m∗ ) ≤ 0 dat pi (sji , m∗−i ) ≤ pi (m∗ ) ∀sji ∈ Si . Hieruit volgt nu dat m∗ een Nash evenwicht is. Nu we weten wat een Nash evenwicht is kunnen we het volgende veelgebruikte lemma gebruiken in de rest van deze scriptie:
16
Lemma 2.6. (Karakterisatie). Beschouw een eindig strategisch spel ((Si )ni=1 , (pi )ni=1 ). De volgende uitspraken zijn dan equivalent: i m is een Nash evenwicht in gemengde strategie¨en, met andere woorden: pi (m) ≥ pi (m0i , m−i ), ∀i ∈ {1, . . . , n} en ∀m0i ∈ ∆Si , ii ∀i ∈ {1, . . . , n} en ∀si ∈ Si pi (m) ≥ pi (si , m−i ), iii ∀i ∈ {1, . . . , n} en ∀si ∈ support(mi ) pi (m) = pi (si , m−i ) and ∀i ∈ {1, . . . , n} en ∀si 6∈ support(mi ) pi (m) ≥ pi (si , m−i ).
2.2
Andere evenwichten
Het in de vorige paragraaf ge¨ıntroduceerde Nash evenwicht is het populairste en meest gebruikte evenwicht in de speltheorie. Er zijn naast het Nash evenwicht echter wel andere evenwichten. Een aantal van deze andere evenwichten in de speltheorie zullen we in deze paragraaf bespreken.
2.2.1
Strikte Nash evenwicht
Een variant van het reeds ge¨ıntroduceerde Nash evenwicht is het strikte Nash evenwicht. Bij het Nash evenwicht is de uitbetaling lager of gelijk wanneer van strategie gewisseld wordt. Bij het strikte Nash evenwicht is de uitbetaling strikt lager wanneer van strategie gewisseld wordt. Definitie 2.7. We noemen een gezamelijke strategie s een strikt Nash evenwicht als ∀i ∈ {1, . . . , n}∀s0i ∈ Si \{si } : pi (si , s−i ) > pi (s0i , s−i ). 17
We kunnen dus zeggen dat ieder strikt Nash evenwicht een Nash evenwicht is, maar niet ieder Nash evenwicht is een strikt Nash evenwicht. Voorbeeld 2.8. We bekijken opnieuw het spel Battle of the Sexes.
V B
V 2, 1 0, 0
B 0, 0 1, 2
Figuur 2.4: Battle of the Sexes We zien hier dat de Nash evenwichten (V, V ) en (B, B) strikte Nash evenwichten zijn. Immers geldt voor (V, V ) dat p1 (V, V ) = 2 > p1 (B, V ) = 0 en p2 (V, V ) = 1 > p2 (V, B) = 0 en voor (B, B) geldt dat p1 (B, B) = 1 > p1 (V, B) = 0 en p2 (B, B) = 2 > p2 (B, V ) = 0. Stelling 2.9. Beschouw een gemengde uitbreiding van een eindig strategisch spel ((Si )ni=1 , (pi )ni=1 ). Voor zo een spel geldt dat ieder strikt Nash evenwicht een gewoon Nash evenwicht is. Bewijs. Dit is een direct gevolg van het Karakterisatie lemma in paragraaf 2.1.
2.2.2
Correlated evenwicht
Een ander evenwicht in de speltheorie is het correlated evenwicht. Definitie 2.10. We noemen x ∈ ∆S een correlated evenwicht als ∀i ∈ {1, . . . , n} en ∀si , s0i ∈ Si geldt: X X x(si , s−i ) · pi (si , s−i ) ≥ x(si , s−i ) · pi (s0i , s−i ). s−i ∈S−i
s−i ∈S−i
Voorbeeld 2.11. Een ander spel in de speltheorie is het angsthazen spel. Hierbij rijden twee automobilisten op een kruising af. Ze kunnen besluiten te stoppen (S) of door te rijden (R). Wanneer ze alle twee doorrijden botsen ze op elkaar en dit is voor beide spelers de minst gewenste uitkomst. De speler die als eerste remt wordt beschouwd als angsthaas en de speler die het langst doorrijdt is de held. Wanneer ze tegelijk remmen blijft hun auto heel en wordt geen van de twee als angsthaas beschouwd. Beide spelers hebben de volgende verzameling strategie¨en: S1 = S2 = {S, R}. We defini¨eren nu de uitbetaalfuncties voor beide spelers: 18
• p1 (R, S) = 5, p1 (S, S) = 4, p1 (S, R) = 1, p1 (R, R) = 0. • p2 (S, R) = 5, p2 (S, S) = 4, p2 (R, S) = 1, p2 (R, R) = 0. We kunnen deze gegevens nu samenvatten in de volgende tabel:
S R
S 4, 4 5, 1
R 1, 5 0, 0
Figuur 2.5: Angsthazen spel Dit spel heeft vijf correlated evenwichten: •
0 1 0 0
•
0 0 1 0
•
1/4 1/4 1/4 1/4
•
0 1/2 1/2 0
•
1/3 1/3 1/3 0
We zullen nu laten zien dat het eerste en het laatste evenwicht inderdaad correlated evenwichten zijn: 19
• Stel s1 = S dan: 0 · 4 + 1 · 1 = 1 en 0 · 5 + 1 · 0 = 0 =⇒ 1 ≥ 0 dus het klopt, Stel s1 = R dan: 0 · 5 + 1 · 0 = 0 en 0 · 4 + 1 · 0 = 0 =⇒ 0 ≥ 0 dus het klopt, Stel s2 = S dan: 0 · 4 + 0 · 1 = 0 en 0 · 5 + 0 · 0 = 0 =⇒ 0 ≥ 0 dus het klopt, Stel s2 = R dan: 1 · 5 + 0 · 0 = 5 en 1 · 4 + 0 · 0 = 4 =⇒ 5 ≥ 4 dus het klopt. Dus ∀i ∈ {1, 2} en ∀si , s0i ∈ {S, R} wordt voldaan aan de definitie voor het correlated evenwicht. • Stel s1 = S dan: 1 5 1 1 5 5 5 1 · 4 + · 1 = en · 5 + · 0 = =⇒ ≥ dus het klopt, 3 3 3 3 3 3 3 3 Stel s1 = R dan: 1 5 1 4 5 4 · 5 + 0 · 0 = en · 4 + 0 · 0 = =⇒ ≥ dus het klopt, 3 3 3 3 3 3 Stel s2 = S dan: 1 1 5 1 1 5 5 5 · 4 + · 1 = en · 5 + · 0 = =⇒ ≥ dus het klopt, 3 3 3 3 3 3 3 3 Stel s2 = R dan: 1 5 1 4 5 4 · 5 + 0 · 0 = en · 4 + 0 · 0 = =⇒ ≥ dus het klopt. 3 3 3 3 3 3 Dus ∀i ∈ {1, 2} en ∀si , s0i ∈ {S, R} wordt voldaan aan de definitie voor het correlated evenwicht. Verder zien we dat het eerste en het tweede correlated evenwicht beiden gewone Nash evenwichten zijn. Namelijk (S, R) respectivelijk (R, S). Daarnaast geldt ook dat het derde correlated evenwicht een evenwicht in gemengde strategie¨en is, waarbij beide spelers kiezen voor de gemengde strategie (1/2, 1/2). 20
Stelling 2.12. Elk Nash evenwicht is een correlated evenwicht. Bewijs. We geven eerst kort het idee van het bewijs. Elk Nash evenwicht kunnen we schrijven als ((p, 1 − p), (q, 1 − q)). Het is nu eenvoudig om hierbij het bijbehorende correlated evenwicht op te schrijven. Deze is namelijk: pq p(1-q) q(1-p) (1-p)(1-q) Dus we zien dat we elk Nash evenwicht, in een 2 bij 2 spel, kunnen schrijven als correlated evenwicht. Nu zullen we het exacte bewijs geven. Stel een gezamelijke strategie m is een Nash evenwicht. Dan geldt: X X ∀i m(s)pi (s) ≥ m0 (s)pi (s), s∈S
s∈S
waarbij m0 (s) = m1 (s1 ) · · · · · m0i (si ) · · · · · mn (sn ), met: 1 als si = s0i 0 mi (si ) = 0 anders waarbij i en s0i willekeurig zijn gekozen (s0i ∈ Si ). Laat m−i (s−i ) = m1 (s1 ) · · · · · mi−1 (si−1 ) · mi+1 (si+1 ) · · · · · mn (sn ). Dan geldt dat m0 (s) = m−i (s−i ) · m0i (si ). Merk hierbij op dat zowel m als m0 kansverdelingen zijn op S. Maar nu geldt: P 0 ) s∈S m(s)pi (si , s−iP P = s−i ∈S−i mi (si )( si ∈Si mi (si ))pi (s0i , s−i ) P = s−i ∈S−i mi (si )pi (s0i , s−i ) P P = si ∈Si ,si =s0 m−i (s−i )m0i (si )pi (s0i , s−i ) + si ∈Si ,si 6=s0 m−i (s−i )m0i (si )pi (s0i , s−i ) i i P = s∈S m0 (s)p(s). Dus nu volgt dat m ook een correlated evenwicht is.
21
Hoofdstuk 3 Evenwichten in uitgebreide spellen met perfecte informatie Net als bij de eerder besproken strategische spellen zijn er bij de spellen in uitgebreide vorm ook verschillende evenwichten. In dit hoofdstuk zullen we een aantal van deze evenwichten bespreken. Het bekende Nash evenwicht komt weer aan bod en daarnaast bespreken we het deelspel perfecte evenwicht.
3.1
Het Nash evenwicht
De definitie van het Nash evenwicht bij uitgebreide spellen met perfecte informatie is slechts een aanpassing van de definitie van het Nash evenwicht bij strategische spellen. Definitie 3.1. Het strategieprofiel s∗ in een uitgebreid spel met perfecte informatie is een Nash evenwicht als voor eleke speler i en elke strategie si van speler i geldt dat de uitkomst O(s∗ ) minstens zo goed is voor speler i volgens zijn preferenties als de uitkomst O(si , s∗−i ) waarbij speler i kiest voor strategie si en de andere spelers kiezen voor s∗j . Dus er geldt: pi (O(s∗ )) ≥ pi (O(si , s∗−i )) voor elke strategie si van speler i, waarbij pi de uitbetaalfunctie is van speler i en O de uitkomst functie van het spel is. Opmerking. In het vervolg nemen we aan dat pi (O(s)) = O(s) om verwarring te voorkomen. De uitkomsten onderaan de spelboom zijn dus meteen de uitbetaling. 22
Een manier om de Nash evenwichten van een uitgebreid spel met perfecte informatie te vinden is door het spel om te schrijven naar een strategische vorm. Het moet hierbij natuurlijk wel zo zijn dat elke speler een eindig aantal strategie¨en heeft. We maken hierbij dus een lijst met de strategie¨en van elke speler en we zoeken dan de uitkomst die hoort bij het strategieprofiel op. Hoe dat precies gaat laten we zien in het volgende voorbeeld. Voorbeeld 3.2. We bekijken het volgende spel in uitgebreide vorm met perfecte informatie:
1H vv HHHH vv HN v HHee v HH vv v $ vz v (2, 0) 2G || GGGG | C || GGD GG || G# | | ~| (3, 1) 1B || BBB | BBN ee Ja || BB || B ~|| Ja
(1, 2)
(0, 0)
Figuur 3.1: Een spel in uitgebreide vorm met perfecte informatie We kunnen dit spel omzetten naar de volgende strategische vorm:
Ja, Ja Ja, N ee N ee, Ja N ee, N ee
C 1, 2 0, 0 2, 0 2, 0
D 3, 1 3, 1 2, 0 2, 0
Figuur 3.2: Het spel in strategische vorm Uit zo een strategische vorm kunnen we gemakkelijk de Nash evenwichten halen(dit hebben we gezien in hoofdstuk 2). We zien dus dat deze Nash evenwichten de volgende strategieprofielen zijn: ((Ja, N ee), D), ((N ee, Ja), C) en ((N ee, N ee), C). 23
Opmerking. De verzameling Nash evenwichten van een spel in uitgebreide vorm met perfecte informatie is hetzelfde als de verzameling Nash evenwichten van de strategische vorm van het spel.
3.2
Het deelspelperfecte evenwicht
Het Nash evenwicht uit de vorige paragraaf houdt geen rekening mee met de structuur van het uitgebreide spel. Het gaat er vanuit dat de strategie¨en voordat het spel begonnen is al zijn gekozen. Dit is natuurlijk niet het geval. De spelers kiezen na de beslissing van de voorgaande speler voor een bepaalde strategie. In deze paragraaf zullen we een evenwicht defini¨eren die uit gaat van een optimale keus voor elke speler, gegeven de stategieen van de andere spelers. Om dit evenwicht goed te kunnen defini¨eren moeten we eerst de definitie van een deelspel introduceren. Definitie 3.3. Gegeven is een uitgebreid spel met perfecte informatie Γ = (N, T, P, (i )i∈N ). Voor iedere historie h defini¨eren we een deelspel Γ(h) = (N, T h , P h , (hi )i∈N ) met: • N spelers. • T h = {h0 | (h, h0 ) ∈ T }. • P h (h0 ) = P (h, h0 ) voor elke (h, h0 ) ∈ T . • h0 hi h00 ⇐⇒ (h, h0 ) i (h, h00 ). Opmerking. Γ(∅) = Γ.
24
Voorbeeld 3.4. We bekijken het volgende spel Γ in uitgebreide vorm met perfecte informatie uit een eerder voorbeeld:
j Jan TTTT jjj TTT N ee TTT TTT TTT T)
Jajjjjj
jj jjj ujjj P ietGG w GG D w w C ww GG GG w w G# {ww
(2, 1)
P ietGG
ww E www w w w{ w
(3, 0)
(3, 4)
GG F GG GG G#
(1, 2)
Figuur 3.3: Een spel in uitgebreide vorm met perfecte informatie Hiervoor geldt: • Deelspel Γ(∅) = Γ. • Deelspel Γ(Ja) is:
ww w{ w
P ietGG
ww
C www
GG D GG GG G#
(2, 1)
(3, 0)
Figuur 3.4: Γ(Ja)
25
• Deelspel Γ(N ee) is:
ww w{ w
P ietGG
ww
E www
GG F GG GG G#
(3, 4)
(1, 2)
Figuur 3.5: Γ(N ee) Definitie 3.5. s∗ is een deelspelperfect evenwicht als voor iedere i ∈ N , iedere historie h met P (h) = i en iedere strategie si van speler i geldt: pi (Oh (s∗ )) ≥ pi (Oh (si , s∗−i )). Waarbij Oh (s) de complete historie is in Γ van h gevolgd voor de rij van acties geinduceerd door s. Opmerking. Als h = ∅ dan geldt dat Oh (s) = O(s). Dit impliceert dat ieder deelspelperfect evenwicht ook een Nash evenwicht is. Opmerking. Een deelspelperfect evenwicht s∗ induceert een Nash evenwicht in ieder deelspel Γ(h) voor elke historie h. Voorbeeld 3.6. We bekijken het spel Γ in uitgebreide vorm met perfecte informatie:
V rouw II
uu X uuu u uu zu u
(2, 1)
M an PP PPP jjjj j j j PN Ja PPee jj j j PPP j j j j PP( j j t j
II IIY II II $
(1, 2)
(0, 0)
Figuur 3.6: Een spel Γ in uitgebreide vorm met perfecte informatie 26
Voor dit spel Γ geldt: • De Nash evenwichten van Γ zijn {(Ja, X), (N ee, Y )}. • Voor het deelspel Γ(Ja) is het Nash evenwicht X.
tt z t t
V rouw JJ
tt
X ttt
JJ Y JJ JJ J%
(2, 1)
(0, 0)
Figuur 3.7: Γ(Ja) • Het deelspelperfecte evenwicht van Γ is (Ja, X). Het vinden van een deelspelperfect evenwicht gebeurt met terugwaartse inductie (backward induction). Om deze methode toe te kunnen lichten hebben we nog een definitie nodig. Definitie 3.7. We defini¨eren de lengte van een deelspel als de lengte van de langste geschiedenis binnen dat deelspel. Een deelspel van lengte 1 is dus het ’onderste’ deelspel. De methode van terugwaartse inductie gaat nu als volgt. We beginnen met het zoeken naar de optimale acties van de speler die zijn keuze maakt in het deelspel met lengte 1 (dus de onderste deelspellen). Nu nemen we deze keuze als gegeven. Dan bekijken we nu wat de optimale keus is voor de speler die als eerste zijn keuze maakt in de deelspellen van lengte 2. Dit blijven we herhalen totdat we helemaal aan het begin zijn van het spel. We lichten deze methode nader toe in het volgende voorbeeld:
27
Voorbeeld 3.8. We bekijken het volgende uitgebreide spel Γ met perfecte informatie:
ll 1 RRRRR RRR D lll RRR RRR RRR R( 2C {{ CCC G {{ CCH CC {{ }{{ !
Cllll
ll lll l l vll 2 CC { CC { E {{ CCF { CC { }{{ !
(2, 1)
(3, 0)
(3, 4)
(1, 2)
Figuur 3.8: Γ We bekijken eerst de deelspellen met lengte 1. Dat zijn er 2, namelijk Γ(C) en Γ(D). In het deelspel Γ(C) is de optimale keus voor speler 2 E en in het deelspel Γ(D) is de optimale keus voor speler 2 G. Deze optimale keuzes geven we in de onderstaande figuur aan met de dubbele pijlen. Nu bekijken we de deelspellen van lengte 2. Dit is er maar 1, namelijk het hele spel Γ. Gegeven de optimale keuzes die speler 2 maakt in de ronde na speler 1, E als speler 1 voor C kiest en G als speler 1 voor D kiest, bepalen we nu wat de optimale keuze is voor speler 1. Kiest speler 1 voor C dan is de uitkomst voor speler 1 gelijk aan 2. Kiest speler 1 voor D dan is de uitkomst voor speler 1 gelijk aan 3. Dus is de optimale keus voor speler 1 D. We geven deze optimale keus ook aan met een dubbele pijl.
28
l 1 RR RR R lll l R RR D l C ll R RR R lll l R RR R l l l R $, vlll 2 2C C { C {{{ {{{{ CCC CC { { { { { { E {{ G {{ CCF CCH CC CC {{{{ {{{{ y {{{ ! y {{{ !
(2, 1)
(3, 0)
(3, 4)
(1, 2)
Figuur 3.9: Het deespelperfecte evenwicht van Γ Het deelspelperfecte evenwicht is nu de strategie (D, (E, G)). De uitkomst van dit deelspelperfecte evenwicht is, de uitkomst wanneer je door de speelboom loopt alleen via de dubbele pijlen. In dit geval is dat dus (3, 4). Voorbeeld 3.9. Een ander bekend spel uit de speltheorie is het Duizendpoten spel . Hierbij kiezen de spelers om de beurt of ze willen stoppen (S) of doorgaan (D). Als speler 1 kiest om te stoppen is het spel afgelopen, wanneer speler 1 kiest om door te gaan is speler 2 aan de beurt. Kiest speler 2 om te stoppen is het spel afgelopen, kiest speler 2 om door te gaan is speler 1 weer aan de beurt. Zo gaat het spel door, totdat beide spelers n keer aan de beurt zijn geweest. Bij de laatste beurt van speler 2 is het spel soieso afgelopen of speler 2 zou voor S of D kiest. Alleen de uitbetalingen zijn anders.
D
1
S
/2
(4, 1)
D S
(2, 8)
/
D
1
S
(16, 4)
/2
D
/
(64, 16)
S
(8, 32)
Figuur 3.10: Het Duizendpoten spel (n = 2) Bij het bovenstaande Duizendpoten spel geldt dat n = 2. Het deelspelperfecte evenwicht vinden we met behulp van terugwaartse inductie. In het 29
deelspel met lengte 1 zal speler 2 voor S kiezen, dan is zijn uitbetaling namelijk 32 in plaats van 16. Speler 1 zal daarom bij het deelspel met lengte 2 kiezen voor S, want zijn uitbetaling is dan hoger, gegeven dat speler 2 in de beurt daarna voor S kiest. Bij het deelspel met lengte 3 kiest speler 2 ook om te stoppen S. En bij het deelspel met lengte 4 kiest speler 1 ook om te stoppen, omdat hij dan gegeven de keuzes die de andere speler zal maken de hoogste uitbetaling kan halen. Het deelspel perfecte evenwicht is in onderstaande figuur aangegeven met de dubbele pijlen.
D
1
S
(4, 1)
/2
D S
(2, 8)
/
D
1
S
(16, 4)
/2
D
/
(64, 16)
S
(8, 32)
Figuur 3.11: Het Duizendpoten spel (n = 2) met het deelspelperfecte evenwicht Het deelspelperfecte evenwicht is dus ((S, S), (S, S)) en de bijbehorende uitbetaling is (4, 1). Stelling 3.10. Elk eindig uitgebreid spel met perfecte informatie heeft een deelspelperfect evenwicht. Bewijs. We bekijken het eindige uitgebreide spel Γ met perfecte informatie. Eerst beschouwen we nu de deelspellen met lengte 1. Dat deze deelspellen bestaan volgt uit het feit dat Γ eindig is. Het is duidelijk dat we bij deze deelspellen de optimale keus kunnen maken. Beschouw nu de deelspellen met lengte 2. Gegeven de optimale keus in de deelspellen met lengte 1, is het nu weer mogelijk om de optimale keus te maken. De inductie hypothese is nu dat het voor de deelspellen met lengte n mogelijk is om de optimale keus te maken. We laten nu zien dat het dan ook mogelijk is voor de deelspellen met lengte n + 1 om een optimale keus te maken. Omdat de keuzes die gemaakt worden in de deelspellen van lengte 1 tot en met lengte n gegeven zijn is het voor de speler in het deelspel met lengte n + 1 ook weer mogelijk om een optimale keus te maken gegeven de keuzes is de deelspellen van lengte 1 tot en met lengte n. Hiermee hebben we aangetoond dat elk eindig uitgebreid spel met perfecte een deelspelperfect evenwicht heeft. 30
Hoofdstuk 4 Evenwichten in uitgebreide spellen met imperfecte informatie De evenwichten in uitgebreide spellen met imperfecte informatie zijn dezelfde als bij de uitgebreide spellen met perfecte informatie, het Nash evenwicht en het deelspelperfecte evenwicht.
4.1
Het Nash evenwicht
De definitie van het Nash evenwicht in een uitgebreid spel met imperfecte informatie is exact hetzelfde als de definitie van het Nash evenwicht in een uitgebreid spel met perfecte informatie. Voor deze definitie verwijzen we dus terug naar paragraaf 3.1.
4.2
Het deelspelperfecte evenwicht
De definitie van het deelspelperfecte evenwicht voor uitgebreide spellen met imperfecte informatie is eigenlijk hetzelfde als het deelspelperfecte evenwicht voor uitgebreide spellen met perfecte informatie alleen moeten we de definitie van een deelspel iets aanscherpen.
31
Definitie 4.1. Gegeven is een uitgebreid spel met imperfecte informatie Γ = (N, T, P, fk , (Ii )i∈N , (i )i∈N ). Voor iedere historie h defini¨eren we een deelspel Γ(h) = (N, T h , P h , fkh , (Iih )i∈N , (hi )i∈N ) met: • N spelers. • T h = {h0 | (h, h0 ) ∈ T }. • P h (h0 ) = P (h, h0 ) voor elke (h, h0 ) ∈ T . • h0 hi h00 ⇐⇒ (h, h0 ) i (h, h00 ). • Een historie h definieert een deelspel als I(h) = {h} en als h0 een verlenging is van de historie h en h00 zit in de informatieverzamling I(h0 ) van h0 dan is h00 ook een verlenging van h. Voorbeeld 4.2. We bekijken het volgende uitgebreide spel Γ met imperfecte informatie.
mm 1 SSSSSS mmm SSS D m m SSS mm m SSS m mm C SSS m m m ) m vm (3, 0) m 2 QQQQ m m QQQ mm m Q m F QQQ mmm QQQ mmm E QQQ m m m Q(/ m vmo 1C 1 C C { CC {{ CCC { { { Y CCY CC { { CC CC {{X {{X { { }{ ! }{ !
(2, 1)
(4, 3)
(1, 2)
(0, 0)
Figuur 4.1: Een spel in uitgebreide vorm met imperfecte informatie Γ heeft twee deelspellen: Γ(∅) = Γ en Γ(C):
32
R lll 2 RRRRR RRRF lll l l RRR l llE RRR l l RRR ll l l vlo (/ 1 { CCC { 1 CCC { { CCY CCY {{ {{ CC CC {{X {{X C C! { { }{ ! }{
(2, 1)
(4, 3)
(1, 2)
(0, 0)
Figuur 4.2: Γ(C) Γ(C, E) en Γ(C, F ) zijn geen deelspellen, omdat (C, E) ∈ I1 en (C, F ) ∈ I1 . Anders gezegd, wanneer je de deelspellen Γ(C, E) en Γ(C, F ) zou willen tekenen moet je de informatieverzameling van speler 1 (de stippellijn) als het ware ”doormidden snijden”, dit mag niet volgens de definitie van een deelspel van uitgebreide spellen met imperfecte informatie. Nu we de definitie van een deelspel voor uitgebreide spellen met imperfecte informatie hebben aangepast, is de definitie voor het deelspelperfecte evenwicht precies hetzelfde als voor de uitgebreide spellen met perfecte informatie. We herhalen deze definitie en lichten hem dan toe aan de hand van een voorbeeld. Definitie 4.3. s∗ is een deelspelperfect evenwicht als voor iedere i ∈ N , iedere historie h met P (h) = i en iedere strategie si van speler i geldt: pi (Oh (s∗ )) ≥ pi (Oh (si , s∗−i )). Waarbij Oh (s) de complete historie is in Γ van h gevolgd voor de rij van acties geinduceerd door s. Voorbeeld 4.4. We bekijken opnieuw het uitgebreide spel met imperfecte informatie dat ge¨ıntroduceerd is in het vorige voorbeeld. In het deelspel Γ(C) worden de optimale keuzes aangegeven met de dubbele pijlen:
33
l 2 RRRR lll RRR lll RRFR l l l RRR l ll E RRR l l l RR( l rzo /1C 1 CCCC CCCC { { C { { C CCCC CCCCCY { { CCCYC { { C { { CCC C CCC { { }{{ X % }{{ X %
(2, 1)
(4, 3)
(1, 2)
(0, 0)
Figuur 4.3: De optimale keuzes in Γ(C) Gezien de optimale keuzes in het deelspel Γ(C) zal speler 1 kiezen in zijn eerste beurt voor C. Het deelspelperfecte evenwicht is dus ((C, X), E) en wordt weergegeven in de onderstaande spelboom met de dubbele pijlen. De uitbetaling in het deelspelperfecte evenwicht is (4, 3).
mm 1 SSSSS SSS mmm m m SSD mm SSS m m SSS m m C m SS) m rz mm Q (3, 0) m 2 Q m QQQ mmm QQQ F m m QQQ mmm QQQ mmm E m QQQ m m Q(/ m rzo 1 CC 1 C CCCC { {{ CCCCCCC { CCCC { { Y CCCYC CCCC { { CCC CCC {{X {{X { { }{ % } % {
(2, 1)
(4, 3)
(1, 2)
(0, 0)
Figuur 4.4: Het deelspelperfecte evenwicht van Γ
34
Hoofdstuk 5 Literatuur analyse Wanneer je verschillende literatuur over de speltheorie bestudeert kom je erachter dat bijna iedere auteur een andere opbouw hanteert en daarnaast ook soms een compleet andere notatie gebruikt. In dit hoofdstuk zal een analyse worden gegeven van de verschillen in de opbouw in boeken over speltheorie van verschillende auteurs. Hierbij wordt gekeken naar de volgorde van introduceren van de onderwerpen die in deze bachelorscriptie zijn behandeld en in hoeverre de onderwerpen van deze bachelorscriptie aan bod komen in de verschillende boeken. In deze bachelorscriptie is ervoor gekozen om in de inleiding een introductie te geven van de verschillende soorten spellen, eerst de strategische spellen en de gemengde uitbreiding daarvan en daarna de spellen in de uitgebreide vorm met perfecte informatie en tenslotte de spellen met imperfecte informatie. Daarna wordt in verschillende hoofdstukken een uiteenzetting gegeven over de verschillende soorten evenwichten die je tegenkomt bij ieder van deze spellen. Voor deze structuur is gekozen, omdat het doel was vooral de nadruk te leggen op de verschillende evenwichten die je tegenkomt in de speltheorie. Omdat het daarbij noodzakelijk is voldoende te weten van de verschillende spellen, worden deze ge¨ıntroduceerd in de inleiding. Voor het schrijven van deze scriptie is veel gebruik gemaakt van het boek An Introduction To Game Theory van Matrin Osborne. Osborne heeft qua volgorde van het introduceren van de verschillende spellen dezelfde volgorde als gehanteerd wordt in deze bachelorscriptie. Waarin Osborne wel verschilt is dat hij na het introduceren van een spel meteen de verschillende evenwichten van het ge¨ıntroduceerde spel bespreekt. Osborne bespreekt vrijwel dezelfde evenwichten als in deze scriptie alleen het correlated evenwicht ontbreekt bij de strategische spellen. 35
In het boek Advanced Microeconomic Theory van Geoffrey Jehle en Philp Reny gaat slechts een van de negen hoofdstukken over speltheorie. Toch weten ze in dit ene hoofdstuk alle soorten spellen die in deze bachelorscriptie zijn besproken te introduceren. Net als Osborne kiezen Jehle en Reny ervoor om de evenwichten direct na de beschrijving van het spel te introduceren. Bij de strategische spellen ontbreekt het strikte Nash evenwicht en het correlated evenwicht. De evenwichten die bij de spellen in uitgebreide vorm worden besproken zijn dezelfde als in deze bachelorscriptie. Robert Gibbons heeft in zijn boek A Primer In Game Theory ook voor dezelfde volgorde van het introduceren van de spellen gekozen. Dus eerst de strategische spellen, daarna de uitgebreide spellen met perfecte informatie en tenslotte de uitgebreide spellen met imperfecte informatie. De evenwichten bespreekt hij direct na het introduceren van het spel. Bij de strategische spellen heeft hij ervoor gekozen alleen het Nash evenwicht te bespreken, eerst in pure strategie¨en en daarna in de gemengde strategie¨en. Bij de spellen in uitgebreide vorm wordt het Nash evenwicht niet besproken. Wel bespreekt hij bij de uitgebreide spellen met perfecte informatie het deelspelperfecte evenwicht. Bij de spellen in uitgebreide vorm met imperfecte informatie doet Gibbons dit echter niet. In het boek Games and Decision Making beginnen Charalambos Aliprantis en Subis Chakrabari met het introduceren van strategische spellen. Ze beginnen met de pure strategie¨en en het daarbij behorende Nash evenwicht, waarna ze verder gaan met de gemengde strategie¨en. Bij de uitgebreide spellen worden eerst de spellen met perfecte informatie besproken en daarna de spellen met imperfecte informatie. Bij deze spellen wordt zowel het Nash evenwicht als het deelspelperfecte evenwicht besproken. Het deelspelperfecte evenwicht wordt wel echter pas ge¨ıntroduceerd bij de spellen met imperfecte informatie. Eric Rasmusen pakt het in zijn boek Games And Information, An Introduction to Game Theory anders aan dan we tot nu toe gezien hebben. Voordat hij de formele definities van de spellen geeft, introduceert hij al het Nash evenwicht. Daarna introduceert hij de spellen in dezelfde volgorde als in deze bachelorscriptie. Het deelspelperfecte evenwicht introduceert hij voor de uitgebreide spellen later in het boek. Dit doet hij echter alleen voor de uitgebreide spellen met perfecte informatie. In zijn boek Game Theory, Decisions, Interaction and Evolution 36
kiest James Webb voor dezelfde structuur als waarvoor is gekozen in deze bachelorscriptie wat betreft het introduceren van de spellen. Hij introduceert eerst de strategische spellen, zowel met pure als gemengde strategie¨en. Na het introduceren hiervan behandelt hij het Nash evenwicht. Het strikte Nash evenwicht en het correlated evenwicht ontbreken. Hierna bespreekt Webb de uitgebreide spellen met prefecte informatie waarbij hij direct het Nash evenwicht behandeld. Tenslotte komen de uitgebreide spellen met imperfecte informatie aanbod. Na deze geintroduceert te hebben bespreekt Webb het deelspelperfecte evenwicht. Het Nash evenwicht wordt hier niet opnieuw besproken. Hans Peters begint zijn boek Game Theory, A Multi-Leveled Approach met het introduceren van de strategische spellen waarbij hij het Nashe evenwicht direct bespreekt voor zowel de pure als gemengde strategie¨en. Het strikte Nash evenwicht en het correlated evenwicht noemt hij hierbij niet. Hierna bespreekt hij de uitgebreide spellen, eerst de spellen met perfecte informatie en daarna de spellen met imperfecte informatie. Hij bespreekt hierbij het Nash evenwicht voor beide spellen. Het deelspelperfecte evenwicht wordt als laatste door Peters behandeld. Het boek An Introduction Cource On Mathematical Game Theory geschreven door Julio, Gonzalez-Diaz, Ignacio Garcia-Jurado en Gloria Fiestras-Janeiro kent qua introduceren van de verschillende spellen dezelfde volgorde als in deze scriptie. Na het introduceren van de strategische spellen in pure strategie¨en wordt het Nash evenwicht besproken. Hierna worden de gemengde strategie¨en ge¨ıntroduceerd en wordt opnieuw het Nash evenwicht genoemd. In dit boek kom je ook het correlated evenwicht tegen. Het strikte Nash evenwicht ontbreekt wel. Na de strategische spellen worden de spellen in uitgebreide vorm behandeld. Eerst de spellen met perfecte informatie, daarna de spellen met imperfecte informatie. Bij de spellen met perfecte informatie wordt zowel het Nash evenwicht als het deelspelperfecte evenwicht behandeld. Deze evenwichten worden niet behandeld bij de spellen met imperfecte informatie. Stef Tijs behandelt alle spellen en evenwichten die aan bod komen in deze scriptie in de inleiding van zijn boek Introduction To Game Theory . De definities van deze spellen komen nauwelijks aan bod. De evenwichten die hij noemt zijn het Nash evenwicht en het deelspelperfecte evenwicht. Het correlated evenwicht in de strategische spellen bespreekt Tijs niet.
37
Hoofdstuk 6 Populaire samenvatting In deze bachelorscriptie is een introductie gegeven van verschillende evenwichten in de speltheorie. Speltheorie is een vakgebied dat officieel valt onder de economie, maar veel van de resultaten in de speltheorie worden bewezen en onderbouwd met wiskunde. De speltheorie houdt zich bezig met situaties waarin besluitvormers op elkaar inwerken. Wanneer een besluitvormer een beslissing maakt, neemt hij hierbij de mogelijke besluiten die de andere besluitvormers nemen in acht. Hierdoor is het mogelijk dat de uitkomst van het spel niet resulteert in het maximaal haalbare resultaat voor de spelers. Er worden in deze bachelorscriptie twee soorten spellen besproken met hun bijbehorende evenwichten. Dit zijn de strategische spellen en de spellen in uitgebreide vorm. Bij de spellen in uitgebreide vorm onderscheiden we twee varianten, de spellen met perfecte informatie en de spellen met imperfecte informatie. Het grootste verschil tussen de strategische spellen en de spellen in uitgebreide vorm is dat bij de strategische spellen de spelers tegelijkertijd hun beslissing nemen en bij de spellen in uitgebreide vorm maken de spelers na elkaar een keuze. Strategische spellen geven we weer in een tabel, waarbij de rijspeler speler 1 is en de kolomspeler speler 2. We lichten dit toe met een van de bekendste voorbeelden uit de speltheorie het Gevangenen Dilemma. De beide spelers (de gevangenen) hebben in dit spel 2 keuzes, zwijgen (Z) of praten (P ). De bijbehorende uitbetalingen staan in de vakjes in de onderstaande tabel. De eerste uitbetaling is voor speler 1 en de tweede voor speler 2. Dus wanneer de uitkomst van het spel (P, Z) is, dan is de uitbetaling van speler 1 gelijk aan 3 en de uitbetaling van speler 2 is 0.
38
Z P
Z 2, 2 3, 0
P 0, 3 1, 1
Figuur 6.1: Gevangenen dilemma De evenwichten die we tegenkomen bij de strategische spellen in deze bachelorscriptie zijn het Nash evenwicht, het strikte Nash evenwicht en het correlated evenwicht. Het Nash evenwicht is een uitkomst van het spel waarvoor geldt dat geen enkele speler zijn keuze zou willen veranderen gegeven dat de keuzes van de andere spelers gelijk blijven. Wanneer ´e´en speler zijn keuze zou veranderen zou zijn uitbetaling gelijk blijven of zelfs minder worden. In het Nash evenwicht is dus iedere speler tevreden met zijn keuze. Het Nash evenwicht in het bovenstaande Gevangenen Dilemma is (P, P ). Het strikte Nash evenwicht lijkt erg op het gewone Nash evenwicht, alleen geldt dat de uitbetaling voor iedere speler strikt minder zou zijn wanneer deze speler een andere keuze zou maken, waarbij de keuzes van de andere spelers gelijk blijven. Het correlated evenwicht is een kansverdeling over de uitkomsten. Een uitkomst is een correlated evenwicht als voor iedere speler een andere keuze niet leidt tot een hogere uitbetaling, wanneer de keuzes van de andere spelers gelijk blijven. In deze bachelorscriptie is een aantal stellingen bewezen over de evenwichten in de strategische spellen. Zo is er bewezen dat in iedere gemengde uitbreiding van een strategisch spel (in een gemengde uitbreiding worden ook gemengde keuzes toegestaan, hierbij kiezen de spelers met een zelf gekozen kans voor een bepaalde keuze) een Nash evenwicht bestaat en dat ieder Nash evenwicht een correlated evenwicht is. Omdat bij de spellen in uitgebreide vorm de spelers na elkaar hun keuze maken, worden de spellen in uitgebreide vorm anders weergegeven als de strategische spellen. De spellen in uitgebreide vorm worden weergegeven in een zogenaamde spelboom. Deze weergave lichten we toe met een van de bekenste spellen in uitgebreide vorm, het Duizendpoten spel.
39
D
1
S
(4, 1)
/2
D S
(2, 8)
/
D
1
S
(16, 4)
/2
D
/
(64, 16)
S
(8, 32)
Figuur 6.2: Het Duizendpoten spel Hierbij kiezen de twee spelers om de beurt of ze willen stoppen (S) of doorgaan (D). Wanneer een speler kiest om door te gaan dan is de andere speler aan de beurt, kiest een speler om te stoppen dan is het spel afgelopen. Beide spelers mogen maximaal 2 keer de keuze maken om te stoppen of om door te gaan. De uitbetalingen staan aan het einde van de pijlen, waarbij het eerste getal de uitbetaling is van speler 1 en het tweede getal de uitbetaling van speler 2. Bij de spellen met uitgebreide informatie komen we opnieuw het Nash evenwicht tegen. Daarnaast kennen de spellen in uitgebreide vorm ook een ander evenwicht, het zogenaamde deelspelperfecte evenwicht. De definitie van het Nash evenwicht is exact hetzelfde als bij de strategische spellen. Je kan ieder spel in uitgebreide vorm namelijk omschrijven tot een spel in strategische vorm. Het deelspelperfecte evenwicht is de uitkomst waarbij in ieder deelspel de optimale keuze is gemaakt voor de speler die op dat moment aan zet is. Een spel in uitgebreide vorm is op te delen in verschillende deelspellen, waarbij bij iedere knoop in de spelboom een deelspel begint. Het deelspelevenwicht van een spel is te vinden met behulp van terugwaartse inductie. Dit lichten we toe met het eerder genoemde Duizendpotenspel.
40
D
1
S
(4, 1)
/2
D S
(2, 8)
/
D
1
S
(16, 4)
/2
D
/
(64, 16)
S
(8, 32)
Figuur 6.3: Het Duizendpoten spel met het deelspelperfecte evenwicht In het laatste deelspel (de laatste beurt van speler 2) is het voor speler 2 het best om te stoppen (S) dan door te gaan (D), omdat zijn uitbetaling dan hoger is (32) dan wanneer hij kiest om door te gaan (16). In het een na laatste deelspel (deze begint bij de laatste beurt van speler 1), is het voor speler 1 beter om te stoppen, omdat hij weet dat speler 2 in de beurt daarna zal stoppen. Zijn uitbetaling is wanneer hij stopt namelijk hoger (16), dan wanneer hij kiest om door te gaan (8). Zo redeneer je helemaal terug tot aan het begin van het spel. De optimale keuzes in de deelspellen zijn in de bovenstaande figuur weergegeven met de dubbele pijlen. Je ziet dat iedere speler besluit te stoppen en dat het spel direct na de eerste beurt afgelopen is. De uitkomst van het deelspelperfecte evenwicht (4, 1) is dus heel laag ten opzichte van mogelijk andere te behalen uitbetalingen (64, 16). Het deelspelperfecte evenwicht hoeft dus zeker niet de beste opbrengst voor beide spelers te zijn. Het bovenstaande voorbeeld van een spel in uitgebreide vorm is een spel met perfecte informatie. De evenwichten bij uitgebreide spellen met imperfecte informatie zijn dezelfde als bij de spellen met perfecte informatie. Het verschil is dat bij de spellen in uitgebreide vorm met imperfecte informatie niet bij iedere knoop een nieuw deelspel begint. Wanneer een speler geen onderscheid kan maken tussen twee knopen (dit omdat hij niet weet wat zijn voorganger heeft gedaan) begint in zo een knoop geen nieuw deelspel. Verder loopt de definitie van het deelspelperfecte evenwicht hetzelfde. De stelling dat ieder eindig spel in uitgebreide vorm een deelspelperfect evenwicht heeft is in deze bachelorscriptie bewezen.
41
Bibliografie [1] Krzysztof R. Apt, Strategic Games, February 1, 2011. [2] Martin R. Osborne An Introduction In Game Theory, Oxford University Press, 2009. [3] Geoffrey A. Jehle en Philip J. Reny Advanced Microeconomic Theory, Pearson Education Limited, 2011. [4] Kevin Leyton-Brown en Yoav Shoham Essentials Of Game Theory, Morgan and Claypool publishers, 2008. [5] Maurice Koster, College aantekeningen: Inleiding Speltheorie, 2011. [6] Robert Gibbons A Primer In Game Theory, Pearson Education Limited, 1992. [7] Charalambos D. Aliprantis en Subir K. Chakrabarti Games and Decision Making, Oxford University Press, 2000. [8] Eric Rasmusen Games And Information, An Introduction to Game Theory, Blackwell Publishing, 2007. [9] James N. Webb Game Theory, Decisions, Interaction and Evolution, Springer-Verlag London Limited, 2007. [10] Hans Peters Game Theory, A Multi-Leveled Approach, Springer-Verlag Berlin-Heidelberg, 2008. [11] Julio, Gonzalez-Diaz, Ignacio Garcia-Jurado en M. Gloria FiestrasJaneiro An Introduction Course On Mathematical Game Theory, The American Mathematical Society, 2010. [12] Stef Tijs Introduction To Game Theory, Hindustan Book Agency (India), 2003.
42
