Nejlepší reakce - Best response
v herní teorie, nejlepší odpověď je strategie (nebo strategie), která produkuje nejpříznivější výsledek pro hráče, přičemž strategie ostatních hráčů jsou uvedeny (Fudenberg & Tirole 1991, str. 29; Gibbons 1992, s. 33–49). Koncept nejlepší reakce je ústředním bodem John Nash nejznámější příspěvek, Nashova rovnováha, bod, ve kterém si každý hráč ve hře vybral nejlepší odpověď (nebo jednu z nejlepších odpovědí) na strategie ostatních hráčů (Nash 1950 ).
Korespondence

Reakce korespondence, známé také jako korespondence s nejlepší odpovědí, se používají jako důkaz existence smíšená strategie Nashovy rovnováhy (Fudenberg & Tirole 1991, Oddíl 1.3.B; Osborne & Rubinstein 1994, Oddíl 2.2). Odpovídající reakce nejsou od té doby „reakčními funkcemi“ funkce musí mít na jeden argument pouze jednu hodnotu a u některých strategií oponentů bude nedefinováno mnoho reakčních korespondencí, tj. svislá čára. Jeden vytvoří korespondenci , pro každého hráče ze sady profilů strategií soupeře do sady strategií hráče. Takže pro jakoukoli danou sadu oponentových strategií , představuje hráče i nejlepší odpovědi na .

Odpovědi na korespondenci pro všechny 2x2 normální forma hry lze nakreslit pomocí čára pro každého hráče v a jednotka čtverec strategie prostor. Na obrázcích 1 až 3 jsou uvedeny nejlepší korespondence odpovědí pro lov jelenů hra. Tečkovaná čára na obrázku 1 ukazuje optimální pravděpodobnost tento hráč Y hraje 'Stag' (v ose y), jako funkce pravděpodobnosti, že hráč X hraje Stag (zobrazeno v ose x). Na obrázku 2 ukazuje tečkovaná čára optimální pravděpodobnost, že hráč X bude hrát ‚Stag '(zobrazeno na ose x), jako funkce pravděpodobnosti, že hráč Y bude hrát Stag (zobrazeno na ose y). Všimněte si, že obrázek 2 zobrazuje nezávislý a Odezva proměnné v protilehlých osách k těm, které se běžně používají, takže může být superponováno na předchozí graf, aby se zobrazila Nashovy rovnováhy v bodech, kde se nejlepší reakce obou hráčů shodují na obrázku 3.
Existují tři charakteristické tvary korespondence reakce, jeden pro každý ze tří typů symetrický Hry 2x2: koordinační hry, diskoordinační hry a hry s převládajícími strategiemi (triviální čtvrtý případ, kdy jsou výplaty vždy stejné pro oba tahy, ve skutečnosti není teoretickým problémem hry). Jakákoli výplatní symetrická hra 2x2 bude mít jednu z těchto tří forem.
Koordinační hry
Hry, ve kterých hráči dosáhnou nejvyššího skóre, když oba hráči zvolí stejnou strategii, například lov jelenů a bitva pohlaví jsou nazývány koordinační hry. Tyto hry mají reakční korespondence stejného tvaru jako na Obrázku 3, kde je jedna Nashova rovnováha v levém dolním rohu, další v pravém horním rohu a míchání Nashe někde podél úhlopříčky mezi ostatními dvěma.
Antikoordinační hry

Hry jako kuřecí hra a hra jestřáb-holubice ve kterých hráči dosáhnou nejvyššího skóre, když zvolí opačné strategie, tj. diskoordinované, se nazývají antikoordinační hry. Mají reakční korespondenci (obrázek 4), která se protíná opačným směrem než koordinační hry, se třemi Nashovými rovnováhami, jednou v každém z levého horního a pravého dolního rohu, kde jeden hráč zvolí jednu strategii, druhý hráč zvolí opačnou strategii. Třetí Nashova rovnováha je a smíšená strategie který leží podél úhlopříčky od levého dolního k pravému hornímu rohu. Pokud hráči neví, který z nich je který, pak je smíšený Nash evolučně stabilní strategie (ESS), protože hra je omezena na diagonální čáru zleva dole do pravého horního rohu. Jinak nekorelovaná asymetrie se říká, že existuje, a rohové Nashovy rovnováhy jsou ESS.

Hry s ovládanými strategiemi

Hry s dominoval strategie mají reakční korespondenci, která se protíná pouze v jednom bodě, který bude buď v levém dolním, nebo v pravém horním rohu ve výplatních symetrických hrách 2x2. Například v single-play vězňovo dilema „tah„ Spolupracovat “není optimální pro jakoukoli pravděpodobnost spolupráce soupeře. Obrázek 5 ukazuje reakční korespondenci pro takovou hru, kde rozměry jsou „Pravděpodobnost hry Spolupráce“, Nashova rovnováha je v levém dolním rohu, kde žádný hráč nehraje Spolupráci. Pokud by dimenze byly definovány jako „Defekt pravděpodobnosti hry“, pak by křivky nejlepší odezvy obou hráčů byly 1 pro všechny pravděpodobnosti strategie soupeře a korespondence reakce by se protínala (a vytvářela by Nashovu rovnováhu) v pravém horním rohu.
Ostatní (asymetrické) výplaty
Ve hrách 2x2 s asymetrií výplat je možná širší škála reakčních korespondenčních tvarů. Pro každého hráče existuje pět možných nejlepších tvarů odezvy, které jsou znázorněny na obrázku 6. Zleva doprava: dominovaná strategie (vždy hrajte 2), dominovaná strategie (vždy hrajte 1), stoupající (hrajte strategii 2, pokud je pravděpodobnost, hraje 2 je nad prahovou hodnotou), klesá (hrací strategie 1, pokud je pravděpodobnost, že druhý hráč hraje 2 je nad prahovou hodnotou) a lhostejná (obě strategie hrají za všech podmínek stejně dobře).

I když existují pouze čtyři možné typy výplat symetrických her 2x2 (z nichž jedna je triviální), pět různých nejlepších křivek odezvy na hráče umožňuje větší počet výplat asymetrických typů her. Mnoho z nich se od sebe opravdu neliší. Dimenze mohou být předefinovány (názvy názvů strategií 1 a 2), aby vznikly symetrické hry, které jsou logicky identické.
Odpovídající haléře
Jedna známá hra s asymetrií výplat je odpovídající haléře hra. V této hře vyhrává jeden hráč, řádkový hráč - graficky v dimenzi y - pokud se hráči koordinují (oba volí hlavy nebo oba volí ocasy), zatímco druhý hráč, sloupový hráč - zobrazený v ose x - vyhrává, pokud hráči diskoordinovaný. Reakce hráče Y odpovídá koordinační hře, zatímco reakce hráče X je diskoordinační hrou. Jedinou Nashovou rovnováhou je kombinace smíšených strategií, kde si oba hráči nezávisle vybírají hlavy a ocasy s pravděpodobností po 0,5.

Dynamika
v evoluční teorie her, nejlepší dynamika odezvy představuje třídu pravidel aktualizace strategie, kde strategie hráčů v příštím kole jsou určovány jejich nejlepšími odpověďmi na určitou podskupinu populace. Některé příklady zahrnují:
- Ve velkém populačním modelu si hráči vybírají svou další akci pravděpodobnostně podle toho, které strategie jsou nejlepší reakcí na populaci jako celek.
- V prostorovém modelu si hráči (v dalším kole) zvolí akci, která je nejlepší reakcí na všechny jejich sousedy (Ellison 1993 ).
Důležité je, že v těchto modelech si hráči v příštím kole zvolí pouze nejlepší reakci, která by jim přinesla nejvyšší výplatu v dalším kole. Hráči nezohledňují dopad, který by volba strategie v příštím kole měla na budoucí hraní hry. Toto omezení má za následek často volané dynamické pravidlo krátkozraká nejlepší odpověď.
V teorii potenciální hry, nejlepší dynamika odezvy odkazuje na způsob hledání a Nashova rovnováha vypočítáním nejlepší odezvy pro každého hráče:
Teorém: V každé hře s omezeným potenciálem se nejlepší dynamika odezvy vždy sblíží s Nashovou rovnováhou. (Nisan a kol. 2007, Oddíl 19.3.2)
Uhlazený

Některé modely místo nejlepších korespondencí odpovědí používají vyhlazené funkce nejlepší odezvy. Tyto funkce jsou podobné korespondenci s nejlepší odpovědí, až na to, že funkce „neskočí“ z jedné čisté strategie na druhou. Rozdíl je znázorněn na obrázku 8, kde černá představuje nejlepší korespondenci odezvy a ostatní barvy představují různé vyhlazené funkce nejlepší odezvy. Ve standardních korespondencích s nejlepší odpovědí bude i ten nejmenší přínos pro jednu akci mít za následek, že jednotlivec bude tuto akci hrát s pravděpodobností 1. Ve vyhlazené nejlepší odezvě, protože rozdíl mezi dvěma akcemi snižuje, se hra jednotlivce blíží 50:50.
Existuje mnoho funkcí, které představují vyhlazené funkce nejlepší odezvy. Zde zobrazené funkce představují několik variant následující funkce:
kde představuje očekávanou výplatu akce , a je parametr, který určuje, do jaké míry se funkce odchyluje od skutečně nejlepší odezvy (větší znamená, že hráč pravděpodobně udělá „chyby“).
Použití vyhlazené nejlepší odezvy, teoretické i empirické, má několik výhod. Zaprvé je to v souladu s psychologickými experimenty; když jsou jednotlivci mezi dvěma akcemi zhruba lhostejní, zdá se, že si volí víceméně náhodně. Zadruhé, hra jednotlivců je ve všech případech jednoznačně určena, protože jde o korespondence to je také a funkce. Nakonec pomocí vyhlazené nejlepší reakce s některými pravidly učení (jako v Fiktivní hra ) může mít za následek, že se hráči naučí hrát smíšená strategie Nashovy rovnováhy (Fudenberg & Levine 1998 ).
Viz také
Reference
- Ellison, G. (1993), „Učení, místní interakce a koordinace“ (PDF), Econometrica, 61 (5): 1047–1071, doi:10.2307/2951493, JSTOR 2951493
- Fudenberg, D .; Levine, David K. (1998), Teorie učení ve hrách, Cambridge MA: MIT Stiskněte
- Fudenberg, Drew; Tirole, Jean (1991). Herní teorie. Cambridge, Massachusetts: MIT Stiskněte. ISBN 9780262061414. Náhled knihy.
- Gibbons, R. (1992), Základ v teorii herHarvester-Wheatsheaf, S2CID 10248389
- Nash, John F. (1950), „Equilibrium points in n-osobní hry ", Sborník Národní akademie věd Spojených států amerických, 36 (1): 48–49, doi:10.1073 / pnas.36.1.48, PMC 1063129, PMID 16588946
- Osborne, M.J .; Rubinstein, Ariel (1994), Kurz teorie her, Cambridge MA: MIT Stiskněte
- Young, H.P. (2005), Strategické učení a jeho limity, Oxford University Press
- Nisan, N .; Roughgarden, T .; Tardos, E.; Vazirani, V.V. (2007), Algoritmická teorie her (PDF), New York: Cambridge University Press