Байесовская игра - Bayesian game

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

Джон К. Харсаньи описывает байесовскую игру следующим образом.^[1] Каждый игрок в игре связан с набором типов, причем каждый тип в наборе соответствует возможной функции выигрыша для этого игрока. В дополнение к реальным игрокам в игре есть специальный игрок, называемый Природа. Природа случайно выбирает тип для каждого игрока в соответствии с распределение вероятностей через пространства типов игроков. Это распределение вероятностей известно всем игрокам («общее предварительное предположение»). Такой подход к моделированию превращает игры с неполной информацией в игры несовершенная информация (в котором история игры в игре известна не всем игрокам).

Неполнота информации означает, что по крайней мере один игрок не уверен в типе (и, следовательно, в функции выплаты) другого игрока. Такие игры называются Байесовский потому что обычно предполагается, что игроки обновляют свои убеждения в соответствии с Правило Байеса. В частности, мнение игрока о типе другого игрока может меняться в соответствии с его собственным типом.

Спецификация игр

В байесовской игре необходимо указать пространства типов, пространства стратегий, функции выигрыша и предыдущие убеждения. Стратегия для игрока - это полный план действий, охватывающий все непредвиденные обстоятельства, которые могут возникнуть для каждого типа игрока. Типовое пространство для игрока - это всего лишь набор всех возможных типы этого игрока. Убеждения игрока описывают неуверенность этого игрока в типах других игроков. Каждое убеждение - это вероятность того, что другие игроки имеют определенные типы, учитывая тип игрока с этим убеждением. Функция выигрыша является функцией профилей и типов стратегии.

Формально такую ​​игру дают:^[2]${\displaystyle G=\langle N,\Omega ,p,\langle A_{i},u_{i},T_{i},\tau _{i}\rangle _{i\in N}\rangle }$, куда

1. ${\displaystyle N}$ это набор игроков.
2. ${\displaystyle \Omega }$ это набор состояний природы.
3. ${\displaystyle A_{i}}$ это набор действий для игрока ${\displaystyle i}$. Позволять ${\displaystyle A=A_{1}\times A_{2}\times \dotsb \times A_{N}}$.
4. ${\displaystyle T_{i}}$ это набор типов для игрока ${\displaystyle i}$. Учитывая состояние, тип игрока ${\displaystyle i}$ задается функцией ${\displaystyle \tau _{i}\colon \Omega \rightarrow T_{i}}$. Итак, для каждого состояния природы в игре будут разные типы игроков.
5. ${\displaystyle u_{i}\colon T_{i}\times A\rightarrow \mathbb {R} }$ функция выигрыша для игрока ${\displaystyle i}$.
6. ${\displaystyle p}$ - (априорное) распределение вероятностей по ${\displaystyle \Omega }$.

Чистая стратегия для игрока ${\displaystyle i}$ это функция ${\displaystyle s_{i}\colon T_{i}\rightarrow A_{i}}$. Смешанная стратегия для игрока ${\displaystyle i}$ это функция ${\displaystyle \sigma _{i}\colon T_{i}\rightarrow \Delta A_{i}}$, куда ${\displaystyle \Delta A_{i}}$ - множество всех распределений вероятностей на ${\displaystyle A_{i}}$. Обратите внимание, что стратегия любого игрока зависит только от его типа.

Профиль стратегии ${\displaystyle \sigma }$ это стратегия для каждого игрока. Профиль стратегии определяет ожидаемые выигрыши для каждого игрока, где ожидание берется как для набора состояний природы (и, следовательно, профилей типов) в отношении убеждений. ${\displaystyle p}$, и рандомизация действий, подразумеваемая любыми смешанными стратегиями в профиле ${\displaystyle \sigma }$.

Байесовское равновесие по Нэшу

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

Аналогичная концепция может быть определена для байесовской игры, с той разницей, что стратегия каждого игрока максимизирует его ожидаемый выигрыш с учетом его убеждений о состоянии природы. Убеждения игрока о состоянии природы формируются путем определения априорных вероятностей. ${\displaystyle p}$ по собственному типу согласно правилу Байеса.

А Байесовское равновесие по Нэшу определяется как профиль стратегии, который максимизирует ожидаемый выигрыш для каждого игрока с учетом его убеждений и стратегий, используемых другими игроками. То есть профиль стратегии ${\displaystyle \sigma }$ является байесовским равновесием по Нэшу тогда и только тогда, когда для каждого игрока ${\displaystyle i,}$ фиксируя стратегии всех остальных игроков, стратегия ${\displaystyle \sigma _{i}}$ максимизирует ожидаемый выигрыш игрока ${\displaystyle i}$ согласно его убеждениям.^[2]

Варианты байесовского равновесия

Идеальное байесовское равновесие

Основная статья: Идеальное байесовское равновесие

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

Чтобы справиться с этими проблемами, необходимо использовать идеальное байесовское равновесие в духе подигра идеальное равновесие требует, чтобы, начиная с любого набора информации, последующая игра была оптимальной. Более того, это требует, чтобы убеждения обновлялись в соответствии с правилом Байеса на каждом пути игры, который происходит с положительной вероятностью.

Стохастические байесовские игры

Определение байесовских игр было объединено с стохастические игры чтобы учесть состояния окружающей среды (например, состояния физического мира) и стохастические переходы между состояниями.^[3] Результирующая модель "стохастической байесовской игры" решается с помощью рекурсивной комбинации байесовского равновесия по Нэшу и Уравнение оптимальности Беллмана.

Неполная информация о коллективном агентстве

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

Пример

Дилемма шерифа

Шериф сталкивается с вооруженным подозреваемым. Оба должны одновременно решить, стрелять в другого или нет.

Подозреваемый может относиться к категории «преступник» или «гражданское лицо». У шерифа только один тип. Подозреваемый знает его тип и тип шерифа, но шериф не знает тип подозреваемого. Таким образом, есть неполная информация (потому что у подозреваемого есть личная информация), что превращает это в байесовскую игру. Есть вероятность п что подозреваемый - преступник, и вероятность 1-п что подозреваемый - гражданское лицо; оба игрока знают об этой вероятности (общее предварительное предположение, которое может быть преобразовано в игру с полной информацией с несовершенная информация ).

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

Type = "Гражданский"		Действия шерифа
		Стрелять	Нет
Действия подозреваемого	Стрелять	-3, -1	-1, -2
	Нет	-2, -1	0, 0

Тип = "Преступник"		Действия шерифа
		Стрелять	Нет
Действия подозреваемого	Стрелять	0, 0	2, -2
	Нет	-2, -1	-1,1

Если оба игрока рациональны и оба знают, что оба игрока рациональны и все, что известно любому игроку, известно каждому игроку (т.е. игрок 1 знает, что игрок 2 знает, что игрок 1 рациональн, а игрок 2 знает это и т. Д.) до бесконечности – всем известный факт ), ход игры в соответствии с идеальным байесовским равновесием будет следующим:^[6][7]

Когда тип "гражданский", доминирующая стратегия поскольку подозреваемый - не стрелять, а когда речь идет о «преступнике», доминирующая стратегия подозреваемого - стрелять; Таким образом, можно исключить альтернативную стратегию со строгим доминированием. При этом, если шериф стреляет, он будет иметь выигрыш 0 с вероятностью p и выигрыш -1 с вероятностью 1-p, то есть ожидаемый выигрыш p-1; если шериф не стреляет, он получит выигрыш -2 с вероятностью p и выигрыш 0 с вероятностью 1-p, то есть ожидаемый выигрыш -2p. Таким образом, Шериф всегда будет стрелять, если p-1> -2p, т.е. когда p> 1/3.

Смотрите также

• Байесовский оптимальный механизм
• Байесовская оптимальная цена
• Байесовское программирование
• Байесовский вывод

Рекомендации

1. Харшани, Джон К., 1967/1968. «Игры с неполной информацией, в которые играют байесовские игроки, I-III». Наука управления 14 (3): 159-183 (Часть I), 14 (5): 320-334 (Часть II), 14 (7): 486-502 (Часть III).
2. Kajii, A .; Моррис, С. (1997). «Устойчивость равновесия к неполной информации». Econometrica. 65 (6): 1283–1309. Дои:10.2307/2171737.
3. Альбрехт, Стефано; Крэндалл, Джейкоб; Рамамурти, Субраманиан (2016). «Вера и истина в гипотетическом поведении». Искусственный интеллект. 235: 63–94. arXiv:1507.07688. Дои:10.1016 / j.artint.2016.02.004.
4. Бахарах, М. (1999). «Интерактивное командное мышление: вклад в теорию сотрудничества». Исследования в области экономики. 53: 117–47. Дои:10.1006 / reec.1999.0188.
5. Ньютон, Дж. (2019). «Агентское равновесие». Игры. 10 (1). Дои:10.3390 / g10010014.
6. "Курсера". Coursera. Получено 2016-06-16.
7. Ху, Юйхуан; Лоо, Чу Кыонг (2014-03-17). «Обобщенная квантовая модель принятия решений для интеллектуального агента». Научный мировой журнал. 2014. Дои:10.1155/2014/240983. ISSN  1537-744X. ЧВК  3977121. PMID  24778580.

дальнейшее чтение

• Гиббонс, Роберт (1992). Теория игр для экономистов-прикладников. Издательство Принстонского университета. С. 144–52.
• Левин, Джонатан (2002). «Игры с неполной информацией» (PDF). Получено 25 августа 2016.