Joc potențial

Un joc potențial este un joc în formă normală în care funcțiile payoff au o proprietate specială. Când un jucător își schimbă strategiile, diferența de câștiguri este egală cu diferența de valori ale funcției potențiale. Acest lucru permite găsirea echilibrului Nash ca soluție la o problemă de optimizare. Jocuri potențiale au fost introduse de Monderer și Shapley .

Funcția potențială

Luați în considerare un joc de fețe în formă normală , unde este setul de jucători, este setul de strategii și este funcția de câștig a celui de-al- lea jucător, . Să presupunem că există o funcție astfel încât pentru orice $n$ $\Gamma =<N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N}>$ $N=\{1,2,...,n\}$ $X_{i}$ $H_{i}(x_{1},...,x_{n})$ $i$ $i=1,...,n$ $P:\prod \limits _{i=1}^{n}X_{i}\rightarrow R$ $i\in N$

H i ( X − i , X i ′ ) − H i ( X − i , X i ) = P ( X − i , X i ′ ) − P ( X − i , X i ) {\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})$

pentru strategii arbitrare și orice . Dacă o astfel de funcție există, o vom numi potențial în joc , iar jocul în sine - potențial . $x_{-i}\in \prod \limits _{j\neq i}X_{j)$ $x_{i},x_{i}'\in X_{i}$ $\Gamma$

Echilibrul în strategii pure

Lasă jocul fețelor să permită potențial . Atunci echilibrul Nash al jocului este echilibrul Nash al jocului și invers. În plus, jocul are întotdeauna cel puțin un echilibru în strategii pure. $n$ $\Gamma =<N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N}>$ $P$ $\Gamma$ $\Gamma '=<N,\{X_{i}\}_{i\in N},P>$ $\Gamma$

Soluție optimă

Existența potențialului facilitează foarte mult găsirea echilibrului Nash. Să alegem ca o situație în strategii pure care oferă un maxim pe platou . Apoi, în acest moment, pentru orice , inegalitatea este valabilă , în special, și pentru fiecare argument, adică $x^{*}$ $P(x)$ $\prod \limits _{i=1}^{n}X_{i)$ $x\in \prod \limits _{i=1}^{n}X_{i)$ $P(x)\leq P(x^{*})$

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

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

Aceasta implică faptul că echilibrul Nash în joc și, în consecință, în joc . $x^{*}$ $\gamma '$ $\Gamma$

Oligopolul Cournot

Luați în considerare oligopolul Cournot, unde funcțiile de plată ale jucătorilor au forma

H i ( X unu , . . . , X n ) = ( p − b ∑ j = unu n X j ) X i − c i X i , i = unu , . . . , 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.

Acest joc este, de asemenea, potențial. Potențialul este funcția

P ( X unu , . . . , X n ) = ∑ j = unu n ( p − c j ) X j − b ( ∑ j = unu n X j 2 + ∑ unu ≤ i < j ≤ n X i X j ) . {\displaystyle P(x_{1},...,x_{n})=\sum _{j=1}^{n}(p-c_{j})x_{j}-b\left(\ suma _{j=1}^{n}x_{j}^{2}+\sum _{1\leq i<j\leq n}x_{i}x_{j}\right).}

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

Maximul global al funcției dă echilibrul Nash: $P(x)$

X i = p − c i b − n p − ∑ j = unu n c j n + unu , i = unu , . . . , 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.$

Dirijare

Jocurile potențiale joacă un rol important în jocurile de rutare (jocuri de congestionare), care au fost luate în considerare pentru prima dată de Rosenthal. Ei și-au primit numele deoarece funcția de plăți din ele depinde doar de numărul de jucători care au ales aceleași strategii. În aceste jocuri, există un potențial, al cărui maxim oferă rute optime într-o rețea arbitrară.

Literatură

Monderer D., Shapley L. Potential games, Games and Economic Behavior 14 (1996), 124-143.
Rosenthal RW O clasă de jocuri care posedă echilibre Nash de strategie pură, Int. Journal of Game Theory 2 (1973), 65-67.
Mazalov VV Teoria matematică a jocurilor și aplicațiilor. - Sankt Petersburg - Moscova - Krasnodar : Lan, 2010. - 446 p. - ISBN 978-5-8114-1025-5 .