Теория игр

Коррелированное равновесие

Равновесие Нэша требует независимости действий. Но что если игроки могут координироваться через внешнее устройство - светофор, арбитра, случайный сигнал? Коррелированное равновесие Ауманна формализует эту идею и открывает пространство эффективных договорённостей, недоступных при независимом поведении.

  • **Онлайн-реклама:** аукционы Google AdWords используют КР-основанные механизмы для распределения показов между рекламодателями
  • **Светофоры:** схема работы светофора на перекрёстке - это КР в игре водителей: коррелятор рекомендует (ехать, стоять) или (стоять, ехать)
  • **Радиочастотные аукционы FCC:** комбинаторные аукционы используют КР-подход для эффективного распределения спектра
  • **Многоагентное обучение:** no-regret алгоритмы в online learning автоматически сходятся к КР без централизованной координации

Предварительные знания

  • Равновесие Нэша
  • Смешанные стратегии
  • Основы линейного программирования
  • Эволюционная теория игр

Определение коррелированного равновесия

Роберт Ауманн в 1974 году определил коррелированное равновесие (КР) - концепцию более широкую, чем равновесие Нэша. В игре «Куриные гонки» единственное симметричное NE в смешанных стратегиях даёт ожидаемую выплату 0 каждому, тогда как КР с подбрасыванием монеты (рекомендуя (S,T) или (T,S) с вероятностью 1/2) даёт выплату 2 каждому. Google AdWords в 2016 году принёс 79,4 млрд долларов при ценообразовании, основанном на КР-теории.

Что отличает коррелированное равновесие от равновесия Нэша?

Aumann (1974): CE - распределение mu по профилям действий. Посредник сэмплирует профиль (a_1, ..., a_n) ~ mu и приватно сообщает каждому игроку его a_i. Условие равновесия: при наблюдении a_i игрок i не имеет выгоды отклониться, учитывая условное распределение mu(a_{-i} | a_i). Любое равновесие Нэша - частный случай (mu - произведение).

Вычисление: LP и no-regret learning

В игре «Куриные гонки» (Chicken game) действия: S (straight - не уступать) и T (turn - уступить). Выплаты: (S,S) = (-10,-10), (S,T) = (5,-1), (T,S) = (-1,5), (T,T) = (0,0). Два чистых NE: (S,T) и (T,S). Симметричное смешанное NE: каждый выбирает S с вероятностью 1/6. Ожидаемая выплата при смешанном NE: 0. КР с равномерным выбором между (S,T) и (T,S): ожидаемая выплата 2 каждому.

Какова вычислительная сложность нахождения коррелированного равновесия в игре с n игроками и k действиями?

CE определяется как решение системы линейных неравенств: для всех i и всех s_i, s_i´ ∈ A_i: sum_{a_{-i}} mu(s_i, a_{-i}) * [u_i(s_i, a_{-i}) - u_i(s_i´, a_{-i})] >= 0. Это LP размера O(n*k^n). Существование непосредственно следует из того, что любое равновесие Нэша даёт CE. В отличие от Nash (PPAD-полная), CE вычисляется за poly(input).

Сравнение с равновесием Нэша и применения

Практическое применение КР: в аукционах со второй ценой (Vickrey) при нескольких товарах NE сложно вычислить, но оптимальное КР находится через LP. Это основа механизмов комбинаторных аукционов, используемых в Google, Facebook и распределении радиочастот (FCC).

Какой пример показывает, что коррелированное равновесие может быть строго лучше любого равновесия Нэша?

В Chicken (Hawk-Dove) три равновесия Нэша: два чистых (асимметричных) и одно смешанное. Смешанное NE даёт выплаты (3.5, 3.5) с риском столкновения. CE через светофор-посредник (50/50 кто проезжает первым) даёт (5.5, 5.5) - кооперация без столкновений. Это базовая модель урегулирования транспорта и систем приоритетов.

Связи с другими областями

Коррелированное равновесие соединяет классическую теорию игр с онлайн-обучением, теорией аукционов и алгоритмической теорией игр.

  • Равновесие Нэша — Коррелированное равновесие - выпуклое расширение Нэша через публичный сигнал
  • Алгоритмическая теория игр: цена анархии — Коррелированные равновесия достижимы no-regret динамикой - база цены анархии
  • Сигнальные игры — Оба класса используют асимметричную информацию и публичные/частные сигналы

Итоги

  • КР - распределение sigma над профилями действий: каждый игрок, получив рекомендацию, не хочет отклоняться при условии, что другие следуют своим
  • Множество КР - выпуклый многогранник, содержащий все NE и их выпуклые комбинации
  • Вычислительное преимущество: оптимальное КР находится за полиномиальное время через LP (в отличие от PPAD-трудного NE)
  • Алгоритм Multiplicative Weights с sublinear regret обеспечивает сходимость эмпирического распределения к КР
  • КР - основа механизмов онлайн-аукционов, светофоров и многоагентных систем с централизованным координатором

Вопросы для размышления

  • Почему светофор на перекрёстке реализует коррелированное равновесие, а не просто соглашение между водителями?
  • Как связаны no-regret алгоритмы онлайн-обучения и сходимость к КР?
  • В каких ситуациях КР даёт принципиально лучшую суммарную выплату по сравнению с лучшим NE?
Коррелированное равновесие

0

1

Войти