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

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

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

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

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

Битва полов

	${\textstyle L}$	${\textstyle R}$
${\textstyle T}$	(2,1)	(0,0)
${\textstyle B}$	(0,0)	(5,10)

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

Для сетевых игр понятие цены стабильности имеет принципиальную важность. Их ключевая особенность заключается в том, что цена стабильности в них может быть значительно ниже, чем цена анархии.

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

• ${\displaystyle n}$ игроков;
• целью каждого ${\displaystyle i}$-го игрока является соединение вершин ${\displaystyle s_{i}}$ и ${\displaystyle t_{i}}$ в ориентированном графе ${\displaystyle G=(V,E)}$;
• стратегиями ${\displaystyle P_{i}}$ для игрока являются все пути из ${\displaystyle s_{i}}$ в ${\displaystyle t_{i}}$ в графе ${\displaystyle G}$;
• каждая дуга имеет цену ${\displaystyle c_{i}}$;
• «справедливое распределение цен»: Если ${\displaystyle n_{e}}$ игроков выбирают дугу ${\displaystyle e}$, то цена ${\displaystyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}}$ распределяется равно между ними;
• цена для игрока составляет ${\displaystyle C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}}$;
• социальная цена равна сумме цен для игроков: ${\displaystyle SC(S)=\sum _{i}C_{i}(S)=\sum _{e\in S}n_{e}{\frac {c_{e}}{n_{e}}}=\sum _{e\in S}c_{e}}$.

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

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

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

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

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

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

${\displaystyle A\cdot SC(S)\leqslant \Phi (S)\leqslant B\cdot SC(S).}$

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

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

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

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

${\displaystyle \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).}$

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