Difference between revisions of "Cooperative games/cs"

From Simulace.info
Jump to: navigation, search
(→‎Příklad výpočtu Shapleyovy hodnoty)
(→‎Příklad výpočtu Shapleyovy hodnoty)
Line 309: Line 309:
  
 
Při výpočtu Shapleyovy hodnoty předpokládáme, že hráči přichází na místo, kde uzavírají koaliční dohody, postupně. To znamená jeden po druhém. Máme-li zadánu hru s třemi hráči, je celkem šest možností, jak mohou za sebou přijít. Tyto možnosti jsou zasenené v tabulce.
 
Při výpočtu Shapleyovy hodnoty předpokládáme, že hráči přichází na místo, kde uzavírají koaliční dohody, postupně. To znamená jeden po druhém. Máme-li zadánu hru s třemi hráči, je celkem šest možností, jak mohou za sebou přijít. Tyto možnosti jsou zasenené v tabulce.
 +
 +
 +
{| class="wikitable"  | style="text-align:center; margin: auto;"
 +
|+ style="caption-side:bottom; color:#e76700;"|''Tabulka získaných dat ze simulací pro porovnání hodnot pro různý počet východů a nastavení''
 +
! Postup tvorby koalice !! Hráč 1 !! Hráč 2 !! Hráč 3
 +
|-
 +
|| výchozí simulace || 318||338||94
 +
|-
 +
| překážky || 356||316||75
 +
|-
 +
| chodba + překážky || 246||396||104
 +
|-
 +
| jenom chodba || 212||405||128
 +
|-
 +
| překážky || 376||291||73
 +
|-
 +
| chodba + překážky || 246||447||52
 +
|-
 +
| jenom chodba || 245||483||16
 +
|-
 +
|}
  
 
==Hlasovací==
 
==Hlasovací==

Revision as of 16:06, 12 June 2016

Učební text ve stavu tvorby!.

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.

Před čtením tohoto učebního textu je ideální seznámit se s tématy teorie her, Nashovy rovnováhy případně jednorázové hry.


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).[1]

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.[1]

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. [2]

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. [2]

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, maticí A a B, které jsou v tabulce č.3, respektive č.4. Dle teorie kooperační hry s dvěma hráči sečteme matici A a B a vyjde nám matice pro kooperativní hru. Tato matice je v tabulce č.5.[1]
Tab 3 - Matice A
3 -3
4 1
Tab 4 - Matice B
5 -1
1 4
Tab 5 - Součet matic A a B
8 -4
5 5









Pokud bychom spojili matici A a B dohromady a chtěli určit Nashovu rovnovážnou strategii, byla by to strategie(2,2), v pravé dolní buňce, se zaručenými výhrami (1,4). Z toho tedy vyplývá, že rovnovážná zaručená výhra hráče 1 je 1 a rovnovážná zaručená výhra hráče 2 je 4.

Pro vyhledání ideální strategie kooperace hledáme v tabulce č.5 největší hodnotu. Tu nalezneme v levé horní buňce, strategie (1,1) a její hodnota je 8. Tato hodnota je taktéž maximální celková výhra kooperace.

Doposud známé parametry:

  • 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) = 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 v(2) = 4 }
  • 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) = 8 }
  • 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 = 8 }

Při kooperační hře s nepřenosnou výhrou by se 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 = 3} , 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 = 5 } a všechny podmínky by byly splněny:

  • 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 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 8 > 1 + 4}
  • 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)} č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 + 5 = 8}
  • 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)} č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 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)} č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 5 \geq 4}

Při kooperační hře s přenosnou výhrou spočítáme možnosti výhry dle možností dělení celkové výhry:

  • 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{8}{2} = 4}
Vyobrazení jádra hry v grafu[1]
  • 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* = 1 + \frac{[8 - 1 - 4]}{2} = 2,5}
    • 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* = 4 + \frac{[8 - 1 - 4]}{2} = 5,5}
  • 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 = [8 - 4] : [8 - 1] = 4 : 7}

Ve výsledku všechny kombinace rozdělení výher splňují podmínky, proto se vyplatí oběma hráčům kombinovat.

Jádro hry v grafu

Na grafu lze vidět vyobrazení jádra hry. V tomto případě má jádro podobu úsečky mezi vyznačenými body. Přerušované čáry vyznačují právě tyto body a jsou to minima výhry pro daného hráče. Tím je myšleno, hráč 2 musí mít výhru větší jak 4, aby se mu kooperace vyplatila. To samé platí pro hráče 1, akorát u něj je minimální výhra 1. Pokud bychom se tedy pohybovali po přímce, nalezneme mnoho možností, jak rozdělit výhru mezi hráče. Například 2, 6 nebo 3, 5 a podobně (samozřejmě lze zajít i do desetinných míst). Nesmíme se však dostat u hráče 1 pod hodnotu 1 a u hráče 2 pod hodnotu 4.

Zajímavost

U tohoto druhu hry je možný alternativní způsob stanovení zaručené výhry. Jedná se totiž o stav, kdy by protihráč (hráč 2) volil pro hráče 1 nejhorší možnou strategii. Čili hráč jedna by hrál svou optimální strategii a hráč 2 nejhorší možnou strategii pro hráče 1. Pro odlišení výše definované zaručené výhry se tato nazývá maximinová zaručená výhra. Tato výhra se určí tak, že v prvním kroku určíme pro hráče 1 řádková minima a pro hráče 2 sloupcová minima. Z těchto nazelených minim následně vybereme maximální hodnoty.[1]

Pokud bychom tuto metodu aplikovali na příklad rozebraný výše, tak pro prvního hráče jsou řádková minima -3 a 1, pro druhého hráče jsou sloupcová minima 1 a -1. Dle pravidel tedy z těchto minim vybereme maximální hodnotu a ve výsledku lze konstatovat, že maximonová zaručená výhra má pro oba hráče hodnotu 1.

Tento postup se používá u dvoumaticových her s více než jedním Nashovým rovnovážným řešením, protože u těchto her je obtížné určit rovnovážnou zaručenou výhru.

Kooperativní hry více hráčů

V předchozím části jsme se zabývali pouze možností, že máme dva hráče a ti spolu buď kooperují, nebo jdou proti sobě, nekooperují. U her s více hráčů, kde rozumějmě nastává situace počtu hráčů > 2, nastává situace, kdy někteří hráči spolu mohou kooperovat, někteří nemusí. Otázkou ale zůstává, s kým spolupracovat a proti komu. Skupinu hráčů, kteří spolupracují při volbě strategií nazýváme koalicí, z toho odvozeno koaliční hry.

Koaliční

Definice

"Nechť N = {1, 2, 3, ..., N) je množina hráčů, potom koalicí hráčů rozumíme každou podmnožinu S množiny hráčů N. V případě, že S se shoduje s N, jsou v koalici všichni hráči a hovoříme o velké koalici."[3]

Není radno opomenout, že pokud hráč nevstoupí do žádné koalice, sám tvoří jednoprvkovou koalici. To znamená, že velká koalice existuje jen tehdy, jsou-li všichni hráči v jedné koalici. Hra více hráčů taktéž otevírá nové možnosti kombinací kooperací. S růstem počtu hráčů roste množství kombinací koalic, které lze vytvořit. Ve hře s N hráči lze vytvořit 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 2^N - 1} koalic a jeden hráč může být členem 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 2^{N-1} - 1} různých koalic. Pro ukázku, v koaliční hře s třemi hráči se naskýtá již pět možných řešení koalic:

  • Všichni hráči hrají samostatně (každý tvoří jednoprvkovou koalici).
  • Všichni hráči spolupracují (tvoří velkou koalici).
  • První a druhý hráč spolupracují proti třetímu, který tvoří jednoprvkovou koalici.
  • První a třetí hráč spolupracují proti druhému, který tvoří jednoprvkovou koalici.
  • Druhý a třetí hráč spolupracují proti prvnímu, který tvoří jednoprvkovou koalici.

Množina všech utvořených koalic v rámci jedné hry se nazývá koaliční struktura. Ve hře sedmi hráčů je koaliční struktura definována například takto: ({1, 3, 5},{4, 2},{6},{7}). Ve hře tedy vznikly čtyři koalice. V první koalici spolupracují hráči 1, 3 a 5, ve druhé hráči 4 a 2 a na konec existují dvě jednoprvkové koalice, jedna obsahuje hráče 6 a druhá hráče 7. Tito hráči s nikým nespolupracují. Pro typické konfliktní situace je předpokladem hra s volnou disjunktivní koaliční strukturou. Tato koaliční struktura udává, že jsou přípustné jakékoli koalice a hráč může být členem pouze jedné koalice. Počet možných koaličních struktur při volné disjunktivní koaliční struktuře lze vypočítat podle následujícího vzorce:

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 R(N) = \sum_{k=1}^N \sum_{j=0}^k (-k)^{-j} \dbinom{k}{j} (k - j)^N}}}

Ve výsledku dostáváme počet všech možných koaličních struktur při daném počtu hráčů. Pro ukázku, zde je pár hodnot: R(2)=2, R(3)=5, R(4)=52 a počet možných koalicí se s počtem hráčů rapidně zvyšuje.

Charakteristická funkce

"Charakteristickou funkcí hry s množinou hráčů N nazveme takovou funkci v, která je definována pro všechny podmnožiny S, to jest pro všechny koalice, kterých 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 2^N - 1} . Každé koalici charakteristická funkce přiřazuje hodnotu v(S), což je výhra koalice S."[3]

Charakteristickou funkci lze přirovnat k výplatní funkci, která se objevuje například u výše zmíněných kooperací dvou hráčů. Rozdílem je, že charakteristická funkce určuje výpaty koalicím, nikoliv hráčům. Hodnotu charakteristické funkce pro koalici S lze určit na základě dvou předpokladů:

  • Hráči mimo koalici S volí své rovnovážné strategie. Poté říkáme, že se jedná o rovnovážnou charakteristickou funkci.
  • Hráči mimo koalici S volí své nejhorší možné strategie z pohledu koalice S, aby ji záměrně poškodily. Poté říkáme, že se jedná o maximinovou charakteristickou funkci.

Pokud jsou hráči smysluplní, tak zvolí rozhodně rovnovážnou charakteristickou funkci, jelikož hráči mimo koalici S by měli chtít také maximalizovat svou výhru, než trestat koalici S a zároveň sebe.

Superaditivita

Říkáme, že charakteristická funkce je superaditivní, pokud pro každou dvojici koalic platí:[3]

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(S_1 \cup S_2) \geq v(S_1) + v(S_2)}

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 S_1, S_2 } jsou disjunktivní podmnožiny množiny N. Slovně řečeno, v případě vytvoření vyšší (větší) koalice je výhra větší nebo rovna součtu výher menších koalic. Ovšem v praktických příkladech ne vždy toto pravidlo platí. Například při hře tří hráčů může být pro dva spolupracující hráče výhodnější spolupracovat pouze ve dvou a nechat třetího v jednoprvkové koalici, než vytvořit koalici tří hráčů.

Rozdělení výhry

Předpoklady rozdělení výher jsou následující:[3]

  • Jde o přenosnou výhru! To znamená, že celkový zisk koalice lze rozdělit mezi její členy.
  • Neexistují žádné překážky pro uzavření dohody o jakémkoliv přerozdělení výhry koalice.
  • Pro jednodušší představu výhry ve hře si ji představme jako finanční částku.
  • Výhra hráče se odvíjí od celkové výhry koalice jejímž je členem a od přerozdělení výhry uvnitř koalice.

Princip kolektivní racionality

Princip kolektivní racionality je zájem hráčů na maximalizaci výhry koalice. Dle tohoto principu bychom měli:[3]

  • V prvním kroku sestavit koalici s nejvyšší celkovou výhrou. Pokud by takto nově vytvořená koalice obsahovala všechny hráče, postup končí a je vytvořena koaliční struktura.
  • V druhém kroku sestavit opět koalici s nejvyšší výhrou, avšak za využití hráčů, kteří netvoří koalici z prvního kroku.
  • Takto se pokračuje do té doby, než je ustavena úplná koaliční struktura hry!

Princip skupinové stability

Princip skupinové stability je zájem na maximalizaci výhry hráče či podskupiny hráčů při přerozdělení výhry v rámci koalice. Pro tento princip platí:[3]

  • Celá výhra koalice je rozdělena mezi hráče, kteří v ní jsou.
  • Každá podkoalice L musí mít při dělení výhry koalice K zajištěn minimálně takový podíl, který by si podkoalice L mohla zajistit vystoupením z koalice K.

Pro zajištění skupinové stability musí pro každou koalici K platit:

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 \sum_{i\in K}a_i = v(K), \sum_{i\in L}a_i \geq v(L), L \in K}

Pokud nastane situace, že některá z koalic není skupinově stabilní, je nutné se vrátit do bodu principu kolektivní racionality a utvořit novou koaliční strukturu. Tam místo nevyhovující koalice s nejvyšší výhrou zvolíme koalici s druhou nejvyšší výhrou a celý postup zopakujeme.

Jádro hry

Jádrem hry nazýváme množinu všech přípustných rozdělení 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, a_3, ..., a_n)} , které splňují podmínky skupinové stability. Pokud by došlo k situaci, že koaliční struktura není jednoznačně definována (charakteristická funkce by nabývala stejných hodnot pro více koalicí) a jádra daná těmito koaličními strukturami splňovala podmínky skupinové stability, měla by hra více jader. Pokud by podmínky skupinové stability nesplňovalo ani jedno rozdělení, je jádro prázdné.[3]

Shapleyův vektor - Shapleyova hodnota

Americký matematik a ekonom, Lloyd Stowell Shapley navrhl v roce 1953 Shapleyův vektor. Tato metoda slouží k odhadu síly hráče z pohledu mezního přínosu hráe ke všem koalicím, ve kterých může být členem. Následně jako Shapleyovy heodnoty se označují jednotlivé složky Shapleyova vektoru. N- rozměrný Shapleyův vektor je pro hru definován jako 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 h = (h_1, h_2, ..., h_N)} a každá hodnota vektoru označuje střední hodnotu 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 vypočteme podle vzorce:[3]

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(S) - v(S - {i})}

V praktickém zápisu to může vypadat následovně: v(2, 3, 4) - v(3, 4). A tento vzorec představuje přínos hráče 2 pro koalici, do níž patří, tedy (2, 3, 4). Shapleyovu hodnotu pro i-tého hráče vypočítáme dle následujícího vzorce (vážený součet mezních přínosů dané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 h_i = \sum_{S} \{\frac {(\left|S\right|-1)!(N-\left|S\right|)!}{N!} [v(S)-v(S-\{i\})]\}}

kde symbol 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 \left|S\right|} značí počet členů koalice S a sumace probíhá pro všechny koalice, pro které platí 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 i \in S} .

Příklad výpočtu Shapleyovy hodnoty

Počítání Shapleyovi hodnoty přes výše zmíněný vzorec by bylo matoucí, proto si ukážeme aplikaci vzorce ukážeme na lépe zapamatovatelné technice.

Existuje koaliční hra, kde N = 3, tudíž hra tří hráčů. Charakteristické funkce hry jsou zadány následovně:

v({1}) = 1; v({2}) = 2; v({3}) = 3;
v({1,2}) = 2; v({1,3}) = 3; v({2,3}) = 6;
v({1,2,3}) = 6

Při výpočtu Shapleyovy hodnoty předpokládáme, že hráči přichází na místo, kde uzavírají koaliční dohody, postupně. To znamená jeden po druhém. Máme-li zadánu hru s třemi hráči, je celkem šest možností, jak mohou za sebou přijít. Tyto možnosti jsou zasenené v tabulce.


Tabulka získaných dat ze simulací pro porovnání hodnot pro různý počet východů a nastavení
Postup tvorby koalice Hráč 1 Hráč 2 Hráč 3
výchozí simulace 318 338 94
překážky 356 316 75
chodba + překážky 246 396 104
jenom chodba 212 405 128
překážky 376 291 73
chodba + překážky 246 447 52
jenom chodba 245 483 16

Hlasovací

Příklady na procvičení

Výsledky příkladů

Reference

  1. ↑ 1.0 1.1 1.2 1.3 1.4 DLOUHÝ, Martin; FIALA, Petr. Úvod do teorie her. Praha : Nakladatelství Oeconomica, 2009. 119 s. ISBN 978-80-245-1609-7. S. 35-37.
  2. ↑ 2.0 2.1 Friebelová Jana: Teorie her, str. 15 [online]. Ekonomická fakulta Jihočeské univerzity [cit. 2016-06-11]. Dostupné z: http://www2.ef.jcu.cz/~jfrieb/rmp/data/teorie_oa/TEORIE%20HER.pdf
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 DLOUHÝ, Martin; FIALA, Petr. Úvod do teorie her. Praha : Nakladatelství Oeconomica, 2009. 119 s. ISBN 978-80-245-1609-7. S. 57-70.

Učební videa

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

Retrieved from "http://www.simulace.info/index.php?title=Cooperative_games/cs&oldid=12204"