J´at´ekelm´elet szociol´ ogusoknak
J-1
Bevezet´ es a j´ at´ ekelm´ eletbe szociol´ ogusok sz´ am´ ara Aj´anlott irodalom: M´esz´aros J´ozsef: J´ at´ekelm´elet (Gondolat, 2003) Filep L´aszl´o: J´ at´ekelm´elet (Filum, 2001) Csontos L´aszl´o (ed): A racion´ alis d¨ ont´esek elm´elete (Osiris, 1998) Rasmusen, Eric: Games and Information (Third Edition, Blackwell, 2001) Simonovits Andr´ as: Bevezet´es a j´ at´ekelm´eletbe (2007) http://www.math.bme.hu/diffe/jatek.pdf A j´at´ekelm´elet elnevez´es Neumann J´ anos ´es Oskar Morgenstern The Theory of Games and Economic Behaviour (Princeton, 1944) k¨ onyve nyom´an v´alt ´altal´anoss´a. Az elm´elet hazai k¨ ozismerts´ege Hankiss Elem´er: T´arsadalmi csapd´ak c. 1977-es essz´ej´enek k¨osz¨onhet˝o. Aki gyorsan ´es a matematikai formalizmus lehet˝o mell˝oz´es´evel szeretne t´aj´ekoz´odni, annak a Stanford Enciklop´edi´ aban a j´ at´ekelm´elet c´ımsz´o aj´anlhat´o: http://plato.stanford.edu/entries/game-theory K´et ember A ´es B bankrabl´ assal v´ adolva k¨ ul¨on cell´aban u ¨l. Bizony´ıt´ek nincs ellen¨ uk, k´et lehet˝os´eg¨ uk van: elismerni a bankrabl´ ast vagy tagadni. Mindketten (k¨ ul¨on-k¨ ul¨on) ugyanazt az aj´anlatot kapj´ ak: - ha mindketten elismeritek a bankrabl´ ast, mindketten kaptok 5-5 ´evet, - ha te elismered a bankrabl´ ast ´es a t´ arsad nem, t´eged szabadon bocs´atlak ´es ˝o kap 10 ´evet, - ha ˝o elismeri a bankrabl´ ast ´es te nem, ˝ ot szabadon bocs´atom ´es te kapsz 10 ´evet, - ha mindketten tagadtok, mindketten kaptok 1-1 ´evet (tiltott fegyvervisel´es´ert). Ez a p´elda a j´at´ekelm´eletben k¨ ozismert a ”Fogoly dilemm´aja” szitu´aci´o. Alapvet˝o jellegzetess´ege, hogy a j´at´ek kimenetel´et az ¨ osszes r´esztvev˝o l´ep´eseinek interakci´oja hat´arozza meg, ´es ezt minden r´esztvev˝onek figyelembe kell vennie, amikor saj´at d¨ont´es´et meghozza. Tov´abbi tulajdons´agok: - egyl´ep´eses, k´etszem´elyes, - szimult´an (amikor a j´ at´ekos eld¨ onti, mit l´ep, nem tudja, hogy mit l´ep a m´asik), - nem-kooperat´ıv (a j´ at´ekosok semmilyen m´odon nem hangolj´ak ¨ossze a l´ep´eseiket), - teljes inform´aci´ os (a j´ at´ek ¨ osszes szab´ alya r¨ogz´ıtett, ´es minden j´at´ekos sz´am´ara ismert), - minden j´at´ekos arra t¨ orekszik, hogy nyeres´ege v´arhat´o ´ert´ek´et maximaliz´alja, ´es ugyanezt felt´etelezi az ¨osszes t¨obbi j´ at´ekosr´ ol is. A fenti j´at´ek sz´ am´ıt´ og´epes realiz´ aci´ oja ´es m´eg sok m´as interakt´ıv anyag:
http://GameTheory.net
J´at´ekelm´elet szociol´ ogusoknak
J-2
K´etszem´elyes j´at´ek: a r´esztvev˝ ok: A ´es B j´at´ekosok, tiszta strat´egi´aik: {A1 , ..., AI } ill. {B1 , ..., BJ } Nyeres´eg az A j´ at´ekos szempontj´ ab´ ol: fA (Ai , Bj ) ´es nyeres´eg a B j´at´ekos szempontj´ab´ol: fB (Ai , Bj ) ahol fA ´es fB val´ os sz´ am ´ert´ek˝ u (pozit´ıv fA nyeres´eget, negat´ıv fA vesztes´eget jelent A sz´am´ara).
fA
B1
B2
...
BJ
A1
x1,1
x1,2
...
x1,J
Nyeres´egm´atrix az A j´at´ekos szempontj´ab´ol: ha
A2
x2,1
x2,2
...
x2,J
az A j´at´ekos strat´egi´aja Ai ´es a B j´at´ekos
...
...
...
...
...
strat´egi´aja Bj akkor xi,j az A j´at´ekos nyeres´ege.
AI
xI,1
xI,2
...
xI,J
Z´er´o-¨osszeg˝ u j´at´ek: az A szempontj´ ab´ ol vett nyeres´eg + a B szempontj´ab´ol vett nyeres´eg = 0 us´eggel j´atszik Ai strat´egi´ at, Kevert strat´egia: α = (α1 , ..., αI ) I-dim vektor, az A j´at´ekos αi val´osz´ın˝ I X ahol αi = 1 ´es αi ≥ 0 minden i = 1, ..I (B kevert strat´egi´aj´at β = (β1 , ..., βJ ) jel¨oli). V´arhat´ o i=1
nyeres´eg A szempontj´ ab´ ol az (α, β) strat´egia-p´ar eset´en: fA (α, β) =
I X J X
αi · βj · xi,j
i=1 j=1
Minimax t´etel (von Neumann, 1928):
min max fA (α, β) = max min fA (α, β) β
α
α
β
Elnevez´es: biztons´ agi strat´egia az A j´ at´ekos sz´am´ara: α = arg max min fA (α, β) ◦
α
β
ulyi strat´egia-p´ar) Nash-egyens´ ulyi strat´egia-p´ ar: (α∗ , β ∗ ) (a tov´abbiakban: egyens´ b´armely (α, β) strat´egia-p´ ar eset´en: fA (α∗ , β ∗ ) ≥ fA (α, β ∗ ) ´es fB (α∗ , β ∗ ) ≥ fB (α∗ , β) ´ ıt´as: minden k´etszem´elyes z´er´ o-¨ osszeg˝ u j´at´eknak van egyens´ ulyi strat´egia-p´arja. 1. All´ ´ ıt´as: (felcser´elhet˝ 2. All´ os´eg) minden k´etszem´elyes z´er´o-¨osszeg˝ u j´at´ek eset´en teljes¨ ul, hogy ha (α1∗ , β1∗ ) ´es (α2∗ , β2∗ ) k´et egyens´ ulyi strat´egia-p´ ar, akkor (α1∗ , β2∗ ) egyens´ ulyi strat´egia-p´ar. ´ ıt´as: (ekvivalencia) minden k´etszem´elyes z´er´o-¨osszeg˝ 3. All´ u j´at´ek eset´en teljes¨ ul, hogy ha (α1∗ , β1∗ ) ´es (α2∗ , β2∗ ) k´et egyens´ ulyi strat´egia-p´ ar, akkor fA (α1∗ , β1∗ ) = fA (α2∗ , β2∗ ) K´etszem´elyes z´er´ o-¨ osszeg˝ u j´ at´ek megold´ asa: az ¨osszes egyens´ ulyi strat´egia-p´ar.
J´at´ekelm´elet szociol´ ogusoknak
J-3
2x2-es j´at´ek eset´en: α = az A1 v´ alaszt´ as´ anak val´osz´ın˝ us´ege, ´es β = a B1 v´alaszt´as´anak val´osz´ın˝ us´ege fA
B1
B2
fB
B1
B2
A1
x1,1
x1,2
A1
y1,1
y1,2
A2
x2,1
x2,2
A2
y2,1
y2,2
Az A j´at´ekos szempontj´ ab´ ol vett nyeres´egf¨ uggv´eny: fA (α, β) = α · β · x1,1 + α · (1 − β) · x1,2 + (1 − α) · β · x2,1 + (1 − α) · (1 − β) · x2,2 Az A j´at´ekos k´et tiszta strat´egi´ aj´ ahoz tartoz´o k´et nyeres´egf¨ uggv´eny: fA (α = 1, β) = β · x1,1 + (1 − β) · x1,2
´es fA (α = 0, β) = β · x2,1 + (1 − β) · x2,2
fA 6
" fA = β · x1,1 + (1 − β) · x1,2 "
" " " " " " ! ! " !! " ! " " !!! PP " ! PP " ! XX PP XX "!! XX PX ! " PX PX "! P X ! PX "! PX ! " PX PX !! " PX ! PX " X ! PX PPXXXX ! " ! ! PP " X X " PP " PP " PP f = β · x + (1 − β) · x " 2,1 2,2 A
0
- β
β∗
1
Minden egyenes A valamely r¨ ogz´ıtett strat´egi´aja mellett B strat´egi´aj´anak f¨ uggv´eny´eben jellemzi az A szempontj´ab´ol vett v´ arhat´ o nyeres´eget. A burkol´o egyenesek tartoznak az A tiszta strat´egi´aihoz. Az ´abr´an l´atjuk, hogy B j´ at´ekos β ∗ strat´egi´aj´ara el´eretik min max fA (α, β) β
α
´ ıt´as: minden k´etszem´elyes j´ 4. All´ at´eknak van egyens´ ulyi strat´egia-p´arja. ´ ıt´asban K´etszem´elyes j´at´ek megold´ asa: az ¨ osszes egyens´ ulyi strat´egia-p´arja akkor, ha teljes¨ ul a 2. All´ ´ ıt´ ´ırt felcser´elhet˝os´eg ´es a 3. All´ asban ´ırt ekvivalencia tulajdons´ag. Megjegyz´es: Z´er´ o-¨ osszeg˝ u j´ at´ek eset´en mindig van(nak) egyens´ ulyi strat´egia-p´ar(ok), ´es ez(ek) a j´at´ek megold´asa(i). Nem z´er´ o-¨ osszeg˝ u j´ at´ek eset´en is mindig van(nak) egyens´ ulyi strat´egia-p´ar(ok), de lehet, hogy nem teljes¨ ul a felcser´elhet˝ os´eg ´es az ekvivalencia.
J´at´ekelm´elet szociol´ ogusoknak
J-4
fA
B1
B2
...
BJ
fB
B1
B2
...
BJ
A1
x1,1
x1,2
...
x1,J
A1
y1,1
y1,2
...
y1,J
A2
x2,1
x2,2
...
x2,J
A2
y2,1
y2,2
...
y2,J
...
...
...
...
...
...
...
...
...
...
AI
xI,1
xI,2
...
xI,J
AI
yI,1
yI,2
...
yI,J
K´etszem´elyes (nem felt´etlen¨ ul z´er´ o-¨ osszeg˝ u) j´at´ekot a fenti k´et nyeres´eg-m´atrix jellemez, I · J darab tiszta strat´egia-p´ arral. A k¨ ovetkez˝ o´ abra egy p´eld´an mutatja a tiszta strat´egi´ak elhelyezked´es´et a j´at´ek lehetes´eges (fA , fB ) kimeneteleivel koordin´at´azott s´ıkban: fB
Q
x @ @ R @x
6
P
x E E E E E E E
T
W
x
x D D D S x D D D D D D D D D D DU ( (( Dx
- fA
Legyen R ´es S k´et strat´egia-p´ ar. R domin´alja az S strat´egi´at, ha mindk´et j´at´ekos sz´am´ara R nyeres´ege nagyobb, mint S nyeres´ege (az ´ abra egy ilyen helyzetet szeml´eltet). Egy halmaz konvex burka az ˝ ot tartalmaz´ o konvex halmazok k¨oz¨os r´esze (az ´abr´an a konvex burok hat´arpontjai P,Q,R,T,U). Kooperat´ıv j´ at´ek eset´en a k´et j´at´ekos sz´am´ara el´erhet˝o b´armely nyeres´eg, amit tartalmaz a tiszta strat´egia-p´ arokhoz tartoz´o kimenetelek konvex burka. Pareto-optim´alis a tiszta strat´egia-p´arok konvex burk´ anak nem-domin´alt r´esze ill. az ezekhez tartoz´o strat´egia-p´arok halmaza.
J´at´ekelm´elet szociol´ ogusoknak
J-5
A j´at´ekelm´elet t´ arsadalomtudom´ anyi alkalmaz´asai (l´asd m´eg M´esz´aros: J´at´ekelm´elet): - a racion´alis d¨ ont´esek elm´elete (rational choice theory, RCT) - strat´egi´ak a ”fogoly dilemm´ aja” j´ at´ek ism´etelt v´altozat´aban - szekvenci´alis j´ at´ekok - az oligopol probl´ema - t˝ozsde, aukci´o, versenyt´ argyal´ asi strat´egi´ak - a fogyaszt´oi viselked´es modellez´ese, term´ekfejleszt´es, ´ark´epz´es - t´erbeli folyamatok, ter¨ uletfejleszt´es - evol´ uci´osan stabil strat´egi´ ak (ESS, Maynard Smith) - ´erdekegyeztet´es, t´ arsadalmi alkufolyamatok - a kollekt´ıv racionalit´ as elm´eletei, Arrow t´etele, szavaz´asi rendszerek, koal´ıci´ok - m´ediakutat´as, m˝ usorstrukt´ ura tervez´es (complementary/counter scheduling)
Gyakorl´o feladatok: 1. Az al´abbi j´at´ek z´er´ o-¨ osszeg˝ u. Van-e tiszta strat´egi´akb´ol ´all´o Nash-egyens´ ulypontja?
fA
B1
B2
B3
B4
A1
1
8
9
7
A2
15
12
5
14
A3
12
11
10
15
A4
17
2
8
9
2. Igaz-e, hogy az al´ abbi j´ at´ek sor´ an a B j´at´ekos sohasem v´alasztja a B1 strat´egi´at? fA
B1
B2
B3
fB
B1
B2
B3
A1
6
1
9
A1
4
3
7
A2
7
10
0
A2
3
8
2
J´at´ekelm´elet szociol´ ogusoknak
J-6
Minta ZH
1. (10 pont) Az al´abbi j´at´ek z´er´ o-¨ osszeg˝ u. Igaz-e, hogy a B j´at´ekos sohasem v´alasztja a B3 strat´egi´at?
fA
B1
B2
B3
A1
0
200
160
A2
200
100
140
2. (10 pont) Az al´abbi j´at´ek z´er´ o-¨ osszeg˝ u. B j´ at´ekos aj´anlata az, hogy ˝o sohasem j´atszik B3 -at, ha A sohasem j´atszik A3 -at. B j´ at´ekos azt ´ all´ıtja, hogy aj´anlat´anak elfogad´asa az A j´at´ekos sz´am´ara nem h´atr´anyos. Igaz-e B ´all´ıt´asa?
fA
B1
B2
B3
A1
300
0
-20
A2
0
100
60
A3
120
80
75
3. (30 pont) Ebben a j´at´ekban van egy felt´etel: B j´at´ekosnak olyan strat´egi´ at kell j´ atszania, ami garant´alja, hogy A j´at´ekos nyeres´eg´enek v´arhat´ o ´ert´eke ≤ 28, b´armilyen strat´egi´ at is j´ atszik A.
Igaz-e, hogy ha B a felt´etelnek megfelel˝ o strat´egi´at j´atszik, akkor nyeres´eg´enek v´arhat´o ´ert´eke negat´ıv? fA
B1
B2
fB
B1
B2
A1
30
10
A1
10
110
A2
0
100
A2
50
-50
