Цена стабильности

В теории игр цена стабильности (Шаблон:Lang-en, PoS) — отношение оптимального значения целевой функции в одном из её равновесных состояний и оптимального исхода. Цена стабильности имеет смысл для игр, в которых присутствует некий объективный авторитет, который может немного влиять на игроков и, возможно, помогать им прийти к хорошему равновесию Нэша. При измерении эффективности равновесия Нэша в какой-либо игре имеет смысл рассматривать и цену анархии (Шаблон:Lang-en, PoA).

Примеры

PoS можно выразить следующим образом:

$PoS=\frac{N}{S},PoS⩾0.$

Здесь $N$ — значение лучшего равновесия Нэша, $S$ — значение оптимального решения.

В приведённой ниже игре «Дилемма заключённого» игроки не всегда будут сотрудничать друг с другом, даже если это в их интересах, поскольку имеется единственное равновесие ($B$, $R$), мы имеем $PoS=PoA=\frac{1}{2}$.

Дилемма заключённого

	$L$	$R$
$T$	(2,2)	(0,3)
$B$	(3,0)	(1,1)

Этот пример является версией игры «битва полов». В нем имеются две точки равновесия, ($T$, $L$) и ($B$, $R$) со значениями 3 и 15 соответственно. Оптимальным значением является 15. Тогда $PoS=1$, в то время как $PoA=\frac{1}{5}$.

Битва полов

	$L$	$R$
$T$	(2,1)	(0,0)
$B$	(0,0)	(5,10)

Предпосылки и вехи

Цену стабильности первыми изучили А. Шульцан и Н. Мозес, а сам термин появился в работах Е. Аншелевича. Они показали, что равновесие Нэша всегда существует в чистых стратегиях, и цена стабильности этой игры не превосходит n-го гармонического числа в ориентированных графах. Для неориентированных графов Аншелевич и другие представили определили жёсткую границу стабильности в 4/3 для случая одного источника и двух игроков. Йен Ли доказал, что для таких графов с различными точками назначения для всех игроков, с которыми все игроки должны иметь связь, цена стабильности потока игры на построение сети Шепли равна $O(\log n/\log \log n),$ где $n$ — число игроков. С другой стороны, цена анархии для игры равна примерно $n$.

Игры на построение сети

Условия игры

Игры построения сети имеют естественное обоснование для цены стабильности. В этих играх цена анархии может быть намного меньше цены стабильности.

Пример следующей игры:

• $n$ игроков;
• целью каждого $i$-го игрока является соединение вершин $s_i$ и $t_i$ в ориентированном графе $G=(V,E)$;
• стратегиями $P_i$ для игрока являются все пути из $s_i$ в $t_i$ в графе $G$;
• каждая дуга имеет цену $c_i$;
• «справедливое распределение цен»: Если $n_e$ игроков выбирают дугу $e$, то цена $d_e(n_e)=\frac{c_e}{n_e}$ распределяется равно между ними;
• цена для игрока составляет $C_i(S)=\sum _{e\in P_i}\frac{c_e}{n_e}$;
• социальная цена равна сумме цен для игроков: $SC(S)=\sum _i{C}_i(S)=\sum _{e\in S}{n}_e\frac{c_e}{n_e}=\sum _{e\in S}{c}_e$.

Игра на построение сети с ценой анархии $\mathrm{\Omega }(n)$

Цена анархии

Цена анархии может составлять $\mathrm{\Omega }(n)$. Пример следующей игры на построение сети.

Патологическая цена стабильности игры

В этой игре есть 2 различных равновесия. Если все разделяют дугу $1+\epsilon$, то социальная цена равна $1+\epsilon$. Более того, это равновесие оптимально. Однако, разделение всеми дуги $n$ является также равновесием Нэша. Любой агент имеет цену $1$ в равновесной стратегии, и переключение его на другую дугу повышает его цену до $1+\epsilon$.

Нижняя граница цены стабильности

Здесь приведена патологическая игра с таким же поведением, но уже для цены стабильности. Присутствует $n$ игроков, каждый из которых начинает с вершины $s_i$ и пытается соединить её с вершиной $t$. Допустим, цены непомеченных дуг равны 0.

Оптимальной стратегией для всех игроков является общее использование дуги $1+\epsilon$, что даёт социальную цену $1+\epsilon$. Однако имеется единственная стратегия с равновесием Нэша для этой игры. В случае оптимальности, каждый игрок платит $\frac{1+\epsilon }{n}$ и игрок 1 может уменьшить свою цену путём переключения на дугу $\frac{1}{n}$. Если это происходит, то игроку 2 становится выгодным переключиться на дугу $\frac{1}{n-1}$ и так далее. В конце концов, агенты достигнут равновесия Нэша, оплачивая свою собственную отдельную дугу. Такое распределение имеет социальную цену $1+\frac{1}{2}+\cdots +\frac{1}{n}=H_n$, где $H_n$ является $n$-ым гармоническим числом, что равно $\mathrm{\Theta }(\log n)$. Хотя это значение не ограничено, цена стабильности экспоненциально лучше цены анархии в этой игре.

Верхняя граница цены стабильности

По определению игры на построение сети являются Шаблон:Нп5, поэтому они допускают потенциальную функцию $\mathrm{\Phi }=\sum _e\sum _{i=1}^{n_e}\frac{c_e}{i}$.

Теорема. [Теорема 19.13 из книги 1] Предположим, что существует константы $A$ и $B$, такие, что для любой стратегии $S$

$A\cdot SC(S)⩽\mathrm{\Phi }(S)⩽B\cdot SC(S).$

Тогда цена стабильности меньше $B/A$.

Доказательство. Глобальный минимум $NE$ функции $\mathrm{\Phi }$ является равновесием Нэша, так что

$SC(NE)⩽1/A\cdot \mathrm{\Phi }(NE)⩽1/A\cdot \mathrm{\Phi }(OPT)⩽B/A\cdot SC(OPT).$

Социальная цена была определена как сумма цен по дугам, так что

$\mathrm{\Phi }(S)=\sum _{e\in S}\sum _{i=1}^{n_e}\frac{c_e}{i}=\sum _{e\in S}{c}_e{H}_{n_e}⩽\sum _{e\in S}{c}_e{H}_n=H_n\cdot SC(S).$

Тривиально получаем $A=1$ и вычисления выше дают $B=H_n$, так что можно привлечь теорему для верхней границы цены стабильности.

См. также

• Шаблон:Нп5 — игра без цены стабильности.

Литература

1. Шаблон:Книга
2. Шаблон:Статья
3. Шаблон:Статья