Игра с неполной информацией

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

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

Определение

Игра определяется так: $G = ⟨ N, Ω, ⟨ A_{i}, u_{i}, T_{i}, τ_{i}, p_{i}, C_{i} ⟩_{i \in N} ⟩$ , где

$N$ — множество игроков.
$Ω$ — множество состояний природы. Пример состояния природы: порядок колоды в карточной игре.
$A_{i}$ — множество действий игрока $i$ . Пусть $A = A_{1} \times A_{2} \times \dots \times A_{N}$ .
$T_{i}$ — множество типов игрока $i$ . Тип определяется по правилу $τ_{i} : Ω \to T_{i}$ .
$C_{i} \subseteq A_{i} \times T_{i}$ определяет доступные действия для игрока $i$ , обладающего неким типом в $T_{i}$ .
$u_{i} : Ω \times A \to R$ функция выигрыша игрока $i$ . Более формально, пусть $L = {(ω, a_{1}, \dots, a_{N}) ∣ ω \in Ω, \forall i, (a_{i}, τ_{i} (ω)) \in C_{i}}$ , и $u_{i} : L \to R$ .
$p_{i}$ распределение вероятности на $Ω$ для каждого игрока $i$ , то есть каждый игрок по-разному оценивает вероятности состояний природы; в течение игры они его не знают.

Чистая стратегия $s_{i} : T_{i} \to A_{i}$ должна удовлетворять $(s_{i} (t_{i}), t_{i}) \in C_{i}$ для всех $t_{i}$ . Стратегия каждого игрока зависит только от его типа, так как типы других игроков для него скрыты. Ожидаемый выигрыш игрока $i$ при данном стратегическом профиле равен $u_{i} (S) = E_{ω \sim p_{i}} [u_{i} (ω, s_{1} (τ_{1} (ω)), \dots, s_{N} (τ_{N} (ω)))]$ .

Пусть $S_{i}$ — множество чистых стратегий, $S_{i} = {s_{i} : T_{i} \to A_{i} ∣ (s_{i} (t_{i}), t_{i}) \in C_{i}, \forall t_{i}} .$

Байесовское равновесие игры $G$ определяется как равновесие Нэша (возможно, в смешанных стратегиях) игры $\hat{G} = ⟨ N, \hat{A} = S_{1} \times S_{2} \times \dots \times S_{N}, \hat{u} = u ⟩$ . Если игра $G$ конечна, байесовское равновесие существует всегда.

Примеры

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

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

Подозреваемый имеет два возможных типа: «преступник» и «законопослушный». У шерифа есть только один тип. Подозреваемому известен его тип, шерифу же он неведом. Таким образом, в игре присутствует неполная информация, она относится к классу байесовских. По мнению шерифа, с вероятностью p подозреваемый является преступником, с вероятностью 1-p — законопослушным гражданином. Величины p и 1-p известны обоим игрокам, поскольку делается допущение об общем априорном распределении. Именно оно позволяет преобразовать эту игру в игру полной, но несовершенной информации.

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


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


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

Если оба имеется общее знание о рациональности игроков (игрок 1 рационален; игрок 1 знает, что игрок 2 рационален; игрок 1 знает, что игрок 2, знает, что игрок 1 рационален и т.д. до бесконечности) игра пройдёт по следующему равновесному (совершенное байесовское равновесие) сценарию^[2]^[3]:

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

См. также

Примечания

Шаблон:Reflist

Литература

Шаблон:Теория игр

↑ Harsanyi, John C., 1967/1968. "Games with Incomplete Information Played by Bayesian Players, I-III." Management Science 14 (3): 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III).
↑ Шаблон:Cite web
↑ Шаблон:Статья

[1] Harsanyi, John C., 1967/1968. "Games with Incomplete Information Played by Bayesian Players, I-III." Management Science 14 (3): 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III).

[2] Шаблон:Cite web

[3] Шаблон:Статья

[1]

[2]

[3]

Игра с неполной информацией

Содержание

Определение

Примеры

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

См. также

Примечания

Литература

Навигация

Игра с неполной информацией

Определение

Примеры

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

См. также

Примечания

Литература

Навигация

Поиск