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

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

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

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

Цена анархии может составлять ${\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}}$, так что можно привлечь теорему для верхней границы цены стабильности.