V teorii her je Nashova rovnováha (pojmenovaná po Johnu Forbesovi Nashovi, který ji navrhl) jakýmsi konceptem řešení hry zahrnující dva nebo více hráčů, kde žádný hráč nemá co získat jednostrannou změnou pouze své vlastní strategie. Pokud si každý hráč zvolil strategii a žádný hráč nemůže mít prospěch ze změny své strategie, zatímco ostatní hráči udržují tu svou beze změny, pak aktuální sada strategických voleb a odpovídající výplaty představují Nashovu rovnováhu.
Koncept Nashovy rovnováhy (NE) není pro Nashe zrovna originální (např. Antoine Augustin Cournot ukázal, jak najít to, co dnes nazýváme Nashovou rovnováhou Cournotovy duopolní hry). Někteří autoři jej proto označují jako „Cournotovu-Nashovu rovnováhu“ (nebo jako „Nashovu-Cournotovu rovnováhu“). Nash však poprvé ukázal ve své disertační práci Nespolupracující hry (1950), že Nashova rovnováha musí existovat pro všechny konečné hry s libovolným počtem hráčů. Až do Nashe to bylo dokázáno pouze pro hry dvou hráčů s nulovým součtem Johnem von Neumannem a Oskarem Morgensternem (1947).
Nechť (S, f) je hra, kde S je sada strategických profilů a f je sada výplatních profilů. Nechť je strategický profil všech hráčů s výjimkou hráče . Když každý hráč zvolí strategii vedoucí ke strategickému profilu, pak hráč získá výplatu . Všimněte si, že výplata závisí na zvoleném strategickém profilu, tj. na strategii zvolené hráčem a také na strategiích zvolených všemi ostatními hráči. Strategický profil je Nashova rovnováha (NE) pokud žádná odchylka ve strategii jednoho hráče není zisková, to znamená pokud pro všechny
Hra může mít čistou strategii NE nebo NE ve svém smíšeném rozšíření (výběr čisté strategie stochasticky s pevnou frekvencí). Nash dokázal, že pokud povolíme smíšené strategie (hráči volí strategie náhodně podle předem přiřazených pravděpodobností), pak každá n-player hra, ve které si každý hráč může vybrat z konečně mnoha strategií připouští alespoň jednu Nashovu rovnováhu.
Jak je uvedeno výše, nechť je smíšený strategický profil všech hráčů s výjimkou hráče . Můžeme definovat nejlepší odpověď korespondence pro hráče , . je vztah z množiny všech rozdělení pravděpodobnosti nad soupeře hráče profily na sadu hráče ‚s strategií, jako že každý prvek
je nejlepší odpověď na . Definovat
Jeden může použít Kakutani pevný bod věta dokázat, že má pevný bod. To znamená, že je taková, že . Vzhledem k tomu, představuje nejlepší odezvu pro všechny hráče na , Existence pevného bodu dokazuje, že tam je nějaká strategie nastavena, která je nejlepší odezvou na sebe. Žádný hráč by mohl udělat lépe odchýlením, a to je proto Nash rovnováhy.
Vezměme si následující hru pro dva hráče: oba hráči si současně vyberou celé číslo od 0 do 3. Oba hráči pak vyhrají menší ze dvou čísel v bodech. Navíc, pokud si jeden hráč vybere větší číslo než druhý, pak s/on musí dát dva body tomu druhému. Tato hra má unikátní Nashovu rovnováhu: oba hráči si vyberou 0. Jakákoli jiná volba strategií může být vylepšena, pokud jeden z hráčů sníží své číslo o jeden nižší než číslo druhého hráče. V tabulce vlevo, například, když se začíná na zeleném čtverci, je v zájmu hráče 1 přesunout se na fialový čtverec výběrem menšího čísla, a je v zájmu hráče 2 přesunout se na modrý čtverec výběrem menšího čísla. Pokud je hra upravena tak, že oba hráči vyhrají jmenovanou částku, pokud si oba vyberou stejné číslo, a jinak nevyhrají nic, pak existují 3 Nashovy rovnováhy.
Koordinační hra je klasická (symetrická) hra pro dva hráče, strategická hra pro dva, s výplatní maticí zobrazenou vpravo, kde jsou výplaty podle A>C a D>B. Hráči by tak měli spolupracovat na jedné ze dvou strategií, aby získali vysokou výplatu. Hráči ve hře se musí dohodnout na jedné ze dvou strategií, aby získali vysokou výplatu. Pokud hráči nesouhlasí, je odměněna nižší výplata. Příkladem koordinační hry je nastavení, kdy jsou dvě technologie dostupné dvěma firmám s kompatibilními produkty a ty si musí zvolit strategii, aby se staly tržním standardem. Pokud se obě firmy dohodnou na zvolené technologii, očekávají se vysoké prodeje pro obě firmy. Pokud se firmy nedohodnou na standardní technologii, výsledkem je jen málo prodejů. Obě strategie jsou Nashovou rovnováhou hry.
Řízení na silnici a nutnost rozhodnout se buď jet vlevo, nebo jet vpravo od silnice, je také koordinační hra. Například s payoffs 100 znamená žádnou havárii a 0 znamená havárii, koordinační hra může být definována pomocí následující výplatní matice:
V tomto případě existují dvě čistě strategické Nashovy rovnováhy, kdy se oba rozhodnou buď řídit vlevo nebo vpravo. Pokud připustíme smíšené strategie (kde je čistá strategie zvolena náhodně, s výhradou nějaké fixní pravděpodobnosti), pak existují tři Nashovy rovnováhy pro stejný případ: dvě jsme viděli z čistě strategické formy, kde jsou pravděpodobnosti (0%,100%) pro hráče jedna, (0%, 100%) pro hráče dva; a (100%, 0%) pro hráče jedna, (100%, 0%) pro hráče dva, resp. Přidáme další, kde jsou pravděpodobnosti pro každého hráče (50%, 50%).
Dilema vězně má stejnou výplatní matici, jak je znázorněno v Koordinační hře, ale nyní C > A > D > B. Protože C > A a D > B, každý hráč zlepšuje svou situaci přechodem od strategie #1 ke strategii #2, bez ohledu na to, jak se druhý hráč rozhodne. Dilema vězně má tedy jednu Nashovu rovnováhu: oba hráči volí strategii #2 („zrada“). Co z tohoto dlouho dělá zajímavý případ ke studiu je skutečnost, že D < A („oba zrada“ je globálně horší než „oba zůstávají loajální“). Globální optimální strategie je nestabilní; není to rovnováha.
Jak řekl Ian Stewart, „racionální rozhodnutí někdy nejsou rozumná!“
Nashova rovnováha ve výplatní matici
Existuje jednoduchý numerický způsob, jak identifikovat Nash Equilibria na Payoff Matrix. Je to užitečné zejména ve hrách pro dvě osoby, kde hráči mají více než dvě strategie. V tomto případě se formální analýza může stát příliš dlouhou. Toto pravidlo neplatí v případě, kdy jsou zajímavé smíšené (stochastické) strategie. Pravidlo zní takto: pokud první číslo výplaty v dupletu buňky je maximum sloupce buňky a pokud druhé číslo je maximum řádku buňky – pak buňka představuje Nashovu rovnováhu.
Toto pravidlo můžeme aplikovat na matici 3×3:
Pomocí tohoto pravidla můžeme velmi rychle (mnohem rychleji než při formální analýze) zjistit, že buňky Nashovy Equlibrie jsou (B,A), (A,B) a (C,C). Pro buňku (B,A) je totiž 40 maximem prvního sloupce a 25 maximem druhého řádku. Pro (A,B) je 25 maximem druhého sloupce a 40 maximem prvního řádku. Totéž platí pro buňku (C,C). Pro ostatní buňky buď jeden, nebo oba dupletové členy nejsou maximem odpovídajících řádků a sloupců.
Tím pádem je zřejmá skutečná mechanika hledání rovnovážných buněk: najděte maximum sloupce a zkontrolujte, zda druhý člen n-tice má maximum řádku. Pokud ano – máte Nashovu rovnováhu. Zkontrolujte tímto způsobem všechny sloupce, abyste našli všechny NE buňky. Matice NxN může mít mezi 0 a N čistou strategii Nashovy rovnováhy.
Pojem stability, užitečný v analýze mnoha druhů rovnováhy, může být aplikován i na Nashovu rovnováhu.
Nashova rovnováha pro smíšenou strategickou hru je stabilní, pokud malá změna (konkrétně infinitezimální změna) pravděpodobnosti pro jednoho hráče vede k situaci, kdy platí dvě podmínky:
Pokud jsou oba tyto případy splněny, pak se hráč s malou změnou ve své smíšené strategii okamžitě vrátí k Nashově rovnováze. O rovnováze se říká, že je stabilní. Pokud podmínka jedna neplatí, pak je rovnováha nestabilní. Pokud platí pouze podmínka jedna, pak je pravděpodobné, že pro hráče, který se změnil, bude existovat nekonečný počet optimálních strategií. John Nash ukázal, že druhá situace nemůže nastat v řadě dobře definovaných her.
Ve výše uvedeném příkladu „driving game“ jsou stabilní i nestabilní rovnováhy. Rovnováhy zahrnující smíšené strategie se 100% pravděpodobností jsou stabilní. Pokud jeden z hráčů mírně změní své pravděpodobnosti, budou oba v nevýhodě a jeho soupeř nebude mít důvod měnit svou strategii. Rovnováha (50%,50%) je nestabilita. Pokud jeden z hráčů změní své pravděpodobnosti, pak má druhý hráč okamžitě lepší strategii buď (0%, 100%) nebo (100%, 0%).
Stabilita je klíčová v praktických aplikacích Nashovy rovnováhy, protože smíšená strategie každého hráče není dokonale známá, ale musí být odvozena ze statistického rozložení jeho akcí ve hře. V tomto případě je velmi nepravděpodobné, že by nestabilní rovnováha vznikla v praxi, protože každá minutová změna proporcí každé pozorované strategie povede ke změně strategie a rozpadu rovnováhy.
Všimněte si, že stabilita rovnováhy souvisí se stabilitou strategie, ale liší se od ní.
Pokud má hra jedinečnou Nashovu rovnováhu a hraje se mezi hráči s určitými charakteristikami, pak je pravda (z definice těchto charakteristik), že bude přijata sada strategie NE. Dostatečné podmínky, které musí hráči splnit, jsou:
Nejsou-li splněny podmínky
Příklady problémů teorie her, ve kterých tyto podmínky nejsou splněny:
Jsou-li splněny podmínky
Vzhledem k omezeným podmínkám, za kterých může být NE skutečně pozorováno, jsou zřídkakdy považovány za vodítko pro každodenní chování, nebo jsou pozorovány v praxi při vyjednávání s lidmi. Nicméně jako teoretický koncept v ekonomii a evoluční biologii má NE vypovídací schopnost. Výhodou v ekonomii jsou peníze a v evoluční biologii přenos genů je obojí základní hranicí přežití. Agenti, kteří je z jakéhokoli důvodu nedokážou maximalizovat, budou vytlačeni z trhu nebo prostředí, kterým je připisována schopnost testovat všechny strategie. Tento závěr je vyvozen z výše uvedené teorie „stability“. V těchto situacích byl předpoklad, že pozorovaná strategie je ve skutečnosti NE, často potvrzen výzkumem.[nutná verifikace]
Normal-form game · Extensive-form game · Cooperative game · Information set · Preference
Nashova rovnováha · Podherní dokonalost · Bayesovská-Nashova · Dokonalá Bayesovská · Třesoucí se ruka · Správná rovnováha · Epsilonová rovnováha · Korelovaná rovnováha · Sekvenční rovnováha · Kvazidokonalá rovnováha · Evolučně stabilní strategie · Riziková dominance · Paretova efektivita
Dominantní strategie · Pure strategy · Mixed strategy · Tit for tat · Grim trigger · Collusion · Backward induction
Symetrická hra · Perfektní informace · Dynamická hra · Sekvenční hra · Opakovaná hra · Signalizační hra · Levné povídání · Hra s nulovým součtem · Mechanismus design · Vyjednávací problém · Stochastická hra · Nontransitivní hra · Globální hry
Vězeňské dilema · Cestovatelské dilema · Koordinační hra · Kuře · Dobrovolnické dilema · Aukce dolarů · Bitva pohlaví · Lov jelenů · Odpovídající mince · Hra s ultimátem · Menšinová hra · Kámen-nůžky-papír · Pirátská hra · Hra s diktátorem · Hra s veřejnými statky · Blotto hry ·Válka opotřebení ·El Farol Bar problém ·Stříhání dortů ·Cournot hra ·Deadlock ·Dinerovo dilema ·Hádej 2/3 průměru ·Kuhn poker ·Nash vyjednávací hra ·Screening hra ·Signalizační hra ·Trust hra ·Princezna a monstrum hra
Minimaxova věta · Purifikační věta · Folková věta · Zjevovací princip · Arrowova věta o nemožnosti