Разделение между грубыми коррелированными равновесиями и коррелированными равновесиями

16

Я ищу примеры методов доказательства цены границ анархии, которые способны отделить цену анархии от грубого коррелированного равновесия (ограничивающий набор динамики без внешнего сожаления) от цены анархии над коррелированным равновесием (ограничивающий комплектация без своп-сожалений). Известны ли естественные разделения этого типа?

Одним из препятствий к разделению этих двух классов является то, что наиболее естественный (и распространенный) способ доказать цену границ анархии - это наблюдать только то, что в состоянии равновесия ни у одного игрока нет стимула отклоняться от выполнения своих действий на OPT и каким-то образом использовать это. соединить социальное обеспечение в определенной конфигурации с социальным обеспечением ОПТ. К сожалению, любое доказательство того, что цена анархии по сравнению с грубыми коррелированными равновесиями невелика и учитывает только отклонения каждого игрока от одного альтернативного действия (скажем, действие от OPT), также справедливо для коррелированных равновесий и поэтому не может обеспечить разделение. Это потому, что единственная разница между грубым коррелированным равновесием и коррелированным равновесием заключается в способности игрока в коррелированном равновесии одновременно учитыватьмножественные отклонения, обусловленные его сигналом игрового профиля, выведенного из равновесного распределения.

Известны ли такие разделения?

Аарон Рот
источник

Ответы:

7

Исправьте M >> 1 >> e и посмотрите на следующую координационную игру для двух игроков (оба игрока получают одинаковую утилиту):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

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

M  |  2e

2e |  M

для которого каждое коррелированное равновесие даст каждому игроку больше, чем M / 2 полезности.

С другой стороны, рассмотрим совместное распределение вероятностей, дающее вероятность 1/2 каждому из 1, и, следовательно, полезность 1 каждому игроку. Утверждение состоит в том, что это грубое равновесие. В грубом равновесии возможные отклонения рядового игрока относятся к одной из чистых стратегий независимо от результата совместного распределения. Теперь, если известно только то, что игрок колонок смешивается равномерно между 2-м и 4-м столбцами, то максимальная полезность, которую может получить игрок строки, составляет 0,5 + e <1, поэтому отклонение не выгодно.

Ноам
источник