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

Решение теории игр

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

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

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

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

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

${\displaystyle \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 ))}$

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

Пример

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

В этой игре есть три равновесия Нэша . Два равновесия Нэша в чистой стратегии — это ( 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 в ожидании. Можно показать, что это коррелированное равновесие с максимальной суммой ожидаемых выигрышей для двух игроков.

Изучение коррелированных равновесий

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

Ссылки

1. Ауманн, Роберт (1974). «Субъективность и корреляция в рандомизированных стратегиях». Журнал математической экономики . 1 (1): 67–96. CiteSeerX  10.1.1.120.1740 . doi :10.1016/0304-4068(74)90037-8.
2. Ауманн, Роберт (1987). «Коррелированное равновесие как выражение байесовской рациональности». Econometrica . 55 (1): 1–18. CiteSeerX 10.1.1.295.4243 . doi :10.2307/1911154. JSTOR  1911154. S2CID  18649722. 
3. Пападимитриу, Христос Х.; Рафгарден, Тим (2008). «Вычисление коррелированных равновесий в многопользовательских играх». J. ACM . 55 (3): 14:1–14:29. CiteSeerX 10.1.1.335.2634 . doi :10.1145/1379759.1379762. S2CID  53224027. 
4. Фостер, Дин П.; Вохра, Ракеш В. (1996). «Калиброванное обучение и коррелированное равновесие». Игры и экономическое поведение .

Источники

• Фуденберг, Дрю и Жан Тироль (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 во многих университетах.
• Osborne, Martin J. и Ariel Rubinstein (1994). Курс теории игр , MIT Press. ISBN 0-262-65040-1 (современное введение на уровне аспирантуры) 
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, игровые и логические основы, Нью-Йорк: Cambridge University Press , ISBN 978-0-521-89943-7. Полный справочник с точки зрения вычислений; см. разделы 3.4.5 и 4.6. Можно бесплатно загрузить онлайн.
• Эва Тардос (2004) Заметки для занятий по теории алгоритмических игр (обратите внимание на важную опечатку) [1]
• Искандер Карибжанов. Код MATLAB для построения набора коррелированных равновесий в игре двух игроков в нормальной форме
• Ноам Нисан (2005) Конспект лекций по курсу « Темы на границе экономики и вычислений» (строчную букву u следует заменить на u_i) [2]