Nashova rovnováha

From Simulace.info
Revision as of 22:43, 20 June 2012 by Xbarr10 (talk | contribs) (→‎Příklad 3: Smíšené strategie)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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é strategie, zatímco ostatní hráč(i) ano, jeho výhra se sníží nebo v nejlepším případě 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 s konstantním součtem 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á (právě jedno) 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, eliminace dominovaných strategií

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. (První řádek je pro prvního hráče lepší při každém možném rozhodnutí protihráče.) 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: Hledání sedlového bodu

Nalezněte optimální strategie obou hráčů a Nashovu rovnováhu pro následující jednomaticovou hru:

α β γ
a 0 1 2
b -1 3 -2
c -2 -7 5

Prostor strategií prvního hráče je dán vektorem (a, b, c), prostoj strategií druhého hráče vektorem (α, β, γ). Výplatní matice určuje výplaty prvního hráče, výplaty druhého hráče jsou opačné (jde o hru s nulovým součtem).

Řešení

Žádný ze slouců ani řádků není dominován, řešení zkusíme nalézt pomocí sedlového bodu (maximum ve sloupci, minimum v řádku). Maximum ve sloupci budu značit červenou barvou, minimum v řádku zeleným rámečkem.

  • Maximum v prvním sloupci (optimální reakce prvního hráče, pokud druhý hráč zahraje strategii α) je 0, označím ji tedy červeně.
  • Maximum v druhém sloupci (optimální reakce prvního hráče, pokud druhý hráč zahraje strategii β) je 3, označím ji tedy červeně.
  • Maximum ve třetím sloupci (optimální reakce prvního hráče, pokud druhý hráč zahraje strategii γ) je 5, označím ji tedy červeně.
  • Minimum v prvním řádku (optimální reakce druhého hráče, pokud první hráč zahraje strategii a) je 0, označím zeleným rámečkem.
  • Minimum v druhém řádku (optimální reakce druhého hráče, pokud první hráč zahraje strategii b) je -2, označím zeleným rámečkem.
  • Minimum v druhém řádku (optimální reakce druhého hráče, pokud první hráč zahraje strategii c) je -7, označím zeleným rámečkem.
α β γ
a 0 1 2
b -1 3 -2
c -2 -7 5

V buňce, kde se řádkové minimum a sloupcové maximum setkají, leží sedlový bod, a tedy i Nashova rovnováha.

Ve hře s konstantním součtem mohou nastat následující situace:

  • Existuje jeden sedlový bod, potom Nashova rovnováha leží v tomto sedlovém bodě.
  • Existuje více sedlových bodů o stejné hodnotě, potom Nashova rovnováha leží v každém z nich.
  • Neexistuje sedlový bod, v tomto případě existuje pouze smíšené řešení.

Příklad 3: Smíšené strategie

Nashova rovnováha ve smíšených strategiích a skutečné hry
fotbalový brankář
Přestože se smíšené řešení může zdát jako teoretický, prakticky nevyužitelný koncept (proč hrát strategie s nižším očekávaným užitkem), je možné jej jednoduše aplikovat i na reálné hry, potažmo reálný svět.

M. Dlouhý[1] uvádí jako příklad použití smíšené strategie jednoduchou hru Kámen, nůžky, papír. Lze spočítat, že rovnovážná strategie je pro každého hráče (kámen, nůžky, papír) = (0.33,0.33,0.33), neboli střídat se stejnou pravděpodobností všechny možnosti. Odchýlení od této strategie (zejména v opakované hře) umožňuje protihráči přizpůsobit se (tedy například reagovat na časté používání kamenu častějším používáním papíru).

Neobvyklé spojení teorie her s analýzou reálných dat nabízí paper (Chiappori et al., 2002)[3] o fotbalových penaltách jakožto koordinačné-antikoordinační hře. Vychází z premisy, že útočník - pravák je při pokutovém kopu schopen lépe vystřelit do levé strany branky (má vyšší užitek, jelikož přesná, tvrdá rána má vyšší pravděpodobnost úspěchu). Kdyby ale střílel pouze do levé části brány, brankář by na střely byl připraven. Proto musí strany střídat (smíšená strategie). Pro brankáře platí podobné rozhodování.

Nalezněte optimální strategie obou hráčů a Nashovu rovnováhu pro následující jednomaticovou hru:

α β γ
a 3 5 -8
b -2 -1 5
c -4 -2 3

Prostor strategií prvního hráče je dán vektorem (a, b, c), prostoj strategií druhého hráče vektorem (α, β, γ). Výplatní matice určuje výplaty prvního hráče, výplaty druhého hráče jsou opačné (jde o hru s nulovým součtem).

Řešení

Na první pohled je patrné že řádek c je dominován řádkem b. (racionálně uvažující první hráč tuto možnost nikdy nezvolí, protože strategie b mu ve všech případech přinese větší užitek). Pro zjednodušení výpočtu tedy budeme brát v úvahu pouze první dva řádky, v nichž jistě leží řešení.

Pokusíme se nalézt řešení pomocí sedlového bodu, postup je stejný jako u předchozího příkladu.

α β γ
a 3 5 -8
b -2 -1 5

Matice zjevně neobsahuje sedlový bod (žádný její prvek není zároveň řádkovým minimem a sloupcovým maximem) a nedy ani žádné řešení v ryzích strategiích.

Nalezení řešení ve smíšených strategiích

Smíšené strategie je možné nalézt pomocí metod lineárního programování, a to buď ručně, například pomocí simplexového algoritmu nebo (v prípadě max 2 sloupců nebo řádků) graficky, nebo počítačovým programem (Lingo, MPL, Excel Solver, …). Většina metod vyžaduje na vstupu nezáporná čísla, proto matici upravíme přičtením konstanty (nejnižšího prvku, v tomto případě 8), což řešení nezmění (jde o strategicky ekvivalentní hry).

α β γ
a 11 13 0
b 6 7 13

Předpis pro účelovou funkci a omezující podmínky je dán následující tabulkou:

Nalezení Nashovy rovnováhy ve smíšených strategiích[1]

Účelová funkce (minimalizovat)
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 p_1+p_2+...+p_m}

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_1p_1+a_2_1p_m+...+a_m_1p_m\ge0}
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 ...}
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_np_1+a_2_np_m+...+a_m_np_m\ge0}

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 p_i \ge 0}    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=1,2,...m}

nebo

Účelová funkce (maximalizovat)
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 q_1+q_2+...+q_n}

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_1q_1+a_1_2q_n+...+a_1_nq_n\le0}
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 ...}
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_m_1q_1+a_m_2q_2+...+a_m_nq_n\le0}

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 q_j \ge 0}    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 j=1,2,...n}

Úlohy jsou duálně sdružené, takže stačí vypočítat pouze jednu z nich,proměnné z druhé úlohy jsou potom duální proměnné z první (a naopak).

Pro zjištění strategie je nutné proměnné p nebo q vydělit hodnotou účelové funkce.

Pro náš příklad je výpočetně lepší zvolit druhou možnost, protože vede ke dvěma omezujícím podmínkám (+ jedné na nezápornost), zatímco první ke třem. Účelová funkce je potom:
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 q_1+q_2+q_3} (minimalizovat)
a omezují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 11q_1+13q_2+0q_3\le0}
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 11q_1+13q_2+0q_3\le0}
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 q_j \ge 0}    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 j=1,2,...n}

Po vyřešení úlohy (například v doplňku Řešitel pro MS Excel 2010: File:Nash equilibrium pr3.xlsx) dostáváme následující rovnovážné strategie: (a, b)=(52%, 48%) pro prvního hráče a (α, β, γ)=(32%, 27%, 41%) pro druhého hráče (první hráč by měl hrát v 52% případů a, v 48% případů b). Tyto strategie je možné zachytit i graficky:

smisena strategie
Smíšená strategie

Cenu hry je možné určit jako součin pravděpodobností jednotlivých prvků s výplatní maticí. V tomto případě vychází 8,032. Od tohoto výsledku je nutné odečíst konstantu 8, kterou jsme k výplatní matici přičetli v prvním kroku. Výsledná cena hry je potom 0,032, což znamená, že hra je mírně nespravedlivá ve prospěch prvního hráče.

Otázky a příklady k procvičení

  1. Zajišťuje Nashova rovnováha automaticky pareto-optimální řešení?
  2. Kolik nashových rovnovážných řešení může existovat v maticové hře?
      a. žádné
      b. 0 - počet prvků
      c. pouze 1
      d. 1 - počet prvků
  3. Najděte Nashovo rovnovážné řešení v prvním příkladu (Vězňovo dilema) bez vyškrtávání dominovaných sloupců - pomocí sedlových bodů (tip: Je použita jiná notace než v druhém příkladu, je proto nutné hledat maxima ve sloupcích i řádcích, ale vždy ve výplatní funkci správného hráče)
  4. Ukažte, že při uvažování dominovaného řádku se řešení třetího příkladu nezmění.
  5. Najděte Nashova rovnovážná řešení pro následující hry:
α β γ
a -3 8 0
b 3 10 1
c -2 4 -7
α β γ
a 8 0 1
b 99 0 -99
c 1 -8 16
α β γ
a 1 4 1
b 0 -3 0
c 1 9 1
α β γ
a 3 -2 1
b 4 -2 -3
c -1 3 8
  1. Sestavte výplatní matici pro hru Kámen, nůžky, papír (diskutováno v infoboxu) a nalezněte Nashovo rovnovážné řešení hry.

Reference

  1. ↑ 1.0 1.1 1.2 1.3 1.4 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
  3. ↑ Chiappori, P. A.; Levitt, S. and Groseclose, T.: Testing mixed-strategy equilibria when players are heterogeneous: The case of penalty kicks in soccer In: The American Economic Review Vol. 92, No. 4 (Sep., 2002), pp. 1138-1151, dostupné z http://pricetheory.uchicago.edu/levitt/Papers/ChiapporiGrosecloseLevitt2002.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
Retrieved from "http://www.simulace.info/index.php?title=Nash_equilibrium/cs&oldid=1493"