Dvou maticové hry a jejich aplikace Dvou-maticové Obsah kapitoly
Studijní cíle
1. Hry s konstantním součtem • Hra v normálním tvaru (ryzí strategie) • Smíšené strategie 2. Hry s nekonstantním součtem • Nekooperativní hra • Dvou-maticová Dvou maticová hra • Modelové konflikty o The Prisoner‘s Dilemma (Vězňovo dilema) o Chicken (Kuře, ale spíše Zbabělec) o The Battle of the Sexes (Manželský spor) Cílem tohoto tematického bloku je pochopení elementárního modelu teorie her, kterým je dvou-maticová dvou maticová hra.
Doba potřebná ke studiu
3 3-4hod
Pojmy k zapamatování
maticová a dvoumaticová hra, hry s konstantním součtem, hra v normálním tvaru, ryzí strategie, smíšené strategie, hry s nekonstantním součtem, nekooperativní hra, modelové konflikty V tomto tematickém bloku se seznámíme se základním typem her. Půjde o nekooperativní hry bez opakování a jejich další dělení. Nejprve si vysvětlíme maticovou hru a následně dvou dvou-maticovou maticovou hru. Jde o základní model, který je využíván v následujících kapitolách a v praxi se s ním setkáváme nejčastěji. nejčastě
Úvod
Výkladová část
Hry s konstantním součtem - Hra v normálním tvaru Jde o základní model teorie her, který je určen třemi množinami: • množina hráčů {1, 2, 3,…, N} • množina prostorů strategií {X1 , X2 , X3, …, XN} • množina výplatních funkcí {f1(x1, x2, x3, …, xN}, …, {fN(x1, x2, x3, …, xN} – ty jsou definovány na kartézském součinu prostoru strategií, u hry dvou hráčů postačí označení f1(x, y) pro výplatní funkci 1. hráče a f2(x, y) pro výplatní funkci 2. hráče. Kartézský tézský součin Jde o součin dvou množin, např. A a B. Například mějme množiny A = <2,6> a B = <1,7>, pak jejich součin vypadá takto:
1
Předpoklady modelu jsou: • inteligentní (racionální) hráči; • dokonalá informovanost; Definice hry: • jde o antagonistický konflikt, kdy jeden získá a druhý ztrácí; • hra s konstantním (nulovým) součtem, kde platí: , , onst, í 0, , ! " # , ! Ten, kdo se odchýlí od optimálních strategií, si nemůže polepšit. To je princip, na kterém je založena Nashova rovnováha, nebo též Nashovo rovnovážné řešení nebo také rovnovážná strategie. Tyto pojmy si dobře zapamatujte, budou nás provázet celou dobu. Ve hře s nulovým součtem a s konečným prostorem strategií, můžeme pro znázornění využít matici, pomocí které nalezneme rovnováhu: $
' (
% % ' ' ( %
& & ' (&
Řádky reprezentují i-té strategie hráče 1 a sloupce j-té strategie hráče 2. Model je nazýván maticová hra. Řešením je nalezení sedlového prvku matice A. Sedlový prvek (Nashovo rovnovážné řešení) najdeme tak, že určíme maxima ve sloupcích a minima v řádcích. Mohou nastat tyto případy: • matice má jeden sedlový prvek, • matice má více sedlových prvků, • matice nemá žádný sedlový prvek. Příklad 1.1: Nalezněte sedlový prvek v těchto maticích:
2
Matice A 1
3
-2
5
-3
2
4
-3
2
2
3
3
1
0
-3
-1
1
3
1
-1
2
-1
0
2
0
-2
0
-2
3
-2
-3
2
5
2
1
2
3
Matice B
Matice C
Řešení naleznete na konci učebního textu.
Hry s konstantním součtem - Smíšené strategie Pro matice, ve kterých se nepodařilo najít sedlový prvek, se používá k řešení smíšeného rozšíření maticové hry, kde prostory strategií představují vektory, s jakou pravděpodobností je budou volit jednotliví hráči strategie. Využívá se zde smíšených „pravděpodobnostních“ strategií. Platí opět, že ten kdo se odchýlí od rovnovážné strategie, nemůže získat a naopak ztrácí. K
N
P
K
0
1
-11
N
-1
0
1
P
1
-11
0
Jako příklad můžeme použít hru „kámen, „kámen, nůžky, papír“. Matice nemá sedlový prvek, přesto víme o pravděpodobnosti, s jakou nastane ta či ona varianta. V tomto konkrétním případě je to (1/3; 1/3; 1/3). Úkol: Nalezněte vlastní hru, která má řešení pouze ve smíšených strategiích.
3
Hry s nekonstantním součtem Nekooperativní hra - Dvou-maticová hra Uvažujeme dále pouze dva hráče. V tomto typu hry má každý z hráčů k dispozici vlastní výplaty na základě zvolených strategií. Tedy pro nelezení sedlového prvku musíme obě matice spojit do jedné dvou-matice. Kde Matice A reprezentuje dostupné strategie hráče 1 a Matice B hráče 2. Matice A – hráč 1 3
4
-2
2
Hráč volí své strategie z řádků. Tedy má k dispozici dvě strategie, řádek 1 a řádek 2. Matice B – hráč 2 5
2
7
1
Hráč volí své strategie ze sloupců. Tedy má k dispozici dvě strategie, sloupec 1 a sloupec 2. Spojením obou matic dostaneme jednu dvou-matici: Hráč 2 Strategie 1
Strategie 2
Strategie 1
3
5
4
2
Strategie 2
-2
7
2
1
Hráč 1
Matice spojíme tak, že výplaty z matice A a z matice B napíšeme vedle sebe přesně tak, jak jsou uvedeny v původních maticích. V matici A (tj. ve výplatní matici prvního hráče) je třeba výplata v levém horním rohu (tuto pozici v matici lze označit symbolem (1;1)) ve výši 3. V matici B (tj. ve výplatní matici druhého hráče) je výše výplaty v levém horním rohu 5. Tyto hodnoty pak napíšeme vedle sebe v dvou-matici opět do levého horního rohu a získáme tak hodnoty výplat (3;5). Přičemž hodnota 3 je výplatou hráče 1, pokud tento hráč zvolí svoji první strategii, a hodnota 5 je výplatou hráče 2, pokud tento hráč zároveň zvolí svoji první strategii. V pravém horním rohu (1;2) matice A je výplata 4 a v matici B je 2. Spojením do dvou-matice dostaneme v pravém horním rohu výplaty (4;2). Přičemž hodnota 4 je výplatou hráče 1, pokud tento hráč zvolí svoji první strategii, a hodnota 5 je výplatou hráče 2, pokud tento hráč zároveň zvolí svoji druhou strategii. Takto budeme postupovat i u levého a pravého dolního rohu. Sedlový prvek najdeme tak, že v matici A (prvky v levé části dvou-matice) nalezneme maxima ve sloupcích (nadále budeme používat modré podbarvení pro lepší přehled) a v matici B (prvky v pravé části matice) maxima v řádcích (nadále budeme používat zelené podbarvení). Nashovo rovnovážné řešení, tj. řešení výhodné pro prvního i druhého hráče, je v této matici pouze jedno (potom v terminologii teorie her nastává tzv. čistá Nashova rovnováha) a sedlový prvek je levý horní roh matice (tam kde se vyskytuje podbarvení u obou prvků, jak modré tak zelené) –
4
podrobněji viz příklad. Tato pozice se označuje (1;1) a výplaty jsou (3;5). Hledání sedlového prvku je matematické zjednodušení komplikovanějšího popisu. Nyní si tento popis uvedeme, přičemž dále již budeme využívat převážně matematické zjednodušení. Hráč 1 (původní matice A) má k dispozici dvě strategie, které vybírá ze dvou řádků. Jeho protihráč (hráč B) vybírá ze sloupců. Proto hráč 1 vybere takovou strategii, která mu přinese nejvyšší výplatu na základě rozhodnutí Hráče 2. Hráči 1 a 2 se přitom nemohou domluvit, že každý z nich uplatní určitou strategii. Hráč 1 se potom ptá: Pokud hráč 2 zvolí určitou strategii reprezentovanou sloupcem, jaká je moje nejlepší odpověď na tuto strategii? Čísla v každém řádku pro příslušný sloupec (strategii hráče 2) tak reprezentují výplaty, které může hráč 1 obdržet při zvolení svých řádkových strategií a zároveň při volbě strategie hráče 2. Hráč 1 zde hledá takovou svoji strategii, která mu při dané strategii hráče 2 maximalizuje jeho výplatu, tedy maximální řádkovou hodnotu příslušného sloupce. Stejná je situace i u hráče 2 (původní matice B) – tento hráč má na výběr také dvě strategie, které reprezentují sloupce, ale vybírá je z řádků, protože musí přizpůsobit své rozhodnutí možnostem, které má k dispozici zbývající hráč (tj. hráč 1). Hráč 2 se tudíž ptá, jaká je jeho nejlepší strategie, pokud hráč 1 zvolí určitou strategii (reprezentovanou řádkem). Čísla v každém sloupci pro příslušný řádek (strategii hráče 1) tak reprezentují výplaty, které může hráč 2 obdržet při zvolení svých sloupcových strategií a zároveň při volbě strategie hráče 1. Hráč 2 zde hledá takovou svoji strategii, která mu při dané strategii hráče 1 maximalizuje jeho výplatu, tedy maximální sloupcovou hodnotu příslušného řádku.
Modelové hry Základními modely sociálních dilemat jsou tyto následující: 1. The Prisoner‘s Dilemma (Vězňovo dilema) 2. Chicken (Zbabělec) 3. The Battle of the Sexes (Manželský spor) The Prisoner‘s Dilemma - Vězňovo dilema Jde o základní model pro ostatní modelové situace, který se používá k označení všech ostatních modelů tohoto typu, zkráceně PD Games. V originálním modelu se jedná o situaci dvou vězňů, kteří spáchali nějaký trestný čin a byli dopadeni. Při výslechu jsou oba odděleni a mají na výběr dvě možnosti, buď se přiznat, nebo se nepřiznat. Pro řešení výběru jejich rozhodovací strategie použijeme opět dvou-matici (záměrně jsou použity záporné hodnoty, výplaty mají charakter trestu): Vězeň 2 Přiznat
Nepřiznat
Přiznat
-3
-3
-1
-4
Nepřiznat
-4
-1
-2
-2
Vězeň 1
Vězeň 1 zkoumá, jaká strategie je pro něj výhodnější, pokud vězeň 2 uplatní strategii přiznat se. V takovém případě je pro vězně 1 výhodná strategie přiznat se – dostane trest odnětí svobody ve
5
výši 3 roky, pokud by se nepřiznal, dostal by 4 roky. Vězeň 1 dále zkoumá, jaká strategie je pro něj výhodnější, pokud vězeň 2 uplatní strategii nepřiznat se. I zde je pro vězně 1 výhodná strategie přiznat se – dostane trest odnětí svobody ve výši 1 roku, pokud by se nepřiznal, dostal by 2 roky. Obdobně je na tom i vězeň 2. Pokud se vězeň 1 přizná, je pro vězně 2 výhodné přiznat se (dostane 3 roky, jinak by dostal 4 roky). Pokud se vězeň 1 nepřizná, tak je pro vězně 2 rovněž výhodné přiznat se – při přiznání dostane 1 rok, jinak by dostal 2 roky. Nashova rovnováha (v ryzích strategiích) v této hře tedy existuje, dominantní strategií každého hráče bude přiznání (1;1) s výplatami (-3;-3). Tato strategie je však pro oba hráče horší, než kdyby se nepřiznali. Problém ovšem je, že pokud se jeden hráč nepřizná a druhý se přizná, pak nepřiznání bude stát více. Každý hráč bude tedy volit jistotu a přizná se. Lze namítnout, že ve výše zmíněné podobě je hra Vězňovo dilema málo realistická. V realitě vskutku nelze jednoznačně stanovit trest jen na základě toho, zda-li se nějaký pachatel přizná, zda se přitom přizná jiný pachatel apod. Popularitu získala daná hra kvůli něčemu jinému – ukazuje, že mohou nastat situace, kdy se všechny osoby chovají určitým jednotným způsobem (všechny osoby uplatňují stejnou strategii) s cílem maximalizovat svůj užitek, uplatněním této strategie si však všichni jednající pohorší. Jinými slovy, pokud by jednotliví hráči zvolili jinou než pro ně nejvýhodnější strategii, tak by na tom byli lépe, než když všichni hráči tuto nejvýhodnější strategii zvolí. Podmínkou toho, aby se jednalo o hru typu Vězňovo dilema, je, že v případě všech hráčů jsou splněny následující nerovnosti: výplata hráče v případě, že hráč nespolupracuje (přizná se) a druhý hráč spolupracuje (nepřizná se), je větší než výplata, když se oba přiznají, výplata hráče v případě, že se oba nepřiznají, je větší než výplata, když se oba přiznají, výplata hráče v případě, když se oba hráči přiznají, je větší než jeho výplata, když že se nepřizná a druhý hráč přizná. Schematicky lze tyto podmínky vyjádřit takto: NK > KK > NN > KN, kde: první symbol znamená strategii nějakého hráče (jedno zda-li prvního nebo druhého), druhý symbol znamená strategii zbývajícího hráče; N znamená, že daný hráč nespolupracuje, čili používá nekooperativní strategii (přizná se); K znamená, že spolupracuje, tj. použije kooperativní strategii (nepřizná se). Za hodnoty dosadíme hodnoty z výplatní matice některého hráče (např. prvního), pokud jednotliví hráči zvolí v podmínce uvedené strategie. Čísla tedy reprezentují výplaty nějakého hráče při zvolených strategiích. V případě prvního hráče jsou tyto výplaty ve výše uvedeném příkladě následující: - 1 > -2 > -3 > -4 Např., pokud se první hráč přizná a druhý nepřizná (NK), obdrží první hráč trest 1 rok. Pokud se oba hráči přiznají (KK), obdrží první hráč 2 roky. Atd. Stejné výplaty má ovšem i druhý hráč. I pro něj tedy platí: - 1 > -2 > -3 > -4 Každý hráč tak má dominantní strategii – přiznat se. Pokud se přizná, bude jeho výplata vyšší nezávisle na tom, jak se rozhodne druhý hráč (-3 > -4; -1 > -2). Nashova rovnováha v ryzích strategiích v této hře tedy existuje, ale je pro oba horší, než kdyby se nepřiznali (tj. spolupracovali). Jak jsme již uvedli, tento typ her se vyskytuje velmi často, např.: Dvě firmy uzavřely kartelovou dohodu a mohou ji porušit, nebo dodržet. Dvě politické strany uzavřely dohodu o tom, že jejich výdaje na volební kampaň nepřekročí určitou částku a mohou ji porušit, nebo dodržet. Dvě velmoci uzavřely dohodu o snížení počtu zbraní a mohou ji porušit, nebo dodržet. Při vyplnění výplatní matice u tohoto typu her můžeme využít různé postupy. V případě kartelové
6
dohody lze příslušné hodnoty získat kalkulací, v ostatních případech používáme spíše expertní exp odhad. Úkol: Vyberte si některý konkrétní případ her typu Vězňova dilema a pokuste se sestavit jeho výplatní matici. Chicken - Zbabělec Model řeší situaci, kdy dva hráči volí strategii ustoupit od devastujícího rozhodnutí (kooperativní strategie), nebo strategii neustoupit (nekooperativní strategie). Ten kdo ustoupí, prohrává. Pokud by ustoupili oba hráči, celkově nedojde k devastaci, žádný z hráčů však nic nezíská. Příkladem může být rozhodnutí dvou hochů zamilovaných do stejné dívky, žžee (s jejím vědomím) vyřeší svůj (momentální) životní problém tím, že se rozjedou autem proti sobě vysokou rychlostí. Kdo uhne, dívku ztrácí. V případě, že neuhne žádný z nich, ztrácí ovšem oba svůj život. Pro řešení použijeme opět matici: Hráč 2 Ustoupit
Neustoupit
Ustoupit
0
0
-5
5
Neustoupit
5
-5
-10
-10
Hráč 1
V ryzích strategiích existují v této hře dvě Nashovy rovnovážné strategie1 strategie (2;1) a (1;2). Každá je však výhodná pouze pro jednoho hráče. Pokud však oba hráči budou volit pro sebe vhodnější strategii (tj. neustoupit), bude to pro oba nevýhodné - výsledkem je strategie (2;2) a výplaty (-10;( 10). Podmínkou toho, aby se jednalo o hru u typu Kuře (Zbabělec), je, že u každého hráče platí následující nerovnosti: NK > KK > KN > NN, kde stejně jako u hry Vězňovo dilema znamená první symbol strategii nějakého hráče (je jedno, zda-ii prvního nebo druhého), druhý symbol strategii zbývajícího hráče; hr K znamená kooperovat (ustoupit) a N nekooperovat (neustoupit). Přičemž hodnota prohry je velmi vysoká oproti zisku, který lze navíc dosáhnout jen v případě, že hráč, který jej dosáhne, zvolí nekooperativní strategii, zatímco druhý kooperativní. Konkrétní étní výplaty prvního hráče (na základě výše uvedené tabulky) při uplatnění daných strategii jsou u dané nerovnosti: 5 > 0 > - 5 > - 10 Stejné hodnoty má i druhý hráč.
1 Připomínáme, že zde první číslo v závorce obsahuje strategii prvního hráče, druhé číslo v závorce strategii druhého hráče.
7
The Battle of the Sexes - Manželský spor Tento model si lze přiblížit na následující situaci, po které je model nazván: Manželé mohou strávit večer společně, ale každý z nich má jiné představy o tom jak. Manžel chce jít na fotbalový zápas a žena na nákupy. Oba manželé spolu rádi tráví čas a mají alespoň nějaký (větší) užitek ze společného večera, i když není vybrána jejich preference, než z večera, kdy je každý z manželů sám. Každý z manželů se rozhoduje samostatně. Pro řešení použijeme opět matici:
Manžel Manželka Kopaná
Manžel
Nákupy
Kopaná
2
1
0
0
Nákupy
0
0
1
2
Existujíí dvě rovnovážná řešení (celkem tedy dva sedlové prvky (1;1) a (2;2)) s výplatami (2;1) a (1;2). Pokud bude muž teoreticky volit pro sebe výhodnější první sloupec, ale žena pro sebe výhodnější druhý řádek, tak bude paradoxně výsledkem výplata (0;0). ediska každého z hráčů lze rozlišit strategie na tu, která je výhodná pro něj (V), a tu, která je Z hlediska pro něj nevýhodná, ale je výhodná pro druhého hráče (N). Podmínkou toho, aby se jednalo o hru typu manželský spor, je, že pro každého hráče jsou splněny následující následující nerovnosti: VN > NV > VV = NN, kde opět první symbol znamená strategii nějakého hráče (jedno, zda prvního nebo druhého), druhý symbol strategii zbývajícího hráče. Například z pohledu muže mají jeho výplaty při uplatnění daných strategií obsažených v nerovnosti následující podobu: 2 > 1 > 0 = 0. Stejnou podobu mají výplaty i z pohledu ženy. Většinu těch, co se s tímto schématem seznámí, logicky napadne, že nejlépe pro oba hráče bude, pokud se domluví – např. jeden týden půjdou manželé nakupovat, druhý druhý týden na fotbal. Jenže to by již byla zcela jiná hra obsahující vyjednávání. Zde předpokládáme, že oba hráči činí rozhodnutí nezávisle, současně, a bez toho, aby věděli, jak se rozhodne druhý hráč. Může tak dojít i k tomu, že každý chce vyhovět tomu druhému druhému (žena je ochotna podřídit se muži a jít s ním na fotbal, muž je ochoten podřídit se ženě a jít s ní na nákup, protože jeden druhého velmi miluje), výsledkem však bude situace, kdy každý půjde jinam a užitek každého bude nejmenší.
Rozšiřující text
Pro další dobrovolné rozšíření znalostí si můžete nastudo astudovat zbývající čtyři dilemata, k tomu použijte učebnici Mikroekonomie, středně pokročilý kurz, kurz, Heissler, Valenčík, Wawrosz.
Shrnutí
V tomto tematickém bloku jsme se seznámili s maticovými a dvoudvou maticovými hrami a jejich řešením. Dále s rozdělením základních sociálních dilemat a jejich podrobným popisem a aplikovatelností na
8
Kontrolní otázky a úkoly
Seznam použitých zkratek Studijní literatura
Odkazy
ekonomii. Definujte vlastní model dvou-matice. matice. Co je to dominovanost? Navrhněte vlastní model, kde prohozením výplat dostanete jiný výsledek hry a zdůvodněte ho. PD (Games) - Prisonner's dilemma - obecně pro modely vězňovo dilema DLOUHÝ M., FIALA P. Úvod do teorie her. 2. přepracované vydání. Praha 2009. VŠE – Oeconomica. ISBN 978-80 978 80-245-1609 1609-7. (nebo 1. vydání z roku 2007) MAŇAS, M. Teorie her a konflikty zájmů. 1. vydání. Praha 2002. VŠE - Oeconomica. ISBN 80-24580 -0450-2. (nebo pozdější vydání) ŘEŠENÍ DVOUMATICOVÝCH HER http://www.gametheory.net/Mike/applets/NormalForm/NormalForm. html ŘEŠENÍ MATICOVÝCH HER http://euler.fd.cvut.cz/predmety/teorie_her/matrix/games.html (maximálně 5x5 strategií) OPAKOVANÉ VĚZŇOVO DILEMA http://www.lifl.fr/IPD/ipd.html.en
Klíč k úkolům
KÁMEN, NŮŽKY, PAPÍR http://www.playrps.com/ Řešení příkladu 1.1: Matice A má pouze jeden sedlový prvek a to (1;3) s výplatou 2. 1
3
-2
5
-3
2
4
-3
2
2
3
3
1
0
-3
-1
Matice B má dva sedlové prvky (1;1) a (3;1) s výplatami 1. 1
3
1
-1
2
-1
0
2
0
-2
0
-2
Matice C nemá sedlový prvek. 3
-2
-3
2
5
2
9
1
2
3
10
