Kooperativní hra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kooperativní hra v teorii her označuje hru, ve které hráči mohou vzájemně spolupracovat (kooperovat). V kooperativní hře mají hráči možnost před volbou strategií vyjednávat a uzavírat závazné dohody o tom, jaké strategie zahrají, aby zvýšili svoji výhru. Hráči obecně mohou, ale nemusí spolupracovat. Hráči budou vzájemně spolupracovat pouze tehdy, bude-li to pro ně výhodné. To znamená, jestliže získají vyšší výhru, než kdyby nespolupracovali.

Řešení kooperativních her poskytuje odpovědi na 3 základní otázky:

  • Kdo s kým bude spolupracovat a má kooperace vůbec smysl?
  • Jaké strategie hráči zvolí?
  • Jak si hráči rozdělí mezi sebou zisk?

Dělení kooperativních her[editovat | editovat zdroj]

Kooperativní hry můžeme rozdělit podle 2 základních hledisek – přenositelnosti výhry a počtu hráčů. Z hlediska přenositelnosti výhry je dělíme na hry s přenosnou a nepřenosnou výhrou.

Hra s přenosnou výhrou[editovat | editovat zdroj]

U hry s přenosnou výhrou si hráči mohou celkovou výhru při kooperaci přerozdělit mezi sebe. V takovém případě můžeme výplatní matice obou hráčů sečíst a hráči budou ochotni spolupracovat, i když by jeden z nich podle své výplatní matice získal méně než při nekooperaci, protože mu to druhý při rozdělování společné výhry může vynahradit.

Dvoumaticová hra
X Y
A 1,3 9,1
B 3,4 5,2

Rovnovážným řešením při nekooperaci jsou strategie (B, X) s výhrami (3, 4). Rovnovážným řešením při kooperaci jsou strategie (A, Y) se společnou výhrou 9+1=10. Hráči budou spolupracovat, protože 10 > (3+4).

Hra s nepřenosnou výhrou[editovat | editovat zdroj]

Jestliže je výhra nepřenosná, získává každý hráč výhru ze své výplatní matice, která tedy musí být vyšší než v případě nekooperace. Pokud je předchozí příklad hrou s nepřenosnou výhrou, 2.hráč spolupracovat nebude, protože by získal pouze výhru 1 oproti výhře 4 při nekooperaci.

Podle počtu hráčů pak rozlišujeme kooperativní hru dvou hráčů a kooperativní hru více hráčů.

Kooperativní hra dvou hráčů[editovat | editovat zdroj]

Kooperativní hra dvou hráčů je specifická tím, že v ní spolupracují všichni (oba) hráči. Hráči budou spolupracovat jenom v případě, že jim to přinese vyšší výhru. Prvním krokem řešení tedy je zjištění výhry hráčů, kdyby kooperativní hru odehráli jako nekooperativní.

Zaručená výhra[editovat | editovat zdroj]

Výhra v nekooperativní hře plyne z Nashova rovnovážného řešení nekooperativní hry a označuje se jako zaručená výhra. Zaručenou výhru prvního hráče označujeme v(1), zaručenou výhru druhého hráče v(2). Celková částka, kterou si hráči mohou zajistit kooperací dohromady, je:

v(1,2) = MAX [f_1(x,y) + f_2(x,y)]

kde f1 je výplatní funkce prvního hráče, f2 výplatní funkce druhého hráče, x zvolená strategie prvního hráče a y zvolená strategie druhého hráče. Pro hráče je výhodné spolupracovat, jestliže platí v(1,2) > v(1) + v(2), a optimální strategie jsou takové strategie, které odpovídají maximální hodnotě v(1,2). Najdeme je sečtením výplatních matic obou hráčů a nalezením maximální hodnoty ve výsledné matici. [1]

Dvoumatice
X Y
A 1,8 7,6
B 3,4 5,2

Ve této hře jsou rovnovážným řešením v případě nekooperace strategie (B, X) s výhrami (3, 4). Zaručená výhra prvního hráče v(1) má tedy hodnotu 3 a zaručená výhra druhého hráče v(2) hodnotu 4. Sečtením výplatních matic obou hráčů získáme novou matici.

Součtová matice
X Y
A 9 13
B 7 7

Maximální celková výhra v(1,2) je rovna 7 + 6 = 13, odpovídají ji strategie (A, Y). Protože je splněna nerovnost v(1,2) > v(1) + v(2) (13 > 3 + 4), je pro hráče výhodné uzavřít dohodu a spolupracovat.

Jádro hry[editovat | editovat zdroj]

Poslední otázkou je, jak si hráči mezi sebou rozdělí společnou výhru v(1,2). Rozdělením nazýváme takovou dvojici částek a1 a a2, pro kterou platí

a_1 + a_2 = v(1,2), a_1 \geq v(1), a_2 \geq v(2)

Množinu všech rozdělení (a1, a2), které splňují předchozí vztahy, nazýváme jádrem hry.[2] Je zřejmé, že rozdělení obecně existuje mnoho, v předchozím příkladu jsou to např. rozdělení (6,5;6,5), (7;6) nebo (5;8). Výhru proto můžeme rozdělit několika způsoby:

  • dát každému hráči polovinu společné výhry, pokud takové rozdělení patří do jádra hry (6,5;6,5)
  • ponechat každému hráči zaručenou výhru a polovinu toho, co hráči získali kooperací navíc (6;7)
  • rozdělit společnou výhru v poměru zaručených výher apod.

Kooperativní hra více hráčů[editovat | editovat zdroj]

S rostoucím počtem hráčů v kooperativní hře roste počet možných koalic a vyvstává tak otázka, jakou(é) koalice hráči vytvoří. Koalice je skupina hráčů, kteří spolupracují při volbě strategií.

Koalice, koaliční struktura[editovat | editovat zdroj]

Nechť N = {1, 2, ..., N} je množina hráčů, pak koalicí hráčů rozumíme každou podmnožinu S množiny hráčů N.[3] Jestliže platí S=N, hovoříme o velké koalici. Součástí velké koalice jsou tedy všichni hráči. Pokud hráč nevstoupí do žádné koalice, přesto jej nazýváme koalicí, a to jednoprvkovou. Uvažuje se i prázdná koalice, která nemá žádné členy. Množina všech možných koalic v určité kooperativní hře se nazývá koaliční struktura.[3] Příkladem koaliční struktury ve hře 6 hráčů je ({1,2,3},{4,5},{6}). Tato koaliční struktura znamená, že spolupracují hráči 1, 2 a 3, hráč 4 spolupracuje s hráčem 5 a hráč 6 jedná samostatně (tvoří jednoprvkovou koalici). Koaliční struktura může být volná nebo omezená. Při volné koaliční struktuře nejsou na tvorbu koalic kladena žádná omezení a hráči mohou vstoupit do koalice s kterýmkoliv jiným hráčem. V omezené koaliční struktuře není vytvoření některých koalic povoleno. V typických situacích předpokládáme kooperativní hru s volnou disjunktní koaliční strukturou. To znamená, že přípustné jsou jakékoli koalice a hráč může být členem pouze jedné koalice. Dále též předpokládáme kooperativní hru s přenosnou výhrou.

Charakteristická funkce[editovat | editovat zdroj]

Charakteristická funkce, kterou značíme v, přiřazuje každé koalici její výhru. Je tedy obdobou výplatní funkce v nekooperativní hře s tím, že přiřazuje výhru celé koalici, nikoliv jednotlivým hráčům.[3] Hodnoty charakteristické funkce pro všechny koalice s výjimkou velké koalice závisí na tom, jaké strategie zvolí hráči, kteří členy dané koalice nejsou. Rozlišují se dva základní typy charakteristické funkce – minimaxová a kompetitivní. U minimaxové charakteristické funkce se předpokládá, že nečlenové koalice volí takovou strategii, která je pro koalici nejméně výhodná. V případě kompetitivní charakteristické funkce volí nečlenové koalice stejnou strategii, jako kdyby kooperativní hra byla odehrána jako nekooperativní.

Superaditivnost
Charakteristická funkce kooperativní hry je superaditivní, jestliže pro každou dvojici koalic platí

v(S_1 \cup S_2) \geq v(S_1) + v(S_2)

kde S1, S2 jsou disjuktní podmnožiny množiny všech hráčů N. [3] Při vytvoření větší koalice je v takovém případě výhra větší než součet výher menších koalic. Superaditivnost obecně nemusí být splněna.

Jádro hry[editovat | editovat zdroj]

Konečné rozdělení výhry koalice mezi její členy nazýváme, stejně jako v kooperativní hře dvou hráčů, rozdělením, které má tvar vektoru

(a_1, a_2, ..., a_N)

Výhra hráče závisí na celkové výhře koalice, jejímž je členem, i na přerozdělení výhry uvnitř koalice. Uplatňují se zde dva principy – kolektivní racionality a skupinové stability.

Princip kolektivní racionality
Princip kolektivní racionality vyjadřuje zájem hráče na maximalizaci výhry koalice. Říká, že v prvním kroku sestavíme koalici, která má nejvyšší celkovou výhru. Jestliže tak vznikne velká koalice všech hráčů, je nalezena koaliční struktura celé hry. Jinak ve druhém kroku sestavíme opět koalici s nejvyšší celkovou výhrou, ale už pouze z hráčů, kteří netvoří koalici z prvního kroku. Takto se pokračuje, až dokud není ustavena úplná koaliční struktura hry.

Princip skupinové stability
Princip skupinové stability vyjadřuje zájem na maximalizaci výhry hráče či podskupiny hráčů při přerozdělení výhry koalice. Koaliční struktura sestavená podle principu kolektivní racionality musí, aby byla skupinově stabilní, splňovat následující 2 pravidla:

  • mezi členy koalice je rozdělena celá výhra koalice
  • každé podkoalici L je přidělena alespoň taková výhra, kterou by si tato podkoalice zajistila sama o sobě vystoupením z koalice K

Pro každou koalici K musí podle tohoto principu platit

\sum_{i \in K} a_i = v(K), \sum_{i \in L} a_i \geq v(L), L \in K[4]

Jestliže by tato pravidla nebyla splněna, pro podkoalici L by bylo výhodnější z koalice K vystoupit a koalice K by tak nebyla skupinově stabilní. Pokud některá z podkoalic není skupinově stabilní, je třeba se vrátit k předchozímu principu kolektivní racionality a sestavit jinou koaliční strukturu.
Množinu všech rozdělení (a1, a2, ..., aN), která odpovídají principu skupinové stability, nazýváme opět jádrem hry. Pokud charakteristická funkce nabývá shodných hodnot pro více koalic, není koaliční struktura určena jednoznačně a hra může mít více jader. Jestliže podmínky skupinové stability nesplňuje žádné rozdělení, je jádro hry prázdné. Pro řešení kooperativních her byla kromě principu skupinové stability navržena řada koncepcí, žádná z koncepcí však nezaručuje jednoznačné normativní řešení pro daný typ konfliktu.[5]

Spravedlivé dělení výhry[editovat | editovat zdroj]

Jádro kooperativní hry více hráčů může, stejně jako u kooperativní hry dvou hráčů, obsahovat více rozdělení. Nabízí se proto otázka, které z těchto rozdělení zvolit jako v nějakém smyslu spravedlivé. Uvádí se několik přístupů:

Shapleyova hodnota[editovat | editovat zdroj]

Shapleyova hodnota říká, jak významnou pozici má hráč v kooperativní hře, protože vyjadřuje průměrný přínos hráče do všech koalic, jichž může být členem. Pracuje s rozdílem mezi výhrou koalice s hráčem a podkoalice bez hráče. Shapleyovy hodnoty vycházejí z metody odhadu síly hráče z hlediska jeho mezního přínosu ke všem koalicím, jichž může být členem, kterou navrhl v roce 1953 americký matematik a ekonom L. S. Shapley. Shapleyovy hodnoty tvoří Shapleyův vektor, který je pro kooperativní hru N hráčů definován jako

h = (h_1, h_2, ..., h_N)

Jeho jednotlivé složky označují střední hodnotu mezního přínosu i-tého hráče ke všem koalicím, ve kterých může být členem.[5] Přínos hráče ke koalici S se vypočte jako rozdíl:

v(S) - v(S - \{i\})

Např. v(1,2,3) – v(2,3) představuje přínos hráče 1 do koalice (1, 2, 3). Shapleyovu hodnotu pro i-tého hráče vypočteme jako vážený součet mezních přínosů podle vzorce:

h_i = \sum_{i \in S} \{\frac {(\left|S\right|-1)!(N-\left|S\right|)!}{N!}
[v(S)-v(S-\{i\})]\}

kde symbol |S| značí počet členů koalice S a sumace probíhá přes všechny koalice, pro které platí i ∈ S.[5] Shapleyovy hodnoty představují také jedno z možných dělení výhry v kooperativní hře N hráčů.

Volební hry[editovat | editovat zdroj]

Příkladem kooperativní hry N hráčů je volební hra. Nechť N = {1, 2, ..., N} je množina politických stran v parlamentu. Počet poslanců i-té strany se značí ai. Celkový počet poslanců strany v parlamentu pak můžeme vyjádřit jako

a_0 = \sum_{i=1}^N a_i

Charakteristická funkce v(S) u volební hry nabývá hodnoty 0 v případě, že koalice S je vítězná, nebo 1 v případě, že je koalice S koalicí poraženou. Takováto hra se nazývá prostá.[6] U volebních her platí, že charakteristická funkce je superaditivní, protože větší koalice znamená větší počet hlasů a tím i vyšší pravděpodobnost prosazení zákona. Vítězství či prohra dané koalice závisí na volebním pravidlu \alpha, které udává minimální poměr hlasů v % potřebných k prosazení zákona v parlamentu. Minimální počet hlasů k prosazení zákona se pak vypočte jako

\lfloor \alpha a_0 \rfloor + 1

Pro vítěznou koalici musí platit, že

\sum_{i=1}^N a_i - \lfloor \alpha a_0 \rfloor > 0

V opačném případě se jedná o koalici poraženou.
Při analýze volebních her se pracuje s následujícími 3 předpoklady:

  • všichni zástupci politické strany hlasují jednotně
  • po vytvoření koalice stran hlasují všichni její členové stejně
  • možná je libovolná koalice a všechny koalice jsou stejně pravděpodobné

Řešení volebních her spočívá ve výpočtu indexů síly jednotlivých politických stran, které vycházejí ze skutečnosti, že samotný počet členů politické strany není dostatečným ukazatelem síly a vlivu politických stran. Záleží také na síle strany k vytvoření vítězné koalice.[6]

Shapleyův-Shubikův index síly[editovat | editovat zdroj]

Shapleyův-Shubikův index síly je modifikací Shapleyovy hodnoty. Vyjadřuje přínos politické strany vzhledem ke všem koalicím, jejichž členem se může stát. Vzhledem k tomu, že charakteristická funkce ve volebních hrách nabývá pouze hodnoty 0 nebo 1, zjednoduší se výpočet tohoto indexu na vztah

h_i = \sum_{i \in S} \{\frac {(\left|S\right|-1)!(N-\left|S\right|)!}{N!}\}

kde sumace probíhá přes všechny vítězné koalice S takové, že iS, v(S) = 1 a zároveň v(S-{i}) = 0.[7] Jestliže platí v(S) = 1 a zároveň v(S-{i}) = 0 nazýváme stranu i jako nepostradatelnou. Pro hodnoty hi platí, že jsou nezáporné a jejich součet je roven jedné. Proto je můžeme interpretovat jako pravděpodobnosti. Hodnota Shapleyova-Shubikova indexu síly vyjadřuje pravděpodobnost, že strana i bude nepostradatelná při sestavování všech teoretický možných vítězných koalic.

Banzhafův index síly[editovat | editovat zdroj]

Banzhafův index síly použil v roce 1965 J. F. Banzhaf, obvykle se značí b = (\beta_1, \beta_2, ..., \beta_N). Jeho jednotlivé složky pro strany 1, 2, ..., N se počítají podle vztahu

 \beta_i = \frac {e_i}{\sum_{i=1}^N e_i}

kde ei označuje počet koalic S, ve kterých je strana i nepostradatelná.[8] Z výpočetního vztahu je zřejmé, že také pro hodnoty \beta_i platí, že jsou nezáporné a jejich součet je roven jedné. Můžeme je proto opět interpretovat jako pravděpodobnosti. Hodnota Banzhafova indexu vyjadřuje pravděpodobnost situace, při které strana i svým vystoupením z koalice může anulovat vítězné postavení této koalice. Hodnoty Shapleyova-Shubikova a Banzhafova indexu mohou obecně nabývat rozdílných hodnot.

Literatura[editovat | editovat zdroj]

  • DLOUHÝ, Martin; FIALA, Petr. Úvod do teorie her. Praha : Nakladatelství Oeconomica, 2007. 114 s. ISBN 978-80-245-1273-0.  

Reference[editovat | editovat zdroj]

  1. DLOUHÝ, Martin; FIALA, Petr. Úvod do teorie her. Praha : Nakladatelství Oeconomica, 2007. 114 s. [dále jen Dlouhý, Fiala]. ISBN 978-80-245-1273-0. S. 25-26.  
  2. Dlouhý, Fiala, str.26-28
  3. a b c d Dlouhý, Fiala, str.28
  4. Dlouhý, Fiala, str.29
  5. a b c Dlouhý, Fiala, str.30
  6. a b Dlouhý, Fiala, str.31
  7. Dlouhý, Fiala, str.32
  8. Dlouhý, Fiala, str.34

Související články[editovat | editovat zdroj]