TEORIE HER –“kostra” přednášky Libor Polák, Masarykova Univerzita Brno 1 Hry n hráčů v normální formě 1.1 Základní definice Nechť n ∈ N, n ≥ 2 a N = {1, . . . , n} je množina (všech) hráčů; nechť Xi je neprázdná množina (všech) strategií i-tého hráče, i ∈ N ; nechť ui : j∈N Xj → R je výherní funkce i-tého hráče, i ∈ N . Uspořádanou dvojici G = ((Xi)i∈N , (ui)i∈N ) nazýváme hrou n hráčů v normální formě. Píšeme i = N \ {i}, ˘ui(xi, x1, . . . , xi−1, xi+1, . . ., xn) = ui(x1, . . . , xn) pro i ∈ N, XS = i∈S Xi, S = N \ S pro S ⊆ N a stručně X = XN . Podmnožiny množiny N nazýváme koalice a prvky množiny X nazýváme situace. Strategie x ∈ Xi dominuje (pro i-tého hráče) strategii x′ ∈ Xi, jestliže ∀ y ∈ Xbi ˘ui(x, y) ≥ ˘ui(x′ , y) a ∃ y ∈ Xbi ˘ui(x, y) > ˘ui(x′ , y) . Strategie x ∈ Xi je nedominovaná (pro i-tého hráče), neexistuje-li x ∈ Xi dominující x. Strategie x ∈ Xi se nazývá dominantní (pro i-tého hráče), jestliže ∀ x′ ∈ Xi, y ∈ Xbi ˘ui(x, y) ≥ ˘ui(x′ , y) . Situace x ∈ X dominuje podle Pareta situaci x′ ∈ X, platí-li ∀ i ∈ N ui(x) ≥ ui(x′ ) a ∃ i ∈ N ui(x) > ui(x′ ) . Situace x ∈ X se nazývá optimální podle Pareta, není-li dominována (podle Pareta) žádnou x′ ∈ X. Strategie x, x′ ∈ Xi se nazývají ekvivalentní (pro i-tého hráče), platí-li ∀ y ∈ Xbi ˘ui(x, y) = ˘ui(x′ , y) . Strategií x ∈ Xi si i-tý hráč zaručuje inf y∈Xbi ˘ui(x, y) ∈ R ∪ {−∞} . L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 2 “Číslo” h− i = sup x∈Xi inf y∈Xbi ˘ui(x, y) ∈ R ∪ {−∞, ∞} nazýváme dolní hodnotou hry (pro i-tého hráče). Podobně h+ i = inf y∈Xbi sup x∈Xi ˘ui(x, y) ∈ R ∪ {−∞, ∞} nazýváme horní hodnotou hry (pro i-tého hráče). Strategie x ∈ Xi i-tého hráče se nazývá opatrná, platí-li inf y∈Xbi ˘ui(x, y) = h− i . Hra se nazývá podstatná, existuje-li x ∈ X tak, že ∀ i ∈ N ui(x) ≥ h− i a ∃ i ∈ N ui(x) > h− i . Situace x ∈ X se nazývá rovnovážná (podle Nashe), platí-li ∀ i ∈ N, y ∈ Xi ˘ui(y, xbi) ≤ ui(x) . Hra G = (X, Y ; u, v) dvou hráčů se nazývá antagonistická, platí-li ∀ x, x′ ∈ X × Y u(x) ≤ u(x′ ) ⇔ v(x) ≥ v(x′ ) a s nulovým součtem, je-li dokonce v = −u. Obecněji: hra G = (X1, . . ., Xn; u1, . . ., un) je s konstantním součtem, řekněme c, je-li ∀ x ∈ X u1(x) + · · · + un(x) = c . Hra je konečná, jsou-li množiny X1, . . . , Xn konečné. Obvykle pak klademe Xi = {1, ..., mi}, i ∈ N . Pro n = 2 pak ještě stručněji X = {1, ..., m}, Y = {1, ..., n} a hovoříme o bimaticové hře. Maticová hra je bimaticová hra s nulovým součtem. Pro konečnou hru G = (X1, . . . , Xn; u1, . . . , un) definujeme její pravděpodobnostní rozšíření G∗ = (X∗ 1 , ..., X∗ n; u∗ 1, ..., u∗ n) takto X∗ i = {xi ∈ Rmi | xi,1, ..., xi,mi ≥ 0, xi,1 + ... + xi,mi = 1}, i ∈ N , u∗ i (x) = m1 k1=1 · · · mn kn=1 x1,k1 · · · xn,kn · ui(k1, ..., kn) , x ∈ X∗ = X∗ 1 × · · · × X∗ n . Zobrazení k ∈ Xi → k∗ = (0, ..., 0, 1, 0, ..., 0) ∈ X∗ i , 1 na k-té pozici, je prosté a proto lze množinu Xi považovat za podmnožinu množiny X∗ i - odtud termín “rozšíření”. Strategiím z Xi říkáme čisté a strategiím z X∗ i smíšené. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 3 1.2 Několik existenčních tvrzení Věta 1 Nechť i ∈ N, nechť pro každé j ∈ N je Xj kompaktní metrický prostor a nechť funkce ui je spojitá. Pak existuje nedominovaná strategie i-tého hráče. Věta 2 Za předpokladů Věty 1 je ekvivalentní: (i) existuje dominantní strategie i-tého hráče, (ii) všechny nedominované strategie i-tého hráče jsou ekvivalentní, (iii) množina všech nedominovaných strategií i-tého hráče je rovna množině všech jeho dominantních strategií. Věta 3 Za předpokladů Věty 1 je množina všech opatrných strategií i-tého hráče neprázdná kompaktní a protíná se s množinou všech jeho nedominovaných strategií. Věta 4 Nechť G je nepodstatná hra a nechť x je situace z opatrných strategií. Pak: (i) ∀ i ∈ N, ∀ y ∈ Xbi ui(x) = h− i ≤ ˘ui(xi, y), (ii) x je optimální podle Pareta, (iii) ∀ S ⊆ N, ∀ y ∈ XS není možné, aby současně ∀ i ∈ S ui(x) ≤ ˘uS i (y, xbS) a ∃ i ∈ S ui(x) < ˘uS i (y, xbS). (Přitom index S nahoře značí, že uvažujeme nejprve argumenty s indexy z množiny S.) 1.3 Antagonistické hry Používáme označení G = (X, Y ; u, v) ; platí h− 1 = sup x∈X inf y∈Y u(x, y) a h+ 1 = inf y∈Y sup x∈X u(x, y) . Lemma 1 Platí h− 1 ≤ h+ 1 a to dokonce pro libovolnou hru dvou hráčů. Poznámka 1 (x, y) ∈ X × Y je rovnovážná situace ⇔ ∀ (x, y) ∈ X × Y u(x, y) ≤ u(x, y) ≤ u(x, y) ⇔ ∀ (x, y) ∈ X × Y u(x, y) ≤ u(x, y) . Věta 1 Nechť (x, y), (x, y) jsou rovnovážné situace. Pak rovněž (x, y), (x, y) jsou rovnovážné situace a platí u(x, y) = u(x, y) . Strategie x ∈ X se nazývá optimální (pro prvního hráče), existuje-li y ∈ Y tak, že (x, y) je rovnovážná situace. Podobně pro druhého hráče. Věta 2 Nechť (x, y) je rovnovážná situace. Pak h− 1 = h+ 1 = u(x, y) = inf y∈Y u(x, y) = sup x∈X u(x, y) . Zejména tedy x maximalizuje infy∈Y u(x, y) a y minimalizuje supx∈X u(x, y) . (Obecně pro (x, y) ∈ X × Y máme infy∈Y u(x, y) ≤ h− 1 ≤ h+ 1 ≤ supx∈X u(x, y).) L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 4 Věta 3 Nechť (x, y) ∈ X × Y a nechť inf y∈Y u(x, y) ≥ sup x∈X u(x, y) . Pak (x, y) je rovnovážná situace. Lemma 2 Za předpokladu existence rovnovážné situace y minimalizuje supx∈X u(x, y) ⇔ y maximalizuje infx∈X v(x, y) . Zejména, má-li hra rovnovážnou situaci, je pro každého z hráčů “optimální” = “opatrná”. 1.4 Maticové hry Maticová hra je plně zadána maticí A = (aij) typu m/n; máme X = {1, ..., m}, Y = {1, ..., n}, u(i, j) = aij, v = −u. Jejím pstním rozšířením je hra (X∗ , Y ∗ ; u∗ ) s nulovým součtem, kde X∗ = {x ∈ Rm | x1, . . . , xm ≥ 0, x1 + ... + xm = 1}, Y ∗ = {y ∈ Rn | y1, . . . , yn ≥ 0, y1 + ... + yn = 1}, u∗ (x, y) = xAy⊤ . Lemma 1 (x, y) ∈ X∗ ×Y ∗ je rovnovážnou situací pstního rozšíření hry s maticí A ⇔ ∀ (i, j) ∈ X × Y i∗ Ay⊤ ≤ xAj∗⊤ . Věta (von Neumann) Pstní rozšíření libovolné maticové hry má rovnovážnou situaci. V (konstruktivním) důkazu používáme následující vzájemně duální úlohy lineárního pro- gramování: max{v | A⊤ x⊤ ≥ vJn, xi = 1, x ≥ 0} (1) min{w | Ay⊤ ≤ wJm, yj = 1, y ≥ 0} (2) kde Jk je sloupcový vektor z k jedniček. Pro výpočet jsou vhodnější úlohy: min{t1 + ... + tm | A⊤ t⊤ ≥ Jn, t ≥ 0} (1′ ) max{u1 + ... + un | Au⊤ ≤ Jm, u ≥ 0} (2′ ). Za (neomezujícího) předpokladu, že (1) má přípustné řešení s v > 0, jsou zobrazení α : (x, v) → x/v a β : t → (t, 1)/(t1 + ... + tm) vzájemně inverzními bijekcemi mezi množinou všech přípustných řešení úlohy (1) s kladným v a množinou všech přípustných řešení úlohy (1’) převádějící množinu všech řešení (1) na množinu všech řešení (1’) a zpět. Zcela analogická zobrazení fungují mezi množinami všech přípustných řešení (2) a (2’) a mezi množinami všech řešení (2) a (2’). Konečně úlohu (2’), která je ze všech čtyř úloh lineárního programování v nejvhodnějším tvaru, lze řešit tak, abychom současně dostali i řešení úlohy (1’). L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 5 1.5 Konečné hry Definici pstního rozšíření konečné hry máme na konci sekce 1.1. Věta (Nash) Pstní rozšíření libovolné konečné hry n-hráčů má rovnovážnou situaci. 1.6 Hry na čtverci Jedná se o hry 2 hráčů s nulovým součtem s množinami strategií X = Y = [0, 1] . Věta Nechť u : [0, 1] × [0, 1] → R je spojitá, pro libovolné pevné y ∈ [0, 1] je funkce u(−, y) konkávní a pro libovolné pevné x ∈ [0, 1] je funkce u(x, −) konvexní. Pak existuje rovnovážná situace. Smíšenými strategiemi jsou zde tzv. distribuční funkce na intervalu [0, 1], tj. funkce F : [0, 1] → R, které jsou zprava spojité, neklesající, nezáporné splňující F(1) = 1. Nechť X∗ = Y ∗ jsou rovny množině všech takovýchto funkcí. Interpretace: F(x) je pst, s níž hráč vybírá strategii z intervalu [0, x]. Klademe u∗ (F, G) = [0,1]×[0,1] u(x, y)dF(x)dG(y) . Věta Libovolná hra na čtverci se spojitou výherní funkcí má rovnovážnou situaci ve smíšených strategiích. 2 Teorie užitečnosti Nechť U je (neprázdná) množina událostí. Jediným požadavkem je uzavřenost na tzv. loterie, kterými rozumíme formální konvexní kombinace. Interpretace: Množina U se týká dané osoby v daném okamžiku a loterie r1A1 + ... + rnAn (r1, . . . , rn ∈ R, r1, . . . , rn ≥ 0, r1 +...+rn = 1, A1, . . . , An ∈ U ) je událost spočívající v tom, že s pstí ri nastane událost Ai, i = 1, ..., n. Na množině U uvažujeme relace ≺ , a relaci ≻ inverzní k relaci ≺ . A ≺ B interpretujeme jako dávat přednost události B před událostí A a A B interpretujeme jako žádné z událostí A, B nedávat přednost před druhou. Předpokládáme, že jsou splněny následující axiomy: U1 ∀ A, B ∈ U nastává právě jedna z možností: A ≺ B, A B, A ≻ B; U2 je relací ekvivalence; U3 ≺ je tranzitivní relace; U4 A ≺ B C ⇒ A ≺ C a A B ≺ C ⇒ A ≺ C ; U5 1 · A + 0 · B = A ; U6 r1A1 + ... + rnAn = rσ(1)Aσ(1) + ... + rσ(n)Aσ(n) pro libovolnou permutaci σ množiny {1, ..., n} ; U7 rA + (1 − r)(sB + (1 − s)C) = rA + (1 − r)sB + (1 − r)(1 − s)C ; U8 rA + (1 − r)A = A ; L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 6 U9 A C, r ∈ [0, 1], B ∈ U ⇒ rA + (1 − r)B rC + (1 − r)B ; U10 A ≺ C, r > 0, B ∈ U ⇒ rA + (1 − r)B ≺ rC + (1 − r)B ; U11 A ≺ B ≺ C ⇒ ∃ r ∈ [0, 1] tak, že rA + (1 − r)C B – spojitost - nejdiskutovatelnější axiom. Věta Existuje u : U → R tak, že ∀ A, B ∈ U, r ∈ [0, 1] platí u(A) < u(B) ⇔ A ≺ B , u(rA + (1 − r)B) = r · u(A) + (1 − r) · u(B) . Je-li v jiné takové, existuje α ∈ R, α > 0, β ∈ R tak, že ∀ A ∈ U v(A) = α · u(A) + β . Zobrazení u z minulé věty nazýváme funkcí užitečnosti (daného hráče v daném oka- mžiku). Nyní můžeme upřesnit interpretaci definice hry v normální formě. Jednotliví hráči volí (nezávisle) své strategie. Tak vzniká situace x, která je pro i-tého hráče událostí s užitečností ui(x). 3 Úlohy o dohodě 3.1 Nashova teorie Úloha o dohodě je uspořádaná trojice (S, u∗ , v∗ ), kde S ⊆ R2 je konvexní a kompaktní množina a (u∗ , v∗ ) ∈ S. Interpretace: V daném okamžiku může dvojice hráčů po vzájemné dohodě volit událost z množiny U. Nechť u a v jsou jejich funkce užitečnosti. Klademe S = {(u(A), v(A)) | A ∈ U}. (S je konvexní, neboť U je uzavřená na loterie.) Dále: u∗ je užitečnost, kterou si dokáže zaručit první hráč bez spolupráce s druhým hráčem; podobně v∗ . Nechť D je množina všech úloh o dohodě. Pro funkci ϕ : D → R2 formulujme axiomy: ∀ (S, u∗ , v∗ ) ∈ D, T ⊆ R2 konvexní a kompaktní N1 ϕ(S, u∗ , v∗ ) ≥ (u∗ , v∗ ) ; N2 ϕ(S, u∗ , v∗ ) ∈ S ; N3 (u, v) ∈ S, (u, v) ≥ ϕ(S, u∗ , v∗ ) ⇒ (u, v) = ϕ(S, u∗ , v∗ ) ; N4 ϕ(S, u∗ , v∗ ) ∈ T ⊆ S, (u∗ , v∗ ) ∈ T ⇒ ϕ(T, u∗ , v∗ ) = ϕ(S, u∗ , v∗ ) ; N5 ∀ ξ : R2 → R2 tvaru (u, v) → (αu + β, γv + δ), kde α, β, γ, δ ∈ R, α, γ > 0, platí ϕ(ξ(S), ξ(u∗ , v∗ )) = ξ(ϕ(S, u∗ , v∗ )) ; N6 S symetrická podle osy v = u, u∗ = v∗ ⇒ ϕ(S, u∗ , v∗ ) leží na přímce v = u ; N7 (u∗ , v∗ ) ∈ T ⊆ S ⇒ ϕ(T, u∗ , v∗ ) ≤ ϕ(S, u∗ , v∗ ) . Poznámka Neexistuje funkce ϕ : D → R2 splňující axiomy N1 - N7. Věta (Nash) Existuje, a to jediná, funkce ϕ : D → R2 splňující axiomy N1 - N6. Pro danou úlohu (S, u∗ , v∗ ) nastane právě jedna z možností (i) existuje (u, v) ∈ S, u > u∗ , v > v∗ ; (ii) neplatí (i), ale existuje u > u∗ tak, že (u, v∗ ) ∈ S ; L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 7 (iii) neplatí (i), ale existuje v > v∗ tak, že (u∗ , v) ∈ S ; (iv) neplatí žádná z podmínek (i)–(iii). Je zřejmé, jak vypadá ϕ(S, u∗ , v∗ ) v případech (ii)–(iv). V případě (i) je ϕ(S, u∗ , v∗ ) bod maximalizující funkci (u − u∗ ) · (v − v∗ ) na množině {(u, v) ∈ S | u ≥ u∗ , v ≥ v∗ }. Úlohy o dohodě přirozeně vznikají z bimaticových her takto: Mějme bimaticovou hru s maticemi A a B typu m/n. Množina {(xAy⊤ , xBy⊤ ) | (x, y) ∈ X∗ × Y ∗ } nemusí být konvexní; její konvexní obal je roven množině S′ = conv{(ai,j, bi,j) | (i, j) ∈ X × Y } . Klademe S = conv({(ai,j, bi,j) | (i, j) ∈ X × Y } ∪ {(u∗ , v∗ )}) . Přitom u∗ = supx∈X∗ infy∈Y ∗ xAy⊤ , v∗ = supy∈Y ∗ infx∈X∗ xBy⊤ . 3.2 Vyhrožovací strategie pro bimaticové hry Uvažujeme hru G = (X∗ , Y ∗ ; (u, v) : (x, y) → ϕ(S, xAy⊤ , xBy⊤ )) , kde S = conv{(aij, bij) | (i, j) ∈ X × Y } . Strategiím této hry říkáme vyhrožovací strategie. Věta Výše uvedená hra G je antagonistická a má rovnovážnou situaci. 4 Hry ve tvaru charakteristické funkce 4.1 Základní definice Tak jako v první části, nechť n ∈ N, n ≥ 2 a N = {1, . . ., n} je množina (všech) hráčů, nechť 2N značí množinu všech podmnožin množiny N - její prvky nazýváme koalice. Hra ve tvaru charakteristické funkce je zobrazení v : 2N → R splňující (i) v(∅) = 0 – personálnost (ii) pro libovolná S, T ⊆ N taková, že S ∩T = ∅ platí v(S ∪T) ≥ v(S)+v(T) – superaditivita. Číslo v(S) nazýváme výhrou koalice S. Takovéto hry vznikají přirozeně z her v normální formě, položíme-li v(S) = sup x∈XS inf y∈XbS i∈S ˘uS i (x, y) . Rozdělením hry v nazýváme libovolné x ∈ Rn splňující (i) x1 + ... + xn = v(N) ; (ii) ∀ i ∈ N xi ≥ v({i}) . L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 8 Množinu všech rozdělení hry v značíme E(v). Pokud se všichni hráči “domluví”, pak vzhledem k superaditivitě lze očekávat, že vytvoří jedinou koalici N a o v(N) se budou “dělit” podle nějakého rozdělení. Ze superaditivity plyne, že i∈N v({i}) ≤ v(N). Hra se nazývá podstatná, je-li zde ostrá nerovnost. Nechť ∅ = S ⊆ N, x, y ∈ E(v). Rozdělení x dominuje pro koalici S rozdělení y, píšeme x ≻S y, platí-li (i) ∀ i ∈ S xi > yi ; (ii) i∈S xi ≤ v(S) . Rozdělení x dominuje rozdělení y, píšeme x ≻ y, existuje-li ∅ = S ⊆ N tak, že x ≻S y. Množinu všech nedominovaných rozdělení nazýváme jádrem a značíme ji C(v). Hry u, v (obě n hráčů) se nazývají izomorfní, existuje-li bijekce f : E(u) → E(v) taková, že ∀ x, y ∈ E(u), ∅ = S ⊆ N x ≻S y ⇔ f(x) ≻S f(y) a nazývají se ekvivalentní, existují-li r > 0, α1, . . . , αn ∈ R tak, že ∀ S ⊆ N v(S) = r · u(S) + i∈S αi . Lemma Libovolné dvě ekvivalentní hry jsou izomorfní. Hra v je v (0, 1)-redukované formě, platí-li (i) ∀ i ∈ N v({i}) = 0 a (ii) v(N) = 1. Lemma Libovolná podstatná hra je ekvivalentní, a to právě jedné, hře v (0, 1)-redukované formě. Věta Pro libovolnou hru v platí C(v) = {x ∈ Rn | ∀ S ⊆ N i∈S xi ≥ v(S), i∈N xi = v(N)}. V ⊆ E(v) se nazývá NM-řešení (von Neumann & Morgenstern) hry v, platí-li (i) x, y ∈ V ⇒ x ≻ y ; (ii) x ∈ E(v) \ V ⇒ ∃ y ∈ V x ≺ y . Interpretace: NM-řešení V je norma chování dané sociální skupiny (množiny N). Při odchýlení se se najde koalice nutící danou normu dodržet. Které rozdělení z V se ale zvolí ? To záleží na kooperačních schopnostech jednotlivých hráčů. Hra v je prostá, je-li ∀ S ⊆ N v(S) ∈ {0, 1} a symetrická, je-li každé číslo v(S) dáno pouze počtem prvků množiny S. 4.2 Ekonomické aplikace Pomocí netriviálního použití duality lze dokázat, že následující hry mají neprázdné jádro. 1. Přiřazovací hra. Nechť M = {1, . . . , m} je množina prodejců a M′ = {m + 1, . . ., 2m} je množina kupců, nechť N = M ∪ M′ (úloha s různým počtem kupců a prodejců se řeší analogicky). Hráč L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 9 i ∈ M vlastní dům, který si hodnotí na ai, hráč m + j ∈ M′ chce koupit některý z domů, přitom i-tý hodnotí na bij. Nechť cij = v({i, m + j}) = bij − ai pro bij ≥ ai 0 jinak . Pro S ⊆ M nebo S ⊆ M′ máme v(S) = 0. Pro |S ∩ M| ≥ |S ∩ M′ | > 0 máme v(S) = max i∈S∩M ci,m+α(i) | α : S ∩ M → S ∩ M′ , α prosté . 2. Produkční hra. Nechť N = {1, . . . , n} a nechť i ∈ N má bi1 jednotek zdroje c1, . . . , biq jednotek zdroje cq . Zdroje jsou bezcenné. Jednotka zboží Gl vyžaduje a1l jednotek zdroje c1, . . . , aql jednotek zdroje cq . a může být prodána za pl, l = 1, . . ., m. Nechť koalice S ⊆ N bude vyrábět xl jednotek zboží Gl, l = 1, . . . , m a nechť v(S) = max{ m l=1 plxl | pro k = 1, . . . , q platí ak1x1 + · · · + akmxm ≤ i∈S bik }. 4.3 Shapleyho vektor Nechť n je pevné přirozené číslo. Nechť V je množina všech her n-hráčů ve tvaru charakteristické funkce. Pro u, v ∈ V, α ∈ R, α > 0 a permutaci π množiny N = {1, . . ., n} definujeme u+v, αu, πu ∈ V vztahy: pro S ⊆ N nechť (u+v)(S) = u(S)+v(S), (αu)(S) = αu(S), (πu)(S) = u(π−1 S). Hráč i je podstatný, existuje-li i ∈ S ⊆ N tak, že v(S∪{i}) > v(S)+v({i}). V opačném případě hovoříme o balvanu. Formulujme několik axiomů na funkci ϕ : V → Rn : (píšeme v → (ϕ1[v], . . ., ϕn[v]) ) S1 ϕi[u + v] = ϕi[u] + ϕi[v] ; S2 ϕi[αu] = α · ϕi[u] ; S3 ϕi[πu] = ϕπ−1i[u] ; S4 pro libovolnou množinu S obsahující všechny podstatné hráče máme i∈S ϕi[u] = v(S). Věta (Shapley) Existuje, a to jediná, funkce ϕ : V → Rn splňující axiomy S1–S4. Ta je tvaru ϕi[v] = i∈T⊆N (|T| − 1)! · (n − |T|)! n! · (v(T) − v(T \ {i})) . L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 10 5 Social Choice 5.1 Arrowova věta Nechť N = {1, . . ., n}, n ≥ 2, je množina agentů a nechť A = {1, . . ., m}, m ≥ 2, je množina alternativ. Nechť Sm značí množinu všech permutací množiny A. Její prvky budeme reprezentovat ostrými lineárními uspořádáními množiny A. Libovolné zobrazení p : N → Sm nazýváme preferenčním schématem. Množinu všech takovýchto zobrazení značme stručně P. Konečně zobrazení d : P → Sm se nazývá funkce sociálního rozhodování, stručně (SDF), platí-li (i) ( ∀ ( 0 . Proměnnou xj dáme do báze místo xik0 , čísla v k0-tém řádku vydělíme číslem αk0,j a vhodné násobky tohoto řádku přičteme ke každému dalšímu (včetně posledního) tak, aby nový jtý sloupec byl tvaru (0, ..., 0, 1, 0, ..., 0)⊤ , 1 na k0-té pozici. Zde je nebezpečí zacyklení pro βk0 = 0. Pokud se nedokážeme vyhnout nulovému podílu změnou sloupce použijeme např. Blandovo pravidlo: Vybíráme zleva první sloupec se záporným αj a je-li vícekrát βk = 0, αkj > 0 , volíme k0 s nejmenším ik0 . Jak ale “nastartovat” simplexový algoritmus ? Pokud je (náhodou) některý sloupec matice A tvaru (0, ..., 0, 1, 0, ..., 0)⊤ , dáme příslušnou proměnnou do báze. Pro každý další řádek zavádíme novou nezápornou proměnnou z, nalevo do tohoto řádku přidáme +z a nejprve minimalizujeme součet všech nových proměnných. Pokud měla původní úloha přípustné řešení, umíme skončit s pomocnými proměnnými mimo bázi. V nejhorším (a obvyklém) případě tedy řešíme nejprve pomocnou úlohu min{ z1 + . . . + zm | A · x⊤ + E · z⊤ = b⊤ , x ≥ 0, z ≥ 0 } . Dualita K úloze lineárního programování max    cx⊤       A11 A12 A21 A22                x1 ... xn′ xn′+1 ... xn          ≤ =          b1 ... bm′ bm′+1 ... bm          , x1, ..., xn′ ≥ 0    (P) definujeme úlohu duální L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 14 min    by⊤       A ⊤ 11 A ⊤ 21 A ⊤ 12 A ⊤ 22                y1 ... ym′ ym′+1 ... ym          ≥ =          c1 ... cn′ cn′+1 ... cn          , y1, ..., ym′ ≥ 0    (D). Přitom A11 je blok matice A typu m′ /n′ , A12 je blok matice A typu m′ /n − n′ , A21 je blok matice A typu m − m′ /n′ , A22 je blok matice A typu m − m′ /n − n′ . 1 Specielně pro m′ = m, n′ = n máme max{ cx⊤ | Ax⊤ ≤ b⊤ , x ≥ 0 } a min{ by⊤ | A⊤ y⊤ , y ≥ 0 } . Platí: 1. Modifikujeme-li úlohu (D) na tvar úlohy (P) a použijeme-li výše uvedené schéma, obdržíme opět úlohu (P). 2. Je-li x přípustné řešení (P) a y přípustné řešení (D), platí cx⊤ ≤ by⊤ – slabá věta o dualitě. 3. Má-li každá z úloh (P), (D) přípustné řešení, má každá i řešení a hodnoty účelových funkcí na nich splývají – silná věta o dualitě. Lineární programování v teorii her Náš (konstruktivní) důkaz von Neumannovy věty vedl k tomu, že máme řešit úlohy min{ t1 + ... + tm | A⊤ t⊤ ≥ (1, ..., 1)⊤ , t ≥ 0 } (1′ ) max{ u1 + ... + un | Au⊤ ≤ (1, ..., 1)⊤ , u ≥ 0 } (2′ ). Ty jsou vzájemně duální, (2’) je v nejvhodnějším možném tvaru pro použití simplexového algoritmu a dokonce při jejím řešení získáme i řešení (1’) (neboť účelové funkce obou úloh mají nezáporné koeficienty). Při řešení (2’) začínáme s tabulkou: u1 . . . un z1 . . . zm z1 1 ... A E ... zm 1 −1 . . . −1 0 . . . 0 0 Poslední tabulka při řešení (2’) dává i řešení t úlohy (1’): 1 Úlohy (P) a (D) nalatexoval p. Petr Kučera. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 15 u1 . . . un z1 . . . zm ... . . . . . . ... . . . t1 . . . tm L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 16 TEORIE HER příklady a zadání zkoušek Libor Polák, Masarykova Univerzita Brno Hry v normální formě 1. Dělení koláče 1. hráč zvolí x ∈ [0, 1]. 2. hráč poté co zná x buď “souhlasí” (pak 1. hráč vyhrává x a 2. vyhrává 1 − x ) nebo zvolí y ∈ [0, x) (pak 1. vyhrává 1 − y a 2. vyhrává y). a) Uveďte normální formu této hry. b) Spočtěte h− 1 . c) Najděte všechny rovnovážné situace. d) Má 1. hráč dominantní/ nedominovanou strategii ? 2. Dvojice výrobců Dvojice výrobců produkuje vzájemně zaměnitelné zboží. Pokud si stanoví ceny za jednotku x > 0 respektive y > 0, bude poptávka c = (y/x)α respektive d = (x/y)β jednotek zboží ( α, β > 1 ). Dále víme, že výrobní náklady na jednotku jsou a respektive b ( a, b > 0 jsou dané konstanty). a) Uveďte normální formu této hry. b) Najděte všechny rovnovážné situace. c) Má 1. hráč strategii, která dominuje libovolnou jinou ? d) Najděte všechny opatrné strategie 1. hráče. e) Je to antagonistická hra ? 3. Piráti Nechť f, g : [0, ∞) → R jsou rostoucí funkce, nechť ∀ k, l ∈ N0 f(k) = g(l), f(1) < g(n), g(1) < f(n). Hráči: n pirátů. Každý může zvolit 1. nebo 2. koráb na ostrov pokladů. Použije-li t pirátů 1. koráb a n − t pirátů 2. koráb, budou tyto na cestě f(t) respektive g(n − t) dnů. a) Uveďte normální formu této hry. b) Najděte všechny rovnovážné situace. c) Pro n = 3 najděte výherní funkce pstního rozšíření. d) Ukažte, že existuje jediné p ∈ (0, 1) tak, že strategie “vzít s pstí p 1. koráb” pro každého piráta je rovnovážná situace (n = 3). 4. Souboj Nechť f, g : [0, 1] → R jsou spojité neklesající funkce a nechť f(0) = g(0) = 0, f(1) = g(1) = L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 17 1. Dva střelci, každý s jediným nábojem, jdou proti sobě. V čase t ∈ [0, 1] je pst zásahu protivníka f(t) respektive g(t). Jak vypadají strategie hráčů ? Existují optimální strategie? Pokud ano, všechny najděte. Pistole jsou s tlumiči / bez tlumičů ! 5. Prodej aut Je n agentů prodávající automobily. Zisk i-tého agenta z prodeje jednoho automobilu je pi, za jeho skladování platí ci. Objedná-li i-tý agent xi ∈ [0, ∞), i = 1, . . ., n, prodá za dané období d · xi x1+···+xn v případě x1 + · · · + xn ≥ d a xi jinak. a) Najděte normální formu této hry. b) Najděte všechny opatrné strategie i-tého agenta. c) Najděte všechny nedominované strategie i-tého agenta. d) Najděte všechny rovnovážné situace této hry (alespoň pro n = 2). e) Je pro n = 2 tato hra antagonistická ? f) Které strategie z d) jsou optimální podle Pareta ? L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 18 Teorie her, zadání zkoušek 1996/7 Test Matice P a Q určují bimaticovou hru. Určete h− 1 , h+ 1 , h− 2 , h+ 2 - 4 krát 1 bod; najděte všechny nedominované strategie pro každého z hráčů - 2 krát 1 bod; najděte všechny opatrné strategie pro každého z hráčů - 2 krát 1 bod; najděte všechny rovnovážné situace - 2 body; najděte všechny situace optimální podle Pareta - 2 body; je to podstatná hra ? - zdůvodněte - 2 body. Matice pro skupinu A: P =   3 0 2 2 4 1 1 2 0 0 2 1   Q =   4 1 3 1 1 3 2 0 2 3 4 2   Matice pro skupinu B: P =     1 0 2 1 3 3 3 2 4 4 1 2     Q =     2 2 1 0 1 0 2 1 2 2 2 1     1. termín 1. Definujte hru n-hráčů v normální formě, dolní a horní hodnotu hry pro i-tého hráče a dokažte příslušnou nerovnost (20 b). 2. Definujte antagonistickou hru a dokažte, že množina všech rovnovážných situací je tvaru P × Q pro vhodné množiny P, Q strategií prvního resp. druhého hráče (20 b). 3. Symetrická hra n-hráčů ve tvaru charakteristické funkce je zadána čísly v0 = 0, v1 = 0, v2, ..., vn = 1. Kdy má neprázdné jádro ? (20 b) L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 19 2. termín 1. Připomeňte Shapleyho axiomy (8 b) a odvoďte Shapleyho vektor pro hry tvaru wS, S = ∅ (12 b). (wS je prostá hra, pro níž wS(T) = 1 ⇔ S ⊆ T.) 2. Co je to úloha o dohodě (4 b) ? Jak bimaticovou hru s maticemi A, B typu m/n interpretujeme jako úlohu o dohodě (10 b) ? Jak ji řešíme v jediném netriviálním případě (6 b) ? Axiomy formulovat nemusíte. 3. Najděte nějakou rovnovážnou situaci hry na čtverci s výherní funkcí u(x, y) = −2x2 + y2 + 3xy − x − 2y. (12 b; nedoporučuji počítat dolní/ horní hodnotu). Existuje pro prvního hráče dominantní strategie (8 b) ? Zdůvodnění ! 3. termín 1. Odvoďte přímo z Nashových axiomů, jak vypadá řešení úlohy o dohodě (S, 0, 0), kde S = conv{(0, 0), (1, 0), (0, 4)}. 2. Definujte maticovou hru (2 b), její pravděpodobnostní rozšíření (3 b), modifikujte definici rovnovážné situace pro tento případ (3 b), formulujte (3 b) a dokažte (6 b) Lemma redukující předchozí pojem na ověření konečného počtu nerovností, formulujte von Neumannovu větu (3 b). 3. Nechť n = 2, N = {1, 2}, u : 2N → R, u(∅) = 0, u({1}) = a, u({2}) = b, u(N) = c. Kdy je to hra ? (3 b) Kdy má neprázdné jádro ? (3 b) Nechť nyní n = 3, N = {1, 2, 3}, v : 2N → R, v(∅) = v({1}) = v({2}) = v({3}) = 0, v(N) = 1, v({1, 2}) = p, v({1, 3}) = q, v({2, 3}) = r. Kdy je to hra ? (4 b) Kdy má neprázdné jádro ? (10 b) L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 20 Teorie her, zadání zkoušek 1997/8 1. test 1. Každý z dvojice hráčů schová do své pravé ruky 1 nebo 2 nebo 3 mince (všechny mince jsou stejného druhu). Poté ruce současně otevřou a pokud mají stejný počet mincí, získává všechny ukázané první hráč. V opačném případě získává všechny druhý hráč. Najděte optimální strategie obou hráčů. (10 bodů) 2. Matice A a B určují bimaticovou hru. a) Určete h− 1 , h+ 1 , h− 2 , h+ 2 – 2 body; b) najděte všechny nedominované strategie pro každého z hráčů – 2 krát 1 bod; c) najděte všechny rovnovážné situace – 2 body; d) najděte všechny situace optimální podle Pareta – 2 body; e) je to podstatná hra ? – zdůvodněte – 2 body. A =     2 0 1 2 5 1 2 3 1 4 3 0 2 1 1 4 0 2 1 2     B =     2 1 2 4 4 4 1 5 1 1 1 1 3 2 2 0 1 1 0 0     2. test 1. Matice A a B určují bimaticovou hru. a) Najděte nějakou rovnovážnou situaci této hry ve smíšených strategiích, které nejsou čisté. b) Najděte všechny opatrné (smíšené) strategie obou hráčů. c) Řešte tuto hru jako úlohu o dohodě. A = 4 0 0 1 B = 1 0 0 a 1 < a ≤ 4 . L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 21 2. Nechť n = 3, N = {1, 2, 3}, v : 2N → R, v(∅) = v({1}) = v({2}) = v({3}) = 0, v(N) = 1, v({1, 2}) = a, v({1, 3}) = b, v({2, 3}) = c. a) Kdy je to hra ? b) Kdy má neprázdné jádro ? Závěrečné dějství - 1. termín 1. Von Neumannova věta a) definujte maticovou hru – 2 body, b) definujte její rovnovážnou situaci – 2 body, c) uveďte příklad maticové hry nemající rovnovážnou situaci – 2 body, d) definujte pravděpodobnostní rozšíření maticové hry – 3 body, e) definujte jeho rovnovážnou situaci – 2 body, f) formulujte (2 body) a dokažte (3 body) lemma redukující ověření rovnovážnosti na konečný počet nerovností, g) formulujte (2 body) a dokažte (5 bodů) von Neumannovu větu, h) demonstrujte větu na svém příkladě z c) – 2 body. 2. Hlasování Trojice agentů N = {1, 2, 3} vybírá kandidáta z množiny A = {a, b, c, d}. Agenda výběru je následující: agent 1 vyškrtne jednoho z kandidátů, poté agent 2 vyškrtne dalšího kandidáta, konečně agent 3 vyškrtne jednoho ze dvou zbývajících. Zůstane vítěz. Užitečnosti zvolení jednotlivých kandidátů jsou pro hráče 1,2,3 dány funkcemi u, v, w splňujícími u(d) < u(c) < u(b) < u(a), v(c) < v(d) < v(a) < v(b), w(c) < w(a) < w(b) < w(d) . a) Nalezněte normální formu této hry. Kolik prvků mají množiny všech strategií jednotlivých hráčů ? – 5 bodů (Množiny strategií nesmí záviset na funkcích u, v, w .) b) Najděte pro jednotlivé hráče množiny všech jejích nedominovaných strategií – 6 bodů. (Pro hráče 1 a 2 je to náročnější než jiné části úlohy - dělejte to raději na závěr.) c) Vyřešte hru pomocí postupného odstraňování dominovaných strategií – 4 body. (Není potřeba zcela zvládnout b): nechť původní množiny strategií jsou X, Y, Z, nechť Z′ L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 22 je množina všech nedominovaných strategií 3. hráče. Najdeme množinu Y ′ všech nedominovaných strategií 2. hráče pro hru (X, Y, Z′ ; ...) a poté množinu X′ všech nedominovaných strategií 1. hráče pro hru (X, Y ′ , Z′ ; ...). ) d) Popište množinu všech situací optimálních podle Pareta. Kolik je jich ? – 5 bodů. e) Nalezněte nějakou rovnovážnou situaci této hry – 5 bodů. Závěrečné dějství - 2. termín 1. Jádro her ve tvaru charakteristické funkce a) Definujte hru n hráčů ve tvaru charakteristické funkce, rozdělení, dominování a jádro. – 2, 2, 4 a 2 body b) Vyjádřete jádro systémem nerovností a dokažte to. – 3 a 9 bodů c) Dejte příklad hry s prázdným jádrem. – 3 body 2. Aukce Jistý předmět (vzácný obraz, továrna, fotbalový tým) se draží “obálkovou metodou”. Vyvolávací cena je r, i-tý (i ∈ {1, ..., n}) účastník aukce si předmět cení na ai . Nechť 0 < r < an < ... < a2 < a1 . Předpokládáme, že peníze jsou spojité (= lze platit libovolné x ∈ R). Účastníci nezávisle na sobě uvedou cenu, za kterou chtějí předmět koupit. Předmět získává ten, který nabídl nejvíce; je-li více těch, kteří uvedli maximální hodnotu, předmět získává ten z nich, který má nejmenší pořadové číslo (= ten, který si předmětu nejvíce cení). Vítěz aukce zaplatí za předmět cenu, kterou nabídl. a) Uveďte normální formu této hry. (4 body) b) Pro každého z hráčů určete množinu všech jeho nedominovaných strategií. (3 body za uvedení výsledku, 4 body za důkaz toho, že dominované jsou skutečně dominované, podobně 4 body za nedominované.) c) Najděte všechny rovnovážné situace této hry. (5 bodů) d) Najděte všechny situace optimální podle Pareta. (5 bodů) Pro archív Aukce II Úloha se od předchozí liší jen tím, že vítěz zaplatí za předmět nejvyšší cenu z nabídek ostatních. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 23 Závěrečné dějství - 3. termín 1. Úlohy o dohodě a) Formulujte úlohu o dohodě – 3 body. b) Dejte její interpretaci – 3 body. c) Formulujte Nashovy axiomy – 4 body. d) Formulujte hlavní větu – 3 body. e) Dokažte její část týkající se jednoznačnosti ( Pokud použijete nějaké lemma, formulujte je, ale nedokazujte. ) – 9 bodů. f) Jak vznikají úlohy o dohodě z bimaticových her ? – 3 body 2. Hlasování II Dvojice agentů N = {1, 2} vybírá kandidáta z množiny A = {a1, ..., a2m+1} (m ∈ N) . Užitečnosti kandidátů pro agenty 1, 2 jsou dány funkcemi u, v . Nechť u(a1) > u(a2) > · · · > u(a2m+1) . Agenti současně udají pořadí kandidátů. Vítěz je ten s nejlepším nejhorším oceněním. Je-li takových více, dává se přednost kandidátu s nejnižším pořadovým číslem. a) Uveďte normální formu této hry – 4 body. b) Kdy je tato hra antagonistická ? – 3 body c) Jaká je dolní hodnota této hry pro prvního hráče ? – 5 bodů d) Charakterizujte opatrné strategie prvního hráče. – 5 bodů e) Nechť m = 1, v(a2) > v(a3) > v(a1) . Najděte všechny rovnovážné situace – 5 bodů. f) Pro hru s parametry z e) charakterizujte situace optimální podle Pareta – 3 body. Pokud vám nejde a), c), d) v plné obecnosti, udělejte to alespoň za předpokladů z e) – 2, 2, 2 body. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 24 Teorie her, zadání zkoušek 1998/9 1.test 1. Každý z dvojice hráčů schová do své pravé ruky 1 nebo 2 nebo 3 mince (všechny mince jsou stejného druhu). Poté ruce současně otevřou a ten. kdo má o jedinou minci více získává všechny ukázané (počítáme modulo 3). Pokud ukázali stejný počet, nic se neděje. Najděte optimální strategie obou hráčů. (10 bodů) 2. Matice A a B určují bimaticovou hru. a) Určete h− 1 , h+ 1 , h− 2 , h+ 2 – 2 body; b) najděte všechny nedominované strategie pro každého z hráčů – 2 krát 1 bod; c) najděte všechny rovnovážné situace – 2 body; d) najděte všechny situace optimální podle Pareta – 2 body; e) je to podstatná hra ? – zdůvodněte – 2 body. A =       1 3 5 3 3 2 0 1 2 5 3 0 2 1 1 4 0 2 1 2 1 2 3 1 4       B =       2 1 2 4 4 4 1 5 1 1 3 1 2 0 3 1 1 3 2 2 0 1 1 0 0       3. Dokažte, že pro maticovou hru s kososymetrickou maticí (t.j. A⊤ = −A ) existuje rovnovážná smíšená strategie tvaru (x, x). (5 prémiových bodů). 2. test 1. Uvažujme hru “piráti” s výherní funkcí danou tím, že piráti z korábu, krerý přijel dříve, se rozdělí o (jediný) poklad rovnoměrně. Nechť f(t) < g(n−t), f(t+1) > g(n−t−1). a) Popište pravděpodobnostní rozšíření této hry. b) Najděte všechny rovnovážné situace v ryze smíšených strategiích v případě n = 3, t = 1. 2. Nechť u bimaticové hry i-tá strategie prvního hráče dominuje jeho j-tou strategii. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 25 a) Dokažte, že existuje rovnovážná situace ve smíšených strategiích, v níž první hráč používá j-tou strategii s pravděpodobností 0. b) Dejte příklad, kde navíc k-tá strategie druhého hráče dominuje jeho l-tou strategii a existuje rovnovážná situace, v níž první hráč hraje svou j-tou strategii s nenulovou pravděpodobností a druhý hráč svou l-tou strategii též s nenulovou pravděpodobností. 1. termín 1. a) O událostech A, B, C víme, že C ≺ B ≺ A a že u(B) = b, u(C) = c. Jak určíme u(A) ? b) Co když řešíme maticovou hru jako úlohu o dohodě ? (10 a 5 bodů.) 2. a) Uveďte všechny prosté hry 3 hráčů. (Nerozlišujte mezi takovými, kdy jedna vznikne z druhé přeznačením hráčů.) b) Které z nich jsou podstatné ? c) Které z nich mají neprázdné jádro ? (5, 5 a 5 bodů.) 3. Úsečka [0, 1] symbolizuje koláč, který se dělí mezi dva hráče. Užitečnost zisku A ⊆ [0, 1] je pro prvního resp. druhého hráče p(A) = A ( 3 2 − x)dx resp. q(A) = A ( 1 2 + x)dx . Nad koláčem se pohybuje nůž od bodu 0 do bodu 1 (zleva doprava). Kterýkoliv z hráčů může v kterýkoliv okamžik nůž zastavit. Pokud dají signál k zastavení současně, má přednost signál prvního hráče. Ten, kdo nůž zastavil dostává levou část, zbývající hráč pravou část. a) Najděte normální formu této hry. b) Najděte všechny opatrné strategie pro každého z hráčů. c) Pro každého z hráčů najděte všechny jeho nedominované strategie. d) Najděte nějakou rovnovážnou situaci této hry. e) Je naše hra antagonistická ? (Můžete se pokusit o charakterizaci všech situací optimálních podle Pareta.) (Každá část 6 bodů.) 2. termín 1. Grafické řešení maticových her typu 2/m. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 26 a) Nakreslíme všechny úsečky [ [0, a2j], [1, a1.j] ], j = 1, ..., m. Jak najdeme opatrné strategie 1. hráče ? Jak najdeme rovnovážné situace ? b) Metodou z a) najděte všechny rovnovážné situace hry s maticí A = 5 3 −2 1 −1 0 6 2 (10 a 5 bodů.) 2. Nechť v je hra ve tvaru charakteristické funkce s neprázdným jádrem C a nechť V je nějaké její NM-řešení. a) Jaký je vztah mezi množinami C a V ? b) Dejte příklad, kdy C = V . c) Dejte příklad, kdy C = V . (5, 5 a 5 bodů.) 3. Spravedlivá korupce. Tři agenti vybírají alternativu z množiny A = {1, ..., m}. Jejich zisky při výběru j-té jsou pj, qj resp. rj. Agenda je následující: První navrhne alternativu a částky druhému a třetímu (mohou být i záporné), které od něj dostanou při schválení. Pokud některý z nich nesouhlasí, navrhuje druhý alternativu a částku třetímu (může být i záporná), kterou od něj dostane při schválení. (Prvního agenta se již nikdo na nic neptá.) Pokud třetí nesouhlasí, vybere alternativu. Předpokládáme, že všechny částky jsou celočíselné. a) Najděte normální formu této hry. b) Popište opatrné strategie jednotlivých agentů. c) Popište nedominované strategie jednotlivých agentů. d) Nechť p = (10, 9, 6, 8, 11), q = (2, 5, 9, 10, 11), r = (10, 8, 6, 4, 2) . Odstraňte dominované strategie třetího agenta. V nové hře nechte pouze opatrné strategie druhého agenta a konečně v takto získané hře vyšetřete opatrné strategie prvního agenta. (6, 6, 6 a 12 bodů.) 3. termín 1. Nechť A je matice typu 3 × 3. a) Nechť jedinou rovnovážnou situací hry určené maticí A je pozice (1, 1). Může odebráním 3. řádku / přidáním 4. řádku tato rovnovážná situace zmizet a rovnovážnou se stát nějaká jiná ? L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 27 b) Nechť jedinou opatrnou strategií hry určené maticí A je volba 1. řádku. Může odebráním 3. řádku / přidáním 4. řádku tato opatrná strategie zmizet a nějaká jiná se stát opatrnou ? c) Předpoklady jako v b). Může odebráním 3. sloupce / přidáním 4. sloupce tato opatrná strategie zmizet a nějaká jiná se stát opatrnou ? Je to celkem 6 otázek. Záporné odpovědi vysvětlete, kladné dokumentujte příklady. (5, 5 a 5 bodů.) 2. Nechť v je hra ve tvaru charakteristické funkce, která je symetrická a je určena hod- notami v0 = v1 = 0, v2 = 2/3, v3 = 1 . a) Najděte množinu všech rozdělení a jádro této hry. b) Která rozdělení jsou dominována vektorem (1/3, 1/3, 1/3) ? c) Dokažte, že množina {(1/3 + ε, 1/3, 1/3 − ε) | 0 ≤ ε ≤ 1/3} ∪ {(1/3 − ε, 1/3 + ε, 1/3) | 0 ≤ ε ≤ 1/3} ∪ {(1/3, 1/3 − ε, 1/3 + ε) | 0 ≤ ε ≤ 1/3} tvoří NM-řešení naší hry. Návod: Pro rozdělení (x, y, z) splňující x ≥ y, z rozlišme 1. x + z < 2/3 2. x + z = 2/3 3. x + z > 2/3, z < 1/3 4. x + z > 2/3, z ≥ 1/3. (5, 5 a 5 bodů.) 3. Korupce se svatým předsedou. Množina agentů N = {1, ..., n} vybírá alternativu z množiny A = {1, ..., m}. Nejprve uvažme druhou fázi agendy: Je dána matice Q typu n/(m + 1) a agent i0. Ten nabízí alternativu a (nezáporné) úplatky ostatním hráčům. Zisk i-tého hráče při výběru j-té alternativy je dán číslem qi,j. V posledním sloupci jsou uvedeny zisky jednotlivých agentů v případě, že některý agent s návrhem nesouhlasí. (Ke všem hodnotám jsou přičteny úplatky získané v první fázi.) a) Najděte normální formu této hry. b) Popište opatrné strategie jednotlivých agentů. c) Popište nedominované strategie jednotlivých agentů. d) Demonstrujte vše na příkladě i0 = 1, Q =   15 10 6 8 7 4 10 3 7 6 6 4 17 7 9   První fáze: L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 28 Předseda navrhne alternativu a vektor bočních plateb mezi agenty, tj. a ∈ A, b ∈ Zn , b1+ ... + bn = 0. Na výběru alternativy je zainteresován pouze morálně. V našem modelu není hráčem. Dále je dána matice P typu n/m. Zisk i-tého hráče při výběru j-té alternativy je dán číslem pi,j. Agenti licitují, kdo bude ve druhé fázi podávat návrh. Probíhá to tak, že postupně nabízejí ostatním úplatek (kladný, všem stejný). Rozhoduje výše úplatku, v případě rovnosti má přednost agent s nižším pořadovým číslem. e) Předpokládáme, že ve druhé fázi bude hrát agent i0 opatrnou strategii (vzhledem k nedominovaným strategiím ostatních) a ostatní nějaké nedominované. Jak si budete počínat v roli i-tého hráče ? f) Demonstrujte vše na příkladě a = 4, b = (−1, −1, 2), P =   15 10 6 8 4 10 3 7 6 4 17 7   . Předpokládáme, že všechny částky jsou celočíselné. (4, 5, 5, 5, 5 a 6 bodů.) L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 29 Teorie her, zadání zkoušek 1999/2000 1. termín 1. Matice A a B určují bimaticovou hru. a) Najděte nějakou rovnovážnou situaci této hry ve smíšených strategiích, které nejsou čisté. b) Najděte všechny opatrné (smíšené) strategie obou hráčů. c) Řešte tuto hru jako úlohu o dohodě. A = a 0 0 1 B = 1 0 0 5 1 < a ≤ 5 . (3, 3 a 4 body) 3. Prsty a) 2 hráči sedí naproti sobě u stolu. Pod ním si na pravé i levé ruce připraví jeden nebo dva vztyčené prsty. Současně zvednou ruce zpoza stolu. Pravou rukou každý hádá, kolik má jeho protivník vztyčených prstů na levé ruce. Jestliže uhodl právě jeden z hráčů, vyhrává počet peněžních jednotek rovných počtu vztyčených prstů na levých rukách. Najděte optimální strategie příslušné maticové hry. b) Zábavnější varianta: všechny uhodnuté prsty se useknou a hra se opakuje. Konec nastává, když se některý z hráčů již nemůže chlubit žádnými prsty levé ruky. Nalezněte alespoň rekurentní vztahy. (10 a 10 bodů) 3. Aukce Jistý předmět (vzácný obraz, továrna, fotbalový tým) se draží ‘obálkovou metodou”. Vyvolávací cena je v, i-tý (i ∈ {1, ..., n}) účastník aukce si předmět cení na ci . Nechť 0 < v < cn < ... < c2 < c1 . Předpokládáme, že peníze jsou spojité (= lze platit libovolné x ∈ R). Účastníci nezávisle na sobě uvedou cenu, za kterou chtějí předmět koupit. Předmět získává ten, který nabídl nejvíce; je-li více těch, kteří uvedli maximální hodnotu, předmět získává ten z nich, který má nejmenší pořadové číslo (= ten, který si předmětu nejvíce cení). Vítěz zaplatí za předmět nejvyšší cenu z nabídek ostatních. a) Uveďte normální formu této hry. (4 body) L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 30 b) Pro každého z hráčů určete množinu všech jeho nedominovaných strategií. (3 body za uvedení výsledku, dalších 6 bodů za důkaz.) c) Najděte všechny situace optimální podle Pareta. (5 bodů) Kdo si hraje, nezlobí. 2. termín 1. Grafické řešení maticových her typu 2/m. ) Nakreslíme všechny úsečky [ [0, a2j], [1, a1.j] ], j = 1, ..., m. Jak najdeme opatrné strategie 1. hráče ? Jak najdeme rovnovážné situace ? b) Metodou z a) najděte všechny rovnovážné situace hry s maticí A = −2 1 −1 −3 4 0 2 5 (10 a 5 bodů.) 2. Prosté hry. a) Uveďte všechny (superaditivní a personální) prosté hry 3 hráčů. (Nerozlišujte mezi takovými, kdy jedna vznikne z druhé přeznačením hráčů.) b) U každé z nich vyznačte diktátory a veta hráče. c) U každé z nich spočtěte jádro. (4, 3 a 5 bodů.) 3. Aukce III V aukci II se jistý předmět draží “obálkovou metodou”. Vyvolávací cena je v, i-tý (i ∈ {1, ..., n}) účastník aukce si předmět cení na ci . Nechť 0 < v < cn < ... < c2 < c1 . Předpokládáme, že peníze jsou spojité (= lze platit libovolné x ∈ R). Účastníci nezávisle na sobě uvedou cenu, za kterou chtějí předmět koupit. Předmět získává ten, který nabídl nejvíce; je-li více těch, kteří uvedli maximální hodnotu, předmět získává ten z nich, který má nejmenší pořadové číslo (= ten, který si předmětu nejvíce cení). Vítěz zaplatí za předmět nejvyšší cenu z nabídek ostatních. Již víme, že zde má každý hráč jedinou dominantní strategii - tou je pro i-tého hráče ci. Nyní hráči i = 2, ..., n dají (nezávisle) 1. hráči lísteček uvádějící, kolik požadují za odstoupení z aukce ( x2, ..., xn > 0). 1. hráč se rozhodne, které hráče vyplatí a aukce proběhne tak, že každý hraje svoji dominantní strategii. a] Najděte všechny nedominované strategie 1. hráče. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 31 b) Najděte nějakou rovnovážnou situaci naší hry. c) Předpokládejme, že při stejném zisku dá 1. hráč přednost strategii, při níž se dražby zúčastní menší počet hráčů. Jak by si počínal i-tý (i ≥ 2), kdyby znal x2, ..., xi−1, xi+1, ..., xn ? (6, 6 a 6 bodů) I dospělí si mohou hrát. 3. termín 1. Prsty o život 2 hráči sedí naproti sobě u stolu. Pod ním si na pravé ruce připraví jeden, dva nebo tři vztyčené prsty. Současně zvednou ruce zpoza stolu. První hráč se snaží uhodnout svým gestem, kolik ukáže druhý. Naopak druhý hráč se snaží ukázat jiný počet prstů než první. Hraje se o život. (12 bodů) 2. Jádro her ve tvaru charakteristické funkce U hry tří hráčů je dáno v(∅) = v({2}) = v({3}) = 0, v({1, 3}) = 2/3, v({2, 3}) = 5/8. v({1, 2, 3}) = 1. Vzhledem k parametrům a = v({1}), b = v({1, 2}) diskutujte a) Kdy je to (personální a superaditivní) hra ? b) Nechť jsou splněny předpoklady z a). Kdy má tato hra neprázdné jádro ? (5 a 10 bodů) 3. Pohyblivý nůž II Úsečka [0, 1] symbolizuje koláč, který se dělí mezi dva hráče. Užitečnost zisku A ⊆ [0, 1] je pro prvního resp. druhého hráče p(A) = A x dx resp. q(A) = A (1 − x)dx . Nad koláčem se pohybuje nůž od bodu 0 do bodu 1 (zleva doprava). Kterýkoliv z hráčů může v kterýkoliv okamžik nůž zastavit. Pokud dají signál k zastavení současně, má přednost signál prvního hráče. Ten, kdo nůž zastavil dostává levou část, zbývající hráč pravou část. a) Najděte normální formu této hry. b) Najděte všechny opatrné strategie prvního hráče. c) Najděte všechny nedominované strategie prvního hráče. (4, 6 a 8 bodů) Co Tě nezabije, to Tě posílí (aspoň na chvíli). L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 32 Teorie her, zadání zkoušek 2000/1 1. termín 1. Dejte příklad bimaticové hry a strategií k a l pro prvního hráče této hry ?ak, aby k byla opatrná ale nebyla nedominovaná a l byla nedominovaná ale nebyla opatrná. (Uvažujeme pouze čisté strategie). 2. Dva mladíci se baví tím, že se středem vozovky proti sobě rozjedou svými auty a kdo první uhne ztratí prestiž. Jedná se o bimaticovou hru s maticemi A = 0 −5 5 −100 B = 0 5 −5 −100 Strategiemi každého z hráčů jsou Uhne, Neuhne. a) Najděte všechny opatrné čisté strategie obou hráčů. b) Najděte všechny opatrné smíšené strategie obou hráčů. c) Najděte všechny nedominované čisté strategie obou hráčů. d) Najděte všechny nedominované smíšené strategie obou hráčů. e) Najděte všechny rovnovážné situace v čistých strategiích. f) Najděte všechny rovnovážné situace ve smíšených strategiích. g) Najděte všechny situace optimální podle Pareta (v čistých strategiích). h) Řešte tuto úlohu jako úlohu o dohodě. i) Řešte tuto úlohu ve vyhrožovacích strategiích. 3. Uvažujeme symetrickou hru 3 hráčů ve tvaru charakteristické funkce v0 = v1 = 0, v2 = 2 3 , v3 = 1 . a) Spočtěte její jádro C. b) Pro každý vektor x z množiny všech rozdělení E, který není v C najděte nějaký vektor y dominující x. c) Je množina C NM-řešením ? Zdůvodněte. d) Je pravda, že libovolné NM-řešení V obsahuje množinu C ? Zdůvodněte. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 33 2. termín 1. Dejte příklad maticové hry, u níž postupné odstraňování dominovaných strategií vede na hru s maticí typu 1/1. Příklad ?usí být takový, že potřebujeme alespoň 3 fáze. 2. Hraje se hra “kámen, nůžky, papír” s tím, že vítěz získává předmět užitečnosti 1, V případě remízy nezískává nikdo nic. a) Je to antagonistická hra ? b) Najděte všechny opatrné smíšené strategie obou hráčů. c) Najděte nějakou rovnovážnou situaci ve smíšených strategiích. c) Řešte tuto úlohu jako úlohu o dohodě. 3. Uvažujeme hru 3 hráčů ve tvaru charakteristické funkce v(∅) = 0, v({1}) = v({2}) = v({3}) = 1/6, v({1, 2}) = v({1, 3}) = 2/3, v({2, 3}) = a, a ∈ R . a) Pro která a se jedná o (superaditivní) hru ? b) Pro která a má tato hra neprázdné jádro ? c) Transformujte hru na (0,1)-redukovaný tvar. d) Spočtěte Shapleyeho vektor naší hry. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 34 Teorie her, zadání zkoušek 2001/2 2. termín 1. Boty Jediný hodnotný předmět vlastněný levobotkem je jedna levá bota; podobně pro pravobotka. Hráči : m levobotků a n pravobotků, m > n . Výhra koalice je dána počtem párů bot, které se jim podaří sestavit. a) Spočtěte jádro této hry. b) Pro m = 3, n = 2 spočtěte Shapleyho vektor. Body: 10, 10 2. Jízda Dvě dívky se baví tím, že se středem vozovky proti sobě rozjedou svými auty a která první uhne ztratí prestiž. Jedná se o bimaticovou hru s maticemi A = 0 −1 1 −10 B = 0 1 −1 −10 Strategiemi každého z hráčů jsou Uhne, Neuhne. a) Najděte všechny rovnovážné situace v čistých strategiích. b) Najděte všechny rovnovážné situace ve smíšených strategiích. c) Najděte všechny situace optimální podle Pareta (v čistých strategiích). d) Řešte tuto úlohu jako úlohu o dohodě. e) Řešte tuto úlohu ve vyhrožovacích strategiích. Body: 3, 4, 3, 5, 5 3.Mince Každý z dvojice hráčů schová do své pravé ruky 1 nebo 2 nebo 3 mince (všechny mince jsou stejného druhu). Poté ruce současně otevřou a pokud mají stejný počet mincí, všechny ukázané si bere druhý hráč. V opačném případě získává všechny první hráč. Najděte optimální strategie obou hráčů. 20 bodů L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 35 Teorie her, zadání zkoušek 2002/3 1. termín 1. U bimaticové hry může mít strategie prvního hráče následující vlastnosti : (O) býti opatrnou, (ND) býti nedominovanou, (SR) býti složkou nějaké rovnovážné situace. Které z osmi možných kombinací mohou nastat ? Pokud něco nemůže nastat, dokažte to. To co může nastat dokumentujte příklady. Pokuste se vystačit maximálně se dvěma hrami. Uvažujeme pouze čisté strategie ! 2. Dva kandidáti na prezidenta se před devátým volebním kolem předvádějí tím, že se středem vozovky proti sobě řítí svými služebními auty a kdo první uhne ztratí hlasy části svých voličů. Jedná se o bimaticovou hru s maticemi A = −10 2 −5 −1 B = −10 −5 2 −1 Strategiemi každého z hráčů jsou Neuhne, Uhne. a) Najděte všechny nedominované čisté strategie obou hráčů. b) Najděte všechny nedominované smíšené strategie obou hráčů. c) Najděte všechny opatrné čisté strategie obou hráčů. d) Najděte všechny opatrné smíšené strategie obou hráčů. e) Najděte všechny rovnovážné situace v čistých strategiích. f) Najděte všechny rovnovážné situace ve smíšených strategiích. g) Najděte všechny situace optimální podle Pareta (v čistých strategiích). h) Řešte tuto úlohu jako úlohu o dohodě. i) Řešte tuto úlohu ve vyhrožovacích strategiích. 3. Uvažujeme hru 3 hráčů ve tvaru charakteristické funkce v(∅) = 0, v({1}) = a, v({2}) = 1/6, v({3}) = 1/4, v({1, 2}) = 1/2, v({1, 3}) = 2/3, v({2, 3}) = 3/4, v({1, 2, 3}) = 1, a ∈ R . a) Pro která a se jedná o (superaditivní) hru ? b) Pro která a má tato hra neprázdné jádro ? c) Transformujte hru na (0,1)-redukovaný tvar. d) Spočtěte Shapleyeho vektor naší hry. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 36 e) Pro která a patří Shapleyeho vektor do jádra ? 2. termín 1. U maticové hry může mít strategie prvního hráče následující vlastnosti : (O) býti opatrnou, (ND) býti nedominovanou, (SR) býti složkou nějaké rovnovážné situace. Které z osmi možných kombinací mohou nastat ? Pokud něco nemůže nastat, dokažte to. To co může nastat dokumentujte příklady. Pokuste se vystačit maximálně se dvěma hrami. Uvažujeme pouze čisté strategie ! 2. Dva noví kandidáti na prezidenta se před desátým volebním kolem předvádějí tím, že se středem vozovky proti sobě řítí svými služebními auty a kdo první uhne ztratí hlasy části svých voličů. Jedná se o bimaticovou hru s maticemi A =   −10 3 2 −5 −1 −10 −4 −10 −1   B =   −10 −5 −4 3 −1 −10 2 −10 −1   Strategiemi každého z hráčů jsou Neuhne, Uhne doleva, Uhne doprava. a) Najděte všechny nedominované čisté strategie prvního hráče. b) Najděte všechny opatrné čisté strategie prvního hráče. c) Najděte nějakou opatrnou smíšenou strategii prvního hráče. d) Najděte všechny rovnovážné situace v čistých strategiích. e) Najděte nějakou další rovnovážnou situaci ve smíšených strategiích. f) Najděte všechny situace optimální podle Pareta (v čistých strategiích). g) Řešte tuto úlohu ve vyhrožovacích strategiích. 3. Uvažujeme hru 3 hráčů ve tvaru charakteristické funkce v(∅) = 0, v({1}) = 1/4, v({2}) = 1/6, v({3}) = 1/4, v({1, 2}) = a, v({1, 3}) = 2/3, v({2, 3}) = 3/4, v({1, 2, 3}) = 1, a ∈ R . a) Pro která a se jedná o (superaditivní) hru ? b) Pro která a má tato hra neprázdné jádro ? c) Transformujte hru na (0,1)-redukovaný tvar. d) Spočtěte Shapleyeho vektor naší hry. e) Pro která a patří Shapleyeho vektor do jádra ? Body: 20; 3,3,10,3,12,3,6; 8,8,8,8,8. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 37 Teorie her, zadání zkoušek 2003/4 1. termín 1. Dvojice prodejců získává jednotku daného zboží za p > 0 resp. q > 0. Stanoví-li si prodejní ceny x > 0 resp. y > 0, prodají y2 c x2 + y2 resp. x2 c x2 + y2 jednotek ( c > 0 je daná konstanta). a) Určete normální formu této hry. b) Spočtěte dolní hodnotu hry pro prvního hráče a jeho opatrné strategie. c) Určete nedominované strategie prvního hráče. d) Najděte všechny rovnovážné situace. 2. Řešte prosím maticovou hry s maticí A =   0 −1 2 1 0 −1 −2 1 0   . 3. Trojice akcionářů má 10, 20, resp. a > 0 kusů akcií. Vítězná koalice je ta, která má více jak polovinu ze všech akcií. Určete laskavě Shapleyho vektor. 2. termín 1. 1. hráč zvolí x ∈ [0, 1]. 2. hráč poté co zná x buď ‘souhlasí” (pak 1. hráč vyhrává x a 2. vyhrává 1 − x ) nebo zvolí y ∈ [0, x) (pak 1. vyhrává 1/2 − y/2 a 2. vyhrává y). a) Uveďte normální formu této hry. b) Spočtěte dolní hodnotu hry a všechny opatrné strategie prvního hráče. c) Najděte všechny situace optimální podle Pareta. d) Najděte všechny nedominované strategie prvního hráče. 2. Řešte usilovně maticovou hry s maticí L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 38 A = −1 4 0 1 5 1 3 2 . 3. Nechť n = 3, N = {1, 2, 3}, v : 2N → R, v(∅) = 0, v({1}) = 1, v({2}) = 2, v({3}) = 3, v({1, 2}) = 6, v({1, 3}) = 8, v({2, 3}) = p, v(N) = 12. a) Pro která p je uvedená hra superaditivní ? b) Pro která p má tato hra neprázdné jádro ? L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 39 Teorie her, zadání zkoušek 2004/5 1. termín 1. Dvojice prodejců získává jednotku daného zboží za p > 0 resp. q > 0. Stanoví-li si prodejní ceny x > 0 resp. y > 0, prodají yc x + y resp. xc x + y jednotek ( c > 0 je daná konstanta). a) Určete normální formu této hry. b) Spočtěte dolní hodnotu hry pro prvního hráče a jeho opatrné strategie. c) Určete nedominované strategie prvního hráče. d) Najděte všechny rovnovážné situace. 2. Řešte prosím maticovou hry s maticí A =   0 −1 3 1 0 −1 −3 1 0   . 3. Trojice akcionářů má 10, 20, resp. a > 0 kusů akcií. Vítězná koalice je ta, která má alespoň 2/3 všech akcií. Určete laskavě Shapleyho vektor. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 40 Teorie her, zadání zkoušek 2005/6 1. termín 1. Dvojice hráčů má vybrat kandidáta z množiny A = {a, b, c}. Oba (nezávisle) zadají pořadí kandidátů. Za první místo jsou 2 body a za druhé 1 bod. Má-li více kandidátů stejný počet bodů, dává se přednost tomu, kdo je dříve v abecedě. Nechť pro užitečnosti zvolení jednotlivých kandidátů platí u(a) > u(b) > u(c), v(a) < v(b) < v(c) . a) Uveďte tabulku, v níž jsou řádky indexovány strategiemi prvního hráče a sloupce strategiemi druhého hráče. Na pozici (i, j) je vybraný kandidát, použil-li první hráč strategii i a druhý strategii j. b) Je naše hra antagonistická ? Zdůvodněte. c) Najděte pro oba hráče všechny jejich (čisté) opatrné strategie. d) Najděte pro oba hráče všechny jejich (čisté) nedominované strategie. e) Najděte všechny rovnovážné situace v čistých strategiích. f) Mějme maticovou hru s maticí A typu m/n, m ≥ 2. Nechť m-tý řádek je dominován (m − 1)-tým, nechť A′ je matice A bez posledního řádku. Dokažte : je-li (x, y) (smíšená) rovnovážná situace hry s matici A′ , je ((x, 0), y) rovnovážná situace hry s matici A. g) Nechť u(a) = 3, u(b) = 2, u(c) = 1, v(a) = 1, v(b) = 3, v(c) = 4 . Opakovaným užitím f) a analogického tvrzení pro druhého hráče najděte nějakou další rovnovážnou situaci ve smíšených strategiích. 2. Nechť a, b > 0 a nechť bimaticová hra je určena maticemi A = a 0 0 1 , B = 1 0 0 b . a) Najděte (jediné) smíšené opatrné strategie obou hráčů. Zdůvodněte jednoznačnost. b) Kromě dvou rovnovážných situací v čistých strategiích existuje jediná další ve smíšených strategiích. Najděte ji a zdůvodněte, že více rovnovážných situací neexistuje. 3. Nechť n = 3, N = {1, 2, 3}, v : 2N → R, v(∅) = 0, v({1}) = a, v({2}) = b, v({3}) = c, v({1, 2}) = 2, v({1, 3}) = 3, v({2, 3}) = 4, v(N) = p. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 41 a) Pro která a, b, c, p je uvedená hra superaditivní ? b) Pro která a, b, c, p má tato hra neprázdné jádro ? 2. termín 1. Dělení koláče II. Každý z n ≥ 2 hráčů (nezávisle) určí xi ∈ [0, 1] (i ∈ {1, . . ., n}). Výhra i-tého je ui(x1, . . . , xn) = xi pro x1 + · · · + xn ≤ 1 0 jinak , i ∈ {1, . . ., n} . a) Pro každého z hráčů najděte všechny jeho opatrné strategie. Výsledek zdůvodněte. b) Je naše hra antagonistická ? Výsledek zdůvodněte. Kolokvium : c) Ukažte, že situace x, pro níž x1 + · · · + xn = 1, je rovnovážná. Zkouška : c) Najděte všechny rovnovážné situace. Výsledek zdůvodněte. d) Pro každého z hráčů najděte všechny jeho nedominované strategie. Výsledek zdůvod- něte. 2. Akcionáři. Trojice akcionářů má 10, 30, resp. p > 0 kusů akcií. Vítězná koalice je ta, která má více jak polovinu ze všech akcií. Určete laskavě Shapleyho vektor. 3. Maticová hra. Najděte nějakou dvojici (x, y) optimálních strategií pro maticovou hru s maticí A =   −2 4 2 1 −1 0 3 −3 −1   . Uvedením xA a Ay⊤ se přesvědčte o správnosti výpočtu. 3. termín 1. Dotace. i-tý z n ≥ 2 občanů ČR (nezávisle) určí pro rok 2007 dotaci vládní straně xi ∈ [0, ai], kde ai je jeho příjem v roce 2006, i ∈ {1, . . ., n}. Užitečnost kvality života i-tého v roce 2007 bude : suma vybraných peněz krát ai − xi . L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 42 a) Pro každého z hráčů najděte všechny jeho opatrné strategie. Výsledek zdůvodněte. b) Je naše hra pro n = 2 antagonistická ? Výsledek zdůvodněte. Kolokvium : c) Nechť a1 = · · · = an. Najděte nějakou rovnovážnou situaci x = (x1, . . . , xn) splňující x1 = · · · = xn. Možný návod : vzpomeňte si, kde má funkce x(1 − x) na [0, 1] maximum. 2. Piráti II. Posádka n ≥ 2 pirátů našla v jeskyni pustého ostrova obrovský poklad ve formě beden zlata. Každý může jít do jeskyně jen jednou a bednu musí nést dva piráti. To vede na hru v ve tvaru charakteristické funkce, kde v(S) = |S|/2 pro |S| sudé ..... jinak. Spočtěte, prosím, jádro naší hry. Pokud vám to nejde v plné obecnosti, učiňte tak laskavě alespoň pro n = 3 a n = 4. 3. Volby. V nedaleké spřátelené zemi se nedávno konaly parlamentní volby. Do sněmovny se dostaly strany A, B, . . ., F s následujícím počtem poslanců : 50, 31, 20, 20, 15, 14. Vítězná koalice je ta, která má nadpoloviční většinu poslanců. Spočtěte pozorně Shapleyho vektor strany A. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 43 Teorie her, zadání zkoušek 2006/7 1. termín 1. Poslanci si mají rozdělit sumu c na své měsíční platy. Všichni současně určí, kolik by kdo chtěl dostávat. Je-li součet požadavků realizovatelný, jejich přání se splní. V opačném případě se rovnoměrně rozdělí o sumu c/2. a) Najděte normální formu této hry. b) Najděte dolní hodnotu hry pro i-tého hráče a všechny jeho opatrné strategie. c) Najděte nějakou rovnovážnou situaci ( existuje i taková, že x1 = · · · = xn). d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Najděte všechny nedominované strategie i-tého hráče. 2. Každý z dvojice lvů se snaží získat kontrolu nad jistým územím. Každý má dvojici strategii : zbabělou a agresivní. Jedná se o bimaticovou hru s maticemi A = 3 1 4 0 , B = 3 4 1 0 . V bodech a) - d) pracujeme jen s čistými strategiemi. a) Pro prvního hráče najděte dolní a horní hodnotu hry a všechny jeho opatrné strategie. b) Pro prvního hráče najděte všechny jeho nedominované strategie. c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Řešte úlohu jako úlohu o dohodě. 3. Majitel firmy je hráč 0. Má n zaměstnanců označených 1,. . . , n. Nechť f : {0, 1, . . ., n} → R+ (= {a ∈ R | a ≥ 0}), f(0) = 0. Pro S ⊆ {0, 1, . . ., n} klademe v(S) = 0 pro 0 ∈ S f(|S| − 1) pro 0 ∈ S . a) Pro která f je hra superaditivní ? b) Nechť je splněna podmínka z a). Spočtěte jádro pro n = 2. Můžete psát f(1) = a, f(2) = b. Jen zkouška : c) Nechť funkce f je konkávní. Ukažte, že příslušnost vektoru k jádru lze vyjádřit n + 1 vztahy. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 44 2. termín 1. Dvojice hráčů hraje hru (X, Y, u, v), kde X = Y = [0, 1], u(x, y) = x(1 − x − y) a v(x, y) = y(1 − x − y) . a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. b) Najděte nějakou rovnovážnou situaci. Jen zkouška : c) Najděte všechny nedominované strategie prvního hráče. 2. Máme bimaticovou hru s hráči : N - nejslavnější fotbalový klub, M - méně slavný fotbalový klub, s čistými strategiemi pro každý z klubů : P - podplatit rozhodčího, U - řádně se připravit a usilovně hrát. Užitečnosti jednotlivých událostí pro nastávající utkaním jsou dány maticemi A = 2 2 0 1 , B = −1 0 2 1 . V bodech a) - d) pracujeme jen s čistými strategiemi. a) Pro prvního hráče najděte dolní a horní hodnotu hry a všechny jeho opatrné strategie. b) Pro prvního hráče najděte všechny jeho nedominované strategie. c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Řešte úlohu jako úlohu o dohodě. 3. Majitel firmy je hráč 0. Má n zaměstnanců označených 1,. . . , n. Nechť f : {0, 1, . . ., n} → R+ (= {a ∈ R | a ≥ 0}), 0 = f(0) ≤ . . . ≤ f(n). Pro S ⊆ {0, 1, . . ., n} klademe v(S) = 0 pro 0 ∈ S f(|S| − 1) pro 0 ∈ S . a) Pro n = 2 spočtěte Shapleyho vektor. Jen zkouška : b) Spočtěte Shapleyho vektor pro libovolné n. 3. termín 1. Dvojice hráčů hraje hru (X, Y, u, v), kde X = Y = [0, 1], u(x, y) = x(1 − xy) a v(x, y) = y(1 − xy) . a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. L. Polák, Univerzita Brno, pomocný text ke kurzu Teorie her 45 b) Najděte nějakou rovnovážnou situaci. c) Je naše hra antagonistická ? Zdůvodněte. 2. Najděte nějakou rovnovážnou situaci pravděpodobnostního rozšíření maticové hry s maticí : A =   1 0 2 0 0 2 0 2 1 0 1/2 1   . Můžete si pomoci postupným odstraňováním dominovaných strategií. 3. Nechť n = 3, N = {1, 2, 3}, v : 2N → R v(∅) = v({2}) = v({3}) = 0, v({1}) = a, v({1, 2}) = v({1, 3}) = 1, v({2, 3}) = b, v(N) = 2 . a) Kdy je to superaditivní hra ? b) Kdy má neprázdné jádro ? Teorie her - 2007/08 - 1. termín 1. Dotace II. i-tý z n ≥ 2 občanů ČR (nezávisle) určí pro rok 2008 dotaci vládní straně xi ∈ [0, ai], kde ai je jeho příjem v roce 2007, i ∈ {1, . . . , n}. Nechť c je konstanta meší než všechna a1, . . . , an. Užitečnost kvality života i-tého v roce 2007 bude : (c + suma vybraných peněz) · (ai − xi) . a) Pro každého z hráčů najděte všechny jeho opatrné strategie. Výsledek zdůvodněte. b) Je naše hra pro n = 2 antagonistická ? Výsledek zdůvodněte. c) Nechť a1 = · · · = an. Najděte nějakou rovnovážnou situaci x = (x1, . . . , xn) splňující x1 = · · · = xn. d) (jen zkouška) Najděte všechny nedominované strategie i-tého hráče. 2. Piráti III. Posádka n ≥ 2 pirátů našla v jeskyni pustého ostrova obrovský poklad ve formě beden zlata. Každý může jít do jeskyně jen jednou a bednu musí nést alespoň tři piráti. To vede na hru v ve tvaru charakteristické funkce, kde v(S) =    |S|/3 pro |S| dělitelné 3 ..... .... ..... .... Spočtěte, prosím, jádro naší hry a její Shapleyho vektor. Kolokvium : Pokud vám to nejde v plné obecnosti, učiňte tak laskavě alespoň pro n = 3 a n = 4. 3. Maticová hra. Řešte prosím maticovou hry s maticí A =   0 −1 3 1 0 −1 −3 1 0   . Teorie her - 2007/08 - 2. termín 1. Platy poslanců II. Poslanci si mají rozdělit sumu c > 0 na své měsíční platy. Všichni současně určí, kolik by kdo chtěl dostávat, nechť pro i-tého (i ∈ {1, . . ., n}) je to xi ≥ 0. Je-li součet požadavků realizovatelný, jejich přání se splní. V opačném případě se rovnoměrně rozdělí o sumu c2 x1+···+xn . a) Najděte dolní hodnotu hry pro i-tého hráče a všechny jeho opatrné strategie. b) Je naše hra pro n = 2 antagonistická ? c) Najděte nějakou rovnovážnou situaci (existuje i taková, že x1 = · · · = xn ). d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Najděte všechny nedominované strategie i-tého hráče. 2. Piráti IV. Posádka n = 3m, m ≥ 1, pirátů našla v jeskyni pustého ostrova obrovský poklad ve formě beden zlata. Než se však na ostrov dostali, prodělali spoustu bitev. Zůstalo jich m s oběma zdravýma rukama, m majících jen levou ruku v pořádku a m majících jen pravou ruku v pořádku. Každý může jít do jeskyně jen jednou a bednu musí nést alespoň jeden se zdravou levou rukou a alespoň jeden další se zdravou pravou rukou. Kolokvium : Spočtěte jádro a Shapleyho vektor pro m = 1. Zkouška : Spočtěte jádro a Shapleyho vektor pro m = 1 a pro m = 2. 3. Bimaticová hra. Je dána bimaticová hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najděte všechny opatrné smíšené strategie. b) Najděte všechny rovnovážné situace ve smíšených strategiích. Jen zkouška : c) Řešte hru jako úlohu o dohodě pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uveďte též, jak se dohoda realizuje. Teorie her - 2007/8 - 3. termín 1. Dvojice hráčů hraje hru (X, Y, u, v), kde X = Y = [0, 1], u(x, y) = x(1 − x + y) a v(x, y) = y(1 + x − y) . a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. b) Najděte nějakou rovnovážnou situaci. c) Je tato hra antagonistická ? Jen zkouška : d) Najděte všechny nedominované strategie prvního hráče. 2. Je dána bimaticová hra s maticemi A = 2 0 4 1 , B = 2 3 0 1 . V bodech a), b) pracujeme se smíšenými strategiemi. a) Pro prvního hráče najděte dolní a horní hodnotu hry a všechny jeho opatrné strategie. b) Pro prvního hráče najděte všechny jeho nedominované strategie. V bodech c), d) pracujeme jen s čistými strategiemi. c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Řešte úlohu jako úlohu o dohodě. 3. Uvažujme přiřazovací hru pro m=2. Nechť M = {C, D}, M′ = {P, Q}. Nechť b11 − a1 = p, b12 − a1 = q, b21 − a2 = r, b22 − a2 = s jsou kladná čísla splňující q, r < p, s. a) Spočtěte jádro. V případě neprázdnosti dostanete polovinu bodů již za uvedení vektoru z jádra. b) Pro prvního prodávajícího najděte jeho složku Shapleyho vektoru. Kolokvium : počítáme s konkrétními hodnotami p = 4, q = 1, r = 2, s = 3. Teorie her - 2008/9 - 1. termín 1. Uplácení. Obce 1, . . . , n dostávají na rok 2009 dotace 0 < a1 < · · · < an . i-tá obec dává kraji “úplatek” ve výši xi ∈ [0, ai], i = 1, . . . , n. Ta, která dala nejvíce dostává “mimořádnou” krajskou dotaci ve výši (x1 + · · · + xn)/2. Dalo-li více obcí stejnou sumu, dotaci získává ta z nich, která má nejmenší pořadové číslo. a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. b) Je naše hra pro n = 2 antagonistická ? c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Najděte všechny nedominované strategie prvního hráče. 2. Pravobotci a levobotci. Hráči: r z nich vlastní jen pravou botu, l z nich vlastní len levou botu. “Výhra” koalice je dána počtem párů bot, které mohou její hráči sestavit. Jedná se o hru ve tvaru charakteristické funkce, kde v : ... → ... je dáno vztahem ... Kolokvium : Spočtěte jádro pro r = 2, l = 3 a pro r = l = 3 a Shapleyho vektor pro r = 1, l = 3 a pro r = 2, l = 3. Zkouška : Spočtěte jádro pro libovolné r, l a Shapleyho vektor pro r = 1, l = 3 a pro r = 2, l = 3. 3. Bimaticová hra. Je dána bimaticová hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najděte všechny opatrné smíšené strategie prvního hráče. b) Najděte všechny rovnovážné situace ve smíšených strategiích. (Pro kolokvium stačí najít nějakou, která se nesestává z čistých.) Jen zkouška : c) Řešte hru jako úlohu o dohodě pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uveďte též, jak se dohoda realizuje. Teorie her - 2008/9 - 2. termín 1. Uplácení II. V Kocourkově se o post starosty ucházejí hráči 1, . . . , n. Občané jsou již tak otráveni politikou, že jdou volit pouze za úplatek ve výši 1. Kandidáti nevolí, voliči jsou tak čestní, že přijmou jen jeden úplatek a pak skutečně dají hlas příslušnému kandidátu. Strategií hráče je počet uplacených. Efekt postu starosty je 1000, voličů je dostatek, získá-li více kandidátů stejný počet hlasů, vyhrává ten s nejmenším pořadovým číslem. a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. b) Je naše hra pro n = 2 antagonistická ? c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Najděte všechny nedominované strategie prvního hráče. 2. Vláčky. Hráči: l lokomotiv, c vagónů. “Výhra” vlaku je dána počtem vagónů, pokud má alespoň jednu lokomotivu. Jedná se o hru ve tvaru charakteristické funkce, kde v : ... → ... je dáno vztahem ... Kolokvium : Spočtěte jádro a Shapleyho vektor pro l = 1, c = 3 a pro l = 2, c = 3. Zkouška : Spočtěte jádro pro libovolné l, c a Shapleyho vektor pro l = 1, c = 3 a pro l = 2, c = 3. 3. Maticová hra. Najděte nějakou rovnovážnou situaci maticové hry A =     1 1 0 1 2 0 3 3 3 0 3 1 0 1 2 3 0 0 0 2     . Jen zkouška: formulujte tvrzení umožňující vynechání dominovaných strategií. Teorie her - 2008/9 - 3. termín 1. Obálky. Hráči 1, . . . , n současně položí na stůl obálky s jimi zvolenými obnosy x1, . . . , xn. Poté se obálky otevřou a vše získá ten, kdo dal nejvíce. Dalo-li víče hráčů stejnou sumu, vyhrává ten z nich, kdo má nejmenší poředové číslo. a) Najděte dolní hodnotu hry pro prvního hráče a všechny jeho opatrné strategie. b) Je naše hra pro n = 2 antagonistická ? c) Najděte všechny rovnovážné situace. d) Najděte všechny situace optimální podle Pareta. Jen zkouška : e) Najděte všechny nedominované strategie prvního hráče. 2. Hasiči. U požáru se sejde partička dobrovolných hasičů. Z nich r má redukce k hydrantům, h má navzájem propojitelné díly hadice a s má koncové stříkačky. K sestavení funkční hadice je zapotřebí alespoň jedné redukce a jedné stříkačky, užitek je pak dán její délkou, tj. počtem použitých dílů. Jedná se o hru ve tvaru charakteristické funkce, kde v : ... → ... je dáno vztahem ... Kolokvium : Spočtěte jádro a Shapleyho vektor pro r = 1, h = 2, s = 1 a pro r = 1, h = 1, s = 2. Zkouška : Spočtěte jádro pro libovolné r, h, s a Shapleyho vektor pro r = 1, h = 2, s = 1 a pro r = 1, h = 1, s = 2. 3. Bimaticová hra. Najděte všechny rovnovážnou situace bimaticové hry, jejichž složky jsou smíšené strategie, které nejsou čisté. A = a b c d B = p q r s Hledáme x, y ∈ .................................. tak, aby x maximalizovalo funkci ............................................................. na intervalu .................................... a y maximalizovalo funkci ............................................................. na intervalu .................................... To nastane právě když .............................................................. ............................................................ Tedy hledané strategie jsou řešením ....................................................... Jen zkouška: zvolte matice tak, aby úloha měla jediné řešení, nekonečně mnoho řešení, neměla řešení. Teorie her - 2009/10 - 1. term´ın 1. Dotace II. i-t´y z n ≥ 2 obˇcan˚u ˇCR (nez´avisle) urˇc´ı pro rok 2008 dotaci vl´adn´ı stranˇe xi ∈ [0, ai], kde ai je jeho pˇr´ıjem v roce 2007, i ∈ {1, . . . , n}. Necht’ c je konstanta meˇs´ı neˇz vˇsechna a1, . . . , an. Uˇziteˇcnost kvality ˇzivota i-t´eho v roce 2007 bude : (c + suma vybran´ych penˇez) · (ai − xi) . a) Pro kaˇzd´eho z hr´aˇc˚u najdˇete vˇsechny jeho opatrn´e strategie. V´ysledek zd˚uvodnˇete. b) Je naˇse hra pro n = 2 antagonistick´a ? V´ysledek zd˚uvodnˇete. c) Necht’ a1 = · · · = an. Najdˇete nˇejakou rovnov´aˇznou situaci x = (x1, . . . , xn) splˇnuj´ıc´ı x1 = · · · = xn. d) (jen zkouˇska) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Volby V parlamentn´ıch volb´ach dostaly strany C, O, T, K, V po ˇradˇe 56,53,41,26 a 24 kˇresel. Koalice je v´ıtˇezn´a, m´a-li alespoˇn 101 poslanc˚u. Spoˇctˇete Shapleyho vektor. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najdˇete vˇsechny opatrn´e sm´ıˇsen´e strategie. b) Najdˇete vˇsechny rovnov´aˇzn´e situace v ˇcist´ych strategi´ıch a nˇejakou dalˇs´ı rovnov´aˇznou situaci ve sm´ıˇsen´ych strategi´ıch. Jen zkouˇska : c) ˇReˇste hru jako ´ulohu o dohodˇe pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uved’te t´eˇz, jak se dohoda realizuje. Teorie her - 2009/10 - 2. term´ın 1. Dvojice hr´aˇc˚u hraje hru (X, Y, u, v), kde X = Y = [0, 1], u(x, y) = x(1 − x + y) a v(x, y) = y(1 + x − y) . a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Najdˇete nˇejakou rovnov´aˇznou situaci. c) Je tato hra antagonistick´a ? Jen zkouˇska : d) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Je d´ana bimaticov´a hra s maticemi A = ( 2 0 4 1 ) , B = ( 2 3 0 1 ) . V bodech a), b) pracujeme se sm´ıˇsen´ymi strategiemi. a) Pro prvn´ıho hr´aˇce najdˇete doln´ı a horn´ı hodnotu hry a vˇsechny jeho opatrn´e strategie. b) Pro prvn´ıho hr´aˇce najdˇete vˇsechny jeho nedominovan´e strategie. V bodech c), d) pracujeme jen s ˇcist´ymi strategiemi. c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) ˇReˇste ´ulohu jako ´ulohu o dohodˇe. 3. Uvaˇzujme pˇriˇrazovac´ı hru pro m=2. Necht’ M = {C, D}, M = {P, Q}. Necht’ b11 − a1 = p, b12 − a1 = q, b21 − a2 = r, b22 − a2 = s jsou kladn´a ˇc´ısla splˇnuj´ıc´ı q, r < p, s. a) Spoˇctˇete j´adro. V pˇr´ıpadˇe nepr´azdnosti dostanete polovinu bod˚u jiˇz za uveden´ı nˇejak´eho vektoru z j´adra. b) Pro prvn´ıho prod´avaj´ıc´ıho najdˇete jeho sloˇzku Shapleyho vektoru. Kolokvium : poˇc´ıt´ame s konkr´etn´ımi hodnotami p = 4, q = 1, r = 2, s = 3. Teorie her - 2009/10 - 3. term´ın 1. Platy poslanc˚u II. Poslanci si maj´ı rozdˇelit sumu c > 0 na sv´e mˇes´ıˇcn´ı platy. Vˇsichni souˇcasnˇe urˇc´ı, kolik by kdo chtˇel dost´avat, necht’ pro i-t´eho (i ∈ {1, . . . , n}) je to xi ≥ 0. Je-li souˇcet poˇzadavk˚u realizovateln´y, jejich pˇr´an´ı se spln´ı. V opaˇcn´em pˇr´ıpadˇe se rovnomˇernˇe rozdˇel´ı o sumu c2 x1+···+xn . a) Najdˇete doln´ı hodnotu hry pro i-t´eho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete nˇejakou rovnov´aˇznou situaci (existuje i takov´a, ˇze x1 = · · · = xn ). d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati III. Pos´adka n ≥ 2 pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn tˇri pir´ati. Kaˇzd´y pir´at se m˚uˇze pod´ılet jen na nesen´ı jedn´e bedny. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) =    |S|/3 pro |S| dˇeliteln´e 3 ..... .... ..... .... Spoˇctˇete, pros´ım, j´adro naˇs´ı hry a jej´ı Shapleyho vektor. Kolokvium : Pokud v´am to nejde v pln´e obecnosti, uˇciˇnte tak laskavˇe alespoˇn pro n = 3 a n = 4. 3. Maticov´a hra. ˇReˇste pros´ım maticovou hry s matic´ı A =     0 0 −1 3 1 0 0 −1 −3 1 1 0 0 1 0 −1     . Teorie her - 2010/11 - 1. term´ın 1. Ob´alky. Hr´aˇci 1, . . . , n souˇcasnˇe poloˇz´ı na st˚ul ob´alky s jimi zvolen´ymi obnosy x1, . . . , xn. Pot´e se ob´alky otevˇrou a vˇse z´ısk´a ten, kdo dal nejv´ıce. Dalo-li v´ıce hr´aˇc˚u stejnou sumu, vyhr´av´a ten z nich, kdo m´a nejmenˇs´ı poˇradov´e ˇc´ıslo. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Maticov´a hra. ˇReˇste pros´ım maticovou hry s matic´ı A =     0 0 −1 3 1 0 0 −1 −3 1 1 0 0 1 0 −1     . 3. Pˇriˇrazovac´ı hra. Uvaˇzujme pˇriˇrazovac´ı hru pro m=2. Necht’ M = {C, D}, M = {P, Q}. Necht’ b11 − a1 = p, b12 − a1 = q, b21 − a2 = r, b22 − a2 = s jsou kladn´a ˇc´ısla splˇnuj´ıc´ı q, r < p, s. a) Spoˇctˇete j´adro. V pˇr´ıpadˇe nepr´azdnosti dostanete polovinu bod˚u jiˇz za uveden´ı vektoru z j´adra. b) Pro prvn´ıho prod´avaj´ıc´ıho najdˇete jeho sloˇzku Shapleyho vektoru. Teorie her - 2010/11 - 2. term´ın 1. Upl´acen´ı II. V Kocourkovˇe se o post starosty uch´azej´ı hr´aˇci 1, . . . , n. Obˇcan´e jsou jiˇz tak otr´aveni politikou, ˇze jdou volit pouze za ´uplatek ve v´yˇsi 1. Kandid´ati nevol´ı, voliˇci jsou tak ˇcestn´ı, ˇze pˇrijmou jen jeden ´uplatek a pak skuteˇcnˇe daj´ı hlas pˇr´ısluˇsn´emu kandid´atu. Strategi´ı hr´aˇce je poˇcet uplacen´ych. Efekt postu starosty je 1000, voliˇc˚u je dostatek, z´ısk´a-li v´ıce kandid´at˚u stejn´y poˇcet hlas˚u, vyhr´av´a ten s nejmenˇs´ım poˇradov´ym ˇc´ıslem. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Pir´ati IV. Pos´adka n = 3m, m ≥ 1, pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Neˇz se vˇsak na ostrov dostali, prodˇelali spoustu bitev. Z˚ustalo jich m s obˇema zdrav´yma rukama, m maj´ıc´ıch jen levou ruku v poˇr´adku a m maj´ıc´ıch jen pravou ruku v poˇr´adku. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn jeden se zdravou levou rukou a alespoˇn jeden dalˇs´ı se zdravou pravou rukou. Spoˇctˇete j´adro a Shapleyho vektor pro m = 1 a pro m = 2. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najdˇete vˇsechny opatrn´e sm´ıˇsen´e strategie prvn´ıho hr´aˇce. b) Najdˇete vˇsechny rovnov´aˇzn´e situace ve sm´ıˇsen´ych strategi´ıch. c) ˇReˇste hru jako ´ulohu o dohodˇe pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uved’te t´eˇz, jak se dohoda realizuje. Teorie her - 2010/11 - 3. term´ın 1. Dotace II. i-t´y z n ≥ 2 obˇcan˚u ˇCR (nez´avisle) urˇc´ı pro rok 2011 dotaci vl´adn´ı stranˇe xi ∈ [0, ai], kde ai je jeho pˇr´ıjem v roce 2010, i ∈ {1, . . . , n}. Necht’ c je konstanta meˇs´ı neˇz vˇsechna a1, . . . , an. Uˇziteˇcnost kvality ˇzivota i-t´eho v roce 2011 bude : (c + suma vybran´ych penˇez) · (ai − xi) . a) Pro kaˇzd´eho z hr´aˇc˚u najdˇete vˇsechny jeho opatrn´e strategie. V´ysledek zd˚uvodnˇete. b) Je naˇse hra pro n = 2 antagonistick´a ? V´ysledek zd˚uvodnˇete. c) Necht’ a1 = · · · = an. Najdˇete nˇejakou rovnov´aˇznou situaci x = (x1, . . . , xn) splˇnuj´ıc´ı x1 = · · · = xn. d) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati III. Pos´adka n ≥ 2 pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn tˇri pir´ati. Kaˇzd´y pir´at se m˚uˇze pod´ılet jen na nesen´ı jedn´e bedny. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) =    |S|/3 pro |S| dˇeliteln´e 3 ..... .... ..... .... Spoˇctˇete, pros´ım, j´adro naˇs´ı hry a jej´ı Shapleyho vektor. Pokud v´am to nejde v pln´e obecnosti, uˇciˇnte tak laskavˇe alespoˇn pro n = 3 a n = 4. 3. Bimaticov´a hra. Najdˇete vˇsechny rovnov´aˇznou situace bimaticov´e hry, jejichˇz sloˇzky jsou sm´ıˇsen´e strategie, kter´e nejsou ˇcist´e. A = a b c d B = p q r s Hled´ame x, y ∈ .................................. tak, aby x maximalizovalo funkci ............................................................. na intervalu .................................... a y maximalizovalo funkci ............................................................. na intervalu .................................... To nastane pr´avˇe kdyˇz .............................................................. ............................................................ Tedy hledan´e strategie jsou ˇreˇsen´ım ............................. ....................................................... Ukaˇzte, ˇze pro a > c, d > b, p > q, s > r m´a ´uloha jedin´e ˇreˇsen´ı. .......................... Teorie her - 2011/2 - 1. term´ın 1. Ob´alky. Hr´aˇci 1, . . . , n souˇcasnˇe poloˇz´ı na st˚ul ob´alky s jimi zvolen´ymi obnosy x1, . . . , xn ≥ 0. Pot´e se ob´alky otevˇrou a vˇse z´ısk´a ten, kdo dal nejv´ıce. Dalo-li v´ıce hr´aˇc˚u stejnou sumu, vyhr´av´a ten z nich, kdo m´a nejmenˇs´ı poˇradov´e ˇc´ıslo. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Maticov´a hra. ˇReˇste pros´ım maticovou hry s matic´ı A =     0 0 −1 3 1 0 0 −1 −3 1 1 0 0 1 0 −1     . 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najdˇete vˇsechny opatrn´e sm´ıˇsen´e strategie prvn´ıho hr´aˇce. b) Najdˇete vˇsechny rovnov´aˇzn´e situace ve sm´ıˇsen´ych strategi´ıch. c) ˇReˇste hru jako ´ulohu o dohodˇe pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uved’te t´eˇz, jak se dohoda realizuje. Teorie her - 2011/2 - 2. term´ın 1. Dotace II. i-t´y z n ≥ 2 obˇcan˚u ˇCR (nez´avisle) urˇc´ı pro rok 2012 dotaci vl´adn´ı stranˇe xi ∈ [0, ai], kde ai je jeho pˇr´ıjem v roce 2011, i ∈ {1, . . . , n}. Necht’ c je konstanta meˇs´ı neˇz vˇsechna a1, . . . , an. Uˇziteˇcnost kvality ˇzivota i-t´eho v roce 2012 bude : (c + suma vybran´ych penˇez) · (ai − xi) . a) Pro kaˇzd´eho z hr´aˇc˚u najdˇete vˇsechny jeho opatrn´e strategie. V´ysledek zd˚uvodnˇete. b) Je naˇse hra pro n = 2 antagonistick´a ? V´ysledek zd˚uvodnˇete. c) Necht’ a1 = · · · = an. Najdˇete nˇejakou rovnov´aˇznou situaci x = (x1, . . . , xn) splˇnuj´ıc´ı x1 = · · · = xn. d) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati IV. Pos´adka n = 3m, m ≥ 1, pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Neˇz se vˇsak na ostrov dostali, prodˇelali spoustu bitev. Z˚ustalo jich m s obˇema zdrav´yma rukama, m maj´ıc´ıch jen levou ruku v poˇr´adku a m maj´ıc´ıch jen pravou ruku v poˇr´adku. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn jeden se zdravou levou rukou a alespoˇn jeden dalˇs´ı se zdravou pravou rukou. Spoˇctˇete j´adro a Shapleyho vektor pro m = 1 a pro m = 2. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A = a b c d B = p q r s Sm´ıˇsen´e strategie 1. hr´aˇce repezentujeme ˇc´ıslem x ∈ [0, 1] ud´avaj´ıc´ım pst hran´ı 1. ˇr´adku. Podobnˇe pro 2. hr´aˇce. a) x = 1, y = 1 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. b) x = 1, y = 0 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. b) x = 1, y ∈ (0.1) je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. Takov´e y existuje pr´avˇe kdyˇz ............................................................. ............................................................. d) Necht’ a > c, d > b, p > q, s > r. najdˇete vˇsechny rovnov´aˇzn´e situace tvaru x ∈ (0.1), y ∈ (0.1). ............................................................. ............................................................. Teorie her - 2011/2 - 3. term´ın 1. Upl´acen´ı II. V Kocourkovˇe se o post starosty uch´azej´ı hr´aˇci 1, . . . , n. Obˇcan´e jsou jiˇz tak otr´aveni politikou, ˇze jdou volit pouze za ´uplatek ve v´yˇsi 1. Kandid´ati nevol´ı, voliˇci jsou tak ˇcestn´ı, ˇze pˇrijmou jen jeden ´uplatek a pak skuteˇcnˇe daj´ı hlas pˇr´ısluˇsn´emu kandid´atu. Strategi´ı hr´aˇce je poˇcet uplacen´ych. Efekt postu starosty je 1000, voliˇc˚u je dostatek, z´ısk´a-li v´ıce kandid´at˚u stejn´y poˇcet hlas˚u, vyhr´av´a ten s nejmenˇs´ım poˇradov´ym ˇc´ıslem. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Pir´ati III. Pos´adka n ≥ 2 pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn tˇri pir´ati. Kaˇzd´y pir´at se m˚uˇze pod´ılet jen na nesen´ı jedn´e bedny. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) =    |S|/3 pro |S| dˇeliteln´e 3 ..... .... ..... .... Spoˇctˇete, pros´ım, j´adro naˇs´ı hry a jej´ı Shapleyho vektor. Pokud v´am to nejde v pln´e obecnosti, uˇciˇnte tak laskavˇe alespoˇn pro n = 3 a n = 4. 3. Maticov´a hra. ˇReˇste usilovnˇe maticovou hry s matic´ı A = 5 1 3 2 −1 4 0 1 . Teorie her - 2012/3 - 1. term´ın 1. Hlasov´an´ı o d˚uvˇeˇre vl´adˇe. n poslanc˚u (= hr´aˇc˚u) je pro vysloven´ı d˚uvˇery vl´adˇe. Tyto hlasy nestaˇc´ı. Jist´y lobbista dok´aˇze zajistit ´uspˇeˇsn´e hlasov´an´ı o d˚uvˇeˇre za ´uplatu c > 0 (ˇc´ast pro sebe a ˇc´ast pro nˇekolik pˇrebˇehl´ık˚u). Setrv´an´ı vl´ady m´a pro i-t´eho (i = 1, . . . , n) efekt ai < c a i-t´y d´a pˇred hlasov´an´ım lobbistovi ob´alku s obnosem xi ∈ [0, ai] (i = 1, . . . , n). Pen´ıze se nevrac´ı a plat´ı a1 + · · · + an ≥ c. a) Pro kaˇzd´eho z hr´aˇc˚u najdˇete vˇsechny jeho opatrn´e strategie. V´ysledek zd˚uvodnˇete. b) Je naˇse hra pro n = 2 antagonistick´a ? V´ysledek zd˚uvodnˇete. c) Necht’ a1 = · · · = an. Najdˇete nˇejakou rovnov´aˇznou situaci x = (x1, . . . , xn) splˇnuj´ıc´ı x1 = · · · = xn. d) Najdˇete vˇsechny situace optim´aln´ı podla Pareta. e) (jen zkouˇska) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Volby V parlamentn´ıch volb´ach dostaly strany C, K, T, O, Z po ˇradˇe 28.3, 17.4, 16.5, 9.3 a 8.4 procent hlas˚u. Ostatn´ı strany doslaly m´enˇe neˇz 5 procent. 200 poslaneck´ych m´ıst se urˇc´ı rovnomˇernˇe. Koalice je v´ıtˇezn´a, m´a-li alespoˇn 101 poslanc˚u. Spoˇctˇete Shapleyho vektor. 3. Pir´ati V. Pos´adka m ≥ 2 mlad´ych pir´at˚u a n ≥ 2 star´ych pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn dva pir´ati. Mlad´y pir´at se m˚uˇze pod´ılet i na nesen´ı dvou beden, star´y se m˚uˇze pod´ılet na nesen´ı bedny jen jednou rukou. To vede na hru v ve tvaru charakteristick´e funkce. Spoˇctˇete, pros´ım, j´adro naˇs´ı hry. (Kolokvium jen pro n sud´e.) Teorie her - 2012/3 - 2. term´ın 1. Ostrava - 2. dˇejstv´ı. V posledn´ım hlasov´an´ı proˇsel n´avrh na odkup stadionu o jedin´y hlas. Opˇet se naˇsly “procedur´aln´ı nedostatky” a bude se hlasovat znovu. Ti, co hlasovali pro, jsou jiˇz opakovan´ym hlasov´an´ım znechuceni a nen´ı jist´e, ˇze budou opˇet pro. Proto si je jist´y lobbista pozval na chodbu, kde tito (nez´avisle) uv´adˇej´ı sumy x1 ≥ 0, . . . , xn ≥ 0, za nˇeˇz budou opˇet hlasovat pro. Na ´uplaty je k dispozici obnos a > 0. Je-li x1 + · · · + xn ≤ a, vyplat´ı se ´uplatky, jinak nic. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Pir´ati VI. Pos´adka pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Neˇz se vˇsak na ostrov dostali, prodˇelali spoustu bitev. Z˚ustalo jich m ≥ 1, kteˇr´ı vid´ı, a n ≥ 1 slep´ych. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou, pir´at m˚uˇze n´est jen jednu bednu, kaˇzdou bednu nesou dva pir´ati, z nichˇz alespoˇn jeden vid´ı. To vede na hru v ve tvaru charakteristick´e funkce. Uved’te ji a spoˇctˇete j´adro. 3. Maticov´a hra. ˇReˇste maticovou hry s matic´ı A =     6 0 2 5 4 1 3 2     . Teorie her - 20012/13 - 3. term´ın 1. Platy poslanc˚u II. Poslanci si maj´ı rozdˇelit sumu c > 0 na sv´e mˇes´ıˇcn´ı platy. Vˇsichni souˇcasnˇe urˇc´ı, kolik by kdo chtˇel dost´avat, necht’ pro i-t´eho (i ∈ {1, . . . , n}) je to xi ≥ 0. Je-li souˇcet poˇzadavk˚u realizovateln´y, jejich pˇr´an´ı se spln´ı. V opaˇcn´em pˇr´ıpadˇe se rovnomˇernˇe rozdˇel´ı o sumu c2 x1+···+xn . a) Najdˇete doln´ı hodnotu hry pro i-t´eho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete nˇejakou rovnov´aˇznou situaci (existuje i takov´a, ˇze x1 = · · · = xn ). d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati III. Pos´adka n ≥ 2 pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn tˇri pir´ati. Kaˇzd´y pir´at se m˚uˇze pod´ılet jen na nesen´ı jedn´e bedny. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) =    |S|/3 pro |S| dˇeliteln´e 3 ..... .... ..... .... Spoˇctˇete, pros´ım, j´adro naˇs´ı hry. 3. Maticov´a hra. ˇReˇste pros´ım maticovou hry s matic´ı A =     0 0 −1 3 1 0 0 −1 −3 1 1 0 0 1 0 −1     . Teorie her - 2013/4 - 1. term´ın 1. Dotace II. i-t´y z n ≥ 2 obˇcan˚u ˇCR (nez´avisle) urˇc´ı pro rok 2012 dotaci vl´adn´ı stranˇe xi ∈ [0, ai], kde ai je jeho pˇr´ıjem v roce 2011, i ∈ {1, . . . , n}. Necht’ c je konstanta meˇs´ı neˇz vˇsechna a1, . . . , an. Uˇziteˇcnost kvality ˇzivota i-t´eho v roce 2012 bude : (c + suma vybran´ych penˇez) · (ai − xi) . a) Pro kaˇzd´eho z hr´aˇc˚u najdˇete vˇsechny jeho opatrn´e strategie. V´ysledek zd˚uvodnˇete. b) Je naˇse hra pro n = 2 antagonistick´a ? V´ysledek zd˚uvodnˇete. c) Necht’ a1 = · · · = an. Najdˇete nˇejakou rovnov´aˇznou situaci x = (x1, . . . , xn) splˇnuj´ıc´ı x1 = · · · = xn. d) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati IV. Pos´adka n = 3m, m ≥ 1, pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Neˇz se vˇsak na ostrov dostali, prodˇelali spoustu bitev. Z˚ustalo jich m s obˇema zdrav´yma rukama, m maj´ıc´ıch jen levou ruku v poˇr´adku a m maj´ıc´ıch jen pravou ruku v poˇr´adku. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est alespoˇn jeden se zdravou levou rukou a alespoˇn jeden dalˇs´ı se zdravou pravou rukou. Spoˇctˇete j´adro a Shapleyho vektor pro m = 1 a pro m = 2. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A = ( a b c d ) B = ( p q r s ) Sm´ıˇsen´e strategie 1. hr´aˇce repezentujeme ˇc´ıslem x ∈ [0, 1] ud´avaj´ıc´ım pst hran´ı 1. ˇr´adku. Podobnˇe pro 2. hr´aˇce. a) x = 1, y = 1 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. b) x = 1, y = 0 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. b) x = 1, y ∈ (0.1) je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. Takov´e y existuje pr´avˇe kdyˇz ............................................................. ............................................................. d) Necht’ a > c, d > b, p > q, s > r. najdˇete vˇsechny rovnov´aˇzn´e situace tvaru x ∈ (0.1), y ∈ (0.1). ............................................................. ............................................................. Teorie her - 2013/4 - 2. term´ın 1. Ob´alky. Hr´aˇci 1, . . . , n souˇcasnˇe poloˇz´ı na st˚ul ob´alky s jimi zvolen´ymi obnosy x1, . . . , xn ≥ 0. Pot´e se ob´alky otevˇrou a vˇse z´ısk´a ten, kdo dal nejv´ıce. Dalo-li v´ıce hr´aˇc˚u stejnou sumu, vyhr´av´a ten z nich, kdo m´a nejmenˇs´ı poˇradov´e ˇc´ıslo. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Maticov´a hra. ˇReˇste pros´ım maticovou hry s matic´ı A =     0 0 −1 3 1 0 0 −1 −3 1 1 0 0 1 0 −1     . 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najdˇete vˇsechny opatrn´e sm´ıˇsen´e strategie prvn´ıho hr´aˇce. b) Najdˇete vˇsechny rovnov´aˇzn´e situace ve sm´ıˇsen´ych strategi´ıch. c) ˇReˇste hru jako ´ulohu o dohodˇe pro a = 4, b = 2, c = 1, p = 1, q = 3, r = 6. Uved’te t´eˇz, jak se dohoda realizuje. Teorie her - 2013/4 - 3. term´ın 1. Upl´acen´ı II. V Kocourkovˇe se o post starosty uch´azej´ı hr´aˇci 1, . . . , n. Obˇcan´e jsou jiˇz tak otr´aveni politikou, ˇze jdou volit pouze za ´uplatek ve v´yˇsi 1. Kandid´ati nevol´ı, voliˇci jsou tak ˇcestn´ı, ˇze pˇrijmou jen jeden ´uplatek a pak skuteˇcnˇe daj´ı hlas pˇr´ısluˇsn´emu kandid´atu. Strategi´ı hr´aˇce je poˇcet uplacen´ych. Efekt postu starosty je 1000, voliˇc˚u je dostatek, z´ısk´a-li v´ıce kandid´at˚u stejn´y poˇcet hlas˚u, vyhr´av´a ten s nejmenˇs´ım poˇradov´ym ˇc´ıslem. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Pir´ati II. Pos´adka n ≥ 2 pir´at`u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve form`ı beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou a bednu mus´ı n´est dva pir´ati. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) = { |S|/2 pro |S| sud´e ..... jinak. Spoˇctˇete, pros´ım, j´adro naˇs´ı hry. Pokud v´am to nejde v pln´e obecnosti, uˇciˇnte tak laskavˇe alespoˇn pro n = 3 a n = 4. 3. Hra ve tvaru charakteristick´e funkce. Necht’ n = 3, N = {1, 2, 3}, v : 2N → R, v(∅) = 0, v({1}) = a, v({2}) = b, v({3}) = c, v({1, 2}) = 2, v({1, 3}) = 3, v({2, 3}) = 4, v(N) = p. a) Pro kter´a a, b, c, p je uveden´a hra superaditivn´ı ? b) Pro kter´a a, b, c, p m´a tato hra nepr´azdn´e j´adro ? Teorie her - 2014/5 - 1. term´ın 1. Upl´acen´ı. Obce 1, . . . , n dost´avaj´ı na rok 2015 dotace 0 < a1 < · · · < an . i-t´a obec d´av´a kraji “´uplatek” ve v´yˇsi xi ∈ [0, ai], i = 1, . . . , n. Ta, kter´a dala nejv´ıce dost´av´a “mimoˇr´adnou” krajskou dotaci ve v´yˇsi (x1 + · · · + xn)/2. Dalo-li v´ıce obc´ı stejnou sumu, dotaci z´ısk´av´a ta z nich, kter´a m´a nejmenˇs´ı poˇradov´e ˇc´ıslo. a) Najdˇete doln´ı hodnotu hry pro prvn´ıho hr´aˇce a vˇsechny jeho opatrn´e strategie. b) Je naˇse hra pro n = 2 antagonistick´a ? c) Najdˇete vˇsechny rovnov´aˇzn´e situace. d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie prvn´ıho hr´aˇce. 2. Pir´ati VI. Pos´adka pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Neˇz se vˇsak na ostrov dostali, prodˇelali spoustu bitev. Z˚ustalo jich m ≥ 1, kteˇr´ı vid´ı, a n ≥ 1 slep´ych. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou, pir´at m˚uˇze n´est jen jednu bednu, kaˇzdou bednu nesou dva pir´ati, z nichˇz alespoˇn jeden vid´ı. To vede na hru v ve tvaru charakteristick´e funkce. Uved’te ji a spoˇctˇete j´adro. Kolokvium: ˇreˇste jen pˇr´ıpad m ≥ n. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A = ( a b c d ) B = ( p q r s ) Sm´ıˇsen´e strategie 1. hr´aˇce repezentujeme ˇc´ıslem x ∈ [0, 1] ud´avaj´ıc´ım pst hran´ı 1. ˇr´adku. Podobnˇe pro 2. hr´aˇce. a) x = 1, y = 1 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. b) x = 1, y = 0 je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. c) (Jen zkouˇska.) Neexistuje rovnov´aˇzn´a v ˇcist´ych stategi´ıch, pr´avˇe kdyˇz bud’ ..................................................... nebo ......................................................... d) x = 1, y ∈ (0, 1) je rovnov´aˇzn´a, pr´avˇe kdyˇz ............................................................. ............................................................. e) (Jen zkouˇska.) Existuje-li takov´e y, m´a hra rovnov´aˇznou situaci i v ˇcist´ych strategi´ıch. Dokaˇzte. ............................................................. ............................................................. f) Necht’ a < c, d < b, p > q, s > r. Najdˇete vˇsechny rovnov´aˇzn´e situace tvaru x ∈ (0, 1), y ∈ (0, 1). ............................................................. ............................................................. Teorie her - 2014/5 - 2. term´ın 1. Platy poslanc˚u. n poslanc˚u si m´a rozdˇelit sumu c na sv´e mˇes´ıˇcn´ı platy. Vˇsichni souˇcasnˇe urˇc´ı, kolik by kdo chtˇel dost´avat. Je-li souˇcet poˇzadavk˚u realizovateln´y, jejich pˇr´an´ı se spln´ı. V opaˇcn´em pˇr´ıpadˇe se rovnomˇernˇe rozdˇel´ı o sumu c/2. a) Najdˇete norm´aln´ı formu t´eto hry. b) Najdˇete doln´ı hodnotu hry pro i-t´eho hr´aˇce a vˇsechny jeho opatrn´e strategie. c) Najdˇete nˇejakou rovnov´aˇznou situaci ( existuje i takov´a, ˇze x1 = · · · = xn). d) Najdˇete vˇsechny situace optim´aln´ı podle Pareta. Jen zkouˇska : e) Najdˇete vˇsechny nedominovan´e strategie i-t´eho hr´aˇce. 2. Pir´ati II. Pos´adka n ≥ 2 pir´at˚u naˇsla v jeskyni pust´eho ostrova obrovsk´y poklad ve formˇe beden zlata. Kaˇzd´y m˚uˇze j´ıt do jeskynˇe jen jednou, m˚uˇze se pod´ılet jen na nesen´ı jedin´e bedny a bednu mus´ı n´est dva pir´ati. To vede na hru v ve tvaru charakteristick´e funkce, kde v(S) = { |S|/2 pro |S| sud´e ..... jinak. Spoˇctˇete, pros´ım, j´adro naˇs´ı hry. Kolokvium: staˇc´ı pro n = 3 a n = 4. 3. Bimaticov´a hra. Je d´ana bimaticov´a hra s maticemi A =   a 0 0 0 b 0 0 0 c   , B =   p 0 0 0 q 0 0 0 r   , kde a, b, c, p, q, r > 0. a) Najdˇete vˇsechny opatrn´e sm´ıˇsen´e strategie prvn´ıho hr´aˇce. b) Najdˇete vˇsechny rovnov´aˇzn´e situace ve sm´ıˇsen´ych strategi´ıch. Kolokvium : Nemus´ıte dokazovat, ˇze m´ate opravdu vˇsechny.