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

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

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

Определение править

Игра определяется так: $G=⟨<!--\; ⟨\; -->N,\mathrm{\Omega <!--\; \Omega \; -->},⟨<!--\; ⟨\; -->A_i,u_i,T_i,{\mathrm{\tau <!--\; \tau \; -->}}_i,p_i,C_i{⟩<!--\; ⟩\; -->}_{i\in <!--\; \in \; -->N}⟩<!--\; ⟩\; -->$$G=\langle N,\Omega ,\langle A_{i},u_{i},T_{i},\tau _{i},p_{i},C_{i}\rangle _{i\in N}\rangle$ , где

1. $N$$N$  — множество игроков.
2. $\mathrm{\Omega <!--\; \Omega \; -->}$$\Omega$  — множество состояний природы. Пример состояния природы: порядок колоды в карточной игре.
3. $A_i$$A_{i}$  — множество действий игрока $i$$i$ . Пусть $A=A_1\times <!--\; \times \; -->A_2\times <!--\; \times \; -->\cdots <!--\; \cdots \; -->\times <!--\; \times \; -->A_N$$A=A_{1}\times A_{2}\times \dotsb \times A_{N}$ .
4. $T_i$$T_{i}$  — множество типов игрока $i$$i$ . Тип определяется по правилу ${\mathrm{\tau <!--\; \tau \; -->}}_i:<!--\; :\; -->\mathrm{\Omega <!--\; \Omega \; -->}\to <!--\; \to \; -->T_i$$\tau _{i}\colon \Omega \rightarrow T_{i}$ .
5. $C_i\subseteq <!--\; \subseteq \; -->A_i\times <!--\; \times \; -->T_i$$C_{i}\subseteq A_{i}\times T_{i}$  определяет доступные действия для игрока $i$$i$ , обладающего неким типом в $T_i$$T_{i}$ .
6. $u_i:<!--\; :\; -->\mathrm{\Omega <!--\; \Omega \; -->}\times <!--\; \times \; -->A\to <!--\; \to \; -->R$$u_{i}\colon \Omega \times A\rightarrow R$  функция выигрыша игрока $i$$i$ . Более формально, пусть $L=\{(\mathrm{\omega <!--\; \omega \; -->},a_1,\dots <!--\; \dots \; -->,a_N)\mid <!--\; \mid \; -->\mathrm{\omega <!--\; \omega \; -->}\in <!--\; \in \; -->\mathrm{\Omega <!--\; \Omega \; -->},\mathrm{\forall <!--\; \forall \; -->}i,(a_i,{\mathrm{\tau <!--\; \tau \; -->}}_i(\mathrm{\omega <!--\; \omega \; -->}))\in <!--\; \in \; -->C_i\}$$L=\{(\omega ,a_{1},\dotsc ,a_{N})\mid \omega \in \Omega ,\forall i,(a_{i},\tau _{i}(\omega ))\in C_{i}\}$ , и $u_i:<!--\; :\; -->L\to <!--\; \to \; -->R$$u_{i}\colon L\rightarrow R$ .
7. $p_i$$p_{i}$  распределение вероятности на $\mathrm{\Omega <!--\; \Omega \; -->}$$\Omega$  для каждого игрока $i$$i$ , то есть каждый игрок по-разному оценивает вероятности состояний природы; в течение игры они его не знают.

Чистая стратегия $s_i:<!--\; :\; -->T_i\to <!--\; \to \; -->A_i$$s_{i}\colon T_{i}\rightarrow A_{i}$  должна удовлетворять $(s_i(t_i),t_i)\in <!--\; \in \; -->C_i$$(s_{i}(t_{i}),t_{i})\in C_{i}$  для всех $t_i$$t_{i}$ . Стратегия каждого игрока зависит только от его типа, так как типы других игроков для него скрыты. Ожидаемый выигрыш игрока $i$$i$  при данном стратегическом профиле равен $u_i(S)=E_{\mathrm{\omega <!--\; \omega \; -->}\sim <!--\; \sim \; -->p_i}[u_i(\mathrm{\omega <!--\; \omega \; -->},s_1({\mathrm{\tau <!--\; \tau \; -->}}_1(\mathrm{\omega <!--\; \omega \; -->})),\dots <!--\; \dots \; -->,s_N({\mathrm{\tau <!--\; \tau \; -->}}_N(\mathrm{\omega <!--\; \omega \; -->})))]$$u_{i}(S)=E_{\omega \sim p_{i}}[u_{i}(\omega ,s_{1}(\tau _{1}(\omega )),\dotsc ,s_{N}(\tau _{N}(\omega )))]$ .

Пусть $S_i$$S_{i}$  — множество чистых стратегий, $S_i=\{s_i:<!--\; :\; -->T_i\to <!--\; \to \; -->A_i\mid <!--\; \mid \; -->(s_i(t_i),t_i)\in <!--\; \in \; -->C_i,\mathrm{\forall <!--\; \forall \; -->}{t}_i\}.$$S_{i}=\{s_{i}\colon T_{i}\rightarrow A_{i}\mid (s_{i}(t_{i}),t_{i})\in C_{i},\forall t_{i}\}.$ 

Байесовское равновесие игры $G$$G$  определяется как равновесие Нэша (возможно, в смешанных стратегиях) игры $\stackrel{^<!--\; ^\; -->}{G}=⟨<!--\; ⟨\; -->N,\stackrel{^<!--\; ^\; -->}{A}=S_1\times <!--\; \times \; -->S_2\times <!--\; \times \; -->\cdots <!--\; \cdots \; -->\times <!--\; \times \; -->S_N,\stackrel{^<!--\; ^\; -->}{u}=u⟩<!--\; ⟩\; -->$${\hat {G}}=\langle N,{\hat {A}}=S_{1}\times S_{2}\times \dotsb \times S_{N},{\hat {u}}=u\rangle$ . Если игра $G$$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 рационален и т.д. до бесконечности) игра пройдёт по следующему равновесному (совершенное байесовское равновесие) сценарию:

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

См. также править

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

Литература править

• Gibbons, Robert. Game Theory for Applied Economists (неопр.). — Princeton University Press, 1992. — С. 144—152.
• Levin, Jonathan Games with Incomplete Information  (неопр.) (2002). Дата обращения: 25 августа 2016.