Цена стабильности - Price of stability

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

Примеры

Другой способ выражения PoS:

${\displaystyle {\text{PoS}}={\frac {\text{value of best Nash equilibrium}}{\text{value of optimal solution}}},\ {\text{PoS}}\geq 0.}$

В следующих Дилемма заключенного игра, поскольку существует единственное равновесие (B, R), имеем PoS = PoA = 1/2.

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

	Оставили	Правильно
Вершина	(2,2)	(0,3)
Нижний	(3,0)	(1,1)

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

	Оставили	Правильно
Вершина	(2,1)	(0,0)
Нижний	(0,0)	(5,10)

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

Цена стабильности была впервые изучена А. Шульзаном и Н. Моисеем и получила название в исследованиях Э. Аншелевича. Они показали, что чистая стратегия равновесие по Нэшу всегда существует и цена стабильности этой игры составляет не более n-го номер гармоники в ориентированных графах. Для неориентированных графов Аншелевич и другие представили жесткую границу цены стабильности 4/3 для случая одного источника и двух игроков. Цзянь Ли доказал, что для неориентированных графов с выделенным местом назначения, к которому должны подключиться все игроки, цена стабильности игры про дизайн сети Shapely равна ${\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 \textstyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}}$ делится поровну между ними;
• Стоимость игрока составляет ${\displaystyle \textstyle C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}}$
• Социальная стоимость - это сумма затрат игрока: ${\displaystyle \textstyle 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)}$. Рассмотрим следующую игру по дизайну сети.

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

Рассмотрим в этой игре два разных состояния равновесия. Если все поделятся ${\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 \textstyle {\frac {1}{n}}}$ край. Как только это произойдет, игрок 2 будет заинтересован переключиться на ${\displaystyle \textstyle {\frac {1}{n-1}}}$ край и так далее. В конце концов, агенты достигнут равновесия по Нэшу в оплате за свое преимущество. Это распределение имеет социальные издержки ${\displaystyle \textstyle 1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}=H_{n}}$, куда ${\displaystyle H_{n}}$ это ${\displaystyle n}$^th номер гармоники, который ${\displaystyle \Theta (\log n)}$. Несмотря на то, что она неограниченна, цена стабильности в этой игре экспоненциально выше, чем цена анархии.

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

Обратите внимание, что по замыслу игры с дизайном сети - это игры с перегрузкой, поэтому они допускают потенциальную функцию ${\displaystyle \textstyle \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)\leq \Phi (S)\leq B\cdot SC(S).}$

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

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

${\displaystyle SC(NE)\leq 1/A\cdot \Phi (NE)\leq 1/A\cdot \Phi (OPT)\leq 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}}\leq \sum _{e\in S}c_{e}H_{n}=H_{n}\cdot SC(S).}$

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

Смотрите также

• Конкурсная игра о местоположении - игра без цены стабильности.

Рекомендации

1. Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.
2. Л. Агуссурья и Х. К. Лау. Цена стабильности в эгоистичных играх с планированием. Веб-аналитика и агентские системы: Международный журнал, 9: 4, 2009.
3. Цзянь Ли. An ${\displaystyle O(\log n/\log \log n)}$ верхняя граница цены стабильности для ненаправленных игр с сетевым дизайном Shapely. Письма по обработке информации 109 (15), 876-878, 2009.