Cooperative games/cs

Kooperativní hra, spadající do oblasti teorie her označuje takovou hru, ve které mají hráči možnost vzájemné kooperace, tedy spolupráce. Toto rozšíření, respektive možnost jim umožnňuje volit svoji strategii na základně ostatních. Tím je myšleno, před volbou své strategie vyjednat a uzavřít úmluvu s jinými hráči, jakou strategii zahrají oni. Cílem tvorby těchto úmluv (dohod) je zvýšení zisku, nebo výhry kombinací strategií v dané hře. Při uzavření úmluvy je povinností hráče dodržet dané podmínky. Avšak koncept spolupráce není povinný. Ke spolupráci dojde pouze, když souhlasí obě strany. A podmínka souhlasu je většinou jasná, pokud spolupráce přinese hráči větší užitek (výhodu), než když by hrál sám. Jinak řečeno, kooperací získám víc, než kdybych hrál na vlastní triko.

Základní příklad: Hráči Alice a Bob hrají online hru, kde rozvíjejí své město. Alicino okolí tvoří z 90 procent lesy a z 10 procent železnými doly. Naopak okolí Bobova města tvoří z 90 procent železné doly a z 10 procent lesy. Alice má dostatek dřeva na stavbu nových domů, ale nedostatek železa pro tvorbu oceli na zbraně. Bob je na tom opačně, disponuje železem na výrobu zbraní, ale má nedostatek dřeva. Hra poskytuje směnu surovin, ovšem s příplatkem zlata a v nevýhodném kurzu. Alice a Bob se mohou domluvit (kooperovat), že každý nebude draze měnit suroviny s hrou, ale vymění je navzájem. Vytvoří úmluvu (dohodu), ve které si specifikují směnný poměr surovin a dle tohoto poměru si budou vzájemně vyměňovat suroviny, aby dosáhli vyššího zisku. Navíc ušetří zlato, které bylo jako poplatek za směnu.

Kooperativní hry dvou hráčů

Kooperativní hry dvou hráčů jsou zvláštní tím, že pokud dojde ke vzájemné spolupráci, kooperují všichni (oba) hráči. Narozdíl od kooperace více hráčů, kde se všichni hráči nemusí zapojit a některý může hrát bez využití spolupráce. U totoho druhu hry platí taktéž pravidlo, že spolupráce mezi dvěma hráči se uskuteční pouze, pokud to přinese oběma hráči stejný vyšší zisk (výhru), než kdyby nespolupracovali. Pokud jeden z hráčů nezíská na kooperaci více, než při nekooperativní hře, nemá důvod tvořit dohodu s druhým hráčem.

Teorie

Základním krokem je určení, jaká by byla výhra v případě, kdyby danou kooperativní hru hráči odehráli jako hru nekooperativní. Tato výhra plyne z Nashova rovnovážného řečení nekooperativní hry a v této problematice se označuje rovnovážná zaručená výhra. O tuto výhru hráč nepřijde, jelikož to je výhra, kterou získá při nekooperativní hře. Zaručená výhra prvního hráče a její hodnotu označujeme v(1), zaručenou výhru druhého hráče stejně, akorát s číslovkou dva v(2).

Posléze maximální celkovou částka, kterou mohou hráči získat dohromady kooperací je vyjádřena následujícím vztahem:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1,2) = max [f_1(x,y) + f_2(x,y)]}

kde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_1} vyjadřuje výplatní funkci prvního hráče, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_2} výplatní funkci druhého hráče, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} vyjadřuje zvolenou strategii prvního hráče a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} zvolenou strategii druhého hráče.

Pokud platí podmínka Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1,2) > v(1) + v(2)} , čili celková částka (výhra) získaná kooperací je větší, než součet rovnovážných zaručených výher obou hráčů, tak je pro hráče výhodné utvořit dohodu a ve hře kooperovat. Posléze tedy optimální strategie, kterou by měli hráči zahrát, odpovídá hodnotě Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1,2)} . Tuto hodnotu nalezneme tak, že provedeme součet výplatních matich jednotlivých hráčů a najdeme maximální hodnotu v této nové matici.

Následným problémem se jeví rozdělení celkové částky kooperace mezi jednotlivé hráče po skončení hry. Toto rozdělení je definováno takovou dvojicí částek Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1} a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_2} , pro kterou platí následující podmínky:

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1 + a_2 = v(1,2)}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1 \geq v(1)}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_2 \geq v(2)}

Slovním popisem:

• výhra kooperací hráče 1 sečteno s výhrou kooperací hráče 2 se musí rovnat maximální celkové částce kooperace
• výhra kooperací hráče 1 musí být větší nebo rovna rovnovážné zaručené výhře hráče 1
• výhra kooperací hráče 2 musí být větší nebo rovna rovnovážné zaručené výhře hráče 2

Tuto množinu rozdělení parametrů Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1} a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_2} , splňující předchozí podmínky, nazýváme jádro hry.

Jádro hry

Jádro hry je tedy množinou kombinací výher jednotlivých hráčů při kooperativní hře. Není však přesně popsáno, jak rozdělit celkový zisk, respektive kolik si který hráč vezme z celkové výhry.

Existuje ovšem pár základních možností rozdělení celkové výhry:

• Každý hráč dostane polovinu celkové výhry kooperací, pokud takovéto rozdělení splňuje podmínky jádra hry.
• Každý hráč dostane zaručenou výhru a polovinu z části, co hráči získali kooperací navíc.
• Rozdělení celkové výhry v poměru, například dle rovnovážných zaručených výher, či předem dohodnutém poměru.

Vzorce pro typy výher jsou následující:

• Každý hráč dostane polovinu celkové výhry kooperací:
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1 = a_2 = \frac{v(1,2)}{2}}
• Každý hráč dostane zaručenou výhru a polovinu ze zbytku po kooperaci:
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1* = v(1) + \frac{[v(1,2) - v(1) - v(2)]}{2}}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_2* = v(2) + \frac{[v(1,2) - v(1) - v(2)]}{2}}
• Rozdělení výhry v poměru ke společné výhře:
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1 : a_2 = [v(1,2) - v(2)] : [v(1,2) - v(1)]}

Kooperativní hry s přenosnou výhrou

Jedná se o situaci, kdy je výhra přenosná, tudíž hráči mohou určitým způsobem celkovou výhru kooperace přerozdělit mezi sebe. Byť při této hře může dojít k situaci, že by jeden hráč při kooperaci dostal menší výhru, než svou zaručenou při nekooperaci, tak tím, že je výhra přenosná, sdílení a rozdělení výhry dostane chvilkově znevýhodněného hráče do lepší pozice, než při nekooperaci.

Kooperativní hry s nepřenosnou výhrou

Jedná se o situaci, pokud je výhra nepřenosná, každý hráč získá výhru ze své výplatní matice a nedostane podíl z celkové části. To znamená, že nedochází k možnostem dělení celkového zisku mezi hráče, ale výhra je vyplacena v poměru, který udává výplatní matice dané kombinaci strategií. Nepřenosná výhra se tedy může stát pro jednoho hráče extrémně výhodnou, naopak pro druhého hráče extrémně nevýhodnou. Posléze se tedy stává, že druhý hráč do kooperace nevstoupí, respektive nemá zájem, jelikož jeho zaručená výhra je větší, než výhra při kooperativní hře s nepřenosnou výhrou. Ovšem mohou nastat situace, kdy kooperace bude výhodná pro oba hráče, poté by mělo ke kooperaci dojít.

Příklady

V následující části jsou dva příklady, jeden na bližší porozumnění přenosné a nepřenosné výhry. Druhý konkrétní příklad kooperativní hry pro dva hráče s rozdělením celkové výhry.

Příklad kooperativní hry s přenosnou a nepřenosnou výhrou

Vezměme příklad, kde je zadána hra pro dva hráče s následující výplatní maticí pro dva hráče:

Tab 1 - Výplatní matice pro dva hráče

	X	Y
A	3,5	11,3
B	5,6	7,4

Jelikož jde o kooperační hru, sečteme hodnoty v daných buňkách (sečteme výplatní matice každého hráče) a vyjde nám celková výhra dané kombinace strategií, která se rovná maximální hodnotě tabulky. Součet výplatních matic ukazuje tabulka č.2:

Tab 2 - Součet výplatních matic

	X	Y
A	8	14
B	11	11

Nyní určíme základní parametry. Rovnovážným řešením při nekooperaci je strategie (B,X), které mají výhry (5,6). Z toho určíme, že zaručená výhra hráče 1 je Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1) = 5} a zaručená výhra hráče 2 je Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(2) = 6} . Rovnovážným řešením při kooperaci je strategie (A,Y) s celkovou výhrou Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1,2) = 11 + 3 = 14} .

Přenosná výhra: Hráči mohou sdílet výhru! Byť hráč 2 má zaručenou výhru při nekooperaci Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(2) = 6} a při kooperaci dostane v základu výhru 3 (dle Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(1,2) = (11,3)} ), tak se mu stále vyplatí spolupracovat, jelikož hráč 1 se s ním o svou výhru 11 podělí. Ve finále, pokud by si dělili celkovou výhru kooperace na půl, tak by každý z hráčů obdržel výhru 7. Z toho vyplývá Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_1 = a_2 = 7} .

Současně jsou splněny podmínky výher:

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 7 + 7 = 14} - podmínka součtu výher se rovná celkové výhře kooperace
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 7 \geq 5} - podmínka hráče 1, výhra při kooperaci je větší než rovnovážná zaručená výhra při nekooperaci
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 7 \geq 6} - podmínka hráče 2, výhra při kooperaci je větší než rovnovážná zaručená výhra při nekooperaci

Nepřenosná výhra: Hráči nemohou sdílet výhru! Rovnovážná zaručená výhra hráče 2 při nekooperaci je 6. Při kooperaci by v tuto chvíli obdržel hráč 1 výhru 11 a hráč 2 výhru 3. Tyto výhry se stanou finálními, nedojde k žádnému sdílení. Kooperace se tudíž stává pro hráče 2 nevýhodná a hráč 2 spolupracovat nebude, protože nekooperace mu přinese větší výhru, než kooperace.

Z toho důvodu není splněna podmínka Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_2 \geq v(2)} čili Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3 \geq 6} - výhra při kooperaci je větší než rovnovážná zaručená výhra při nekooperaci.

Příklad kooperativní hry pro dva hráče

Příklad na kooperativní hru pro dva hráče s řešením celkové kooperativní výhry na náhledem na způsoby rozdělení výhry. Hra je dána dvěma maticemi:

Tab 3 - Matice A

3	-3
4	1

Tab 3 - Matice B

5	-1
1	4

Tab 3 - Součet matic A a B

8	-4
5	5

Kooperativní hry více hráčů

Koaliční

Hlasovací

Příklady na procvičení

Výsledky příkladů

Reference

Učební videa

Game theory: Coalitional games
Yale university: Game theory - cooperative games
Game theory: Cooperative games and Shapley value