Korelovaná rovnováha - Correlated equilibrium

v herní teorie, a korelovaná rovnováha je koncepce řešení to je obecnější než dobře známé Nashova rovnováha. Poprvé o tom diskutoval matematik Robert Aumann v roce 1974.^[1][2] Myšlenka je, že každý hráč si zvolí svou akci podle svého pozorování hodnoty stejného veřejného signálu. Strategie přiřadí akci každému možnému pozorování, které hráč může provést. Pokud by se žádný hráč nechtěl odchýlit od doporučené strategie (za předpokladu, že se ostatní neodchýlí), rozdělení se nazývá korelovaná rovnováha.

Formální definice

An ${ displaystyle N}$- strategická hra hráče ${ displaystyle displaystyle (N, A_ {i}, u_ {i})}$ se vyznačuje akční sadou ${ displaystyle A_ {i}}$ a užitná funkce ${ displaystyle u_ {i}}$ pro každého hráče ${ displaystyle i}$. Když hráč ${ displaystyle i}$ zvolí strategii ${ displaystyle a_ {i} v A_ {i}}$ a zbývající hráči si zvolí strategický profil popsaný v ${ displaystyle N-1}$-tuple ${ displaystyle a _ {- i}}$, pak hráč ${ displaystyle i}$užitečnost je ${ displaystyle displaystyle u_ {i} (a_ {i}, a _ {- i})}$.

A modifikace strategie pro hráče ${ displaystyle i}$ je funkce ${ displaystyle phi _ {i} dvojtečka A_ {i} do A_ {i}}$. To znamená, ${ displaystyle phi _ {i}}$ říká hráč ${ displaystyle i}$ upravit jeho chování hraním akce ${ displaystyle phi _ {i} (a_ {i})}$ na pokyn hrát ${ displaystyle a_ {i}}$.

Nechat ${ displaystyle ( Omega, pi)}$ být počitatelný pravděpodobnostní prostor. Pro každého hráče ${ displaystyle i}$, nechť ${ displaystyle P_ {i}}$ být jeho informačním oddílem, ${ displaystyle q_ {i}}$ být ${ displaystyle i}$je zadní a nechte ${ displaystyle s_ {i} dvojtečka Omega pravá šipka A_ {i}}$, přiřazení stejné hodnoty stavům ve stejné buňce ${ displaystyle i}$informační oddíl. Pak ${ displaystyle (( Omega, pi), P_ {i}, s_ {i})}$ je korelovanou rovnováhou strategické hry ${ displaystyle (N, A_ {i}, u_ {i})}$ pokud pro každého hráče ${ displaystyle i}$ a pro každou změnu strategie ${ displaystyle phi _ {i}}$:

${ displaystyle sum _ { omega in Omega} q_ {i} ( omega) u_ {i} (s_ {i} ( omega), s _ {- i} ( omega)) geq sum _ { omega in Omega} q_ {i} ( omega) u_ {i} left ( phi _ {i} left (s_ {i} ( omega) right), s _ {- i} ( omega) vpravo)}$

Jinými slovy, ${ displaystyle (( Omega, pi), P_ {i})}$ je korelovaná rovnováha, pokud žádný hráč nemůže zlepšit svou očekávanou užitečnost pomocí modifikace strategie.

Příklad

Zvažte kuřecí hra na obrázku. V této hře se dva jednotlivci navzájem vyzývají k soutěži, kde každý může odvážit se nebo kuře ven. Pokud se jeden chystá Dare, je lepší pro druhého vykouřit. Pokud se ale jeden chystá vykouřit, pro druhého je lepší Dare. To vede k zajímavé situaci, kdy se každý chce odvážit, ale pouze v případě, že by ten druhý mohl vyklouznout.

V této hře jsou tři Nashovy rovnováhy. Dva čistá strategie Nashovy rovnováhy jsou (D, C) a (C, D). Je tam také smíšená strategie rovnováha, kde se každý hráč odváží s pravděpodobností 1/3.

Nyní zvažte třetí stranu (nebo nějakou přirozenou událost), která lízne jednu ze tří karet označených: (C, C), (D, C), a (C, D), se stejnou pravděpodobností, tj. pravděpodobností 1/3 pro každou kartu. Po vytažení karty třetí strana informuje hráče o strategii, která jim byla na kartě přiřazena (ale ne strategie přidělená jejich soupeři). Předpokládejme, že je hráč přiřazen D, nechtěl by se odchýlit za předpokladu, že by druhý hráč hrál svoji přidělenou strategii, protože dostane 7 (nejvyšší možná výplata). Předpokládejme, že je hráč přiřazen C. Poté bude hrát druhý hráč C s pravděpodobností 1/2 a D s pravděpodobností 1/2. The očekávaná užitečnost of Daring je 7 (1/2) + 0 (1/2) = 3,5 a očekávaná užitečnost chickingu je 2 (1/2) + 6 (1/2) = 4. Takže hráč by preferoval chickening out .

Jelikož žádný z hráčů nemá motiv k odchýlení se, jedná se o korelovanou rovnováhu. Očekávaná výplata této rovnováhy je 7 (1/3) + 2 (1/3) + 6 (1/3) = 5, což je vyšší než očekávaná výplata smíšené strategie Nashova rovnováha.

Následující korelovaná rovnováha má pro oba hráče ještě vyšší výplatu: Doporučit (C, C) s pravděpodobností 1/2 a (D, C) a (C, D) s pravděpodobností po 1/4. Pak, když se hráči doporučuje hrát Cví, že druhý hráč bude hrát D s (podmíněnou) pravděpodobností 1/3 a C s pravděpodobností 2/3 a dostane očekávanou výplatu 14/3, což se rovná (ne méně než) očekávané výplatě, když hraje D. V této korelované rovnováze dostanou oba hráči očekávání 5,25. Lze ukázat, že se jedná o korelovanou rovnováhu s maximálním součtem očekávaných výplat pro oba hráče.

Učení korelované rovnováhy

Jednou z výhod korelovaných rovnováh je, že jsou výpočetně levnější než Nashovy rovnováhy. To lze zachytit skutečností, že výpočet korelované rovnováhy vyžaduje pouze řešení lineárního programu, zatímco řešení Nashovy rovnováhy vyžaduje úplné nalezení jejího pevného bodu.^[3] Další způsob, jak to vidět, je, že je možné, aby si dva hráči navzájem odpovídali na historické hry hry a nakonec se sblížili s korelovanou rovnováhou.^[4]

Reference

Zdroje