Ограничение скорости роста цены анархии через концепции равновесия

Мы знаем и любим множество вложенных классов концепций решений:

• PN: Pure Nash Equilibrium
• MN: Смешанное равновесие по Нэшу
• CE: коррелированное равновесие
• CCE: курс коррелированного равновесия.

Отношения между этими наборами:

$$PN \subset MN \subset CE \subset CCE$$ Мы можем рассмотреть цену анархии по любому из этих концепций решения: наихудшее социальное обеспечение для любого профиля в наборе, разделенное на оптимальное социальное обеспечение: $$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$ Итак, с помощью вышеуказанных условий: Мой вопрос: известны ли их пределы того, насколько быстро может расти это количество? Можно иметь игру с конечной , но неограниченно большой . Но если я знаю, что конечно, также должен быть конечным? ? Насколько больше они могут быть? $$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$ $POA(PN)$$POA(CCE)$$POA(PN)$$POA(MN)$$POA(CE)$

Соотношение между и может быть сколь угодно большим. Рассмотрим следующую игру заторов; у нас есть игроков и предметов, и каждый игрок может выбрать любой предмет. Стоимость для игрока зависит от загруженности выбранного предмета; это если игроков выберут этот предмет. будет резко растущей функцией.$POA(MN)$$POA(PN)$$n$$n$$f(x)$$x$$f$

Единственный чистый Нэш - каждый игрок выбирает уникальный предмет, поэтому каждый платит . С другой стороны, по симметрии, рандомизированная стратегия, в которой каждый игрок выбирает равномерно случайный предмет, представляет собой смешанный Нэш. Если резко возрастет, общая стоимость будет намного дороже, поскольку есть некоторый шанс, что несколько игроков выберут один и тот же предмет.$f(1)$$f$

В этом сообщении в блоге приведен пример, где существует неограниченный разрыв между ценой стабильности CE и MN; Я полагаю, что что-то подобное продемонстрировало бы неограниченный разрыв и для ПД.