Kooperativní hra

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

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.

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

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áž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 f₁ je výplatní funkce prvního hráče, f₂ 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.

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

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₁ a a₂, 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í (a₁, a₂), které splňují předchozí vztahy, nazýváme jádrem hry. 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 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. 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. 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, 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. 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 S₁, S₂ jsou disjuktní podmnožiny množiny všech hráčů N. 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

$(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 N}a_{i}=v(N),\sum _{i\in L}a_{i}\geq v(L),L\subset N$

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í (a₁, a₂, ..., a_N), 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.

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 $n>2$ 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í $v({i})=0$ pro jednoprvkové koalice, $v({i,j})=1000$ pro kteroukoli koalici dvou hráčů a $v({1,2,3})=1200$. Abychom zaručili stabilitu, musí každá dvojice obdržet alespoň $1000$, v součtu tedy všichni tři hráči dohromady $1500$. Ty ale nejsou k disposici, výplata velké koalice je jen $1200$

Bondareva-Shapley theorem: Nutná a postačující podmínka neprázdného jádra hry

Olga N. Bondareva v roce 1963 a nezávisle Lloyd S. Shapley v roce 1967 formulovali a dokázali nutnou a postačující podmínku pro hru koaliční hru $(v(S))_{S\subseteqq N}$k tomu, aby daná hra měla neprázdné jádro, tedy aby výšezmíněná soustava $\sum _{i\in L}a_{i}\geq v(L),L\subset N$, $\sum _{i\in N}a_{i}=v(N)$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 $\sum _{i\in N}a_{i}>v(N)$Například ve hře tří hráčů s charakteristickou funkcí $v({i})=0$ pro jednoprvkové koalice, $v({i,j})=1000$ pro kteroukoli koalici dvou hráčů a $v({1,2,3})=1200$ dostáváme pro jádro (mimo dalších) podmínky ${\begin{array}{lcl}a_{1}+a_{2}\geqq 1000\\a_{1}+a_{3}\geqq 1000\\a_{2}+a_{3}\geqq 1000\end{array}}$, což v součtu dává $2(a_{1}+a_{2}+a_{3})\geqq 3000$- spor s $a_{1}+a_{2}+a_{3}=1200$. Bondareva i Shapley dokázali, že platí rovněž opačné tvrzení: Z neexistence součtu některých z nerovností $\sum _{i\in L}a_{i}\geq v(L),L\subset N$, který by vedl ke sporu s rovností $\sum _{i\in N}a_{i}=v(N)$již plyne, že jádro hry je neprázdné. Formálně: Systém podmnožin množiny $N$ $(S)_{S\subset N}\subset 2^{N}$ je balancovaný, pokud lze najít nezápornou váhu $\lambda _{S}$ pro každou z množin systému tak, že každý prvek z $N$ je ve váženém součtu obsažen v tomto systému s vahou právě $1$. Podle Bondareva-Shapley teorému je jádro hry neprázdné právě když pro jakýkoli balancovaný systém $(S)_{S\subset N}\subset 2^{N}$ a odpovídající váhy $\lambda _{S}$ platí $\sum _{S}\lambda _{S}v(S)\leqq v(N)$

Bondareva formulovala výsledek čtyři roky před Shapleyem, ovšem 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, ve starší literatuře také Shapley theorem.

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 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. 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. 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_i. 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á. 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.

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

$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 i ∈ S, v(S) = 1 a zároveň v(S-{i}) = 0. Jestliže platí v(S) = 1 a zároveň v(S-{i}) = 0 nazýváme stranu i jako nepostradatelnou. Pro hodnoty h_i 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 = ($\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 e_i označuje počet koalic S, ve kterých je strana i nepostradatelná. 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

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

Související články

• Teorie her
• Souboj pohlaví
• Vězňovo dilema
• Koordinační hra

Externí odkazy

• Obrázky, zvuky či videa k tématu kooperativní hra na Wikimedia Commons

Autoritní data	PSH: 11429