Tiszta és kevert stratégiák
Tiszta stratégia: Az i-edik játékos az S i stratégiahalmazból egyértelműen választ ki egy stratégiát és ezt alkalmazza.
Tekintsük a következő játékot. Két vállalat – I és II – azonos terméket állít elő. Azon gondolkodnak, hogy érdemes-e az értékesítés növelése érdekében közös reklámhadjáratot kezdeni. A két vállalat lehetséges stratégiái ezek szerint: a kampányban részt venni (R), illetve nem részt venni (NR). A kifizetési mátrix legyen az alábbi:
II-es vállalat
I-es vállalat
R
NR
R
(5;5)
(− 1;6)
NR
(4;1)
(0;0)
Könnyen belátható, hogy a játéknak nincs megoldása.
Ilyen esetekben segít a kevert stratégiák alkalmazása.
Kevert stratégia: Tegyük fel, hogy az i-edik játékos m db tiszta stratégia közül választhat: S i = {si1 , s i2 ,..., s im },
p1 p2 i = 1,2,..., n . Kevert stratégiának nevezzük a p = vektort, ahol p j ≥ 0 , M p m
∑p
j
j = 1,2,..., m ,
= 1 ; itt p j azt a valószínűséget jelenti, amellyel az i-edik játékos a j-edik stratégiát
j
választja.
1
Ennek szellemében a tiszta stratégia olyan kevert stratégia, amelyet 1 valószínűséggel választanak.
Két játékos és két stratégia esetében ez azt jelenti, hogy az I-es játékos az egyik stratégiáját p valószínűséggel, a másikat pedig 1 − p valószínűséggel választja; a II-es játékos ennek megfelelően stratégiáit q és 1 − q valószínűségekkel választja. A fenti játék kifizetési mátrixa:
II-es vállalat
R
NR
p valószínűséggel
1-p valószínűséggel
(5;5)
(− 1;6)
(4;1)
(0;0)
R q valószínűséggel
I-es vállalat
NR 1-q valószínűséggel
Ha az I-es vállalat az R stratégiát választja, akkor a lehetséges kifizetései 5, illetve -1, attól függően, hogy a II-es vállalat melyik stratégia mellett dönt. Mivel ezeket a lehetőségeket p, illetve 1-p valószínűségekkel választja, ezért az I-es vállalat várható kifizetése
5 ⋅ p − 1 ⋅ (1 − p ) = 6 ⋅ p − 1 . Amennyiben az I-es vállalat úgy dönt, hogy nem vesz részt a reklámkampányban, azaz az NR stratégia mellett teszi le a voksot, akkor az előzőek értelmében a várható kifizetése 4 ⋅ p − 0 ⋅ (1 − p ) = 4 ⋅ p . Látszik, hogy az I-es vállalat várható kifizetése a II-es vállalat döntésétől függ.
Ez utóbbinak most az az érdeke, hogy az I-es vállalatot teljes bizonytalanságban tartsa a felöl, hogy vajon melyik stratégiát fogja majd választani. Ellenkező esetben ugyanis az I-es vállalat számára a döntés egyértelmű. Ha a II-es vállalat bármilyen kis mértékben is jelzi, hogy a kampányban fog részt venni, akkor az I-es vállalat is e mellett dönt, hiszen 5 > 4 , ha pedig a 2
II-es vállalat jelzése arról szól, hogy a kampányban nem veszt, akkor az I-es vállalat is ezt fogja tenni, mert 0 > −1 . A II-es vállalat az I-es vállalat teljes döntési bizonytalanságát azzal éri el, hogy olyan valószínűséggel választ stratégiát, amely egyenlővé teszi egymással az I-es vállalat várható kifizetéseit. Tehát a fenti példában:
megfelelően 1 − p =
6p − 1 = 4p , azaz p =
1 , ennek 2
1 . Ugyanez érvényes a II-es vállalat vonatkozásában is: a II-vállalat 2
várható kifizetései 5 ⋅ q + 1 ⋅ (1 − q ) = 4 ⋅ q + 1 és 6 ⋅ q + 0 ⋅ (1 − q ) = 6 ⋅ q , ezek egyenlők, ha 4q + 1 = 6q , vagyis ha q =
1 1 , tehát 1 − q = . Ha az I-es vállalat a reklámkampányban való 2 2
részvétel mellett döntene, akkor a várható kifizetése 5 ⋅ 0,5 − 1 ⋅ 0,5 = 2 , amely megegyezik a várható kifizetésével, ha távol tartja magát a reklámkampánytól, hiszen 4 ⋅ 0,5 + 0 ⋅ 0,5 = 2 . Hasonlóan látható be, hogy a II-es vállalat várható kifizetései a két stratégia megválasztásakor mindkét esetben 3.
Ha a tiszta stratégiák alkalmazásával kialakuló kifizetéseit egy koordináta-rendszerben ábrázoljuk, akkor ezek egy négyszöget határozzák meg. Könnyen belátható, hogy az összes kevert stratégia ezen négyszög belsejében lévő pontokat vagy a négyszöget behatároló egyeneseken lévő pontokat determinál. Ez nyilván a kevert stratégiájú Nash-egyensúlyra is igaz. (ld. az alábbi grafikont)
3
π II
(− 1;6 ) (5;5)
(2;3)
(4;1) πI
(0;0)
A fenti gondolatmenet egyenes következménye, hogy mind az I-es, mind a II-es vállalat Nash-stratégiát (legjobb-válasz-stratégiát) alkalmaz, ha az R és NR stratégiákat q és 1-q,
illetve p és 1-p valószínűségekkel választják. Ha viszont mindkét játékos Nash-stratégiát választ, akkor az ennek következtében létrejövő helyzet Nash-egyensúly. Más szóval: a játék
1 1 1 1 – kevert stratégiájú – Nash-egyensúlya , ; , . 2 2 2 2
Látható, hogy kevert stratégiák esetén a Nash-egyensúlyt már nem a stratégiák segítségével definiáljuk, hanem azok valószínűségi eloszlásaival, tehát a p = (p,1 − p ) és q = (q,1 − q ) párokkal. Kissé általánosabban megfogalmazva: Ha az i játékos S i stratégiahalmazában m különböző tiszta stratégia található, azaz s k , k = 1,2,..., m és minden s k ∈ Si , akkor egy kevert
p1 p2 stratégia olyan p = vektort jelent, amelyekre igaz, hogy M p m
m
∑p r =1
r
= 1 . Nyilván végtelen
sok kevert stratégia létezik. Ennek figyelembevételével jelöljük Pi -vel az i játékos összes kevert stratégiáját tartalmazó halmazt. Természetesen teljesen analóg módon definiálható a j 4
q1 q2 játékos összes kevert stratégiáját tartalmazó halmazt, Pj -t, amely az összes olyan q = M q s s
vektort jelent, amelyre igaz, hogy
∑q r =1
r
= 1 ; itt feltételeztük, hogy a j játékos s db stratégia
(
∗
közül választhat. Ebben az esetben azt mondjuk, hogy a p , q
∗
) kevert stratégiájú Nash-
egyensúly létezik, ha minden a játékban részt vevő játékos olyan kevert stratégiát választ,
(
)
(
)
∗ ∗ ∗ ∗ ∗ amely Nash-stratégia, azaz ha π i p , q ≥ π i pˆ, q minden p , pˆ ∈ Pi , q ∈ S j és minden i és
j esetén.1
1
A fenti koncepció természetesen nem csak két játékosra érvényes, hanem n játékosra is kiterjeszthető. Ebben az esetben minden játékos rendelkezik az kevert stratégiáit tartalmazó Pi halmazzal. Ennek elemei mindazon
(
)
p i = p i1 , p i 2 , K , p im i vektorok, amelyekre igaz, hogy
mi
∑p k =1
ik
= 1 ; itt m i az i játékos (tiszta) stratégiáinak
P−i -vel a P1 × P2 × L × Pi −1 × Pi +1 × L × Pn halmazt, amely tehát az összes i játékoson kívüli játékosok összes kevert stratégiáinak összes kombinációját tartalmazza. A P−i halmaz elemeit p -vel −i
száma. Jelöljük most
jelöljük. Ebben az esetben Nash-egyensúly olyan
(
∗
∗
)
(
∗
)
∗
(p , p ∗ 1
∗
∗ 2
, K , p ∗n
)
stratégiaegyüttes, amelyre igaz, hogy
π i p i , p −i ≥ π i p i , p −i , minden p i , p i ∈ Pi , p −i ∈ P−i , i = 1, 2, K , n .
5
Evolúciós játékok
Fogalmak:
1. Tiszta stratégia 2. Vegyes stratégia. Ha m tiszta stratégia létezik és a p ij annak valószínűsége, hogy az i-
[
edik játékos a j-edik stratégiát választja, j = 1, ..., m , akkor a p i = p1i , p2i , ..., pmi
]
T
vektor az i-edik játékosnak egyik lehetséges vegyes stratégiája, ahol nyilván m
∑p j =1
i j
= 1.
3. Nash-stratégia: valamely játékos legjobb válasza az ellenfél bármelyik stratégiája, azaz ha S i és S j két játékos stratégia-halmazai, π i (si ; s j ) pedig az a kifizetés, amelyet az i-deik játékos kap, ha si -t választ, a j-edik játékos pedig s j -t, si ∈ S i és s j ∈ S j , akkor si∗ ∈ S i Nash-stratégia, ha minden s j ∈ S j esetén
π i (si∗ ; s j ) ≥ π i (si ; s j ) , ∀si ∈ S i .
4. Nash-egyensúly: minden játékos Nash-stratégiát választ.
Adott a héja-galamb-játék, amelynek keretében valamely populáció két tagja valamely erőforrásért folytatott harcban vagy héjaként (agresszíven) vagy galambként (békésen) viselkedhet. Az erőforrás értéke legyen V, a „harc” költségei legyenek C. Véletlenszerűen kiválasztunk két individuumot. Ebből a következő kifizetések adódnak: (H – héja; G – galamb)
6
II. játékos
H
H
G
V − C V − C ; 2 2
(V ;0)
I. játékos
(0;V )
G
Legyen C > V , ekkor a kifizetések sorrendje:
V V ; 2 2
V −C V < 0 <
Gyakorló feladat:
Határozza meg a tiszta stratégiák mellett kialakuló Nash-egyensúly(oka)t! Tegyük fel, hogy az I. játékos p valószínűséggel H-t választ és – ennek megfelelően – 1 − p valószínűséggel G-t; a II. I. játékos pedig q valószínűséggel H-t választ és – ennek megfelelően – 1 − q valószínűséggel G-t.
Gyakorló feladat:
Vizsgálja meg, hogy létezik-e Nash-egyensúly vegyes stratégiák esetén. Ha igen, akkor
p q , valamint a q = határozza meg ezeket, azaz határozza meg a p = vektorokat! 1 − p 1 − q
7
V − C T A számolási menet során képezzük a p Aq = [1 1 − p ] 2 0
V q szorzatot, ami nem V 1 − q 2
q más, mint az I. játékos várható kifizetése, ha a II. játékos a q = vegyes stratégiát 1 − q választja. Amennyiben
T T pˆ Aq ≥ pˆˆ Aq , ∀ pˆˆ ∈ S I ,
Azt mondjuk, hogy pˆ az I. játékos legjobb válasza a II. játékos q stratégiájára. Ebből következik, hogy ha minden játékos esetében pˆ a legjobb válasza a saját pˆ stratégiájára, azaz, ha
T T pˆ A pˆ ≥ pˆˆ A pˆ , ∀ pˆˆ ∈ S i , i = I , II ,
akkor pˆ nyilván Nash-egyensúly.
Evolúciós játékok esetében a vegyes stratégiájú játékokban szereplő valószínűségeket adottnak tekintjük, mégpedig azon részarányokkal azonosítjuk ezeket, amelyekben a két különböző viselkedést mutató egyedből álló részpopulációk az összpopulációban jelen vannak. Tehát tegyük fel valamely populációt (élőlények, vállalatok, fogyasztók, stb.), amely két csoportba osztható: az egyik csoport héja-viselkedést mutat (mindig!), azaz agresszív, a másik csoportba tartozó egyedek mindig galamb-viselkedést mutatnak, azaz békések, azaz egyedek viselkedése úgyszólván genetikailag meghatározott.
Legyen N (t ) valamely populáció (vállalat, fogyasztók, élőlények, stb.) száma a t-edik időpontban, N i (t ), i = 1, ..., n , pedig egy meghatározott viselkedésű részpopuláció száma, szintén a t-edik időpontban. Jelöljük A = [a ij ], i , j = 1, ..., n , a kifizetési mátrixot, amelynek aij eleme azt mutatja, hogy mekkora az i-edik csoporthoz tartozó egyed „életképessége”, ha 8
valamely j-edik csoportbeli egyeddel találkozik; általában azt szokták mondani, hogy aij az iedik csoporthoz tartozó egyed utódainak száma, ha valamely j-edik csoportbeli egyeddel találkozik. Azt tételezzük fel, hogy az A mátrix szimmetrikus, azaz aij = a ji , illetve A = A . T
Ha – mint a héja-galamb-játék esetében – n = 2 , akkor N1 (t ) az agresszív viselkedésű egyedek száma, N 2 (t ) pedig a békésebb egyedek száma, mindkettő természetesen a t-edik időpontban. Igaz, hogy N (t ) = N1 (t ) = N 2 (t ) . Ha µ -vel jelöljük a – mindkét csoportra egyaránt érvényes – (természetes) halálozási rátát, akkor
[
]
N i (t + 1) = N i (t ) 1 − µ + e i A p (t ) , i = 1,2 T
p1 (t ) 1 0 N (t ) ahol e1 = , e 2 = és p(t ) = ; továbbá pi (t ) = i , i = 1,2 . N (t ) 0 1 p2 (t )
Gyakorló feladat:
Határozza meg N1 (t ) -t és N 2 (t ) -t! Az A mátrixot használja a következő alakban
a A = 11 a21
a12 ! a22
Ha meghatároztuk N i (t + 1) -t, i = 1,2 , akkor ebből adódik
1 − µ + e i A p (t ) N (t + 1) , i = 1,2 , pi (t + 1) = i = pi (t ) T N (t + 1) 1 − µ + p A p (t ) T
illetve
9
e i A p(t ) − p (t ) A p(t ) T
pi (t + 1) − pi (t ) = pi (t )
T
1 − µ + p (t ) A p(t ) T
.
Gyakorló feladat:
T
Határozza meg az e1 A p(t ) értéket és értelmezze ezt! Ha a periódus hossza nem egységnyi, hanem δ , akkor
pi (t + δ ) − pi (t )
δ
e i A p(t ) − p (t ) A p(t ) T
= pi (t )
T
1 − δµ + δ p (t ) A p(t ) T
,
azaz
lim
pi (t + δ ) − pi (t )
δ
δ →0
e i A p(t ) − p (t ) A p(t ) T
= lim pi (t ) δ →0
T
1 − δµ + δ p (t ) A p(t ) T
,
tehát
[
]
dpi (t ) T T = p& i (t ) = pi (t ) e i A p (t ) − p (t ) A p (t ) . dt Nyilván, ha e i A p (t ) − p (t ) A p(t ) > 0 , akkor pi (t ) nő, ha e i A p (t ) − p (t ) A p(t ) < 0 , akkor T
T
T
T
csökken pi (t ) .
Más szóval:
Ha az i-edik csoporthoz tartozó egyedek kifizetése meghaladja a populáció egészére átlagosan érvényes kifizetést, akkor az i-edik csoport részaránya a populáción belül nő, s fordítva, ha az i-edik csoporthoz tartozó egyedek kifizetése elmarad a populáció egészére átlagosan érvényes kifizetés mögött, akkor az i-edik csoport részaránya a populáción belül csökken. Ennek értelmében a populáció összetétele változatlan, azaz a populáció egyensúlyban van, ha minden részpopuláció az átlagos kifizetést realizál, hiszen ekkor p& i (t ) = 0, ∀i . 10
Gyakorló feladat:
Vegyük a fenti kétszereplős esetet és vizsgáljuk meg, mikor aszimptotikusan stabil a populációs egyensúly!
A fenti egyensúlyi állapot stabilitás különbözik az evolúciósan stabil stratégia, illetve egyensúlytól.
Definíció: ∗
∗
Evolúciósan stabilnak nevezzük azt a p stratégiát, amely az összes p ≠ p esetén kielégíti a következő feltételeket:
∗T
(i)
∗
∗
p Ap ≥ p Ap ,
∗T
∗
T
∗T
∗
ha p A p = p A p , akkor p A p > p A p . T
(ii)
11
T
Következmény:
Minden evolúciósan stabil stratégia egyben Nash-egyensúly. De nem minden Nash-egyensúly evolúciósan stabil.
Értelmezés:
1. Nincs olyan p stratégia, amely egy evolúciósan stabil p
∗
stratégiával szemben
magasabb kifizetést realizál. ∗
2. Ha a két kifizetés egyenlő egymással, akkor az evolúciósan stabil p stratégia a másikkal szemben nagyobb kifizetést biztosít, mint az utóbbi saját magával szemben.
Tehát az evolúciósan stabil stratégia rezisztens minden másik stratégiával szemben, de ugyanakkor arra képes, hogy bármilyen másik stratégiát gyengít(hes)se.
Gyakorló feladat:
Vizsgáljuk meg, hogy a következő kifizetési mátrix-szal megadott játék evolúciósan stabil-e, ha feltételezzük, hogy a populációnak van olyan csoportja, amely mindig az A stratégiát választja, szemben a másik csoporttal, amely mindig B-t választ:
II. játékos
A
B
A
(2;2)
(2;5)
B
(5;2)
(− 5;−5)
I. játékos
12
