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

Цена стабильности (англ. price of stability, PoS) для игры — отношение оптимального значения целевой функции в одном из её равновесных состояний и оптимального исхода. Цена стабильности имеет смысл для игр, которые имеют некую высшую силу или условия игры, которые каким-либо образом влияют на положение игроков и могут помочь им сойтись к равновесию Нэша. При измерении эффективности равновесия Нэша в какой-либо игре имеет смысл рассматривать и цену анархии (англ. Price of Anarchy, PoA).

Примеры

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

PoS={\frac {N}{S}},\ PoS\geqslant 0.

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

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

Дилемма заключённого
	${\textstyle L}$	${\textstyle R}$
${\textstyle T}$	(2,2)	(0,3)
${\textstyle B}$	(3,0)	(1,1)

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

Битва полов
	${\textstyle L}$	${\textstyle R}$
${\textstyle T}$	(2,1)	(0,0)
${\textstyle 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}$ .

Игра на построение сети с ценой анархии

\Omega (n)

Цена анархии

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

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

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

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

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

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

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

По определению игры на построение сети являются играми на переполнение^[англ.], поэтому они допускают потенциальную функцию $\Phi =\sum _{e}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}$ .

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

A\cdot SC(S)\leqslant \Phi (S)\leqslant B\cdot SC(S).

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

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

SC(NE)\leqslant 1/A\cdot \Phi (NE)\leqslant 1/A\cdot \Phi (OPT)\leqslant B/A\cdot SC(OPT).

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

\Phi (S)=\sum _{e\in S}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}=\sum _{e\in S}c_{e}H_{n_{e}}\leqslant \sum _{e\in S}c_{e}H_{n}=H_{n}\cdot SC(S).

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

См. также

Распределение объектов (конкурентная игра)^[англ.] — игра без цены стабильности.

Примечания

Литература

Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Éva Tardos. Algorithmic Game Theory. — Cambridge, UK: Cambridge University Press, 2007. — ISBN 0-521-87282-0.
L. Agussurja, H. C. Lau. The Price of Stability in Selfish Scheduling Games // Web Intelligence and Agent Systems: An International Journal. — 2009. — Т. 9, вып. 4.
Jian Li. An $O(\log n/\log \log n)$ upper bound on the price of stability for undirected Shapely network design games // Information Processing Letters. — 2009. — Т. 109, вып. 15. — С. 876—878.

[1] Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Éva Tardos. Algorithmic Game Theory. — Cambridge, UK: Cambridge University Press, 2007. — ISBN 0-521-87282-0.

[2] L. Agussurja, H. C. Lau. The Price of Stability in Selfish Scheduling Games // Web Intelligence and Agent Systems: An International Journal. — 2009. — Т. 9, вып. 4.

[3] Jian Li. An $O(\log n/\log \log n)$ upper bound on the price of stability for undirected Shapely network design games // Information Processing Letters. — 2009. — Т. 109, вып. 15. — С. 876—878.