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

редактировать

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

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

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

Содержание

1 Спецификация игр
2 Байесовское равновесие по Нэшу
3 Варианты байесовского равновесия
- 3.1 Идеальное байесовское равновесие
- 3.2 Стохастические байесовские игры
- 3.3 Неполная информация о коллективном агентстве
4 Пример
- 4.1 Дилемма шерифа
5 См. Также
6 Ссылки
7 Дополнительная литература

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

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

Формально такая игра определяется следующим образом: $G = ⟨N, Ω, p, ⟨A i, ui, T i, τ i⟩ i ∈ N⟩ {\ displaystyle G = \ langle N, \ Omega, p, \ langle A_ {i}, u_ {i}, T_ {i}, \ tau _ {i} \ rangle _ {i \ in N} \ rangle}$ ${\ displaystyle G = \ langle N, \ Omega, p, \ langle A_ {i}, u_ {i}, T_ {i}, \ tau _ {i} \ rangle _ {i \ in N} \ rangle}$ , где

$N {\ displaystyle N}$ $N$ - множество игроков.
$Ω {\ displaystyle \ Omega}$ $\ Omega$ - множество состояний природы.
$A i {\ displaystyle A_ {i}}$ $A_ {i}$ - это набор действий для игрока $i {\ displaystyle i}$ $я$ . Пусть $A = A 1 × A 2 × ⋯ × AN {\ displaystyle A = A_ {1} \ times A_ {2} \ times \ dotsb \ times A_ {N}}$ $A = A_ {1} \ раз A_ {2} \ times \ dotsb \ times A_ {N}$ .
$T i {\ displaystyle T_ {i}}$ $T_ { i}$ - это набор типов для игрока $i {\ displaystyle i}$ $я$ . Учитывая состояние, тип игрока $i {\ displaystyle i}$ $я$ задается функцией $τ i: Ω → T i {\ displaystyle \ tau _ {i} \ двоеточие \ Омега \ rightarrow T_ {i}}$ $\ tau _ {i} \ двоеточие \ Omega \ rightarrow T_ {i}$ . Таким образом, для каждого состояния природы в игре будут разные типы игроков.
$ui: T i × A → R {\ displaystyle u_ {i} \ двоеточие T_ {i} \ times A \ rightarrow \ mathbb {R }}$ ${\ displaystyle u_ {i} \ двоеточие T_ {i} \ times A \ rightarrow \ mathbb {R}}$ - функция выигрыша для игрока. $i {\ displaystyle i}$ $я$ .
$p {\ displaystyle p}$ $p$ - (априорное) распределение вероятностей на $Ω {\ displaystyle \ Omega}$ $\ Omega$ .

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

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

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

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

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

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

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

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

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

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

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

Определение байесовских игр было объединено с стохастическими играми, чтобы учесть состояния среды (например, состояния физического мира) и стохастические переходы между состояниями. Полученная в результате модель «стохастической байесовской игры» решается с помощью рекурсивной комбинации байесовского равновесия по Нэшу и уравнения оптимальности Беллмана.

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

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

Пример

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

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

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

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


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


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

Если оба игрока рациональны и оба знают, что оба рациональны и все, что известно известно, что любой игрок известен каждому игроку (т. е. игрок 1 знает, что игрок 2 знает, что игрок 1 рациональн, а игрок 2 знает это, и т. д. до бесконечности - общеизвестно ), игра в игре будет в соответствии с идеальным байесовским равновесием:

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

См. Также

Ссылки

Дополнительная литература

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