Zobrazení zdroje stránky Kooperativní hra

'''Kooperativní hra''' v [[teorie her|teorii her]] označuje hru, ve které hráči mohou vzájemně spolupracovat ([[kooperace|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ýhra|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 ==
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 ===
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.
<center>
{| class="wikitable"
|+ Dvoumaticová hra
! !!X!!Y
|-
!A
|1,3||9,1
|-
!B
|3,4||5,2
|}
</center>
[[rovnovážné řešení|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 ===
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áčů ==
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 ===
Výhra v nekooperativní hře plyne z [[Nashova rovnováha|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:
<center><math>v(1,2) = MAX [f_1(x,y) + f_2(x,y)]</math></center>
kde ''f<sub>1</sub>'' je [[výplatní funkce]] prvního hráče, ''f<sub>2</sub>'' 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.
<ref>{{citace monografie | jméno = Martin| příjmení = Dlouhý| jméno2 = Petr| příjmení2 = Fiala | titul = Úvod do teorie her| vydavatel = Nakladatelství Oeconomica | místo = Praha | rok = 2007| počet stran = 114| strany = 25–26| isbn = 978-80-245-1273-0| poznámka = [dále jen Dlouhý, Fiala]}}</ref>
<center>
{| class="wikitable"
|+ Dvoumatice
! !!X!!Y
|-
!A
|1,8||7,6
|-
!B
|3,4||5,2
|}
</center>
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.
<center>
{| class="wikitable"
|+ Součtová matice
! !!X!!Y
|-
!A
|9||13
|-
!B
|7||7
|}
</center>
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 ===
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 ''a<sub>1</sub>'' a ''a<sub>2</sub>'', pro kterou platí
<center><math>a_1 + a_2 = v(1,2), a_1 \geq v(1), a_2 \geq v(2)</math></center>

Množinu všech rozdělení ''(a<sub>1</sub>, a<sub>2</sub>)'', které splňují předchozí vztahy, nazýváme '''[[jádro hry|jádrem hry]]'''.<ref>Dlouhý, Fiala, str.26-28</ref>
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áčů ==
S rostoucím počtem hráčů v kooperativní hře roste počet možných [[koalice|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 ===
Nechť ''N = {1, 2, ..., N}'' je množina hráčů, pak '''koalicí''' hráčů rozumíme každou podmnožinu ''S'' množiny hráčů ''N''.<ref name="rfr1">Dlouhý, Fiala, str.28</ref> 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'''.<ref name="rfr1" /> 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 ===
'''[[Charakteristická funkce (teorie her)|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.<ref name="rfr1" />
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'''''<br />
Charakteristická funkce kooperativní hry je '''superaditivní''', jestliže pro každou dvojici koalic platí
<center><math>v(S_1 \cup S_2) \geq v(S_1) + v(S_2)</math></center>
kde ''S<sub>1</sub>'', ''S<sub>2</sub>'' jsou disjuktní podmnožiny množiny všech hráčů ''N''.<ref name="rfr1" /> 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 ===
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
<center><math>(a_1, a_2, ..., a_N)</math></center>
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'''''<br />
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'''''<br />
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
<center><math>\sum_{i \in N} a_i = v(N), \sum_{i \in L} a_i \geq v(L), L \subset N</math><ref>Dlouhý, Fiala, str.29</ref></center>
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.<br />
Množinu všech rozdělení ''(a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>N</sub>)'', 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.<ref name="rfr2">Dlouhý, Fiala, str.30</ref>

==== Příklad hry s prázdným jádrem ====
Definice jádra hry připouští situaci, kdy je jádro prázdné (a tedy skupinově stabilní rozdělení zisku velké koalice neexistuje). Pro <math>n>2</math> hráče tato situace může nastat i u monotónní hry, tzn. u takové, kdy větší koalice přináší vždy větší hodnotu než koalice menší.
Příkladem budiž hra tří hráčů s charakteristickou funkcí <math> v({i})=0 </math> pro jednoprvkové koalice, <math> v({i,j})=1000 </math> pro kteroukoli koalici dvou hráčů a <math>v({1,2,3})=1200 </math>. Abychom zaručili stabilitu, musí každá dvojice obdržet alespoň <math> 1000 </math>, v součtu tedy všichni tři hráči dohromady <math> 1500 </math>. Ty ale nejsou k disposici, výplata velké koalice je jen <math> 1200</math>

==== Bondareva-Shapley theorem: Nutná a postačující podmínka neprázdného jádra hry ====
[[Olga N. Bondareva]]<ref>Bondareva, Olga N. "Some applications of linear programming methods to the theory of cooperative games." ''Problemy kibernetiki'' 10 (1963): 119-139</ref> v roce 1963 a nezávisle [[Lloyd Shapley|Lloyd S. Shapley]]<ref>Shapley, Lloyd S. "On balanced sets and cores." ''Naval research logistics quarterly'' 14.4 (1967): 453-460.</ref> v roce 1967 formulovali a dokázali nutnou a postačující podmínku pro hru koaliční hru <math>(v(S))_{S \subseteqq N}</math>k tomu, aby daná hra měla neprázdné jádro, tedy aby výšezmíněná soustava <math> \sum_{i \in L} a_i \geq v(L), L \subset N</math>, <math>\sum_{i \in N} a_i = v(N)</math>měla řešení. Především: soustava žádné řešení nemá, pokud váženým součtem několika nerovností soustavy jsme schopni dostat spor s koncovou rovností, tedy <math> \sum_{i \in N} a_i > v(N)</math>Například ve hře tří hráčů s charakteristickou funkcí <math> v({i})=0 </math> pro jednoprvkové koalice, <math> v({i,j})=1000 </math> pro kteroukoli koalici dvou hráčů a <math>v({1,2,3})=1200 </math> dostáváme pro jádro (mimo dalších) podmínky <math> \begin{array}{lcl} a_1+a_2 \geqq 1000 \\ a_1+a_3 \geqq 1000 \\ a_2+a_3 \geqq 1000  \end{array}
</math>, což v součtu dává <math> 2(a_1+a_2+a_3) \geqq 3000</math>- spor s <math> a_1+a_2+a_3 = 1200</math>. Bondareva i Shapley dokázali, že platí rovněž opačné tvrzení: Z neexistence součtu některých z nerovností <math> \sum_{i \in L} a_i \geq v(L), L \subset N</math>, který by vedl ke sporu s rovností <math>\sum_{i \in N} a_i = v(N)</math>již plyne, že jádro hry je neprázdné.
'''Formálně:''' Systém podmnožin množiny <math> N</math> <math>(S)_{S \subset N} \subset 2^N</math> je '''[[Balancovaný systém|balancovaný]]''', pokud lze najít nezápornou váhu <math> \lambda_S</math> pro každou z množin systému tak, že každý prvek z <math> N</math> je ve váženém součtu obsažen v tomto systému s vahou právě <math> 1</math>. Podle Bondareva-Shapley teorému je jádro hry neprázdné právě když pro jakýkoli balancovaný systém <math>(S)_{S \subset N} \subset 2^N</math> a odpovídající váhy <math> \lambda_S</math> platí <math>\sum_{S } \lambda_Sv(S) \leqq v(N)</math>

[[Olga N. Bondareva|Bondareva]] formulovala výsledek čtyři roky před [[Lloyd Shapley|Shapleyem]], ovšem [[Ruština|rusky]] a navíc v periodiku ''Проблемы кибернетики'' málo známém vědcům mimo [[Sovětský svaz]], takže dlouho byl za objevitele považován [[Lloyd Shapley]]. [[Lloyd Shapley]] se později zasazoval za používání názvu Bondareva theorem. Dnešní podoba názvu Bondareva-Shapley theorem je kompromisní, lze se rovněž setkat s podobou Shapley-Bondareva theorem,<ref>Lehrer, Ehud. "Allocation processes in cooperative games." ''International Journal of Game Theory'' 31.3 (2003): 341-351.</ref> ve starší literatuře také Shapley theorem.<ref>Schmeidler, David. ''On balanced games with infinitely many players''. No. RM-28. HEBREW UNIV JERUSALEM (ISRAEL) DEPT OF MATHEMATICS, 1967.</ref>

=== Spravedlivé dělení výhry ===
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ů:
* těžiště jádra
* [[nucleolus]]
* [[Shapleyova hodnota]]

== Shapleyova hodnota ==
'''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 [[Lloyd Shapley|L. S. Shapley]].
Shapleyovy hodnoty tvoří Shapleyův vektor, který je pro kooperativní hru ''N'' hráčů definován jako
	<center><math>h = (h_1, h_2, ..., h_N)</math></center>
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.<ref name="rfr2" /> Přínos hráče ke koalici ''S'' se vypočte jako rozdíl:
	<center><math>v(S) - v(S - \{i\})</math></center>
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:
<center> <math>h_i = \sum_{i \in S} \{\frac {(\left|S\right|-1)!(N-\left|S\right|)!}{N!}
[v(S)-v(S-\{i\})]\}</math></center>
kde symbol ''|S|'' značí počet členů koalice ''S'' a sumace probíhá přes všechny koalice, pro které platí ''i ∈ S''.<ref name="rfr2" /> Shapleyovy hodnoty představují také jedno z možných dělení výhry v kooperativní hře N hráčů.

== Volební hry ==
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čí ''a<sub>i</sub>''. Celkový počet poslanců strany v parlamentu pak můžeme vyjádřit jako
<center><math>a_0 = \sum_{i=1}^N a_i</math></center>
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á'''.<ref name="rfr3">Dlouhý, Fiala, str.31</ref> 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 <math>\alpha</math>, 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
<center><math>\lfloor \alpha a_0 \rfloor + 1</math></center>
Pro vítěznou koalici musí platit, že
<center><math>\sum_{i=1}^N a_i - \lfloor \alpha a_0 \rfloor > 0</math></center>
V opačném případě se jedná o koalici poraženou.<br />
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.<ref name="rfr3" />

=== Shapleyův-Shubikův index síly ===
'''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
<center><math>h_i = \sum_{i \in S} \{\frac {(\left|S\right|-1)!(N-\left|S\right|)!}{N!}\}</math></center>
kde sumace probíhá přes všechny vítězné koalice ''S'' takové, že ''i'' ∈ ''S'', ''v(S)'' = 1 a zároveň ''v(S-{i})'' = 0.<ref>Dlouhý, Fiala, str.32</ref> Jestliže platí ''v(S)'' = 1 a zároveň ''v(S-{i})'' = 0 nazýváme stranu ''i'' jako '''nepostradatelnou'''.
Pro hodnoty ''h<sub>i</sub>'' 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 ===
'''Banzhafův index síly''' použil v roce [[1965]] [[J. F. Banzhaf]], obvykle se značí ''b = (<math>\beta_1</math>, <math>\beta_2</math>, ..., <math>\beta_N</math>)''. Jeho jednotlivé složky pro strany ''1, 2, ..., N'' se počítají podle vztahu
<center><math> \beta_i = \frac {e_i}{\sum_{i=1}^N e_i}</math></center>
kde ''e<sub>i</sub>'' označuje počet koalic ''S'', ve kterých je strana ''i'' '''nepostradatelná'''.<ref>Dlouhý, Fiala, str.34</ref> Z výpočetního vztahu je zřejmé, že také pro hodnoty <math>\beta_i</math> 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 ==
* {{citace monografie | jméno = Martin| příjmení = Dlouhý| jméno2 = Petr| příjmení2 = Fiala | titul = Úvod do teorie her| vydavatel = Nakladatelství Oeconomica | místo = Praha | rok = 2007| počet stran = 114| isbn = 978-80-245-1273-0}}

== Reference ==
<references />

== Související články ==
* [[Teorie her]]
* [[Souboj pohlaví (teorie her)|Souboj pohlaví]]
* [[Vězňovo dilema]]
* [[Koordinační hra]]

== Externí odkazy ==
* {{Commonscat}}

{{Autoritní data}}

[[Kategorie:Teorie her]]