Русская Википедия:Игра с неполной информацией
Байесовская игра (Шаблон:Lang-en) или игра с неполной информацией (Шаблон:Lang-en) в теории игр характеризуются неполнотой информации о соперниках (их возможных стратегиях и выигрышах), при этом у игроков есть веры относительно этой неопределённости. Байесовскую игру можно преобразовать в игру полной, но несовершенной информации, если принять допущение об общем априорном распределении. В отличие от неполной информации, несовершенная информация включает знание стратегий и выигрышей соперников, но история игры (предыдущие действия оппонентов) доступна не всем участникам.
Джон Харсаньи описал байесовские игры следующим образом[1]. В дополнение к фактическим участникам игры появляется виртуальный игрок «Природа». Природа наделяет каждого из фактических участников случайной переменной, значения которой называются типами. Распределение (плотность или функция вероятности) типов для каждого из игроков известно. В начале игры природа «выбирает» типы игроков. Тип, в частности, определяет функцию выигрыша участника. Таким образом, неполнота информации в байесовской игре — незнание по крайней мере одним игроком типа некого другого участника. Игроки обладают верами относительно типов соперников; вера — вероятностное распределение на множестве возможных типов. В процессе игры веры обновляются в соответствии с теоремой Байеса.
Определение
Игра определяется так: <math>G = \langle N, \Omega, \langle A_i,u_i,T_i,\tau_i,p_i,C_i \rangle_{i\in N} \rangle</math>, где
- <math>N</math> — множество игроков.
- <math>\Omega</math> — множество состояний природы. Пример состояния природы: порядок колоды в карточной игре.
- <math>A_i</math> — множество действий игрока <math>i</math>. Пусть <math>A=A_1\times A_2\times\dotsb\times A_N</math>.
- <math>T_i</math> — множество типов игрока <math>i</math>. Тип определяется по правилу <math>\tau_i\colon \Omega \rightarrow T_i</math>.
- <math>C_i \subseteq A_i \times T_i</math> определяет доступные действия для игрока <math>i</math>, обладающего неким типом в <math>T_i</math>.
- <math>u_i\colon \Omega \times A \rightarrow R</math> функция выигрыша игрока <math>i</math>. Более формально, пусть <math>L=\{(\omega,a_1,\dotsc,a_N)\mid\omega \in \Omega, \forall i, (a_i,\tau_i(\omega)) \in C_i\}</math>, и <math>u_i\colon L \rightarrow R</math>.
- <math>p_i</math> распределение вероятности на <math>\Omega</math> для каждого игрока <math>i</math>, то есть каждый игрок по-разному оценивает вероятности состояний природы; в течение игры они его не знают.
Чистая стратегия <math>s_i\colon T_i \rightarrow A_i</math> должна удовлетворять <math>(s_i(t_i),t_i) \in C_i</math> для всех <math>t_i</math>. Стратегия каждого игрока зависит только от его типа, так как типы других игроков для него скрыты. Ожидаемый выигрыш игрока <math>i</math> при данном стратегическом профиле равен <math>u_i(S)=E_{ \omega \sim p_i}[u_i( \omega ,s_1(\tau_1( \omega )),\dotsc,s_N(\tau_N( \omega )))]</math>.
Пусть <math>S_i</math> — множество чистых стратегий, <math>S_i = \{s_i\colon T_i \rightarrow A_i \mid (s_i(t_i),t_i) \in C_i, \forall t_i\}.</math>
Байесовское равновесие игры <math>G</math> определяется как равновесие Нэша (возможно, в смешанных стратегиях) игры <math>\hat{G} = \langle N,\hat{A}=S_1\times S_2\times\dotsb\times S_N, \hat{u} =u \rangle</math>. Если игра <math>G</math> конечна, байесовское равновесие существует всегда.
Примеры
Дилемма шерифа
Шериф сталкивается с подозреваемым. Оба должны одновременно принять решение о том, следует ли стрелять.
Подозреваемый имеет два возможных типа: «преступник» и «законопослушный». У шерифа есть только один тип. Подозреваемому известен его тип, шерифу же он неведом. Таким образом, в игре присутствует неполная информация, она относится к классу байесовских. По мнению шерифа, с вероятностью 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.
См. также
Примечания
Литература
- ↑ 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
- ↑ Шаблон:Статья
