Потенциальная игра

Потенциальная игра — это игра в нормальной форме, функции выигрыша в которой обладают особым свойством. При изменении игроком своих стратегий разность его выигрышей равна разности значений потенциальной функции. Это позволяет находить равновесие по Нэшу как решение некоторой оптимизационной задачи. Потенциальные игры были введены в рассмотрение Мондерером и Шепли.

Потенциальная функция

Рассмотрим игру $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})$$

для произвольных $x_{-i}\in \prod \limits _{j\neq i}X_{j}$ и любых стратегий $x_{i},x_{i}'\in X_{i}$. Если такая функция существует, будем называть её потенциалом в игре $\Gamma$, а саму игру — потенциальной.

Равновесие в чистых стратегиях

Пусть игра $n$ лиц $\Gamma =<N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N}>$ допускает потенциал $P$. Тогда равновесие по Нэшу в игре $\Gamma$ является равновесием по Нэшу в игре $\Gamma '=<N,\{X_{i}\}_{i\in N},P>$ , и наоборот. Кроме того, в игре $\Gamma$ всегда существует, по крайней мере, одно равновесие в чистых стратегиях.

Оптимальное решение

Существование потенциала существенно облегчает нахождение равновесия по Нэшу. Выберем в качестве $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})\leq P(x^{*}),\forall x_{i}.$$

Отсюда вытекает, что $x^{*}$ равновесие по Нэшу в игре $\Gamma '$ и, следовательно, в игре $\Gamma$.

Олигополия Курно

Рассмотрим олигополию Курно, где функции выигрыша игроков имеют вид

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

Эта игра также является потенциальной. Потенциалом является функция

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

Глобальный максимум функции $P(x)$ дает равновесие по Нэшу:

$$x_{i}={\frac {p-c_{i}}{b}}-{\frac {np-\sum _{j=1}^{n}c_{j}}{n+1}},\quad i=1,...,n.$$

Маршрутизация

Важную роль потенциальные игры имеют в играх маршрутизации (congestion games), которые впервые были рассмотрены Розенталем. Свое название они получили из-за того, что функция выигрыша в них зависит лишь от числа игроков, выбравших одинаковые стратегии. В этих играх существует потенциал, максимум которого дает оптимальные маршруты в произвольной сети.

Литература

• Monderer D., Shapley L. Potential games, Games and Economic Behavior 14 (1996), 124—143.
• Rosenthal R. W. A class of games possessing pure-strategy Nash equilibria, Int. Journal of Game Theory 2 (1973), 65-67.
• Мазалов В. В. Математическая теория игр и приложения. — Санкт-Петербург — Москва — Краснодар: Лань, 2010. — 446 с. — ISBN 978-5-8114-1025-5.