Русская Википедия:Цена стабильности
Цена стабильности (Шаблон:Lang-en, PoS) для игры — отношение оптимального значения целевой функции в одном из её равновесных состояний и оптимального исхода. Цена стабильности имеет смысл для игр, имеющих некую высшую силу или условия игры, которые каким-либо образом влияют на положение игроков и могут помочь им сойтись к равновесию Нэша. При измерении эффективности равновесия Нэша в какой-либо игре имеет смысл рассматривать и цену анархии (Шаблон:Lang-en, PoA).
Примеры
PoS можно выразить следующим образом:
- <math> PoS = \frac {N} {S},\ PoS \geqslant 0.</math>
Здесь <math display="inline">N</math> — значение лучшего равновесия Нэша, <math display="inline">S</math> — значение оптимального решения.
В приведённой ниже игре «Дилемма заключённого» игроки не всегда будут сотрудничать друг с другом, даже если это в их интересах, поскольку имеется единственное равновесие (<math display="inline">B</math>, <math display="inline">R</math>), мы имеем <math>PoS = PoA = \tfrac{1}{2}</math>.
| <math display="inline">L</math> | <math display="inline">R</math> | |
|---|---|---|
| <math display="inline">T</math> | (2,2) | (0,3) |
| <math display="inline">B</math> | (3,0) | (1,1) |
Этот пример является версией игры «битва полов». В нем имеются две точки равновесия, (<math display="inline">T</math>, <math display="inline">L</math>) и (<math display="inline">B</math>, <math display="inline">R</math>) со значениями 3 и 15 соответственно. Оптимальным значением является 15. Тогда <math>PoS = 1</math>, в то время как <math>PoA = \tfrac{1}{5}</math>.
| <math display="inline">L</math> | <math display="inline">R</math> | |
|---|---|---|
| <math display="inline">T</math> | (2,1) | (0,0) |
| <math display="inline">B</math> | (0,0) | (5,10) |
Предпосылки и вехи
Цену стабильности первыми изучили А. Шульцан и Н. Мозес, а сам термин появился в работах Е. Аншелевича. Они показали, что равновесие Нэша всегда существует в чистых стратегиях, и цена стабильности этой игры не превосходит n-го гармонического числа в ориентированных графах. Для неориентированных графов Аншелевич и другие представили определили жёсткую границу стабильности в 4/3 для случая одного источника и двух игроков. Йен Ли доказал, что для таких графов с различными точками назначения для всех игроков, с которыми все игроки должны иметь связь, цена стабильности потока игры на построение сети Шепли равна <math>O(\log n/\log\log n),</math> где <math>n</math> — число игроков. С другой стороны, цена анархии для игры равна примерно <math>n</math>.
Игры на построение сети
Условия игры
Игры построения сети имеют естественное обоснование для цены стабильности. В этих играх цена анархии может быть намного меньше цены стабильности.
Пример следующей игры:
- <math>n</math> игроков;
- целью каждого <math>i</math>-го игрока является соединение вершин <math>s_i</math> и <math>t_i</math> в ориентированном графе <math>G = (V, E)</math>;
- стратегиями <math>P_i</math> для игрока являются все пути из <math>s_i</math> в <math>t_i</math> в графе <math>G</math>;
- каждая дуга имеет цену <math>c_i</math>;
- «справедливое распределение цен»: Если <math>n_e</math> игроков выбирают дугу <math>e</math>, то цена <math>d_e(n_e) = \frac{c_e}{n_e}</math> распределяется равно между ними;
- цена для игрока составляет <math>C_i(S) = \sum_{e \in P_i} \frac{c_e}{n_e}</math>;
- социальная цена равна сумме цен для игроков: <math>SC(S) = \sum_i C_i(S) = \sum_{e \in S} n_e \frac{c_e}{n_e} = \sum_{e \in S} c_e</math>.
Цена анархии
Цена анархии может составлять <math>\Omega(n)</math>. Пример следующей игры на построение сети.
В этой игре есть 2 различных равновесия. Если все разделяют дугу <math>1 + \varepsilon</math>, то социальная цена равна <math>1 + \varepsilon</math>. Более того, это равновесие оптимально. Однако, разделение всеми дуги <math>n</math> является также равновесием Нэша. Любой агент имеет цену <math>1</math> в равновесной стратегии, и переключение его на другую дугу повышает его цену до <math>1+\varepsilon</math>.
Нижняя граница цены стабильности
Здесь приведена патологическая игра с таким же поведением, но уже для цены стабильности. Присутствует <math>n</math> игроков, каждый из которых начинает с вершины <math>s_i</math> и пытается соединить её с вершиной <math>t</math>. Допустим, цены непомеченных дуг равны 0.
Оптимальной стратегией для всех игроков является общее использование дуги <math>1+\varepsilon</math>, что даёт социальную цену <math>1+ \varepsilon</math>. Однако имеется единственная стратегия с равновесием Нэша для этой игры. В случае оптимальности, каждый игрок платит <math>\textstyle \frac{1 + \varepsilon}{n}</math> и игрок 1 может уменьшить свою цену путём переключения на дугу <math>\tfrac{1}{n}</math>. Если это происходит, то игроку 2 становится выгодным переключиться на дугу <math>\tfrac{1}{n-1}</math> и так далее. В конце концов, агенты достигнут равновесия Нэша, оплачивая свою собственную отдельную дугу. Такое распределение имеет социальную цену <math>1 + \tfrac{1}{2} + \cdots + \tfrac{1}{n} = H_n</math>, где <math>H_n</math> является <math>n</math>-ым гармоническим числом, что равно <math>\Theta(\log n)</math>. Хотя это значение не ограничено, цена стабильности экспоненциально лучше цены анархии в этой игре.
Верхняя граница цены стабильности
По определению игры на построение сети являются Шаблон:Нп5, поэтому они допускают потенциальную функцию <math>\Phi = \sum_e \sum_{i=1}^{n_e} \frac{c_e}{i}</math>.
Теорема. [Теорема 19.13 из книги 1] Предположим, что существует константы <math>A</math> и <math>B</math>, такие, что для любой стратегии <math>S</math>
- <math> A \cdot SC(S) \leqslant \Phi(S) \leqslant B \cdot SC(S).</math>
Тогда цена стабильности меньше <math>B/A</math>.
Доказательство. Глобальный минимум <math>NE</math> функции <math>\Phi</math> является равновесием Нэша, так что
- <math> SC(NE) \leqslant 1/A \cdot \Phi(NE) \leqslant 1/A \cdot \Phi(OPT) \leqslant B/A \cdot SC(OPT).</math>
Социальная цена была определена как сумма цен по дугам, так что
- <math> \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). </math>
Тривиально получаем <math>A = 1</math> и вычисления выше дают <math>B = H_n</math>, так что можно привлечь теорему для верхней границы цены стабильности.
См. также
- Шаблон:Нп5 — игра без цены стабильности.
Примечания
Литература
