AdamátorZápiskyHlášky

Teorie her

Webová stránka předmětu

Známka je za řešení domácích úloh. Budou tři série, z každé máme vyřešit alespoň jednu úlohu, za čtyři úlohy celkem je A.

Část o kombinatorické teorii her přednáší Mgr. Jan Volec, Ph.D. Část o klasické teorii her přednáší Mgr. Jan Hladký, Ph.D.

  1. Kombinatorická teorie her
    1. Pojmy
      1. Hex
        1. Piškvorky
          1. Sčítání her
            1. Nim
            2. Klasická teorie her
              1. Odbočka do algebraické topologie

              Kombinatorická teorie her

              Hra sirky Na stole leží n sirek. Střídají se dva hráči. Každý může ve svém tahu odebrat jednu, dvě, nebo tři sirky. Vyhraje ten, kdo odebere poslední sirku.
              Věta Je-li n=4k, potom vyhraje hráč, který nezačíná.
              Důkaz Indukcí. Odebere-li první hráč j sirek, může jich druhý hráč odebrat 4−j, čímž na stole zbyde 4(k−1) sirek.
              Důsledek Pro počet sirek nedělitelný 4 vyhraje začínající hráč.
              Hra vlajka/Chop Mějme vlajku ve tvaru mřížky s m sloupci a n řádky. Levý dolní čtvereček je připevněný ke stožáru. Hráč na tahu může ustřihnout libovolný počet řádků nebo sloupců. Vyhraje ten, kdo vlajku zredukuje na jediný čtvereček.
              Věta Je-li m=n, vyhraje hráč, který nezačíná.
              Důkaz Indukcí. Ustřihne-li první hrač několik sloupců, resp. řádků, druhý ustřihne stejný počet řádků, resp. sloupců. Tím vznikne opět pozice, kde je stejný počet sloupců a řádků.
              Důsledek Pro m≠n vyhraje začínající hráč.
              Hra čokoláda/Chomp Máme tabulku čokolády s m sloupci a n řádky. Čtvereček vlevo dole je otrávený. Hráč na tahu ukáže na libovolný čtvereček a sní ho společně se všemi, co jsou od něj napravo a/nebo nahoře. Vyhraje překvapivě ten, kdo nesní otrávený čtvereček.

              U této hry pro obecný tvar čokolády není známá obecná výherní strategie. Ale pro obdélníkovou čokoládu máme větu:

              Věta Pro obdélníkovou cokoládu s více než jedním čtverečkem vyhraje první hráč.
              Důkaz Předpokládejme pro spor, že pro nějaké m,n existuje výherní strategie pro druhého hráče. Potom ale první hráč může provést tah, který by druhý hráč podle výherní strategie měl provést, kdyby první hráč ukousnul pravý horní čtvereček. Tím první hráč vyhraje, což je spor.
              Poznámka Technika použitá v tomto důkazu se nazývá kradení strategie.
              Hra piškvorky Hrajme piškvorky na n×n mřížce (n2-škvorky). Vyhraje ten, kdo zaplní celý řádek, sloupec nebo diagonálu.
              Věta První hráč má neprohrávající strategii.
              Důkaz Předpokládejme pro spor, že existuje výherní strategie pro druhého hráče. Potom jako první hráč můžeme prostě zahrát libovolný tah a následně předstírat, že jsme druhý hráč. Pokud nás výherní strategie přinutí hrát na „mrtvé“ políčko, místo toho zahrajeme na nějaké jiné, které bude odteď „mrtvé“.
              Hra Hex Máme šestiúhelníkovou mřížku ve tvaru kosočtverce, kam hráčí umísťují svoje kameny. Vyhraje ten, kdo propojí dvě protější strany (pro každého hráče jiné).
              Věta První hráč má neprohrávající strategii.
              Důkaz Stejný jako u piškvorek.

              Pojmy

              Definice Normální hra je hra, kde prohrává hráč, který nemůže táhnout.
              Definice Kombinatorická hra s úplnou informací pro dva hráče je hra pro dva hráče 𝖫,𝖱 (Lízu a Richarda) charakterizovaná:
              • konečnou množinou pozic/stavů 𝒮,
              • funkcí, která každému stavu s∈𝒮 a hráči h∈{𝖫,𝖱} přiřadí množinu možných tahů f(s,h)⊂𝒮.
              • množinou koncových stavů 𝒯,
              • funkcí, která každému koncovému stavu t∈𝒯 přiřadí, kdo vyhrál: g(t)∈{+−,−+,𝟢𝟢}.
              Definice Herní strom pro dva hráče je zakořeněný strom, určený hrou pro dva hřáče, počáteční pozicí a začínajícím hráčem. Počáteční pozice je kořen. Z pozice s vedou hrany do všech pozic f(s,h), kde h je hráč na řadě (obvykle se střídají).
              Poznámka Budeme uvažovat jen takové hry, kde herní strom má konečnou velikost.
              Definice Strategie pro hráče h je funkce Sh, která pro každý vrchol v herním stromě, kde je h na tahu, vybere jednoho potomka.
              Poznámka Výsledek pro daný herní strom je jednoznačně určen dvojicí strategií S𝖫,S𝖱.
              Definice Strategie S𝖱 (bez újmy na obecnosti pro Richarda) je vyhrávající, pokud pro každou strategii S𝖫 pro Lízu je výsledek −+.
              Definice Herní strom je výherní (W), pokud existuje vyhrávající strategie pro začínajícího hráče.
              Definice Herní strom je proherní (L), pokud existuje vyhrávající strategie pro nezačínajícího hráče.
              Definice Herní strom je remízový (D), pokud existuje neprohrávající strategie pro oba hráče.
              Definice Hloubka herního stromu je délka nejdelší možné cesty z počátečního do koncového stavu.
              Věta Zermelova Každý herní strom pro dva hráče je právě jednoho z typů W, L, D.
              Důkaz Indukcí podle hloubky stromu. Je-li hloubka 0, máme jen jeden uzel, takže je jednoznačně určeno, jak hra dopadne. V indukčním kroku mějme bez újmy na obecnosti herní strom, kde začíná Richard.
              • Pokud alespoň jedem podstrom je proherní, potom původní strom je výherní.
              • Pokud každý podstrom je výherní, potom původní strom je proherní.
              • V jiném případě je původní strom remízový.

              Hex

              Věta Nashova V každé vyplněné mřížce Hexu vyhraje právě jeden hráč.
              Důkaz Představme si pro jednoduchost, že stěny, které má každý hráč propojit, obarvíme barvou tohoto hráče. Začneme v levém dolním rohu, kde vlevo je modrá a dole červená, a budeme postupně chodit po hranách tak, abychom vždy měli nalevo modrou barvu a napravo červenou barvu. Jelikož každý vrchol je stupně 3, vždy máme jednoznačně určeno, kam jít, a taky není těžké dokázat, že se nezacyklíme. Dorazíme až do nějakého jiného rohu, čímž jsme propojili nějaké stěny.
              Poznámka Dá se také dokázat pomocí Brouwerovy věty o pevném bodě.
              Důsledek První hráč má v Hexu výherní strategii.

              Piškvorky

              Definice Nechť a,d∈ℕ. Potom d-rozměrná hyperkrychle velikosti a je množina [a]d≕Ad.
              Definice Dále budeme značit A∗≔A∪{∗}, kde ∗ je žolík. Vzor je slovo τ∈A∗d∖Ad. Kombinatorická přímka Lτ je množina bodů hyperkrychle, kde za žolíky postupně dosazujeme čísla 1,…,a (za všechny žolíky stejné číslo).
              Příklad Máme-li klasické 3×3 piškvorky, tedy s a=3 a d=2, potom 1∗ je první sloupec, ∗2 je druhý řádek a ∗∗ je hlavní diagonála. Všimněme si, že antidiagonála se nedá vyjádřit jako kombinatorická přímka.
              Definice Obarvení krychle pomocí r barev je zobrazení χ:Ad→[r]. Přímka L je monochromatická, pokud pro všechny x,y∈L je χ(x)=χ(y).
              Věta Hales-Jewett Pro všechna r,a∈ℕ existuje D=HJ(r,a)∈ℕ takové, že pro všechna obarvení χ:[a]D→[r] existuje monochromatická přímka.
              Důsledek Při hraní piškvorek v dostatečném počtu dimenzí existuje výherní strategie pro prvního hráče.
              Důkaz Shelah, 1988 Indukcí podle a při pevném r. Pro a=1 triviální (stačí D=1). Pro indukční krok použijeme následující pomocné tvrzení.
              Definice Body x,y∈Ad jsou S-sousední, pokud se liší v jen jedné složce, přičemž jeden z nich tam má a−1 a druhý a.
              Lemma Nechť r∈ℕ,a≥2 a d≔HJ(r,a−1). Potom existuje D∈ℕ takové, že pro každé obarvení AD→[r] existují vzory ν1,…,νd s ∑i=1d|νi| takové, že pro libovolné S-sousední body x,y∈Ad platí
              χ(ν1(x1),…,νd(xd))=χ(ν1(y1),…,νd(yd)).
              Poznámka Vzory ν1,…,νd určují nějakou d-rozměrnou podkrychli/podrovnoběžnostěn.
              Důkaz Budeme iterativně konstruovat νd,…,ν1. νi bude mít délku Ni≔rad+Mi, kde Mi≔∑k=1i−1Nk. Pro dané c=0,…,d−1 uvažme funkce f0,…,fNd−c:AMd−c+c−1→[r] definované jako
              ft(x)≔χ(x1,…,xMd−c,a−1,…,a−1⏟t×,a,…,a⏟(Nd−c−t)×,νd−c+1(x−c),…,νd(x−1))
              (kde používáme „pythonovské značení“ pro indexování odzadu). Podle 🐦holubníkového principu🐦 musí nějaké dvě z těchto funkcí být identické. Označme je fα,fβ,α<β. Potom definujme
              νd−c≔a−1,…,a−1⏟α×,∗,…,∗⏟(β−α)×,a,…,a⏟(Nd−c−β)×.
              Nyní vezměme D, ν1,…,νd z lemmatu. Definujme obarvení χ¯:Ad→[r],
              χ¯(x1,…,xd)≔χ(ν1(x1),…,νd(xd)).
              Snadno si rozmyslíme, že monochromatická přímka pro χ¯ je monochromatická i pro χ. Teď na podkrychli [a−1]d použijeme indukční předpoklad. Existuje tedy χ¯-monochromatická přímka Lτ={τ(1),…,τ(a−1)}. Zároveň z S-sousednosti plyne χ¯(τ(a−1))=χ¯(τ(a)). (Pokud τ obsahuje více žolíků, nahrazujeme je postupně). Z toho již plyne tvrzení věty.

              Sčítání her

              Hra koláč Máme koláč s m řádky a n sloupci. Líza v každém tahu rozřízne koláč svisle, Richard vodorovně. Je-li již víc kusů koláče, rozříznou jen jeden z nich. Prohraje ten, kdo nemůže táhnout.
              Věta Každá pozice v normální hře je jednoho z následujících typů:
              ℒ
              vyhrává Líza, ať začne kdokoliv;
              ℛ
              vyhrává Richard, ať začne kdokoliv;
              𝒩
              vyhrává ten, kdo začne (následující hráč);
              𝒫
              vyhrává ten, kdo nezačne (přechozí hráč).
              Důkaz Přímý důsledek Zermelovy věty.
              Definice Nechť γ je pozice ve hře, α1,…,αn jsou pozice, kam ji může přesunout Líza, a β1,…,βm jsou pozice, kam ji může přesunout Richard. Potom značíme
              γ={α1,…,αn|β1,…,βm}.
              Věta Pozice γ={α1,…,αn|β1,…,βm} je
              • typu ℒ, právě když nějaká αi je typu ℒ|𝒫 a všechny βj jsou typu ℒ|𝒩,
              • typu ℛ, právě když všechny αi jsou typu ℛ|𝒩 a nějaká βj je typu ℛ|𝒫,
              • typu 𝒩, právě když nějaká αi je typu ℒ|𝒫 a nějaká βj je typu ℛ|𝒫,
              • typu 𝒫, právě když všechny αi jsou typu ℛ|𝒩 a všechny βj jsou typu ℒ|𝒩.
              Důkaz Triviální.
              Definice Nechť γ1,γ2 jsou pozice v nějakých hrách. Potom jejich součet je pozice γ1+γ2 odpovídající hře, kde si hráč na tahu vybere jednu z původních her a provede v ní tah.
              Příklad Označíme-li γm,n pozici ve hře řezání koláče obsahující jeden koláč s m řádky a n sloupci, potom
              γm,n={γ1,n+γm−1,n,…,γm−1,n+γ1,n|γm,1+γm,n−1,…,γm,n−1+γm,1}.
              Hra Domineering Máme mřížku, do které Líza pokládá svislé dílky domina a Richard vodorovné dílky domina . Prohraje ten, kdo nemůže táhnout.
              Věta Typ součtu dvou pozic jde určit z jejich typů podle následující tabulky:
              +𝓛𝓡𝓝𝓟
              𝓛ℒ?ℒ|𝒩ℒ
              𝓡?ℛℛ|𝒩ℛ
              𝓝ℒ|𝒩ℛ|𝒩?𝒩
              𝓟ℒℛ𝒩𝒫
              Přitom varianty označené otazníkem mohou dopadnout jakkoli.
              Důkaz otazníků To, že u pozic označených otazníkem je možné všechno, demonstrujeme na hře Domineering.
              𝓝+𝓝𝓛+𝓡
              𝓛 + +
              𝓡 + +
              𝓝 + +
              𝓟 + +
              Definice Pozice α,β jsou ekvivalentní, pokud pro všechny pozice γ jsou α+γ,β+γ stejného typu.
              Věta Pokud β je typu 𝒫, potom pro všechny α je α+β≡α.
              Důkaz Pro všechny γ je α+γ stejného typu jako (α+γ)+β=(α+β)+γ.
              Věta Pokud α,β jsou typu 𝒫, potom α≡β.
              Důkaz Plyne přímo z definice a tabulky.
              Věta Pokud α+β a α′+β jsou typu 𝒫, potom α≡α′.
              Důkaz
              α≡α+(α′+β)=(α+β)+α′≡α′.
              Definice Hra je nestranná, pokud pro všechny pozice γ={α1,…,αn|β1,…,βm} platí {α1,…,αn}={β1,…,βm}.
              Věta Každá pozice v nestranné hře je typu 𝒩 nebo 𝒫.
              Důkaz Kradení strategie.

              Nim

              Hra Nim Na stole leží k hromádek s lentilkami, kde i-tá hromádka obsahuje ni lentilek. Hráč ve svém tahu může sníst libovolný počet lentilek z jedné hromádky. Vyhraje ten, kdo sní poslední lentilku.
              Věta Pozice (n1,…,nk) v Nimu je typu 𝒫, právě když ⨁i=1kni=0, kde ⊕︎ značí binární XOR.
              Důkaz Pozici splňující rovnost nazveme vyvážená. Je zřejmé, že jakýkoli tah z vyvážené pozice vede do nevyvážené pozice. Naopak je-li pozice nevyvážená, můžeme vzít jakoukoli pozici obsahující jedničku na stejné pozici, kde má ⨁i=1kni nejvýznamnější jedničku, a sežráním z této hromádky dosáhnout vyvážené pozice.
              Definice Pro n∈ℕ označíme ∗n jednohromádkový Nim s n kameny.
              Poznámka Pro m,n∈ℕ platí ∗m+∗n=∗(m⊕︎n).
              Věta Pro každou pozici α v Nimu existuje n∈ℕ takové, že α≡∗n.
              Důkaz Nechť velikosti hromádek v α jsou n1,…,nk. Označme n≔⨁i=1kni. Jelikož α+∗n je typu 𝒫 a ∗n+∗n je typu 𝒫, musí být α≡∗n.
              Lemma MEX princip Nechť β={α1,…,αn|α1,…,αn} je pozice v nestranné hře a pro všechna i∈[n] existuje takové ai∈ℕ, že αi≡∗ai. Potom existuje b∈ℕ takové, že β≡∗b.
              Důkaz Vezměme
              b≔min(ℕ∖{a1,…,an}).
              Dokážeme, že β+∗b je typu 𝒫, z čehož už plyne tvrzení. A to tak, že najdeme výherní strategii pro druhého hráče.
              • Zahraje-li první hráč do pozice β+∗c, kde c<b, potom z konstrukce je ∗c≡αi pro nějaké i. Stačí tedy zahrát do pozice αi+∗c.
              • Zahraje-li první hráč do pozice αj+∗b, potom
                αj+∗b≡∗aj+∗b≡∗(aj⊕︎b).
                Jelikož aj≠b, tato hra je typu 𝒩.
              Poznámka Název MEX plyne z toho, že b je minimální vyloučené (minimal excluded) číslo z a1,…,an.
              Věta Každá pozice α v nestranné normální hře je ekvivalentní ∗k pro nějaké k∈ℕ.
              Důkaz Indukcí přes hloubku hry, kde jako indukční krok použijeme MEX princip.
              Cvičení Nechť γn je hra s n sirkami. Pro jaké ☼ je γn≡∗☼?
              ŘešeníZjevně pro n≤3 je γn≡∗n, protože jde o identickou hru. Podle MEX principu dostáváme
              γ4={γ1,γ2,γ3}≡{∗1,∗2,∗3}=∗0,
              γ5={γ2,γ3,γ4}≡{∗2,∗3,∗0}=∗1,
              γ6={γ3,γ4,γ5}≡{∗3,∗0,∗1}=∗2
              a tak dále. Obecně
              γn≡∗(nmod4).
              Cvičení Nechť γm,n je hra Chop velikosti m×n. Pro jaké ⚘ je γm,n≡∗⚘?
              ŘešeníV podstatě jde o Nim s hromádkami velikosti m−1 a n−1, takže γm,n≡∗(m−1)+∗(n−1)≡∗((m−1)⊕︎(n−1)).

              Klasická teorie her

              Definice Nechť N∈ℕ je počet hráčů a Si,i∈N^ je množina možných strategií i-tého hráče. Potom výplatní funkce je funkce f:⨉i=1NSi→ℝN určující, kolik bodů hráči dostanou při dané volbě strategií.
              Definice Hra pro dva hráče je s nulovým součtem, pokud každá výplatní dvojice má nulový součet.
              Hra kámen nůžky papír Mějme dva hráče, Řudiku a Sebíka, a matici
              ((0,0)(1,−1)(−1,1)(−1,1)(0,0)(1,−1)(1,−1)(−1,1)(0,0)).
              Hraje se tak, že Řudika vybere řádek a zároveň Sebík vybere sloupec, čímž je určena výplatní dvojice. Jelikož hra je s nulovým součtem, můžeme zjednodušeně psát
              (01−1−1011−10).
              Čísla tedy v tomto případě značí, kolik bodů Řudika získá a Sebík ztratí.
              Hra Mějme obchod a pekařství vedle autobusové zastávky. Ve hře jsou tři hráči: obchod, pekařství a autobusová společnost. Rozhodují se, jaké změny provedou od začátku roku 2026. Možné strategie jsou:
              S1∈{zavřít,zrušit prodej pečiva,nic neměnit,rozšířit prodej pečiva},S2∈{nic neměnit,rozšířit otevírací dobu},S3∈{zrušit linku,jezdit častěji,jezdit méně často}.
              Definice Nechť A je výplatní matice hry pro dva hráče s nulovým součtem.
              Definice Hráč je racionální, pokud se všemi informacemi, které má, hraje strategii, která nezmenší jeho výplatu.
              Hra Mějme hru pro dva hráče s nulovým součtem s výplatní maticí
              A≔(2130−10).
              Pro Řudiku rozhodně není výhodné hrát třetí řádek, protože druhý řádek dominuje třetímu řádku. Tím pádem pokud Sebík předpokládá, že Řudika hraje racionálně, je pro něj výhodné hrát druhý sloupec. A udělá-li Řudika analogickou úvahu, bude pro ni výhodnější zahrát první řádek. Tento princip můžeme zobecnit:
              Algoritmus iterované odstraňování Dostaneme-li výplatní matici A hry pro dva hráče s nulovým součtem, můžeme opakovaně odstraňovat řádek/sloupec dominovaný nějakým jiným řádkem/sloupcem.
              Poznámka Pokud jsou oba hráči racionální a vědí to o sobě, stačí uvažovat takto redukovanou matici.
              Pozorování Nechť iterovaným odstraňováním vznikne 1×1 matice (c). Potom v původní matici je c minimum na svém řádku a maximum ve svém sloupci.
              Definice Smíšená strategie pro i-tého hráče je pravděpodobnostní rozložení na množině Si. V případě hry pro dva hráče budeme strategii pro Řudiku brát jako řádkový vektor a strategii pro Sebíka jako sloupcový vektor.
              Pozorování Nechť A je výplatní matice pro hru pro dva hráčé s nulovým součtem a p,q jsou smíšené strategie pro Řudiku a Sebíka. Potom střední hodnota výplaty pro Řudiku je p⋅A⋅q.
              Definice Nechť A je matice hry pro dva hráče s nulovým součtem. Smíšená strategie p pro Řudiku zaručuje hodnotu v∈ℝ, pokud pro všechny Sebíkovy strategie q platí p⋅A⋅q≥v. Smíšená strategie q pro Sebíka zaručuje hodnotu v∈ℝ, pokud pro všechny Řudičiny strategie p platí p⋅A⋅q≤v.
              Pozorování Smíšená strategie p pro Řudiku zaručuje hodnotu v∈ℝ, právě když
              p⋅A≥(v⋯v).
              Analogicky pro Sebíka.
              Věta von Neumannova minmaxová Pro hru dvou hráčů s nulovým součtem s maticí A existuje hodnota hry a∈ℝ taková, že
              Důkaz Nechť 𝟏 značí jedničkový vektor. Vytvoříme primární úlohu lineárního programování:
              m≔max{𝟏⋅x|A⋅x≤𝟏,x≥0}.
              Ppdle silné věty o dualitě se její optimální řešení bude rovnat optimálnímu řešení odpovídající duální úlohy:
              m=min{y⋅𝟏|y⋅A≤𝟏,y≥0}.
              Vezměme a≔1m. Můžeme si rozmyslet, že z honstrukce je to hodnota hry. (Je nutné vychytat detaily ohledně toho, když a≤0.)
              Definice Nechť AR,AS jsou matice hry pro dva hráče vyjadřující výplatní funkce pro Řudiku a Sebíka. Smíšená strategie p pro Řudiku zaručuje hodnotu a∈ℝ, pokud pro všechny Sebíkovy strategie q platí p⋅AR⋅q≥v. Smíšená strategie q pro Sebíka zaručuje hodnotu b∈ℝ, pokud pro všechny Řudičiny strategie p platí p⋅AS⋅q≥v.
              Definice Nashova rovnováha pro hru pro dva hráče s maticemi AR,AS jsou smíšené strategie p,q takové, že
              Příklad koordinační hra Mějme hru s výplatní maticí
              A≔((1,1)(0,0)(0,0)(2,2)).
              Tato hra má dvě Nashovy rovnováhy:
              • p=(10),q=(10),
              • p=(01),q=(01).

              Odbočka do algebraické topologie

              Algebraická topologie je oblast matematiky zabývající se zkoumáním tvaru až na homeomorfismus (oboustranně spojitou bijekci).

              Věta Brouwerova o pevném bodě pro ℝ2 Každá spojitá funkce f:[0,1]2→[0,1]2 má pevný bod.
              Důkaz Na Teorii grafů jsme si ji dokázali pro uzavřený trojúhelník. Jelikož uzavřený čtverec je homeomorfní trojúhelníku, věta platí i pro čtverec.
              Věta speciální případ Nashovy Pro každou hru pro dva hráče, kde každý má dvě možné strategie, existuje Nashova rovnováha.
              Důkaz Nechť Řudičina strategie je (p1−p) a Sebíkova strategie je (q1−q). Chceme definovat spojitou funkci f(p,q)≔(p′,q′) takovou, že pokud p′>p, potom je pro Řudiku výhodně zvýšit p, a tak podobně. Označme
              AR⋅(q1−q)≕(a1a2),(p1−p)AS≕(b1b2).
              Potom možná volba funkce je například
              p′≔p+|a1−a2|+1+|a1−a2|,q′≔q+|b1−b2|+1+|b1−b2|,
              kde |x|+≔max{0,x}. (Této funkci se říká Nashův tok). Podle Brouwerovy věťy má tato funkce pevný bod, který udává Nashovu rovnováhu.
              Cvičení Pro úlohu vězňova dilematu vizualizujte Nashův tok a spočtěte Nashovu rovnováhu:
              ((−1,−1)(−5,0)(0,−5)(−3,−3)).
              Cvičení Řudika a Sebík jdou na rande. Řudika by radši šla plavat a Sebík do kina, ale pokud půjde každý jinam, ani jeden si to neužije:
              ((2,1)(0,0)(0,0)(1,2)).
              Vizualizujte Nashův tok a spočtěte Nashovu rovnováhu:
              Cvičení Řudika a Sebík jdou lovit jelena nebo zajíce. Jelena uloví, jen pokud na něj půjdou oba, zatímco zajíce dokáže ulovit každý sám:
              ((3,3)(0,1)(1,0)(1,1)).
              Vizualizujte Nashův tok a spočtěte Nashovu rovnováhu:

              Kooperativní hry

              Uvažujme hru pro dva hráče, která se odehraje hodněkrát a hráči se můžou předem domluvit.

              Definice Výplatní mnohoúhelník P hry pro dva hráče je konvexní obal všech možných výplatních dvojic.
              Definice Status quo je takový bod (x0,y0), že Řudika dokáže vhodnou volbou smíšené strategie zaručit nanejvýš hodnotu x0 a Sebík nanejvýš hodnotu y0.
              Definice Bod (x,y)∈P je Pareto-optimální, pokud v něm neexistuje žádný bod (x′,y′)∈P,(x′,y′)≠(x,y) s x′≥x a y≥y.
              Definice Vyjednávací množina je množina všech Pareto-optimálních bodů (x,y)∈P takových, že x≥x0 a y≥y0.
              Poznámka Vyjednávací množina vyjadřuje body, u kterých připadá v úvahu, aby se na nich hráči domluvili.
              Definice Arbitráž je nějaký algoritmus, podle něhož se hráči domluví, které strategie použijí.
              Definice Nashova arbitráž vypadá následovně:
              • Pokud existuje (x,y)∈P splňující x>x0 a y>y0, vybereme mezi nimi takový, který maximalizuje (x−x0)⋅(y−y0).
              • Pokud žádný takový bod neexistuje, potom zvolíme (x0,y0).
              Věta Nechť daná arbitráž splňuje následující axiomy:
              Racionalita
              Výsledek arbitráže je ve vyjednávací množině.
              Lineární invariance
              Transformujeme-li hru tak, že na výplaty obou hráčů aplikujeme nějaké afinní transformace s kladnými sklony, potom arbitráž pořád vybere stejný bod (akorát transformovaný).
              Symetrie
              Pokud x0=y0 a P je symetrický podle přímky x=y, potom vybereme maximální bod na této přímce.
              Nezávislost na irelevantních možnostech
              Pokud výsledek arbitráže je (x*,y*) a Q⊂P je polygon obsahující (x0,y0) a (x*,y*), potom i v Q zvolíme (x*,y*).
              Potom jde o Nashovu arbitráž.
              Důkaz Mějme Nashovu arbitráž 𝒩, která vrátí bod (xN,yN), a jinou arbitráž 𝒥, která vrátí bod (xJ,yJ). Najdeme takovou afinní transformaci, aby (x0,y0)↦(0,0) a (xN,yN)↦(1,1). Dokážeme, že také (xJ,yJ)↦(1,1).