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. (Způsob zápisu viz článek Teorie her, odstavec Normální forma.) + Dvoumaticová hra XYA1,39,1B3,45,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:
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.
+ Dvoumatice XYA1,87,6B3,45,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 XYA913B77 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 a1 a a2, pro kterou platí
Množinu všech rozdělení (a1, a2), které splňují předchozí vztahy, nazýváme jádrem hry.Dlouhý, Fiala, str.26-28 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.Dlouhý, Fiala, str.28 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í
kde S1, S2 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
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 Dlouhý, Fiala, str.29 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.Dlouhý, Fiala, str.30
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 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í pro jednoprvkové koalice, pro kteroukoli koalici dvou hráčů a . Abychom zaručili stabilitu, musí každá dvojice obdržet alespoň , v součtu tedy všichni tři hráči dohromady . Ty ale nejsou k disposici, výplata velké koalice je jen
Bondareva-Shapley theorem: Nutná a postačující podmínka neprázdného jádra hry Olga N. BondarevaBondareva, Olga N. "Some applications of linear programming methods to the theory of cooperative games." Problemy kibernetiki 10 (1963): 119-139 v roce 1963 a nezávisle Lloyd S. ShapleyShapley, Lloyd S. "On balanced sets and cores." Naval research logistics quarterly 14.4 (1967): 453-460. v roce 1967 formulovali a dokázali nutnou a postačující podmínku pro hru koaliční hru k tomu, aby daná hra měla neprázdné jádro, tedy aby výšezmíněná soustava , 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 Například ve hře tří hráčů s charakteristickou funkcí pro jednoprvkové koalice, pro kteroukoli koalici dvou hráčů a dostáváme pro jádro (mimo dalších) podmínky , což v součtu dává - spor s . Bondareva i Shapley dokázali, že platí rovněž opačné tvrzení: Z neexistence součtu některých z nerovností , který by vedl ke sporu s rovností již plyne, že jádro hry je neprázdné. Formálně: Systém podmnožin množiny je balancovaný, pokud lze najít nezápornou váhu pro každou z množin systému tak, že každý prvek z je ve váženém součtu obsažen v tomto systému s vahou právě . Podle Bondareva-Shapley teorému je jádro hry neprázdné právě když pro jakýkoli balancovaný systém a odpovídající váhy platí
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,Lehrer, Ehud. "Allocation processes in cooperative games." International Journal of Game Theory 31.3 (2003): 341-351. ve starší literatuře také Shapley theorem.Schmeidler, David. On balanced games with infinitely many players. No. RM-28. HEBREW UNIV JERUSALEM (ISRAEL) DEPT OF MATHEMATICS, 1967.
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