J´at´ekelm´elet ´es h´al´ozati alkalmaz´asai 1. ea Csercsik D´avid ITK PPKE
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
1 / 55
1
J´at´ekelm´elet T¨ort´eneti ´attekint´es A j´at´ekelm´elet ´agai
2
Gr´afelm´eleti alapismeretek
3
Sz´am´ıt´astudom´anyi alapismeretek Fut´asid˝o Sz´am´ıt´asi bonyolults´ag Approxim´aci´o
4
Racionalit´as A racionalit´as k¨oztud´asa A t¨omegek b¨olcsess´ege
5
K´ıs´erletek a gondolkod´asr´ ol Kock´azatker¨ ul´es vs. Kock´azatkeres´es Einstellung
6
Ultim´atum j´at´ekok Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
2 / 55
J´ at´ ekelm´ elet
T¨ ort´ eneti ´ attekint´ es
J´at´ekelm´elet t´argya
”the study of mathematical models of conflict and cooperation between intelligent rational decision-makers” Roger B. Myerson
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
3 / 55
J´ at´ ekelm´ elet
T¨ ort´ eneti ´ attekint´ es
R¨ovid o¨sszefoglal´o
El˝ od¨ ok: Sir James Waldegrave (1684-1741) Antoine Augustin Cournot (1801-1877)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
4 / 55
J´ at´ ekelm´ elet
T¨ ort´ eneti ´ attekint´ es
R¨ovid o¨sszefoglal´o
Modern j´at´ekelm´elet Theory of Games and Economic Behavior (1944), Neumann J., Morgenstern O. Az 50-es ´evek forradalma: Nash-egyens´ uly (Nash), R´eszj´at´ek t¨ok´eletes egyens´ uly (Selten), Shapley-´ert´ek, Fogolydilemma A 60-as ´evekben: Nemteljes inform´aci´ os Bayes-i j´at´ekok (Hars´anyi), Kooperat´ıv j´at´ekok (Aumann, Schmeidler), biol´ ogiai alkalmaz´asok, evol´ uci´osan stabil strat´egia
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
5 / 55
J´ at´ ekelm´ elet
T¨ ort´ eneti ´ attekint´ es
A j´at´ekelm´elet atyja
Neumann J´ anos (1903-1957)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
6 / 55
J´ at´ ekelm´ elet
T¨ ort´ eneti ´ attekint´ es
Nobel-eml´ekd´ıjak Az elm´ ult 20 ´ev term´ese (1994): Nash J., Harsanyi J., Selten R. ”for their pioneering analysis of equilibria in the theory of non-cooperative games” (2005): Aumann R., Schelling T. ”for having enhanced our understanding of conflict and cooperation through game-theory analysis”. (2007): Hurwicz L., Maskin E., Myerson R. ”for having laid the foundations of mechanism design theory.” (2012). Roth A.E., Shapley L.S. ”for their work on matching supply and demand for everything from single men and women to organ donors and their recipients.”
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
7 / 55
J´ at´ ekelm´ elet
A j´ at´ ekelm´ elet ´ agai
A j´at´ekelm´elet ´agai
F˝ obb ´agak Nem kooperat´ıv j´at´ekok (Fogolydilemma, alkuj´at´ekok)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
8 / 55
J´ at´ ekelm´ elet
A j´ at´ ekelm´ elet ´ agai
A j´at´ekelm´elet ´agai
F˝ obb ´agak Nem kooperat´ıv j´at´ekok (Fogolydilemma, alkuj´at´ekok) Kooperat´ıv j´at´ekok (Szavaz´as, eloszt´asi probl´em´ak)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
8 / 55
J´ at´ ekelm´ elet
A j´ at´ ekelm´ elet ´ agai
A j´at´ekelm´elet ´agai
F˝ obb ´agak Nem kooperat´ıv j´at´ekok (Fogolydilemma, alkuj´at´ekok) Kooperat´ıv j´at´ekok (Szavaz´as, eloszt´asi probl´em´ak) Algoritmikus j´at´ekelm´elet (P´aros´ıt´as, aukci´ ok)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
8 / 55
J´ at´ ekelm´ elet
A j´ at´ ekelm´ elet ´ agai
A j´at´ekelm´elet ´agai
F˝ obb ´agak Nem kooperat´ıv j´at´ekok (Fogolydilemma, alkuj´at´ekok) Kooperat´ıv j´at´ekok (Szavaz´as, eloszt´asi probl´em´ak) Algoritmikus j´at´ekelm´elet (P´aros´ıt´as, aukci´ ok) Evol´ uci´os j´at´ekelm´elet (Popul´aci´ odinamika)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
8 / 55
J´ at´ ekelm´ elet
A j´ at´ ekelm´ elet ´ agai
A j´at´ekelm´elet ´agai
F˝ obb ´agak Nem kooperat´ıv j´at´ekok (Fogolydilemma, alkuj´at´ekok) Kooperat´ıv j´at´ekok (Szavaz´as, eloszt´asi probl´em´ak) Algoritmikus j´at´ekelm´elet (P´aros´ıt´as, aukci´ ok) Evol´ uci´os j´at´ekelm´elet (Popul´aci´ odinamika) Kombinatorikus j´at´ekok (Sakk ´es m´as t´ablaj´at´ekok)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
8 / 55
Gr´ afelm´ eleti alapismeretek
Gr´afok I.
Defin´ıci´o Egy gr´af pontokb´ol ´es ezeket ¨ osszek¨ ot˝ o szakaszokb´ ol ´all´o strukt´ ura, amely kiv´al´ oan alkalmas h´al´ozatok modellez´es´ere. A pontokat szaksz´oval cs´ ucsoknak, m´ıg az ¨osszek¨ ot˝ o szakaszokat ´ eleknek nevezz¨ uk. Egy G gr´afot megadhatunk u ´gy, hogy felsoroljuk a cs´ ucsainak (V ) ´es ´eleinek (E ) a halmaz´at (a V az angol ’vertex’, m´ıg az E az ’edge’ sz´ob´ol j¨on).
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
9 / 55
Gr´ afelm´ eleti alapismeretek
Gr´afok II.
Fogalmak Ir´any´ıtatlan/ir´any´ıtott gr´af. P´arhuzamos ´el, hurok´el S´eta, u ´t (¨onmag´at nem metsz˝ o s´eta), k¨ or. ¨ Osszef¨ ugg˝os´eg, izol´alt cs´ ucsok. Fa, fesz´ıt˝o fa. ´ uly/´elkapacit´as. Els´
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
10 / 55
Gr´ afelm´ eleti alapismeretek
P´elda P´elda fesz´ıt˝o f´ara
Feladat Tal´aljuk meg a fenti gr´af legolcs´ obb fesz´ıt˝ o f´aj´at!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
11 / 55
Gr´ afelm´ eleti alapismeretek
Minim´alis k¨olts´eg˝u fesz´ıt˝o fa
Kruskal-algoritmus 1
Rendezz¨ uk az ´eleket k¨ olts´eg¨ uk szerint nem-cs¨ okken˝o sorrendbe!
2
Az ´eleket sorban tekintve akkor vegy¨ unk be egyet, ha az eddig kiv´alasztottakkal nem z´ar be k¨ ort!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
12 / 55
Gr´ afelm´ eleti alapismeretek
Minim´alis k¨olts´eg˝u fesz´ıt˝o fa
T´etel Ha G ¨osszef¨ ugg˝o, akkor a Kruskal-algoritmus minim´alis s´ uly´ u fesz´ıt˝o f´at ´all´ıt el˝o. Bizony´ıt´as v´azlat Legyen F0 az algoritmus ´altal el˝ o´all´ıtott gr´af. 1
F0 fa.
2
F0 fesz´ıt˝o fa.
3
F0 minim´alis k¨olts´eg˝ u (indirekt).
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
13 / 55
Gr´ afelm´ eleti alapismeretek
K¨onigsbergi hidak Feladat Be lehet-e j´arni a v´arost, u ´gy, hogy minden h´ıdon pontosan egyszer haladunk ´at?
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
14 / 55
Gr´ afelm´ eleti alapismeretek
Euler bej´ar´as
Defin´ıci´o A G gr´afban Euler-´ utnak nevez¨ unk egy olyan ´elsorozatot, amely G minden ´el´et pontosan egyszer tartalmazza. Ha az ´elsorozat z´art, Euler-k¨ orr˝ ol besz´el¨ unk. Megjegyz´es Az Euler-k¨ or nem felt´etlen¨ ul k¨ or, hiszen egy cs´ ucson ak´ar t¨obbsz¨or is ´athaladhat. Prec´ızebb lenne Euler-s´et´anak h´ıvni, de ez a hagyom´anyos elnevez´ese.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
15 / 55
Gr´ afelm´ eleti alapismeretek
Euler bej´ar´as
T´etel Egy ¨osszef¨ ugg˝o G gr´afban akkor ´es csak akkor van Euler-k¨or, ha G minden pontj´anak foksz´ama p´aros. T´etel Egy o¨sszef¨ ugg˝o G gr´afban akkor ´es csak akkor van Euler-´ ut, ha G -ben a p´aratlan fok´ u pontok sz´ama 0 vagy 2.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
16 / 55
Gr´ afelm´ eleti alapismeretek
Gr´afok III.
Tov´abbi Fogalmak Foksz´am, befok, kifok. Forr´as, nyel˝o. Folyamok. P´aros gr´afok, teljes gr´af.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
17 / 55
Gr´ afelm´ eleti alapismeretek
P´elda P´elda folyamra
Feladat Tal´aljuk meg a fenti gr´afban a legnagyobb folyamot!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
18 / 55
Gr´ afelm´ eleti alapismeretek
P´elda P´elda folyamra
Feladat Tal´aljuk meg a fenti gr´afban a legnagyobb folyamot! ⇒ Max-flow Min-cut t´etel
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
18 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
A sz´am´ıt´astudom´any atyja
Alan Turing (1912-1954)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
19 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. n
n2
2n
n!
10 100 Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9
n2
2n
n!
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9
n2 10−8
2n
n!
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9
n2 10−8
2n 10−7
n!
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9
n2 10−8
2n 10−7
n! 0.36
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9 10−8
n2 10−8
2n 10−7
n! 0.36
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9 10−8
n2 10−8 10−6
2n 10−7
n! 0.36
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9 10−8
n2 10−8 10−6
2n 10−7 1020
n! 0.36
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Fut´asid˝o
Adott egy g´ep, amely m´asodpercenk´ent 10 milli´ard m˝ uveletet k´epes elv´egezni. Jel¨olje az input m´eret´et n. A k¨ ovetkez˝ o t´abl´azat azt mutatja meg, hogy mekkora lesz a fut´asid˝ o k¨ ul¨ onb¨ oz˝ o m˝ uveletig´eny˝ u probl´em´ak eset´en. 10 100
n 10−9 10−8
n2 10−8 10−6
2n 10−7 1020
n! 0.36 10157
Megj.: A F¨old kora kb. 5 · 109 ´ev m´ıg az ¨ osszes elemi r´eszecske becs¨ ult 80 sz´ama az univerzumban megk¨ ozel´ıt˝ oleg 10 .
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
20 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Nagys´agrendek
Defin´ıci´o (Nagy ord´o) Legyen f , g : N → R. Azt mondjuk, hogy f (n) = O(g (n)) ha ∃c > 0, ´es n0 ∈ N k¨ usz¨ob, u ´gy hogy ∀n > n0 -ra igaz, hogy |f (n)| ≤ c · |g (n)|. Hibatagok becsl´ese, pl: (x + 1)2 = x 2 + O(x) x → ∞ eset´en mert 2x + 1 < 3x ha x > 1. Hasonl´ oan e x = 1 + x + O(x 2 ) ha x → 0. Feladat Javasoljunk egy elj´ar´ast n db. pozit´ıv eg´esz sz´am n¨ ovekv˝o sorrendbe rendez´es´ere, majd elemezz¨ uk a m´ odszer fut´asidej´et!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
21 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Fut´ asid˝ o
Gyakran alkalmazott rendez´esek
N´ev Gyorsrendez´es Kupacrendez´es Bubor´ekrendez´es
Csercsik D´ avid (ITK PPKE)
Legjobb n n log n n
´ Atlagos n log n n log n n2
Legrosszabb n2 n log n n2
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
Mem´oriaig´eny log n 1 1
22 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Sz´ am´ıt´ asi bonyolults´ ag
P ´es NP-beli probl´em´ak I.
Defin´ıci´o Egy d¨ont´esi feladat polinom id˝ oben megoldhat´ o, ha l´etezik olyan k pozit´ıv eg´esz, hogy n m´eret˝ u input eset´en a feladat megold´as´at O(nk ) id˝o alatt kisz´amolhatjuk. Egy d¨ont´esi probl´ema P-beli, ha polinom id˝oben megoldhat´o. Sok d¨ont´esi probl´em´ara nem ismert hat´ekony algoritmus, ugyanakkor ha m´ar valaki kisz´amolta a megold´ast, gyorsan le lehet ellen˝ orizni, hogy az val´oban j´ o-e. Egy d¨ ont´esi feladatr´ ol azt mondjuk, hogy NP-beli, ha b´armely megold´asa polinom id˝ oben leellen˝orizhet˝o. Egy feladatr´ol azt mondjuk, hogy NP-teljes, ha azt megoldva b´armely NP-beli probl´em´at polinom id˝oben meg tudunk oldani.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
23 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Sz´ am´ıt´ asi bonyolults´ ag
P ´es NP-beli probl´em´ak II.
Nyitott k´erd´es A sz´am´ıt´astudom´any alapk´erd´ese, hogy P = NP vagy sem. A probl´ema az egyike azon h´et probl´em´anak, ami´ert a Clay Mathematical Institute 1 milli´ o doll´art aj´anlott fel. P´elda NP-teljes probl´em´akra Hamilton-k¨or Part´ıci´ o R´eszgr´af-izomorfia
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
24 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Sz´ am´ıt´ asi bonyolults´ ag
P ´es NP-beli probl´em´ak III. Defin´ıci´o Egy G gr´afban Hamilton-k¨ ornek (-´ utnak) nevez¨ unk egy H k¨ort (utat), ha minden pontj´at pontosan egyszer tartalmazza. Part´ıci´o feladat Legyen ´gy PA = {a1 , a2 , . . . , an } pozit´ıv eg´eszeknek egy multihalmaza, u hogy ni=1 ai = 2b valamely b sz´amra. K´erd´es l´etezik A-nak olyan part´ıci´oja, amelyekben a sz´amok ¨ osszege megegyezik. M´ask´eppen l´etezik-e A-nak egy olyan r´eszhalmaza, amelyben a sz´amok ¨ osszege b. R´eszgr´af izomorfia Legyenek G ´es H gr´afok. K´erd´es l´etezik-e G -nek H-val izomorf r´eszgr´afja.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
25 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Sz´ am´ıt´ asi bonyolults´ ag
P ´es NP-beli probl´em´ak IV.
Defin´ıci´o Egy probl´em´at NP-neh´eznek nevez¨ unk, ha minden NP-beli probl´ema visszavezethet˝o r´a. Ha egy NP-neh´ez probl´ema NP-ben is van, akkor NP-teljes is egyben. P´elda NP-neh´ez probl´em´akra H´atizs´ak-pakol´as Steiner fa
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
26 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
Approxim´aci´o
Defin´ıci´o Egy algoritmust α-approxim´aci´ onak nevez¨ unk egy P probl´em´ara n´ezve, ha az algoritmus ´altal sz´amolt c´elf¨ uggv´eny ´ert´ek ´es az optim´alis c´elf¨ uggv´eny ´ert´ek k¨oz¨ott legfeljebb α-szoros elt´er´es van. Azaz M(p) ≤ α · OPT (p), ahol α > 1 ´es p a P probl´ema egy tetsz˝ oleges p´eld´anya.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
27 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
Steiner fa
Defin´ıci´o Legyen adott G = (V , E ) ¨ osszef¨ ugg˝ o gr´af, egy S ⊂ V cs´ ucshalmaz, valamint egy w : E → R+ ´els´ ulyoz´as. Steiner f´anak nevez¨ unk egy f´at, amely fesz´ıti S minden cs´ ucs´at. Sz´am´ıt´asi bonyolults´ag Annak meghat´aroz´asa, hogy adott k-ra l´etezik-e legfeljebb k k¨olts´eg˝ u Steiner fa NP-teljes. A legolcs´obb Steiner fa megtal´al´asa NP-neh´ez.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
28 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
Steiner fa v´altozatok Eredeti v´altozat Adott a s´ıkon n db cs´ ucs, amelyekhez m´eg tetsz˝ oleges sz´am´ u seg´edcs´ ucs felvehet˝o. Ezeket k´ene ¨osszek¨ otni u ´gy, hogy az ¨ osszek¨ot˝o szakaszok ¨osszhossza minim´alis legyen.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
29 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
Steiner fa v´altozatok Eredeti v´altozat Adott a s´ıkon n db cs´ ucs, amelyekhez m´eg tetsz˝ oleges sz´am´ u seg´edcs´ ucs felvehet˝o. Ezeket k´ene ¨osszek¨ otni u ´gy, hogy az ¨ osszek¨ot˝o szakaszok ¨osszhossza minim´alis legyen.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
29 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
Steiner fa v´altozatok Approxim´aci´os algoritmus metrikus esetre Adott G = (V , E ) teljes gr´af ´es egy c s´ ulyf¨ uggv´eny, amely teljes´ıti a 4-egyenl˝otlens´eget. A feladat egy olyan minim´alis s´ uly´ u f´at tal´alni, amely fesz´ıti az S ⊂ V cs´ ucshalmazt. 1
Hat´arozzunk meg egy minim´alis s´ uly´ u fesz´ıt˝ o f´at az S cs´ ucshalmaz ´altal fesz´ıtett r´eszgr´afon. Legyen ez F .
2
Eredm´eny: F .
´ ıt´as All´ Az algoritmus 2-approxim´aci´ o a metrikus esetre. Azaz ha F ∗ az optim´alis megold´as, akkor c(F ) ≤ 2c(F ∗ )
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
30 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as Defin´ıci´o Adott n k¨ ul¨onb¨oz˝o t´argy, amelyeknek pi ´ert´eke ´es ai s´ ulya van. A h´atizs´ak kapacit´asa b. Annak eld¨ont´ese, hogy be lehet-e pakolni legal´abb k ´ert´ek˝ u t´argyat a h´atizs´akba, u ´gy hogy azok ¨ osszs´ ulya ne l´epje ´at b ´ert´ek´et NP-teljes. Az anal´og optimaliz´al´asi feladat pedig NP-neh´ez.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
31 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as
H´atizs´ak feladat A h´atizs´ak feladatot a k¨ovetkez˝ ok´epp lehet eg´esz´ert´ek˝ u programoz´asi feladatk´ent fel´ırni: X max pi xi i
X
ai xi ≤ b
i
xi ∈ {0, 1}, i = 1, . . . , n
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
32 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as
H´atizs´ak feladat Tekints¨ uk a feladat LP-relax´aci´ oj´at: X max pi xi i
X
ai xi ≤ b
i
0 ≤ xi ≤ 1, i = 1, . . . , n
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
33 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as Megjegyz´es A relax´alt feladat optimuma csak nagyobb lehet, azaz LPOPT ≥ OPT Az LP-relax´alt feladat megold´asa Indexelj¨ uk ´at a t´argyakat, u ´gy hogy teljes¨ ulj¨ on
LPOPT
p1 p2 pn ≥ ≥ ··· ≥ . a1 a2 an Pb k b X b − ki=1 ai = pi + pkb +1 akb +1 i=1
ahol
Pkb
i=1 ai
≤ b ≤=
Csercsik D´ avid (ITK PPKE)
Pkb +1 i=1
ai .
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
34 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as
´ ıt´as All´ k
b nX o OPT ≤ max pi , pkb +1 2
i=1
Bizony´ıt´as Indirekt: OPT >
kb X
pi + pkb +1 ≥ LPOPT ≥ OPT
i=1
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
35 / 55
Sz´ am´ıt´ astudom´ anyi alapismeretek
Approxim´ aci´ o
H´atizs´ak pakol´as
K¨ ovetkezm´eny A k¨ovetkez˝ o algoritmus 2-approxim´aci´ o a h´atizs´ak feladatra: 1
Megkeresem kb -t
2
Ha
kb X
pi > pkb +1 ,
i=1
akkor S = {1, . . . , kb }. K¨ ul¨ onben S = {kb }.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
36 / 55
Racionalit´ as
T¨ok´eletes racionalit´as
Defin´ıci´o A k¨ozgazdas´agtanban ´es j´at´ekelm´eletben gyakran felteszik, hogy a r´esztvev˝ok t¨ ok´ eletesen racion´ alisak. Azaz, a saj´at hasznoss´agukat szeretn´ek maximaliz´alni ennek ´erdek´eben k´epesek tetsz˝ olegesen komplex eszmefuttat´asokra ´es ismerik a lehets´eges kimeneteleket ´es a sz´amukra legkedvez˝obbet v´alasztj´ak ezek k¨oz¨ ul
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
37 / 55
Racionalit´ as
A racionalit´as korl´atai
K´arty´as feladat
K´erd´es: Igaz-e, hogy ha egy k´artya bet˝ us oldal´an mag´anhangz´o van, akkor annak sz´amos oldal´an p´aros sz´am ´all? Oldjuk meg a feladatot a lehet˝o legkevesebb k´artya megford´ıt´as´aval!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
38 / 55
Racionalit´ as
A racionalit´as korl´atai
K´arty´as feladat
K´erd´es: Melyik csekk ´erv´enyes? A 30$ alatt a csekk al´a´ır´as n´elk¨ ul is ´erv´enyes, felette csak al´a´ır´assal. Oldjuk meg a feladatot a lehet˝o legkevesebb k´artya megford´ıt´as´aval!
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
39 / 55
Racionalit´ as
A racionalit´as korl´atai
Monty Hall probl´ema A k¨ozismert t´ev´es vet´elked˝ oben a j´at´ekos h´arom ajt´ o k¨oz¨ ul v´alaszthat. Kett˝o m¨og¨ott egy kecske lapul, a harmadik m¨ og¨ ott viszont egy dr´aga sportaut´o. A j´at´ekos el˝osz¨ or kijel¨ ol egy ajt´ ot. Ekkor a m˝ usorvezet˝o a marad´ek kett˝o k¨oz¨ ul kinyit egy olyat, amely m¨ og¨ ott egy kecske tal´alhat´o. ´ Ezut´an felaj´anlja a j´at´ekosnak, hogy v´altoztathat a d¨ ont´es´en. Erdemes-e a j´at´ekosnak ´atv´altani a m´asik ajt´ ora?
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
40 / 55
Racionalit´ as
A racionalit´as korl´atai
Tanuls´ag Egyszer˝ u logikai feladatokat sem vagyunk k´epesek racion´alisan v´egiggondolni. Legt¨obbsz¨or intu´ıci´onk alapj´an d¨ ont¨ unk. Ez azonban t´ev´ utra vezethet.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
41 / 55
Racionalit´ as
A racionalit´ as k¨ oztud´ asa
T¨ok´eletes racionalit´as
Oroszl´anok ´es az altat´ozott h´ us Egy mesebeli szigeten 15 t¨ ok´eletes logik´aval meg´aldott oroszl´an ´el. Mind nagyon ´ehesek. Egy napon a szigetre ledobnak egy altat´oval ´atitatott h´ ust. Ha egy oroszl´an megeszi, akkor maga is altat´ oval ´atitatott h´ uss´a v´alik, amit a t¨obbiek megehetnek. Ezt mindegyik¨ uk tudja ´es azt is, hogy a ledobott h´ us altat´ozott. Mindent megtesznek az´ert, hogy ´ehs´eg¨ uket csillap´ıts´ak, ugyanakkor elpusztulni sem akarnak. Mi t¨ort´enik ´es mi´ert? (A h´ us oszthatatlan, egy oroszl´an vagy megeszi, vagy nem b´antja!)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
42 / 55
Racionalit´ as
A racionalit´ as k¨ oztud´ asa
A t˝ozsde ´es a sz´eps´egverseny
A tal´algat´os j´at´ek (Ledoux [1981]) Minden j´at´ekos le´ır 1-t˝ol 100-ig egy tetsz˝ oleges sz´amot. Az nyer, aki a legk¨ozelebb lesz a megadott sz´amok ´atlag´anak 2/3-´ahoz (t¨obben is nyerhetnek). K´erd´esek L´etezik-e domin´ans strat´egia? Milyen sz´amot kell mondanunk, ha t¨ ok´eletesen racion´alisak vagyunk? Mi lesz a j´at´ek Nash-egyens´ ulya?
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
43 / 55
Racionalit´ as
A racionalit´ as k¨ oztud´ asa
A tal´algat´os j´at´ek
Defin´ıci´o A racionalit´ as k¨ oztud´ asa azt jelenti, hogy a j´at´ekosok racion´alisak, tudj´ak egym´asr´ol, hogy racion´alisak, ´es azt is tudj´ak egym´asr´ol, hogy tudj´ak egym´asr´ol, hogy racion´alisak ´es ´ıgy tov´abb a v´egtelens´egig. A tal´algat´os j´at´ek a gyakorlatban Egy t¨obb, mint 19000 f˝os, nagy p´enzjutalommal j´ar´ o internetes versenyen a nyertes sz´am a 21.6 ≈ 100 · ( 23 )4 volt. Ez azt jelenti, hogy a gy˝oztes u ´gy becs¨ ulte, hogy az ´atlagos tippel˝ o h´arom szint m´elys´egig tud eljutni ebben a gondolatmenetben.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
44 / 55
Racionalit´ as
A t¨ omegek b¨ olcsess´ ege
A t¨omegek b¨olcsess´ege
Az o¨k¨or s´ ulya Francis Galton a viktori´anis kor egyik polihisztora (egy´ebk´ent Darwin unokatestv´ere) volt. Egy vid´eki v´as´aron egy ´erdekes versenybe botlott. Egy o¨k¨or s´ uly´at kellett megbecs¨ ulni a r´esztvev˝ oknek. T¨obb mint 800-an adt´ak le tipp¨ uket, de egy sem tal´alta el a helyes v´alaszt (ami egy´ebk´ent 1198 font volt). A sz´amokat k´es˝ obb elemezve meglep˝ o felfedez´esre jutott. A medi´an (1207 font) mind¨ ossze 0.8%-ban t´ert el a val´os´agt´ol, a tippek ´atlaga (1197 font) pedig m´eg enn´el is jobban megk¨ ozel´ıtette. Ami m´eg meglep˝obb, hogy a r´esztvev˝ ok k¨ oz¨ ott t¨ obb szak´ert˝ o is akadt, de semmelyik¨ uk nem jutott ilyen k¨ ozel az igazs´aghoz.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
45 / 55
Racionalit´ as
A t¨ omegek b¨ olcsess´ ege
A t¨omegek b¨olcsess´ege
Alkalmazhat´os´ag Term´eszetesen nem minden t¨ omeg b¨ olcs. Az al´abbi krit´eriumok sz¨ uks´egesek ahhoz, hogy a t¨ omeg b¨ olcsess´ege kiakn´azhat´o legyen: a v´elem´enyek soksz´ın˝ us´ege f¨ uggetlens´eg decentraliz´aci´o (hierarchia hi´anya) l´etezzen egy aggreg´aci´ os mechanizmus
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
46 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
K´et k´ıs´erlet Adott egy urna benne 90 alakra ´es s´ ulyra megk¨ ul¨ onb¨ oztethetetlen goly´oval. A goly´ok k¨oz¨ ul 30 fekete, a marad´ek 60 pedig s´arga vagy piros sz´ın˝ u (hogy milyen ar´anyban az nem ismert). Egy goly´ot kell h´ uzni az urn´ab´ol ´es v´alaszthatunk a jutalmaz´asi opci´ ok k¨ oz¨ ul.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
47 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
1. k´ıs´erlet 1. Ha fekete goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. 2. Ha piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
2. k´ıs´erlet 1. Ha s´arga vagy piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. 2. Ha fekete vagy s´arga goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
48 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
1. k´ıs´erlet 1. Ha fekete goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
g 2. Ha piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
2. k´ıs´erlet 1. Ha s´arga vagy piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. 2. Ha fekete vagy s´arga goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
48 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
1. k´ıs´erlet 1. Ha fekete goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
g 2. Ha piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
2. k´ıs´erlet 1. Ha s´arga vagy piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
g 2. Ha fekete vagy s´arga goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
48 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
1. k´ıs´erlet 1. Ha fekete goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. g ⇐⇒ T¨obb a s´arga, mint a piros goly´o. 2. Ha piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
2. k´ıs´erlet 1. Ha s´arga vagy piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
g 2. Ha fekete vagy s´arga goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
48 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Kock´ azatker¨ ul´ es vs. Kock´ azatkeres´ es
Ellsberg-paradoxon
1. k´ıs´erlet 1. Ha fekete goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. g ⇐⇒ T¨obb a s´arga, mint a piros goly´o. 2. Ha piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
2. k´ıs´erlet 1. Ha s´arga vagy piros goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art. g ⇐⇒ T¨obb a piros, mint a s´arga goly´o. 2. Ha fekete vagy s´arga goly´ ot h´ uzunk fizetnek nek¨ unk 100 $-´art.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
48 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Einstellung
Die Hard
Segits John McClane-nek hat´astalan´ıtani a bomb´at! Adott egy 3 ´es egy 5 gallonos vizespalack ´es rendelkez´esre ´all tetsz˝ oleges mennyis´eg˝ u v´ız. Pontosan 4 gallon s´ uly´ u vizet kell r´ahelyezni a m´erlegre, hogy a bomba deaktiv´alja mag´at! Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
49 / 55
K´ıs´ erletek a gondolkod´ asr´ ol
Einstellung
Luchins k´ıs´erlete (1942)
A. vizespalack m´erete 21 14 18 15
Csercsik D´ avid (ITK PPKE)
B. vizespalack m´erete 127 163 43 39
C. vizespalack m´erete 3 25 10 3
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
K´ıv´ant mennyis´eg 100 99 5 18
50 / 55
Ultim´ atum j´ at´ ekok
Ultim´atum j´at´ek
Ultim´atum j´at´ek Adott k´et j´at´ekos. Az egyiknek felaj´anlanak egy ¨ osszeget (pl. 10$), amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. Ha azonban a m´asodik j´at´ekos kevesli a r´a jut´ o r´eszt, akkor megv´et´ ozhatja az eloszt´ast. Ekkor egyik¨ uk sem kap semmit.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
51 / 55
Ultim´ atum j´ at´ ekok
Ultim´atum j´at´ek
Ultim´atum j´at´ek Adott k´et j´at´ekos. Az egyiknek felaj´anlanak egy ¨ osszeget (pl. 10$), amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. Ha azonban a m´asodik j´at´ekos kevesli a r´a jut´ o r´eszt, akkor megv´et´ ozhatja az eloszt´ast. Ekkor egyik¨ uk sem kap semmit. J´ at´ ekelm´ elet: A m´asodik j´at´ekos hasznot maximaliz´al ez´ert b´armilyen keveset is kap elfogadja. Az els˝ o j´at´ekos ezt felismerve a lehet˝o legkevesebbet adja. Val´ os´ ag: A legt¨obb j´at´ekos elfelezi a kapott p´enzt. Az ¨osszeg 30%-n´al kisebb aj´anlatokat rendszerint visszautas´ıtj´ak.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
51 / 55
Ultim´ atum j´ at´ ekok
Dikt´ator j´at´ek
Dikt´ator j´at´ek Adott k´et j´at´ekos. Az egyiknek felaj´anlanak egy ¨ osszeget, amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. A m´asodik j´at´ekosnak semmilyen belesz´ol´asa nincs az eloszt´asba.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
52 / 55
Ultim´ atum j´ at´ ekok
Dikt´ator j´at´ek
Dikt´ator j´at´ek Adott k´et j´at´ekos. Az egyiknek felaj´anlanak egy ¨ osszeget, amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. A m´asodik j´at´ekosnak semmilyen belesz´ol´asa nincs az eloszt´asba. J´ at´ ekelm´ elet: A dikt´ator hasznot maximaliz´al, ez´ert semmit nem ad a m´asiknak. Val´ os´ ag: A legt¨obb j´at´ekos az ¨ osszeg 30%-´at tov´abbadja.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
52 / 55
Ultim´ atum j´ at´ ekok
Bizalom j´at´ek
Bizalom j´at´ek Adott k´et j´at´ekos. Az egyik kap egy ¨ osszeget, amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. A m´asodik j´at´ekos az ´atadott p´enz h´aromszoros´at kapja, amib˝ ol valamennyit visszajuttathat, ha u ´gy d¨ont.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
53 / 55
Ultim´ atum j´ at´ ekok
Bizalom j´at´ek
Bizalom j´at´ek Adott k´et j´at´ekos. Az egyik kap egy ¨ osszeget, amit valamilyen ar´anyban megoszthat a m´asik j´at´ekossal. A m´asodik j´at´ekos az ´atadott p´enz h´aromszoros´at kapja, amib˝ ol valamennyit visszajuttathat, ha u ´gy d¨ont. J´ at´ ekelm´ elet: A m´asodik j´at´ekos hasznot maximaliz´al, ez´ert nem k¨ uld vissza semmit. Az els˝o j´at´ekos ezt felismerve nem ad semmit. ´ aban Val´ os´ ag: A legt¨obb j´at´ekos t¨ obb mint az ¨ osszeg fel´et ´atk¨ uldi. Altal´ legal´abb ennyit vissza is k¨ uldenek.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
53 / 55
Ultim´ atum j´ at´ ekok
Bizalom j´at´ek II
Bizalom j´at´ek (vari´ans) Adott n´egy j´at´ekos, akik csak sz´am´ıt´ og´epen kereszt¨ ul tudnak kommunik´alni. Mindegyik¨ uknek adnak egy fix zsetonmennyis´eget, amit k´es˝ obb p´enzre v´althatnak. D¨ onthetnek, hogy a zsetonjukb´ol valamennyit a k¨ oz¨ osbe raknak. A k¨oz¨osben l´ev˝ o zsetonmennyis´eget a j´at´ek v´eg´en megdupl´azz´ak ´es n´egy fel´e osztj´ak. Teh´at ha mindegyik¨ uk kooper´al, akkor megdupl´azz´ak a p´enz¨ uket, m´ıg ha csak egyvalaki, akkor az elvesz´ıti a berakott p´enz´enek a fel´et.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
54 / 55
Ultim´ atum j´ at´ ekok
Bizalom j´at´ek II
Bizalom j´at´ek (vari´ans) Kurzban and Houser 2005-¨ os k´ıs´erlet´eben 84 j´at´ekos vett r´eszt. A r´esztvev˝ok 13%-a mindig kooper´alt, 20%-uk potyautask´ent viselkedett, a marad´ek pedig a t´arsai viselked´es´et˝ ol f¨ ugg˝oen cselekedte az el˝obbit, vagy az ut´ obbit. Hossz´ u t´avon mindenki ugyanolyan j´ ol j´art, teh´at a strat´egi´ak ilyen kevered´ese ESS-t alkotott. K´es˝obb tesztj´at´ekokon megfigyelt´ek, hogy a j´at´ekosok konzisztensen ugyanazon strat´egi´ak ment´en hoztak d¨ ont´eseket, teh´at ’programozottan’ cselekedtek.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 1. ea
55 / 55
