Nashova rovnováha

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Nashova rovnováha je v teorii her taková situace, kdy žádný z hráčů nemůže jednostrannou změnou zvolené strategie vylepšit svoji situaci. Současně se jedná i o koncept řešení nekooperativních her více hráčů. Své jméno získala po Johnu Nashovi, který dokázal, že každá konečná hra má alespoň jedno takové řešení.

Aplikace[editovat | editovat zdroj]

Koncept Nashovy rovnováhy se využívá pro analýzu výsledků strategické interakce několika aktérů. Jinými slovy se jedná o způsob předvídání rozhodnutí individuálních subjektů, které se rozhodují současně a jejich rozhodnutí závisí na rozhodnutí ostatních. Základním principem určení Nashovy rovnováhy je nemožnost předpovědět výsledek, pokud budeme nahlížet na jednotlivá rozhodnutí izolovaně. Musíme každé rozhodnutí hráče uvažovat v kontextu možných rozhodnutí ostatních. Nashova rovnováha byla použita při analýzách konfliktních situací jako války nebo Závody ve zbrojení [1] (viz Vězňovo dilema) a zmírnění konfliktů při jejich opakování. Také byla použita ke studiu možností kooperace lidí s různými preferencemi (viz Bitva pohlaví). Další aplikace spočívají ve studiu procesů přijímání technických standardů, modelovaní dopravních situací, organizování aukcí.[2]

Definice[editovat | editovat zdroj]

Neformální[editovat | editovat zdroj]

Představme si, že hráči navzájem znají svoje strategie. Pak se každý hráč může zeptat sám sebe: "Pokud znám strategie ostatních a budu je brát za pevně dané, mohu změnou mé akce získat nějaký prospěch?". Pokud bude odpovědí "ano", pak takováto situace není Nashovou rovnováhou. Pokud ale všichni hráči odpoví "ne" pak je toto řešení stabilním a označujeme ho za Nashovu rovnováhu. Nashovu rovnováhu tedy můžeme označit jako nejlepší možnou reakci na strategie ostatních.[3]

Formální[editovat | editovat zdroj]

Nechť (S, f) je hra s n hráči, kde Si je množina možných akcí hráče i, S = S1 X S2 ... Sn jsou strategie všech hráčů a f = (f1(x), ..., fn(x)) je výplatní funkce. Nechť x-i je výběr akcí všech hráčů vyjma hráče i. Každý hráč i ∈ {1, ..., n} si zvolí strategii xi pak ve výsledné situaci x = (x1, ..., xn) přísluší hráči i výplatní funkce fi(x). Situaci xS, kdy si žádný z hráčů nemůže jednostrannou změnou své akce zlepšit výsledek, tedy zvýšit hodnotu výplatní funkce, zapíšeme jako: \forall i,x_i\in S_i, x_i \neq x^*_{i} :  f_i(x^*_{i}, x^*_{-i}) \geq f_i(x_{i},x^*_{-i}). Výsledek může ležet buď v ryzích strategiích (volba konkrétní akce) nebo strategiích smíšených (je přidán koeficient pravděpodobnosti využití jednotlivých akcí). Nash dokázal, že každá konečná hra má alespoň jedno rovnovážné řešení.

Pokud platí v předchozí nerovnici ostrá nerovnost (> namísto \geq) mluvíme o Silné Nashově rovnováze. V případě, že existuje rovnost mezi x^*_i a další akcí z množiny S pak toto řešení označujeme jako Slabou Nashovu rovnováhu.

Důkaz existence[editovat | editovat zdroj]

Nechť \sigma_{-i} značí zvolené akce všech hráčů vyjma hráče i. Definujme nejlepší reakci hráče i jako b_i. b_i značí vztah souboru všech pravděpodobnostních rozdělení akcí ostatních hráčů k množině akcí hráče i, tak že každý prvek: :b_i(\sigma_{-i})\ je nejlepší reakcí na \sigma_{-i}. Definujme b(\sigma) = b_1(\sigma_{-1}) \times b_2(\sigma_{-2}) \times \cdots \times b_n(\sigma_{-n}).\

Pomocí Kakutaniho věty o pevných bodech dokážeme, že bpevný bod. To znamená, že existuje \sigma^* takové, že \sigma^* \in b(\sigma^*). Protože b(\sigma^*) je nejlepší reakcí všech hráčů na situaci \sigma^*, existence pevného bodu dokazuje, že existuje taková situace, která je nejlepší reakcí na sebe samu. Žádný z hráčů nemůže změnou nic získat a jedná se tedy o Nashovu rovnováhu.

Alternativní důkaz za použití Brouwerovy věty o pevných bodech[editovat | editovat zdroj]

Mějme hru G=(N,A,u), kde N je počet hráčů a A = A_1 \times \ldots \times A_N je množina všech možných strategií všech hráčů. Množiny strategií A_i všech hráčů jsou konečné. Nechť \Delta = \Delta_1 \times \ldots \times \Delta_N je množinou míšených strategií hráčů. Konečnost A_i zaručuje kompaktnost množiny \Delta.

Nyní definujeme výplatní funkce. Pro smíšenou strategii \sigma \in \Delta a při volbě akce a \in A_i je ziskem hráče i

Zisk_i(\sigma,a) = \max \{0, u_i(a_i, \sigma_{-i}) - u_i(\sigma_{i}, \sigma_{-i})\}.\

pro \sigma \in \Delta, a \in A_i. Z toho vyplývá, že

\sum_{a \in A_i} g_i(\sigma)(a) = \sum_{a \in A_i} \sigma_i(a) + Zisk_i(\sigma,a) = 1 + \sum_{a \in A_i} Zisk_i(\sigma,a) > 0.\

Nyní použijeme g pro definování f: \Delta \rightarrow \Delta. Nechť 
f_i(\sigma)(a) = \frac{g_i(\sigma)(a)}{\sum_{b \in A_i} g_i(\sigma)(b)}
pro a \in A_i.

Nyní můžeme jasně vidět, že každé f_i je platnou smíšenou strategií v \Delta_i. Také můžeme snadno ověřit, že každé f_i je spojitou funkcí \sigma a tedy i f je spojitou funkcí. \Delta je nyní vektorovým součinem konečného množství kompaktních konvexních množin a tedy i f je kompaktní a konvexní. Nyní můžeme pro f využít Brouwerovy věty o pevných bodech. Tedy f má pevný bod v \Delta, nazvěme ho \sigma^*

Pro důkaz, že \sigma^* je Nashovou rovnováhou v G, stačí ukázat, že: 
\forall 1 \leq i \leq N, ~ \forall a \in A_i, ~ Zisk_i(\sigma^*,a) = 0 \text{.}

Tímto jednoduše vyjadřujeme, že žádný hráč nemá další zisk z jednostranné změny své strategie, což je podmínka Nashovy rovnováhy. Předpokládejme, že možné zisky všech hráčů nejsou všechny rovny nule. Potom \exists i, 1 \leq i \leq N a a \in A_i takové, že Zisk_i(\sigma^*, a) > 0.

Povšimněme si, že

\sum_{a \in A_i} g_i(\sigma^*, a) = 1 + \sum_{a \in A_i} Zisk_i(\sigma^*,a) > 1.

Nechť je tedy C = \sum_{a \in A_i} g_i(\sigma^*, a). Zisk(i,\cdot) označme za vektor zisků s indexy akcí A_i. Pokud je f(\sigma^*) = \sigma^* pak platí i f_i(\sigma^*) = \sigma^*_i.

Následně tedy


\sigma^*_i = \frac{g_i(\sigma^*)}{\sum_{a \in A_i} g_i(\sigma^*)(a)}
\Rightarrow
\sigma^*_i = \frac{\sigma^*_i + Zisk_i(\sigma^*,\cdot)}{C} 
\Rightarrow
C\sigma^*_i = \sigma^*_i + Zisk_i(\sigma^*,\cdot)

\left(C-1\right)\sigma^*_i = Zisk_i(\sigma^*,\cdot)
\Rightarrow
\sigma^*_i = \left(\frac{1}{C-1}\right)Zisk_i(\sigma^*,\cdot).

V případě že C > 1, pak \sigma^*_i tvoří kladné váhy vektoru Zisk_i(\sigma^*,\cdot). Mějme tvrzení, že


\sigma^*_i(a)(u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}))
= 
\sigma^*_i(a)Zisk_i(\sigma^*, a)

\forall a \in A_i. Nejprve poznamenejme, že pokud Zisk_i(\sigma^*, a) > 0 pak je toto správná definice výplatní funkce. Nyní předpokládejme, že

Zisk_i(\sigma^*, a) = 0.

Z našich předchozích tvrzení plyne


\sigma^*_i(a) = \left(\frac{1}{C-1}\right)Zisk_i(\sigma^*, a) = 0

Levá strana výrazu je rovna nula, tedy i celý výraz je roven 0. Nakonec se tedy dostáváme k 
0 = u_i(\sigma^*_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})


  =  \left(\sum_{a \in A_i} \sigma^*_i(a)u_i(a_i, \sigma^*_{-i})\right) - u_i(\sigma^*_i, \sigma^*_{-i})

  =  \sum_{a \in A_i} \sigma^*_i(a) (u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}))

  = \sum_{a \in A_i} \sigma^*_i(a) Zisk_i(\sigma^*, a) \quad

  = \sum_{a \in A_i} \left( C -1 \right) \sigma^*_i(a)^2 > 0

Kde je poslední nerovnost z důvodu, že \sigma^*_i je nenulový vektor. Toto je zřejmý spor, tudíž všechny zisky musí být opravdu nulové. Pak tedy je \sigma^* Nashovou rovnováhou pro G.

Historie[editovat | editovat zdroj]

Koncept Nashovy rovnováhy poprvé představil Augustin Cournot ve svém modelu duopolu (1838). V tomto modelu firmy rozhodovaly o velikosti výroby za účelem maximalizace svého zisku. Nicméně nejvýhodnější velikost výroby závisí i na produkci druhé firmy. Cournotova rovnováha pak nastává v bodě, kdy obě firmy dosahují nejvyššího zisku s ohledem na zvolený objem výroby konkurenta. Moderní koncept Nashovy rovnováhy v teorii her je definován v rámci smíšených strategií, kde si hráči volí pravděpodobnosti volby jednotlivých strategií. Koncept smíšených strategií byl uveden Johnem von Neumannem a Oscarem Morgensternem v roce 1944 v knize Theory of Games and Economic Behavior. Nicméně jejich analýza byla omezena na speciální případy her s nulovým součtem. Ukázali, že Nashova rovnováha ve smíšených strategiích existuje pro jakoukoliv konečnou hru s nulovým součtem. John Forbes Nash v roce 1951 ve svém článku Non-Cooperative Games dokázal, že pro každou konečnou hru existuje alespoň jedna Nashova rovnováha ve smíšených strategiích.Od vývoje konceptu Nashovy rovnováhy bylo odhaleno, že za určitých podmínek může docházet k chybným závěrům. Proto bylo představeno několik odvozených konceptů (též nazývaných upřesněním Nashovy rovnováhy) přizpůsobených tomu, aby odstranily nedostatky Nashova konceptu. Obzvláště závažným problémem Nashovy rovnováhy založené na "nedůvěryhodných" hrozbách. Proto v roce 1965 Reinhard Selten ve svém článku Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetraegheit přestavil rovnováhu podher (menší část "velké" hry je brána jako samostatný celek), čímž odstranil Nashovy rovnováhy založené na "nedůvěryhodných" hrozbách. Další rozšíření Nashovy rovnováhy se zabývají situacemi, kdy se hra opakuje a nebo hráči nemají všechny informace. Nicméně všechna tato rozšíření sdílení základní princip, tedy analyzují jak se rozhodnout v případě, že hráč musí brát v úvahu rozhodnutí ostatních.

Výpočet Nashovy rovnováhy[editovat | editovat zdroj]

Pokud se jedná o nalezení Nashovy rovnováhy ve hře dvou hráčů v oboru ryzích strategií, můžeme použít zjednodušenou metodu. Celou hru zaneseme do matice a hledáme její sedlový bod. To znamená, že hledáme sloupcová maxima pro výplaty prvního hráče a řádková maxima ve výplatách druhého hráče. Tam kde se tyto body shodují nastává Nashova rovnováha. Pro výpočet rovnováhy více hráčů využijeme postupů lineárního programování. Výpočet Nashovy rovnováhy ve smíšených strategiích je úlohou nelineárního programování.[4].

Příklady Nashovy rovnováhy[editovat | editovat zdroj]

Koordinační hra[editovat | editovat zdroj]

Související informace naleznete také v článku Koordinační hra.
Koordinační hra
Druhý hráč zvolí strategii A Druhý hráč zvolí strategii B
První hráč zvolí strategii A 4, 4 1, 3
První hráč zvolí strategii B 3, 1 3, 3

Koordinační hra je klasickým příkladem hry dvou hráčů s možnými dvěma strategiemi. Hráči by měli spolupracovat a zvolit strategii A, protože jejich výplata bude v tomto případě nejvyšší, tedy 4. Další Nashova rovnováha nastává i v situaci, kdy oba zvolí strategii B. V tomto případě je ale výplata obou hráčů menší než v předchozí případě. I přesto však ani jeden z hráčů již nemůže jednostrannou změnou strategii nic získat.

Příkladem koordinační hry je rozhodování dvou firem s kompatibilními produkty mezi dvěma dostupnými technologiemi. Ty mají zvolit jednu z technologií za standard. Pokud se obě firmy shodnou na jedné technologii, mohou očekávat obchodní úspěch. Pokud se ale nedohodnou, skončí jejich produkty neúspěšně.

Při jízdě autem si musíme zvolit, zda pojedeme po levé nebo pravé straně silnice, a jedná se tedy také o koordinační hru. Pokud například hodnota 100 značí, že nedojde k nehodě a 0 značí nehodu, pak můžeme naši hru definovat následovně:

Jízda po silnici
Jízda po levé straně Jízda po pravé straně
Jízda po levé straně 100, 100 0, 0
Jízda po pravé straně 0, 0 100, 100

V tomto případě dostáváme opět dvě rovnovážná řešení v ryzích strategiích, tedy pokud se oba hráči rozhodnou pro jízdu vlevo nebo se oba rozhodnou pro jízdu vpravo. Pokud bychom uvažovali i smíšené strategie, pak k těmto dvěma strategií přidáme ještě jedno rovnovážné řešení, kde se každý z hráčů rozhodne s 50% pravděpodobností pro levou a s 50% pravděpodobností pro pravou stranu.

Vězňovo dilema[editovat | editovat zdroj]

Podrobnější informace naleznete v článku Vězňovo dilema.
Vězňovo dilema
Druhý hráč zradí Druhý hráč mlčí
První hráč zradí 1, 1 4, 1
První hráč mlčí 1, 4 3, 3

Vězňovo dilema podobná koordinační hra. Oba hráči se rozhodují, jestli zradit a přiznat se, nebo nevypovídat. V tomto případě se zde nachází pouze jedna Nashova rovnováha a oba hráči si zvolí možnost zradit, protože v jakékoliv situaci se vyplatí hráči změnit strategii z mlčení na zradu a vždy si svou situaci zlepší. Tento příklad ukazuje, že Nashova rovnováha není vždy Paretovsky optimální. Zde by se vyplatilo oběma hráčům mlčet a jejich celková situace by se zlepšila. Taková situace však není stabilní.

Konkurenční hra[editovat | editovat zdroj]

Konkurenční hra
Druhý hráč vybere '0' Druhý hráč vybere '1' Druhý hráč vybere '2' Druhý hráč vybere '3'
První hráč vybere '0' 0, 0 2, -2 2, -2 2, -2
První hráč vybere '1' -2, 2 1, 1 3, -1 3, -1
První hráč vybere '2' -2, 2 -1, 3 2, 2 4, 0
První hráč vybere '3' -2, 2 -1, 3 0, 4 3, 3

Hra dvou hráčů, kde oba současně vyberou celé číslo od nuly do tří a výhra každého z nich bude rovna menšímu z těchto dvou čísel. Navíc pokud jeden z hráčů vybere vyšší číslo než druhý hráč, musí druhému hráči odevzdat dva jeho body. Tato hra má pouze jednu ryzí Nashovu rovnováhu: oba hráči zvolí číslo 0 (podbarveno červeně). Pokud by zvolili jiné strategie, mohl by jeden z hráčů vždy zlepšit svou situaci snížením zvoleného čísla a taková situace by nebyla stabilní. Pokud bychom například zvolili jako výchozí situaci zeleně podbarvené políčko v tabulce nalevo, bylo by v zájmu prvního hráče vybrat nižší číslo a přesunout hru na fialově podbarvené políčko. Druhý hráč by pak také zvolil nižší číslo a přesunul by tak výsledek na modré políčko a takto se postupně dostaneme na červeně podbarvené políčko, kde již nastává Nashova rovnováha. Pokud bychom upravili pravidla tak, že oba hráči získají počet bodů rovný jejich volbě pouze pokud by zvolili stejné číslo a v opačném případě by nezískali nic, nastala by Nashova rovnováha ve čtyřech bodech na úhlopříčce.

Výskyt[editovat | editovat zdroj]

Pokud má hra jednu Nashovu rovnováhu a je hrána za určitých podmínek, pak hráči zvolí příslušné strategie. Nutné podmínky, které zaručí, že se tak stane jsou následující:

  1. Hráči se zachovají tak, aby maximalizovali svoji očekávanou výplatu.
  2. Hráči provádějí svá rozhodnutí bezchybně.
  3. Hráči jsou dostatečně inteligentní, aby dokázali odvodit správně řešení.
  4. Hráči znají plánované strategie všech ostatních hráčů.
  5. Hráči věří, že odchýlení se od jejich strategie nebude mít za následek odchýlení ostatních hráčů od jejich strategií.
  6. Nejenom že musí všichni hráči vědět, že ostatní hráči splňují tyto podmínky, ale i ostatní hráči musí vědět, že ostatní ví, že ostatní splňují tyto podmínky ...

Kde nejsou podmínky splněny[editovat | editovat zdroj]

Příklady problémů z teorie her, kde tyto podmínky nejsou splněny:

  1. První podmínka není splněna v případě her, které nesprávně popisují proměnné, které chce hráč maximalizovat. V tomto případě nemá hráč žádný důvod přijmout rovnovážnou strategii. Touto hrou může být vězňovo dilema za podmínky, že by hráči nebyli ochotni být uvězněni na doživotí.
  2. Úmyslné nebo neúmyslné nedokonalé provedení. Pokud bychom uvažovali dva bezchybné počítače hrající proti sobě, výsledkem by byla remíza. Pokud by ale nebyly naprosto bezchybné, tak ten, který by jako první udělal chybu, by prohrál.
  3. V mnoha případech není splněna třetí podmínka. Přestože Nashova rovnováha existuje, není její řešení známé kvůli složitosti. Toto můžeme pozorovat například u čínských šachů.
  4. Čtvrtá podmínka nemusí být splněna i přesto, že všichni hráči splňují všechny ostatní podmínky. Hráči chybně podceňují ostatní a přijímají takové strategie, kterými se snaží přimět ostatní k neracionálním rozhodnutím. Tato situace je uvažována zejména v závodech ve zbrojení.

Kde jsou podmínky splněny[editovat | editovat zdroj]

Vzhledem k těmto omezujícím podmínkám, kdy opravdu nastává Nashova rovnováha, je tento koncept málo používán v běžných situacích nebo pozorován při běžném vyjednávání. Nicméně nalézá uplatněni v ekonomických teoriích a evoluční biologii. V ekonomii jsou výplatou hráče peníze a v evoluční biologii přenos genů do další generace.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Nash equilibrium na anglické Wikipedii.

  1. Schelling, Thomas, The Strategy of Conflict, copyright 1960, 1980, Harvard University Press, ISBN 0-674-84031-3.
  2. P. Chiappori, S. Levitt, and T. Groseclose (2002), 'Testing Mixed-Strategy Equilibria When Players Are Heterogeneous: The Case of Penalty Kicks in Soccer'. American Economic Review 92, pp. 1138-51.
  3. VON AHN, Luis. Preliminaries of Game Theory [online]. [cit. 2008-11-07]. Dostupné online.  
  4. Dlouhý, Martin - Fiala, Petr Úvod do teorie her Oeconomica, 2007. [Cit. 01-01-2007]. ISBN 978-80-245-1273-0

Knihy o teorii her (anglicky)[editovat | editovat zdroj]

Původní Nashovy články (anglicky)[editovat | editovat zdroj]

  • Nash, John (1950) "Equilibrium points in n-person games" Proceedings of the National Academy of Sciences 36(1):48-49.
  • Nash, John (1951) "Non-Cooperative Games" The Annals of Mathematics 54(2):286-295.

Další reference (anglicky)[editovat | editovat zdroj]

  • Mehlmann, A. The Game's Afoot! Game Theory in Myth and Paradox, American Mathematical Society (2000).
  • Nasar, Sylvia (1998), "A Beautiful Mind", Simon and Schuster, Inc.

Externí odkazy[editovat | editovat zdroj]