Opakované hry: Vězňovo dilema Rostislav Staněk April 28, 2014 Opakované hry Vězňovo dilema Opakované hry Opakovaná hra se skládá z opakovaní stejné strategické hry. Oproti jednorázovým hrám ale existují strategické vazby mezi jednotlivými koly. Akce hráčů jsou podmíněny tím, co se dělo v minulosti. Hráči mohou být "odměněni" nebo "trestáni" v dalších kolech Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Preference Výsledek opakované hry je oceněn jako diskontovaná suma výplat z jednotlivých strategických her. Výplaty v jednotlivých kolech jsou tzv. separabilní. Označme výplatní funkcí pro danou strategickou hru u, a diskontní faktor Si G< 0,1 >. Sekvence profilů akcí (a1, a2,ar) je oceněna T ^■(a1) + SiUi(a2) + S2Ui(a3) + ... + S^u^a7) = £ S^u^) Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Preference v nekonečně opakované hře Sekvence profilů akcí (a1, a2,...) je oceněna oo uiia1) + 6iu,{čř) + S2ui(a3) + ... = £ ^-^/(a1) t=i Diskontovaný průměr výplat (1 — ô) V Hráč je indiferentní mezi (c, c,...) a (w1, m/2...) OO t=i Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Diskontní faktor Proč je ô £< 0,1 >? • Lidé jsou netrpěliví • Hra může v každém kole skončit s kladnou pravděpodobností • Pokud je výplata měřena v penězích, pak diskontní faktor může odrážet kladnou reálnou úrokovou sazbu Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Definice G je strategická hra. • Množina hráčů je N • Množina konečných historií je množina sekvencí (a1, a2,ar), kde ař je profil akcí v G • Hráčská funkce připisuje každé historii (a1,ař) všechny hráče • Množina akcí dostupná každému hráči po jakékoliv historii je A; • Hráči hodnotí dle konečnou historii (a1, a2,ar) dle své sumy výplat Yll=i äj~lui{at) nebo diskontovaného průměru výplat (l-č)£tT=i «5;-V(ař) Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Opakované hry a extenzivní hry • Strategie v konečné opakované hře specifikuje jakou akci hráč hraje na začátku hry a po jakékoliv sekvenci (a1,ař) • Opakovanou hru lze chápat jako extenzivní hru se simultáními tahy. Nashova rovnováha i SPEjdou definovány jako v extenzivní hře. Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Strategie jako automata Strategií v nekonečně opakovaných hrách může být velmi mnoho. Omezíme se proto na tzv. automata. (stacionární strategie), ve kterých hráč reaguje na určitou sekvenci profilů vždy stejně. Automat se skládá z: • určitého počtu stavů • funkce, která každému stavu připisuje akci, která bude hrána • přechodové funkce, která na základě minulého stavu a výseldku hry posune automat do nového stavu Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Konečně opakované vězňovo dilema Jedinou Nashovou rovnováhou i SPEje profil akcí (D, D) v každé periodě. Lze dokázat zpětnou indukcí Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Strategie v nekonečně opakovaném vězňově dilematu • Grimm-trigger • Tit-for-tat £ C: C (v D) (v C) V: D Figure: Tit for tat strategie • Omezený trest I 1 all outcomes Pq:C Py.D P2:D p3.D (;D) all all Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Nashova rovnováha Je situace v níž všichni hrají grimm-trigger strategii Nashovou rovnováhou? V rovnováze hráč získá (2,2,2,...). Při odchýlení (3,1,1,...). Diskontovaný průměr výplat v případě odchýlení je (1 - 5){3 + 5 + 52 + 53 + ...) = (1 - 5){3 + —-) = 3(1 - 5) + 5 Grimm-trigger je Nashova rovnováha, pokud 3(1 — 5) + 5 ^ 2. Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Dosažitelné výplaty Množina dosažitelných výplat je množina všech vážených průměrů výplat z jednotlivých profilů akcí jednokolové strategické hry, kde váhy jsou dány počtem výskytů výplaty v sekvenci. 2's * payoff (0,3) (1*1) (2,2) (3,0) 2 3 l's payoff - Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Folk teorém • Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v Nashově rovnováze alespoň u,-(D, D). • (xi)x2) je dosažitelný pár výplat v G, pro který platí Xj > uí(D, D). Vždy existuje ô < 1 takový, že pokud ô > ô, pak existuje v G Nashova rovnováha ve které průměrná diskontovaná výplata hráče / je x,-. Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Folk teorém Trajektorie výstupů se skládá z opakování (a1,ak). Označme tuto trajektorii {bl,b2...), kde bqk+t pro q = 0,1,... a t = 1,k. Strategie hráčů je grimm-trigger. Tato strategie je Nashovou rovnováhou, protože / 1 + 1,..., k l,...,k l,...,k Ul{a>) Ul(a^),... > ui{D,D) > ui{D,D) odchýlení v' Ul{D,D),.. -,ui{D,D) ui{D,D) ui{D,D) Table: Nashova rovnováha v nekonečně opakované hře Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema SPE a one-deviation Profil strategií v nekonečně opakované hřeje SPE, pokud splňuje tzv. one-deviation vlastnost. Tj. pokud žádný hráč nemůže zvýšit svou výplatu, pokud se odchýlí na začátku jakékoliv podhry, ve které je první hráčem na tahu, při daných strategiích ostatních hráčů a zbytku své strategie. Pro nekonečné hry platí, jen pokud je ô < 1. Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema SPE Grim-trigger strategie (definovaná výše) tvoří SPE, pokud ô ^ | • Podhra po historii (C,C). Grimm-trigger je optimální, pokud 3(1-<$) + <$ ^2 • Podhra po jiné historii. Odchýlení není výhodné, protože ui(C, D) < ui(D, D) a volba C neovlivní další kola. Rostislav Staněk Opakované hry: Vězňovo dilema Opakované hry Vězňovo dilema Folk teorém • Pro jakýkoli diskontní faktor je průměrná diskontovaná výplata každého hráče v SPE alespoň u,-(D, D). • (xi)x2) je dosažitelný pár výplat v G, pro který platí Xj > uí(D, D). Vždy existuje ô < 1 takový, že pokud ô > ô, pak existuje v G SPE ve které průměrná diskontovaná výplata hráče / je x,-. Rostislav Staněk Opakované hry: Vězňovo dilema