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

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

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

 
Здесь  — значение лучшего равновесия Нэша,  — значение оптимального решения.

В приведённой ниже игре «Дилемма заключённого» игроки не всегда будут сотрудничать друг с другом, даже если это в их интересах, поскольку имеется единственное равновесие (, ), мы имеем .

Этот пример является версией игры «битва полов». В нем имеются две точки равновесия, (, ) и (, ) со значениями 3 и 15 соответственно. Оптимальным значением является 15. Тогда , в то время как .

Предпосылки и вехи 
Цену стабильности первыми изучили А. Шульцан и Н. Мозес, а сам термин появился в работах Е. Аншелевича. Они показали, что равновесие Нэша всегда существует в чистых стратегиях, и цена стабильности этой игры не превосходит n-го гармонического числа в ориентированных графах. Для неориентированных графов Аншелевич и другие представили определили жёсткую границу стабильности в 4/3 для случая одного источника и двух игроков. Йен Ли доказал, что для таких графов с различными точками назначения для всех игроков, с которыми все игроки должны иметь связь, цена стабильности потока игры на построение сети Шепли равна  где  — число игроков. С другой стороны, цена анархии для игры равна примерно .

Игры на построение сети

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

Пример следующей игры:
  игроков;
 целью каждого -го игрока является соединение вершин  и  в ориентированном графе ;
 стратегиями  для игрока являются все пути из  в  в графе ;
 каждая дуга имеет цену ;
 «справедливое распределение цен»: Если  игроков выбирают дугу , то цена  распределяется равно между ними;
 цена для игрока составляет ;
 социальная цена равна сумме цен для игроков: .

Цена анархии 
Цена анархии может составлять . Пример следующей игры на построение сети.

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

Нижняя граница цены стабильности 
Здесь приведена патологическая игра с таким же поведением, но уже для цены стабильности. Присутствует  игроков, каждый из которых начинает с вершины  и пытается соединить её с вершиной . Допустим, цены непомеченных дуг равны 0.

Оптимальной стратегией для всех игроков является общее использование дуги , что даёт социальную цену . Однако имеется единственная стратегия с равновесием Нэша для этой игры. В случае оптимальности, каждый игрок платит  и игрок 1 может уменьшить свою цену путём переключения на дугу . Если это происходит, то игроку 2 становится выгодным переключиться на дугу  и так далее. В конце концов, агенты достигнут равновесия Нэша, оплачивая свою собственную отдельную дугу. Такое распределение имеет социальную цену , где  является -ым гармоническим числом, что равно . Хотя это значение не ограничено, цена стабильности экспоненциально лучше цены анархии в этой игре.

Верхняя граница цены стабильности 
По определению игры на построение сети являются , поэтому они допускают потенциальную функцию .

Теорема. [Теорема 19.13 из книги 1] Предположим, что существует константы  и , такие, что для любой стратегии 
 
Тогда цена стабильности меньше .

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

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

Тривиально получаем  и вычисления выше дают , так что можно привлечь теорему для верхней границы цены стабильности.

См. также 
  — игра без цены стабильности.

Примечания

Литература 

 
 
 

Теория игр
Неподвижные точки (математика)