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

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

Формальное определение [ править ]

-Плеер стратегическая игра характеризуется набором действий и функция полезности для каждого игрока . Когда игрок выбирает стратегию, а оставшиеся игроки выбирают профиль стратегии, описываемый -кортежем , тогда полезность игрока равна .${\ displaystyle N}$${\ Displaystyle \ Displaystyle (Н, А_ {я}, и_ {я})}$${\ 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 и_ {я} (а_ {я}, а _ {- я})}$

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

Позвольте быть счетное вероятностное пространство . Для каждого игрока , пусть будет его информационный раздел, быть «s кзади и пусть , назначая такое же значение для состояний в одной и той же ячейке » информационного раздела s. Тогда будет коррелированное равновесие стратегической игры, если для каждого игрока и для каждой модификации стратегии :${\ 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}\left(\phi _{i}\left(s_{i}(\omega )\right),s_{-i}(\omega )\right)}$

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

Пример [ править ]

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

В этой игре есть три равновесия по Нэшу . Две чистые стратегии равновесия по Нэшу - это ( D , C ) и ( C , D ). Также существует смешанная стратегия равновесия, когда каждый игрок решается с вероятностью 1/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 и ожидаемая полезность chickening из 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]

Ссылки [ править ]

Источники [ править ]