Difference between revisions of "Nash equilibrium/cs"

From Simulace.info
Jump to: navigation, search
(Příklad 1: Vězňovo dilema)
(Vlastnosti Nashovy rovnováhy)
Line 8: Line 8:
 
Z definice vyplývají následující vlastnosti Nashovy rovnováhy, které jsou užitečné pro její nalezení a interpretaci:
 
Z definice vyplývají následující vlastnosti Nashovy rovnováhy, které jsou užitečné pro její nalezení a interpretaci:
 
* Nashova rovnováha nikdy neleží v '''silně''' dominovaném sloupci.
 
* Nashova rovnováha nikdy neleží v '''silně''' dominovaném sloupci.
 +
* Pokud má hra [[Saddle point/cs|sedlový prvek]] (sedlové prvky), pak rovnováha leží v tomto prvku (těchto prvcích).
 
* Nashova rovnováha není (automaticky) [[Parreto efficiency/cs|Pareto-efektivní]]. Klasickým případem je [[Prisoner's dilemma/cs|hra vězňovo dilema]], ve které se hráči bez možnosti kooperace racionálně rozhodnou pro řešení, které je pro oba z hráčů horší, než jiný možný výsledek hry.
 
* Nashova rovnováha není (automaticky) [[Parreto efficiency/cs|Pareto-efektivní]]. Klasickým případem je [[Prisoner's dilemma/cs|hra vězňovo dilema]], ve které se hráči bez možnosti kooperace racionálně rozhodnou pro řešení, které je pro oba z hráčů horší, než jiný možný výsledek hry.
 
* Každá hra '''s konstantním součtem''' má rovnovážné řešení ve smíšených strategiích. (Ryzí strategie jsou podmnožinou smíšených strategií).<ref name=dlouhy/>
 
* Každá hra '''s konstantním součtem''' má rovnovážné řešení ve smíšených strategiích. (Ryzí strategie jsou podmnožinou smíšených strategií).<ref name=dlouhy/>

Revision as of 11:32, 19 June 2012

Jedním ze základních úkolů teorie her je popsání optimálních strategií jednotlivých hráčů, respektive výsledku hry (za předpokladu racionálního chování hráčů). Vhodným nástrojem je nalezení Nashovy rovnováhy.

Definice

Nashova rovnováha je takové řešení, ve kterém platí, že pokud se jeden z hráčů nebude držet své optimální strategie, zatímco jeho soupeř (soupeři) ano, jeho výhra se sníží, nebo zůstane stejná.[1]

Vlastnosti Nashovy rovnováhy

Z definice vyplývají následující vlastnosti Nashovy rovnováhy, které jsou užitečné pro její nalezení a interpretaci:

  • Nashova rovnováha nikdy neleží v silně dominovaném sloupci.
  • Pokud má hra sedlový prvek (sedlové prvky), pak rovnováha leží v tomto prvku (těchto prvcích).
  • Nashova rovnováha není (automaticky) Pareto-efektivní. Klasickým případem je hra vězňovo dilema, ve které se hráči bez možnosti kooperace racionálně rozhodnou pro řešení, které je pro oba z hráčů horší, než jiný možný výsledek hry.
  • Každá hra s konstantním součtem má rovnovážné řešení ve smíšených strategiích. (Ryzí strategie jsou podmnožinou smíšených strategií).[1]
  • Každá hra dvou hráčů má alespoň jedno rovnovážné řešení [1][2]

Řešené příklady

V následujících kapitolách budou představeny metody hledání Nashovy rovnováhy, počínaje nejjednoduššími, použitelnými jen ve specifických případech, po lehce složitější univerzální metody.

Příklad 1: Vězňovo dilema

Najděte Nashovu rovnováhu ve hře vězňovo dilema, jejíž výplatní matice je dána takto: Pokud se ani jeden z vězňů nepřizná, dostane každý trest 2 roky. Pokud se přizná jeden z vězňů, stráví ve vězení jen jeden rok, ale jeho spolupachatel 10. Pokud se přiznají oba hráči, stráví každý ve vězení 10 let.

Přiznat Nepřiznat
Přiznat -5, -5 -1, -10
Nepřiznat -10, -1 -2, -2

Řešení

Využijeme znalosti, že rovnovážné řešení nikdy neleží v silně (ostře) dominovaném řádku či sloupci. Pro prvního hráče první řádek (přiznat) silně dominuje druhý řádek (nepřiznat). Tento řádek tedy můžeme vyškrtnout. Obdobně pro druhého hráče je druhý sloupec dominován prvním.

Přiznat Nepřiznat
Přiznat -5, -5 -1, -10
Nepřiznat -10, -1 -2, -2

V šedě označených buňkách tabulky tedy Nashovo rovnovážné řešení ležet nemůže. Vzhledem k tomu, že každá hra má alespoň jedno rovnovážné řešení, toto řešení je dáno volbou "Přiznat" obou hráčů a tedy výplatní hodnotou (-5, -5).

Ve hrách, které obsahují více nedominovaných řádků či sloupců tento postup k nalezení Nashovy rovnováhy nestačí. Neuvažování dominovaných prvků ale může ulehčit postup v případě dalších metod.

Příklad 2: Vězňovo dilema

Řešení

Další příklady

Reference

  1. 1.0 1.1 1.2 DLOUHÝ, Martin. Úvod do teorie her. 2., přepracované vydání Praha: Oeconomica, 2009, 119 s. ISBN 978-80-245-1609-7.
  2. NASH, John F. Equilibrium Points in n-Person Games. In: Proceedings of the National Academy of Sciences of the United States of America, Vol.36, No. 1. Jan 15, 1950. Dostupné z: http://courses.engr.illinois.edu/ece586/TB/Nash-NAS-1950.pdf

Doplňující literatura

  • Ben Polak, Game Theory (Yale University: Open Yale Courses), http://oyc.yale.edu/ (Accessed June 17, 2012). License: Creative Commons BY-NC-SA, lectures 4-8