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

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

Примеры

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

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

В частности, если оптимальным решением является равновесие Нэша, то PoS равен 1.

В следующей игре «дилемма заключенного» , поскольку существует единственное равновесие, мы имеем PoS = PoA = 1/2. ${\displaystyle (B,R)}$

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

Предыстория и основные этапы

Цена стабильности была впервые изучена А. Шульцем и Н. Штир-Мозесом, в то время как этот термин был придуман Э. Аншелевичем и др. Шульц и Штир-Мозес сосредоточились на равновесиях в игре эгоистичной маршрутизации, в которой ребра имеют пропускную способность. Аншелевич и др. изучали игры проектирования сетей и показали, что чистое стратегическое равновесие Нэша всегда существует, а цена стабильности этой игры не превышает 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 }$

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

Вот патологическая игра в том же духе для Цены стабильности, вместо этого. Рассмотрим игроков, каждый из которых исходит из и пытается подключиться к . Стоимость немаркированных ребер принимается равной 0. ${\displaystyle n}$ ${\displaystyle s_{i}}$ ${\displaystyle t}$

Оптимальная стратегия для всех — разделить преимущество, что даст общую социальную стоимость . Однако для этой игры существует уникальный Нэш. Обратите внимание, что при оптимуме каждый игрок платит , и игрок 1 может уменьшить свою стоимость, переключившись на преимущество. Как только это произойдет, в интересах игрока 2 будет переключиться на преимущество и так далее. В конце концов, агенты достигнут равновесия Нэша, оплачивая свое собственное преимущество. Это распределение имеет социальную стоимость , где — ^th гармоническое число , которое равно . Несмотря на то, что оно не ограничено, цена стабильности экспоненциально лучше цены анархии в этой игре. ${\displaystyle 1+\varepsilon }$ ${\displaystyle 1+\varepsilon }$ ${\displaystyle \textstyle {\frac {1+\varepsilon }{n}}}$ ${\displaystyle \textstyle {\frac {1}{n}}}$ ${\displaystyle \textstyle {\frac {1}{n-1}}}$ ${\displaystyle \textstyle 1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}=H_{n}}$ ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\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. AS Schulz, NE Stier-Moses. О производительности пользовательских равновесий в транспортных сетях . Труды 14-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA), 2003.
2. E. Anshelevich, E. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. Цена стабильности для проектирования сетей со справедливым распределением затрат . SIAM Journal on Computing, 38:4, 1602-1623, 2008. Версия конференции появилась в FOCS 2004.
3. Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
4. Л. Агуссурья и Х. К. Лау. Цена стабильности в играх с эгоистичным планированием . Веб-аналитика и агентские системы: Международный журнал, 9:4, 2009.
5. Цзянь Ли. Верхняя граница цены стабильности для ненаправленных сетевых игр Shapely. Information Processing Letters 109 (15), 876-878, 2009. ${\displaystyle O(\log n/\log \log n)}$