Potenciális játék

A potenciális játék egy normál formájú játék , amelyben a kifizetési függvények különleges tulajdonsággal rendelkeznek. Amikor egy játékos megváltoztatja a stratégiáját, a kifizetések különbsége megegyezik a potenciális függvény értékeinek különbségével. Ez lehetővé teszi a Nash-egyensúly megtalálását néhány optimalizálási probléma megoldásaként. A lehetséges játékokat Monderer és Shapley mutatta be .

Potenciális funkció

Tekintsünk egy arcjátékot normál formában , ahol a játékosok halmaza, a stratégiák halmaza, és a játékos kifizetési függvénye , . Tételezzük fel, hogy létezik olyan függvény , amely bármely $n$ $\Gamma =<N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N}>$ ${\displaystyle N=\{1,2,...,n\))$ $X_{i}$ $H_{i}(x_{1},...,x_{n})$ $én$ $i=1,...,n$ $P:\prod \limits _{i=1}^{n}X_{i}\rightarrow R$ $i\in N$

H én ( x − én , x én ′ ) − H én ( x − én , x én ) = P ( x − én , x én ′ ) − P ( x − én , x én ) {\displaystyle H_{i}(x_{-i},x_{i}')-H_{i}(x_{-i},x_{i})=P(x_{-i},x_{i} ')-P(x_{-i},x_{i})} $H_{i}(x_{-i},x_{i}')-H_{i}(x_{-i},x_{i})=P(x_{-i},x_{i} ')-P(x_{-i},x_{i})$

tetszőleges és bármilyen stratégiához . Ha létezik ilyen függvény, akkor a játékban rejlő potenciálnak , magát a játékot pedig potenciálnak nevezzük . ${\displaystyle x_{-i}\in \prod \limits _{j\neq i}X_{j))$ $x_{i},x_{i}'\in X_{i}$ $\Gamma$

Egyensúly a tiszta stratégiákban

Hagyja, hogy az arcok játéka lehetőséget teremtsen . Ekkor a játék Nash- egyensúlya a játék Nash-egyensúlya , és fordítva. Ezenkívül a játéknak mindig van legalább egy egyensúlya a tiszta stratégiákban. $n$ $\Gamma =<N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N}>$ $P$ $\Gamma$ $\Gamma '=<N,\{X_{i}\}_{i\in N},P>$ $\Gamma$

Optimális megoldás

A potenciál megléte nagyban megkönnyíti a Nash-egyensúly megtalálását. Tiszta stratégiákban válasszunk olyan szituációt, amely maximumot nyújt a készleten . Ekkor ezen a ponton bármelyikre érvényes az egyenlőtlenség , különösen és minden érvre, azaz $x^{*}$ $P(x)$ ${\displaystyle \prod \limits _{i=1}^{n}X_{i))$ ${\displaystyle x\in \prod \limits _{i=1}^{n}X_{i))$ $P(x)\leq P(x^{*})$

P ( x − én ∗ , x én ) ≤ P ( x ∗ ) , ∀ x én . {\displaystyle P(x_{-i}^{*},x_{i})\leq P(x^{*}),\forall x_{i}.}

P(x_{-i}^{*},x_{i})\leq P(x^{*}),\forall x_{i}.

Ez azt jelenti, hogy a Nash-egyensúly a játékban és következésképpen a játékban is . $x^{*}$ $\gamma$ $\Gamma$

Cournot oligopólium

Tekintsük a Cournot-oligopóliumot, ahol a játékosok kifizetési funkcióinak formája van

H én ( x egy , . . . , x n ) = ( p − b ∑ j = egy n x j ) x én − c én x én , én = egy , . . . , n . {\displaystyle H_{i}(x_{1},...,x_{n})=(pb\sum _{j=1}^{n}x_{j})x_{i}-c_{i }x_{i},\,\,\,i=1,...,n.}

H_{i}(x_{1},...,x_{n})=(pb\sum _{j=1}^{n}x_{j})x_{i}-c_{i }x_{i},\,\,\,i=1,...,n.

Ez a játék is potenciális. A potenciál a funkció

P ( x egy , . . . , x n ) = ∑ j = egy n ( p − c j ) x j − b ( ∑ j = egy n x j 2 + ∑ egy ≤ én < j ≤ n x én x j ) . {\displaystyle P(x_{1},...,x_{n})=\sum _{j=1}^{n}(p-c_{j})x_{j}-b\left(\ összeg _{j=1}^{n}x_{j}^{2}+\sum _{1\leq i<j\leq n}x_{i}x_{j}\jobbra).}

P(x_{1},...,x_{n})=\sum _{j=1}^{n}(p-c_{j})x_{j}-b\left(\ összeg _{j=1}^{n}x_{j}^{2}+\sum _{1\leq i<j\leq n}x_{i}x_{j}\jobbra).

A függvény globális maximuma megadja a Nash-egyensúlyt: $P(x)$

x én = p − c én b − n p − ∑ j = egy n c j n + egy , én = egy , . . . , n . {\displaystyle x_{i}={\frac {p-c_{i}}{b}}-{\frac {np-\sum _{j=1}^{n}c_{j}}{n+ 1 }},\quad i=1,...,n.} $x_{i}={\frac {p-c_{i}}{b}}-{\frac {np-\sum _{j=1}^{n}c_{j}}{n+ 1 }},\quad i=1,...,n.$

útvonalválasztás

A potenciális játékok fontos szerepet játszanak a routing játékokban (torlódásos játékok), amelyekkel először Rosenthal foglalkozott. A nevüket azért kapták, mert a kifizetési funkció bennük csak azon játékosok számától függ, akik ugyanazt a stratégiát választották. Ezekben a játékokban van lehetőség, aminek maximuma optimális útvonalakat ad egy tetszőleges hálózatban.

Irodalom

Monderer D., Shapley L. Potential games, Games and Economic Behavior 14 (1996), 124-143.
Rosenthal RW Tiszta stratégiai Nash-egyensúlyú játékok osztálya, Int. Journal of Game Theory 2 (1973), 65-67.
Mazalov VV. A játékok és alkalmazások matematikai elmélete. - Szentpétervár - Moszkva - Krasznodar : Lan, 2010. - 446 p. - ISBN 978-5-8114-1025-5 .