Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Oper´aci´okutat´as I. 2015/2016-2.
Szegedi Tudom´ anyegyetem Informatikai Int´ ezet Sz´ am´ıt´ og´ epes Optimaliz´ al´ as Tansz´ ek
9. El˝ oad´as
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Egy p´elda Adott k´et TV csatorna (N1, N2), melyek 100 milli´o n´ez˝o´ert versenyeznek. Tekints¨ uk a szombat este 20-21 ´ or´as id˝ os´avot. Amikor a csatorn´ak kihirdetik a m˝ usorukat, nem ismerik a m´asik m˝ usor´at. A piackutat´asok alapj´an a k¨ ul¨onb¨oz˝o m˝ usorok eset´en N1 csatorna a k¨ovetkez˝o n´ez˝osz´amokra sz´am´ıthat felt´eve a N1 ´es N2 ad´as´at : N1 Western Akci´ofilm V´ıgj´at´ek
Western 35 45 38
N2 Akci´ ofilm 15 58 14
V´ıgj´at´ek 60 50 70
P´eld´aul, ha N1 Western-t ad, N2 pedig V´ıgj´at´ekot, akkor 60 milli´oan n´ezik N1-et, 100-60=40 milli´ oan pedig N2-t. K´ erd´ es : Mi legyen a k´et csatorna strat´egi´aja, hogy maximaliz´alj´ak a n´ezetts´eg¨ uket?
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Egy p´elda Terminol´ ogia : N1: sorj´ at´ ekos N2: oszlopj´ at´ ekos A fel´ırt m´atrix: kifizet´ esi m´ atrix {Western, Akci´ofilm, V´ıgj´at´ek} : strat´ egi´ ak halmaza Ez egy u ´n. konstans ¨ osszeg˝ u j´ at´ ek: a k´et j´at´ekos nyeres´eg´enek” ” ¨osszege mindig 100 Na de hogyan oldjuk meg a feladatot ? N´ ezz¨ uk meg a kifizet´ esi m´ atrix szerkezet´ et !
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Egy p´elda
Ha N1 Western-t ad, akkor lehet 60 milli´ os n´ezetts´ege (ha N2 V´ıgj´at´ekot ad), de lehet csak 15 milli´ o is (ha N2 Akci´ofilmet ad) ...azaz legrosszab esetben is garant´alt (v´arhat´oan) 15 milli´o n´ez˝o a Western-nel. De ha N1 v´ıgj´at´ekot ad, a helyzet rosszabb, mert csak 14 milli´o n´ez˝o garant´alt. a legrosszabb esetek legjobbika, ha Akci´ ofilmet ad : garant´alt 45 milli´o n´ez˝o N2 ad´as´at´ol f¨ uggetlen¨ ul Egyszer˝ uen: megn´ezi a sorminimumokat ´es veszi a legnagyobbat. Anal´og m´od´on az oszlopj´at´ekos N2 hasonl´ oan tesz : veszi az oszlopmaximumokat ´es veszi a legrosszabb esetet (legkisebbet)
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Egy p´elda
Nem neh´ez l´atni, hogy max(sorminimumok) ≤ min(oszlopmaximumok) A p´eld´ankban N1 az Akci´ ofilmet fogja v´alasztani, N2 pedig a Westernt, ´ıgy 45 vs. 55 mill´o lesz a n´ez˝ ok megoszl´asa. L´atjuk, hogy itt max(sorminimumok) = min(oszlopmaximumok) teljes¨ ul. Az egyenls˝oget megval´ os´ıt´ o strat´egia p´art nyeregpontnak h´ıvjuk. A nyeregponthoz tartoz´ o ´ert´ek (a p´eld´aban 45) a j´ at´ ek ´ ert´ eke.
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Z´erus¨osszeg˝u j´at´ekok Teljes inform´ aci´ os, v´ eges, k´ etszem´ elyes, z´ erus (konstans) ¨ osszeg˝ u j´ at´ ekok : Teljes inform´ aci´ os : mindenki ismeri a j´at´ekszab´alyokat, ki mit l´ephet, mik a l´ep´esek eredm´enyei V´ eges : v´eges sz´am´ u j´at´ekos (most 2 !), v´eges sz´am´ u lehets´eges l´ep´essel (a p´eld´aban 3-3) Z´ erus ¨ osszeg˝ u : pontosan annyit nyer az egyik j´at´ekos, mint amennyit a m´asik vesz´ıt Az ilyen j´at´ekok le´ırhat´ ok egy m´atrixszal, ez´ert r¨ oviden m´ atrix j´ at´ ekoknak nevezz¨ uk ˝ oket M´ atrix j´ at´ ek kifizet´ esi m´ atrix : olyan M m´atrix, amelyben az mij elemek a sor j´at´ekos nyerem´enyei, amennyiben a sor j´at´ekos i-t, az oszlop j´at´ekos a j strat´egi´at j´atsza a j´at´ekban
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Z´erus¨osszeg˝u j´at´ekok - tiszta ´es kevert strat´egia
Az el˝oz˝o j´at´ekban a j´at´ekosok (N1, N2) strat´egi´aja determinisztikus volt : megvizsg´alt´ak a lehets´eges kimeneteleket ´es v´alasztottak egy strat´egi´at (filmt´ıpus) amit k¨ovetnek. Ezt tiszta strat´ egi´ anak h´ıvjuk. Vannak j´ at´ ekok, ahol nincs nyeregpont ⇒ egyetlen, tiszta strat´egia k¨ovet´ese nem mindig garant´alja a legjobb kifizet´est (ld. k¨ovetkez˝o p´elda). Kevert strat´ egia adott n lehets´eges l´ep´es : (s1 , . . . , sn ) (strat´egiahalmaz) si strat´egi´at xi val´ osz´ın˝ us´eggel j´atsszuk xi ≥ 0 ´es x1 + · · · + xn = 1 (eloszl´as a strat´egiahalmaz felett) az optim´ alis strat´ egia : ami maximaliz´alja a v´arhat´o kifizet´est (kifizet´ es v´ arhat´ o´ ert´ ek´ et maximaliz´aljuk)
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game Van egy francia k´artyacsomagunk, aminek egy sz´ın´et kiv´alasztjuk ´es mind a 13 lapj´at kiter´ıtj¨ uk leford´ıtva. Az els˝o j´at´ekos (P1) felh´ uz egy lapot u ´gy, hogy a m´asodik j´at´ekos (P2) nem l´atja azt. P1-nek k´et lehet˝os´ege van : 1
Eldobja a lapot ´es fizet egy doll´art a m´asodik j´at´ekosnak (Pass)
2
Leford´ıtva leteszi a lapot az asztalra, ´atadva a d¨ont´est a m´asodik j´at´ekosnak (Bet)
Amennyibben P1 nem dobott, azaz a j´at´ek folytat´odik, akkor P2-nek szint´en k´et lehet˝os´ege van : 1
Kiter´ıti P1 lapj´at (Call)
2
Passzol ´es fizet egy doll´art az els˝ o j´at´ekosnak (Fold)
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game A lep ter´ıt´esekor k´etf´ele kimenetel lehets´eges : 1
Ha a lap ´ert´eke magas (10, J, Q, K, A), P2 fizet 2$-t az P1-nek
2
Ha a lap ´ert´eke alacsony (2, 3, 4, 5, 6, 7, 8, 9), P1 fizet 2$-t P2-nek
Mik lehetnek P1 start´egi´ai ? Lap ´ert´ek´et˝ol f¨ uggetlen¨ ul dob (PP) Dob, ha a lap ´ert´eke magas, tart, ha alacsony (PB) Dob, ha a lap alacsony, tart, ha magas (BP) Lap ´ert´ek´et˝ol f¨ uggetlen¨ ul tart (BB) P1 lehets´eges strat´egi´ai pedig : Call Fold
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game
Mi t¨ort´enik p´eld´aul, ha P1 BP-t j´atssza, m´ıg P2 a Call-t ? V´arhat´oan mennyit kereshet ´ıgy az els˝ o j´at´ekos ? Annak a val´osz´ın˝ us´ege, hogy magas lapot h´ uz P1 : 5/13 Annak a val´osz´ın˝ us´ege, hogy alacsony lapot h´ uz P1 : 8/13 P1 v´ arhat´ o ( ´atlagos”) nyeres´ ege ebben az esetben : ” 5/13 ∗ 2$ + 8/13 ∗ (−1$) = 2/13$ Mi t¨ort´enik p´eld´aul, ha P1 BP-t j´atssza, m´ıg P2 Fold-ot ? Ekkor az P1 v´ arhat´ o nyeres´ ege: 5/13 ∗ 1$ + 8/13 ∗ (−1$) = −3/13$
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game
A kifizet´ esi m´ atrix a k¨ ovetkez˝ o (hf. sz´amoljuk v´egig )
P1 PP PB BP BB oszlopmax
P2 Call -1 -21/13 2/13 -6/13 2/13
Fold -1 3/13 -3/13 1 1
sormin -1 -21/13 -3/13 -6/13
A j´at´ek z´ erus¨ osszeg˝ u : a k´et j´at´ekos kifizet´es´enek ¨osszege (minden strat´egiap´arra) 0. Azt is l´atjuk, hogy nincs nyeregpont.
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: dominancia Vegy¨ uk ´eszre, hogy P1-nek a BP mindig jobb kifizet´est ad, mind a PP P1-nek BB mindig jobb, mint PB Azt mondjuk, hogy BP domin´ alja P P -t ´es BB domin´ alja P B-t. ⇒ Ha van domin´alt strat´egia, azt elt´avol´ıthatjuk a kifizet´esi m´atrixb´ol (hiszen biztosan nem fogjuk haszn´alni) :
P1 BP BB
P2 Call 2/13 -6/13
Fold -3/13 1
Hat´arozzuk meg, mi lesz a legjobb kevert strat´egia P1-nek.
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: kevert strat´egia P1 v´alassza x1 val´ osz´ın˝ us´eggel BP-t ´es x2 val´osz´ın˝ us´eggel BB-t. A kevert strat´egia : (x1 , x2 ) ; x1 + x2 = 1 V´arhat´o kifzet´es, ha P2 Call-t j´atszik :
2 13 x1
−
6 13 x2
3 V´arhat´o kifzet´es, ha P2 Fold-ot j´atszik : − 13 x1 + x2
Legrosszabb esetben : min { (x1 ,x2 )
2 6 3 x1 − x2 , − x1 + x2 } 13 13 13
Mivel x1 + x2 = 1, ez´ert egyszer˝ us´ıtve : kimenetel = min{ x1
8 6 16 x1 − , − x1 + 1} 13 13 13
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: kevert strat´egia ´ azolva a lehets´eges kimeneteleket : Abr´
A legjobb kevert strat´ egia az E ponthoz tartoz´ o (x1 , x2 ) = (19/24, 5/24) eloszl´as. Ez garant´al v´arhat´o ´ert´ekben 1/39$ nyeres´eget.
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: kevert strat´egia
Teljesen ugyan´ıgy, P2 v´alassza y1 val´ osz´ın˝ us´eggel Call-t ´es y2 -vel Fold-ot. A legrosszabb esetben P2 v´arhat´ o kifizet´ese (vesztes´ege) max { (y1 ,y2 )
2 3 6 y1 − y2 , − y1 + y2 } 13 13 13
mivel y1 + y2 = 1, ez´ert kimenetel = min{ y1
5 3 19 y1 − , − x1 + 1} 13 13 13
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: kevert strat´egia ´ azolva a lehets´eges kimeneteleket : Abr´
A legjobb kevert strat´ egia az F ponthoz tartoz´ o (y1 , y2 ) = (2/3, 1/3) eloszl´as. Ez garant´al v´arhat´o ´ert´ekben 1/39$ vesztes´eget. A legjobb strat´egia P2-nek, hogy 2/3 val´osz´ın˝ us´eggel Call-t, 1/3 val´ osz´ın˝ us´eggel Fold-ot j´atszik.
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: line´aris programoz´as A (x1 , x2 ), illetve (y1 , y2 ) megkeres´es´enek probl´em´aj´at LP feladatk´ent is megfogalmazhatjuk:
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
P´elda – Betting game: line´aris programoz´as
A k´et LP egym´as du´ alisai. Z´erus¨osszeg˝ u j´at´ekokn´al mindig ez a helyzet Er˝os dualit´as ⇒ a k´et LP c´elf¨ uggv´eny ´ert´eke egyenl˝o : ez a j´ at´ ek ´ ert´ eke Az optimumok komplement´arisan laz´ak ⇒ a 2 megold´as egy egyens´ ulypontot ad : egyik j´at´ekos sem tud enn´el jobbat ha elt´er ett˝ol a strat´egi´at´ol : Nash-egyens´ uly T´ etel. (Luce ´ es Raiffa 1989) B´armely z´erus¨ osszeg˝ u j´at´ekhoz l´etezik egy LP feladat, amely megold´asa a j´at´ek egyens´ ulya. Ford´ıtva, minden LP feladathoz megadhat´o egy z´erus¨ osszeg˝ u j´at´ek, amely egyens´ ulyi strat´egi´aja az LP optimuma.
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A fogolydilemma
A val´os´agban a legt¨ obb szitu´aci´ oban a j´at´ekosok nyeres´ege/vesztes´ege nem konstans (vagy nem 0). → lehetnek loose-loose ´es win-win helyzetek. p´eld´aul a kooper´al´ o j´at´ekosok t¨ obbet nyernek egy¨ utt, mint egym´assal versengve, k¨ ul¨on-k¨ ul¨ on Protot´ıpus feladat a h´ıres fogolydilemma: 2 bankrabl´ot (Bonnie ´es Clyde) elfognak egy kisebb b˝ uncselekm´eny miatt, de a bankrabl´ast nem tudj´ak bizony´ıtani. K¨ ul¨on cell´aban helyezik el ˝ oket, es a ker¨ uleti u ¨gy´esz hallgatja ki ˝oket. 1
Ha mindkett˝o vall, akkor 5-5 ´ev b¨ ort¨ ont kapnak
2
Ha csak az egyik vall, a m´asik tagad, akkor a beismer˝o szabadul a tagad´o 20 ´ev b¨ort¨ ont kap
3
Ha mindkett˝o tagad, akkor 1-1 ´ev b¨ ort¨ ont kapnak
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A fogolydilemma A kifizet´esi m´atrix Bonnie Vall Tagad
Clyde Vall (-5, -5) (-20, 0)
Tagad (0, 20) (-1, -1)
Nem (konstans) z´erus¨osszeg˝ u : ha vallanak, −5 − 5 = −10 az ¨osszeg, m´ıg ha tagadnak −1 − 1 = −2. Mi a legjobb, amit tehetnek ? Egy egyens´ ulyi pont ha mindkett˝ o vall: ha b´armelyik j´at´ekos v´altozat ezen, akkor 20 ´ev b¨ort¨ ont kap. Nash egyens´ uly (equlibrium) : olyan strat´egia p´ar, amely eset´en egyik j´at´ekos sem tudja strat´egi´aja v´altoztat´as´aval n¨ ovelni a nyeres´eg´et, amennyiben a m´asik j´at´ekos nem v´altoztat strat´egi´at
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A fogolydilemma
De ha mindkett˝o meggondolja mag´at, es tagadnak : 1-1 ´evvel meg´ ussz´ak. Pareto optimum: Olyan strat´egia p´ar, amit nem tudunk u ´gy megv´altoztatni, hogy valamelyik j´at´ekos kifizet´ese jobb legyen u ´gy, hogy a m´asik j´at´ekos´e nem lesz rosszabb. Ugyanakkor a fogolydilemm´aban a vall strat´egia domin´alja a tagad strat´egi´at ⇒ az egyens´ ulyi strat´egia (NE) egy´ertelm˝ u (vall, vall). T´ etel. (John F. Nash) Minden n-szerepl˝ os j´at´eknak, melyben a strat´egi´ak sz´ama v´eges, van Nash-egyens´ ulya. kevert strat´egi´akat is figyelembe vessz¨ uk az egy´ertelm˝ us´eg nem garant´alt
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
Iter´alt fogolydilemma
A val´os´agban egy j´at´ek” gyakran nem egyetlen interakci´o ” M´ ultb´eli esem´enyek alapj´an v´alaszthatunk strat´egi´at Robert Axelrod The evolution of cooperation” (1984) : iter´alt ” fogolydilemma k´ıs´erlet Kutat´ok k¨ uldhettek be programot, mely iter´alt fogoly dilemm´at j´atszik ´es k¨orr¨ol-k¨ orre friss´ıti a strat´egi´aj´at A programok egym´as ellen j´atszanak Mik a legjobb evol´ uci´ os” strat´egi´ak ? ” Gy˝oztes: Anatol Rapoport tit-for-tat ( j´ o tett hely´ebe j´ot v´arj”) ” strat´egi´aja
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A h´eja-galamb j´at´ek Nem z´erus ¨osszeg˝ u j´at´ekokat az evol´ uci´ o biol´ ogi´ aban is haszn´alnak modellez´esre. A fogolydilemma mellett fontos p´elda a h´ eja-galamb j´ at´ ek: Adott egy faj A faj egyedei kit´erhetnek egym´as el˝ ol vagy harcba sz´allhatnak egym´assal Mindk´et viselked´esnek megvannak a maga el˝ onyei ´es h´atr´anyai Egy egyed vagy mindig kit´er (”galamb” viselked´es), vagy mindig harcba sz´all (”h´eja” viselked´es) Van-e evol´ uci´ osan stabil strat´egia ?
Aj´anlott olvasm´any: Sir John Maynard Smith : Evolution and the Theory ” of Games” (1982)
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A h´eja-galamb j´at´ek Legyen az egyedek k¨ oz¨ otti interakci´ ok fikt´ıv kifizet´esi m´atrixa a k¨ovetkez˝o A egyed
B egyed
Galamb
H´eja
Galamb
(2, 2)
(-1, 5)
H´eja
(5, -1)
(-9,-9)
B´armelyik viselked´es elterjed´ese eset´en a kialakult norm´at´ol elt´er˝o egyed el˝onyh¨oz jut Milyennek kell legyen a k´et viselked´es eloszl´asa egy popul´aci´oban, hogy egyetlen egyednek se ´erje meg v´altoztani” ? ” Mikor v´alik a popul´aci´ o evol´ uci´ osan stabill´a ?
Bevezet´ es
Z´ erus¨ osszeg˝ u j´ at´ ekok
Nem z´ erus¨ osszeg˝ u j´ at´ ekok
A h´eja-galamb j´at´ek Legyen a ”h´ej´ak” ar´anya a popul´aci´ oban x, a ”galambok´e” (1 − x) A h´ej´ak v´arhat´o nyeres´ege −9x + 5(1 − x) = 5 − 14x A galambok v´arhat´ o nyeres´ege 2(1 − x) − x = 2 − 3x Egyens´ uly eset´en 5 − 14x = 2 − 3x azaz x =
3 11
A modellben... egy er˝ oforr´as ´ert´eke 3 az id˝ o ´ert´eke −1 a s´er¨ ul´es ´ert´eke −8
Haszn´alt´ak m´eg t¨obbek k¨ ozt Nukle´aris fegyverek leszerel´es´enek modellez´ese Kubai rak´etav´als´ag j´at´ekelm´eleti modellje Stanley Kubrick Dr. Strangelove c. filmj´eben is megjelenik (k¨olcs¨on¨osen biztos´ıtott megsemmis´ıt´es elve)
