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

Коррелированное равновесие
Концепция решения в теории игр
Отношение
Суперсет	Равновесие Нэша
Значение
Предложено	Роберт Ауманн
Пример	Курица

В теории игр коррелированное равновесие представляет собой более общую концепцию решения , чем хорошо известное равновесие Нэша . Впервые его обсудил математик Роберт Ауманн в 1974 году. Идея состоит в том, что каждый игрок выбирает свои действия в соответствии со своим личным наблюдением за ценностью одного и того же публичного сигнала. Стратегия назначает действие каждому возможному наблюдению, которое может сделать игрок. Если ни один игрок не хочет отклоняться от своей стратегии (при условии, что остальные тоже не отклоняются), распределение, из которого извлекаются сигналы, называется коррелированным равновесием.

Формальное определение

Ан $N$-игровая стратегическая игра $\displaystyle (N,\{A_{i}\},\{u_{i}\})$ характеризуется набором действий $A_{i}$ и функция полезности $u_{i}$ для каждого игрока $i$. Когда игрок $i$ выбирает стратегию $a_{i}\in A_{i}$ а остальные игроки выбирают профиль стратегии, описанный $N-1$-кортеж $a_{-i}$, затем игрок $i$полезность $\displaystyle u_{i}(a_{i},a_{-i})$.

для Модификация стратегии игрока $i$ это функция $\phi _{i}\colon A_{i}\to A_{i}$. То есть, $\phi _{i}$ сообщает игроку $i$ изменить свое поведение, играя в действие $\phi _{i}(a_{i})$ когда приказано играть $a_{i}$.

Позволять $(\Omega ,\pi )$ — счетное вероятностное пространство . Для каждого игрока $i$, позволять $P_{i}$ быть его информационным разделом, $q_{i}$ быть $i$сзади и пусть $s_{i}\colon \Omega \rightarrow A_{i}$, присваивая одно и то же значение состояниям в одной и той же ячейке $i$информационный раздел. Затем $((\Omega ,\pi ),P_{i},s_{i})$ это коррелированное равновесие стратегической игры $(N,A_{i},u_{i})$ если для каждого игрока $i$ и для каждой модификации стратегии $\phi _{i}$:

$\sum _{\omega \in \Omega }q_{i}(\omega )u_{i}(s_{i}(\omega ),s_{-i}(\omega ))\geq \sum _{\omega \in \Omega }q_{i}(\omega )u_{i}(\phi _{i}(s_{i}(\omega )),s_{-i}(\omega ))$

Другими словами, $((\Omega ,\pi ),P_{i})$ является коррелированным равновесием, если ни один игрок не может улучшить свою ожидаемую полезность посредством модификации стратегии.

Пример

	D являются	C отойди
D являются	0, 0	7, 2
C отойди	2, 7	6, 6
Игра в курицу

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

В этой игре существует три равновесия Нэша . Два равновесия по Нэшу в чистой стратегии — это ( D , C ) и ( C , D ). Существует также равновесие в смешанной стратегии , когда оба игрока сдаются с вероятностью 2/3.

Теперь рассмотрим третью сторону (или какое-то естественное событие), которая вытягивает одну из трех карт с пометками: ( C , C ), ( D , C ) и ( C , D ) с одинаковой вероятностью, т. е. вероятностью 1/3 для каждой. карта. После вытягивания карты третья сторона сообщает игрокам о стратегии, назначенной им на карте (но не о стратегии, назначенной их противнику). Предположим, игроку назначен D , он не хотел бы отклоняться, предполагая, что другой игрок использовал назначенную ему стратегию, поскольку он получит 7 (наивысший возможный выигрыш). Предположим, игроку назначен C . Тогда другой игрок сыграет C с вероятностью 1/2 и D с вероятностью 1/2. Ожидаемая полезность Дерзости равна 7(1/2) + 0(1/2) = 3,5, а ожидаемая полезность струсилства равна 2(1/2) + 6(1/2) = 4. Итак, игрок предпочитаю струсить.

Поскольку ни у одного из игроков нет стимула отклоняться, это коррелированное равновесие. Ожидаемый выигрыш для этого равновесия составляет 7(1/3) + 2(1/3) + 6(1/3) = 5, что выше, чем ожидаемый выигрыш в равновесии Нэша смешанной стратегии.

Следующее коррелированное равновесие имеет еще более высокую выгоду для обоих игроков: Рекомендовать ( C , C ) с вероятностью 1/2, а также ( D , C ) и ( C , D ) с вероятностью 1/4 каждый. Тогда, когда игроку рекомендуется сыграть C , он знает, что другой игрок сыграет D с (условной) вероятностью 1/3 и C с вероятностью 2/3, и получит ожидаемый выигрыш 14/3, который равен (не менее ожидаемый выигрыш при игре D. чем ) В этом коррелированном равновесии оба игрока получают ожидание 5,25. Можно показать, что это коррелированное равновесие с максимальной суммой ожидаемых выигрышей двух игроков.

Изучение

Одним из преимуществ коррелированных равновесий является то, что они требуют меньше вычислительных затрат, чем равновесия Нэша . Это можно объяснить тем фактом, что для вычисления коррелированного равновесия требуется только решение линейной программы, тогда как для решения равновесия Нэша требуется полностью найти его фиксированную точку. Другой способ увидеть это состоит в том, что два игрока могут реагировать на исторические ходы игры друг друга и в конечном итоге прийти к коррелированному равновесию.

Ссылки

Источники

• Фуденберг, Дрю и Жан Тироль (1991) Теория игр , MIT Press , 1991, ISBN   0-262-06141-4
• Лейтон-Браун, Кевин; Шохам, Йоав (2008), Основы теории игр: краткое междисциплинарное введение , Сан-Рафаэль, Калифорния: Morgan & Claypool Publishers, ISBN  978-1-59829-593-1 . 88-страничное математическое введение; см. раздел 3.5. Бесплатно онлайн. Архивировано 15 августа 2000 г. в Wayback Machine во многих университетах.
• Осборн, Мартин Дж. и Ариэль Рубинштейн (1994). Курс теории игр , MIT Press. ISBN   0-262-65040-1 (современное введение для выпускников)
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы , Нью-Йорк: Издательство Кембриджского университета , ISBN  978-0-521-89943-7 . Полный справочник с вычислительной точки зрения; см. разделы 3.4.5 и 4.6. Можно скачать бесплатно онлайн .
• Ева Тардос (2004) Заметки по алгоритмической теории игр (обратите внимание на важную опечатку) [1]
• Искандер Карибжанов. Код MATLAB для построения набора коррелированных равновесий в игре в нормальной форме для двух игроков.
• Ноам Нисан (2005) Конспекты лекций из курса « Темы на границе экономики и вычислений» (строчную букву u следует заменить на u_i) [2]