Epsilon-rovnováha - Epsilon-equilibrium

v herní teorie, an epsilon-rovnováha, nebo téměř Nashova rovnováha, je a profil strategie že přibližně uspokojuje stav Nashova rovnováha. V Nashově rovnováze nemá žádný hráč motiv ke změně svého chování. V přibližné Nashově rovnováze je tento požadavek oslaben, aby byla možnost, že hráč může mít malou motivaci udělat něco jiného. To lze stále považovat za koncept adekvátního řešení, například za předpokladu zkreslení status quo. Tento koncept řešení může být upřednostňován před Nashequilibrium kvůli snadnějšímu výpočtu nebo alternativně kvůli možnosti, že ve hrách více než 2 hráčů nemusí být pravděpodobnosti spojené s přesnou Nashovou rovnováhou racionální čísla.^[1]

Definice

Existuje více než jedna alternativní definice.

Standardní definice

Daná hra a skutečný nezáporný parametr ${displaystyle varepsilon}$, a profil strategie se říká, že je${displaystyle varepsilon}$-rovnováha, pokud není možné, aby kterýkoli hráč získal více než ${displaystyle varepsilon}$ v očekávané výplaty jednostranným odklonem od jeho strategie.^[2]:45 Každý Nashova rovnováha je ekvivalentní s ${displaystyle varepsilon}$-rovnováha kde ${displaystyle varepsilon = 0}$.

Formálně, pojďme ${displaystyle G = (N, A = A_ {1} imes dotsb imes A_ {N}, ucolon A o R ^ {N})}$být ${displaystyle N}$- hráčská hra s akčními sadami ${displaystyle A_ {i}}$ pro každého hráče ${displaystyle i}$ a užitná funkce ${displaystyle u}$.Nechat ${displaystyle u_ {i}}$ označuje výplatu hráči ${displaystyle i}$ když profil strategie ${displaystyle s}$ se hraje ${displaystyle Delta _ {i}}$ být prostorem rozdělení pravděpodobnosti ${displaystyle A_ {i}}$Vektor strategií ${displaystyle sigma in Delta = Delta _ {1} imes dotsb imes Delta _ {N}}$ je ${displaystyle varepsilon}$-Nash rovnováha pro ${displaystyle G}$ -li

${displaystyle u_ {i} (sigma) geq u_ {i} (sigma _ {i} ^ {'}, sigma _ {- i}) - varepsilon}$ pro všechny ${displaystyle sigma _ {i} ^ {'} v Delta _ {i}, iin N.}$

Dobře podporovaná přibližná rovnováha

Následující definice^[3]ukládá přísnější požadavek, že hráč může čistě strategii přiřadit pouze pozitivní pravděpodobnost ${displaystyle a}$ pokud je výplata ${displaystyle a}$ očekával maximálně výplatu ${displaystyle varepsilon}$ menší než nejlepší výplata odezvy ${displaystyle x_ {s}}$ pravděpodobnost, že strategický profil ${displaystyle s}$ se hraje. Pro hráče ${displaystyle p}$ nechat ${displaystyle S _ {- p}}$ být strategickými profily hráčů jiných než ${displaystyle p}$; pro ${displaystyle sin S _ {- p}}$ a čistá strategie ${displaystyle j}$ z ${displaystyle p}$ nechat ${displaystyle js}$ být strategickým profilem, kde ${displaystyle p}$ hraje ${displaystyle j}$ a další hráči hrají ${displaystyle s}$.Nechat ${displaystyle u_ {p}}}$ být výplatou ${displaystyle p}$ když strategický profil ${displaystyle s}$ Požadavek lze vyjádřit vzorcem

${displaystyle sum _ {sin S _ {- p}} u_ {p} (js) x_ {s}> varepsilon + sum _ {sin S _ {- p}} u_ {p} (j's) x_ {s} Longrightarrow x_ { j '} ^ {p} = 0.}$

Výsledek

Existence a schéma polynomiálního času (PTAS) pro ε-Nashovy rovnováhy odpovídá otázce, zda existuje jeden pro ε-dobře podporované přibližné Nashovy rovnováhy,^[4] ale existence PTAS zůstává otevřeným problémem. Pro konstantní hodnoty ε jsou polynomiální časové algoritmy pro přibližné rovnováhy známé pro nižší hodnoty ε, než jsou známé pro dobře podporované přibližné rovnováhy. Pro hry s výplatami v rozmezí [0,1 ] a ε = 0,3393, ε-Nashovy rovnováhy lze vypočítat v polynomiálním čase^[5]U her s výplatami v rozsahu [0,1] a ε = 2/3 lze ε dobře podporované rovnováhy vypočítat v polynomiálním čase^[6]

Příklad

Pojem ε-rovnováhy je v teorii důležitý stochastické hry potenciálně nekonečného trvání. Existují jednoduché příklady stochastických her bez č Nashova rovnováha ale s rovnováhou ε pro libovolné ε přísně větší než 0.

Snad nejjednodušším příkladem je následující varianta Odpovídající haléře, navrhl Everett. Hráč 1 skrývá penny a hráč 2 musí hádat, zda má heads up nebo tails. Pokud hráč 2 uhádne správně, vyhraje penny od hráče 1 a hra končí. Pokud hráč 2 nesprávně odhadne, že penny směřuje nahoru, hra končí nulovou výplatou pro oba hráče. Pokud nesprávně odhadne, že je to ocas nahoru, hra opakování. Pokud hra bude pokračovat navždy, výplata pro oba hráče je nulová.

Vzhledem k parametru ε > 0, libovolné profil strategie kde hráč 2 hádá heads up s pravděpodobností ε a ocas nahoru s pravděpodobností 1 -ε (v každé fázi hry a nezávisle na předchozích fázích) je ε-rovnováha pro hru. Očekávaná výplata hráče 2 za strategický profil je alespoň 1 -ε. Je však snadno vidět, že pro hráče 2 existuje nostrategie, která může zaručit očekávanou výplatu přesně 1. Proto hra nemá Nashova rovnováha.

Dalším jednoduchým příkladem je konečně opakované dilema vězně pro období T, kde je průměrná výplata za období T. Jediný Nashova rovnováha této hry je zvolit Defekt v každém období. Nyní zvažte dvě strategie sýkorka a pochmurná spoušť. I když ani jeden sýkorka ani pochmurná spoušť jsou Nashovy rovnováhy pro hru, oba jsou ${displaystyle epsilon}$-rovnováha pro některé pozitivní ${displaystyle epsilon}$. Přijatelné hodnoty ${displaystyle epsilon}$ závisí na výplatách základní hry a na počtu T období.

V ekonomii je koncept a čistá strategie epsilon-rovnováha se používá, když je přístup smíšené strategie považován za nereálný. V čisté strategii epsilon-equilibrium si každý hráč vybere čistou strategii, která je v epsilonu jeho nejlepší čisté strategie. Například v Bertrand – Edgeworthův model, kde neexistuje rovnováha čisté strategie, může existovat rovnováha čisté strategie epsilon.

Reference

Vložené citace

Zdroje

• H Dixone Přibližná Bertrandova rovnováha v replikovaném průmyslu, Review of Economic Studies, 54 (1987), strany 47–62.
• H. Everett. "Rekurzivní hry". V H.W. Kuhn a A.W. Tucker, redaktoři. Příspěvky k teorii her, sv. III, svazek 39 Annals of Mathematical Studies. Princeton University Press, 1957.
• Leyton-Brown, Kevin; Shoham, Yoav (2008), Základy teorie her: Stručný multidisciplinární úvod, San Rafael, CA: Morgan & Claypool Publishers, ISBN  978-1-59829-593-1. 88stránkový matematický úvod; viz část 3.7. Zdarma online na mnoha univerzitách.
• R. Radner. Hromadné chování v nespolupracujících epsilonových rovnováhách oligopolů s dlouhými, ale konečnými životy, Journal of Economic Theory, 22, 121–157, 1980.
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagentní systémy: Algoritmické, herně teoretické a logické základy, New York: Cambridge University Press, ISBN  978-0-521-89943-7. Komplexní reference z výpočetní perspektivy; viz část 3.4.7. Stahovatelné zdarma online.
• S.H. Tijs. Nashovy rovnováhy pro nespolupracující n-osobní hry v normální formě, SIAM recenze, 23, 225–237, 1981.