Просмотр кода страницы Игра с неполной информацией

'''Байесовская игра''' ({{lang-en|Bayesian game}}) или '''игра с неполной информацией''' ({{lang-en|incomplete information game}}) в [[Теория игр|теории игр]] характеризуются неполнотой информации о соперниках (их возможных стратегиях и выигрышах), при этом у игроков есть веры относительно этой неопределённости. Байесовскую игру можно преобразовать в игру [[Игра с полной информацией|полной]], но [[Игра с несовершенной информацией|несовершенной]] информации, если принять допущение об общем априорном распределении. В отличие от неполной информации, несовершенная информация включает знание стратегий и выигрышей соперников, но история игры (предыдущие действия оппонентов) доступна не всем участникам.

[[Джон Харсаньи]] описал байесовские игры следующим образом<ref>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).</ref>. В дополнение к фактическим участникам игры появляется виртуальный игрок «[[Природа (теория игр)|Природа]]». Природа наделяет каждого из фактических участников [[Случайная переменная|случайной переменной]], значения которой называются ''типами''. Распределение ([[Плотность вероятности|плотность]] или [[Функция вероятности|функция]] вероятности) типов для каждого из игроков известно. В начале игры природа «выбирает» типы игроков. Тип, в частности, определяет функцию выигрыша участника. Таким образом, неполнота информации в байесовской игре — незнание по крайней мере одним игроком типа некого другого участника. Игроки обладают ''верами'' относительно типов соперников; вера — вероятностное распределение на множестве возможных типов. В процессе игры веры обновляются в соответствии с [[Теорема Байеса|теоремой Байеса]].

== Определение ==
Игра определяется так:
<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'' известны обоим игрокам, поскольку делается допущение об общем априорном распределении. Именно оно позволяет преобразовать эту игру в игру полной, но несовершенной информации.

Шериф предпочёл бы стрелять, если стреляет подозреваемый, и избежать стрельбы в противном случае (даже если подозреваемый действительно является преступником). Преступник склонен стрелять (даже если шериф не стреляет), в то время как законопослушный гражданин хочет избежать конфликта любым образом (даже если шериф стреляет). Матрицы выигрышей зависит от типа подозреваемого:
{| class="wikitable" style="text-align:center"
|+ &nbsp;
! colspan="2" rowspan="2" |Тип = «Законопослушный»
! colspan="2" |Действие шерифа
|-
!Стрелять
!Не стрелять
|-
! rowspan="2" |Действие подозреваемого
!Стрелять
| -3, -1
| -1, -2
|-
!Не стрелять
| -2, -1
|0, 0
|}
{| class="wikitable" style="text-align:center"
|+ &nbsp;
! colspan="2" rowspan="2" |Тип = «Преступник»
! colspan="2" |Действие шерифа
|-
!Стрелять
!Не стрелять
|-
! rowspan="2" |Действие подозреваемого
!Стрелять
|0, 0
|2, -2
|-
!Не стрелять
| -2, -1
| -1,1
|}
Если оба имеется [[общее знание]] о рациональности игроков (игрок 1 рационален; игрок 1 знает, что игрок 2 рационален; игрок 1 знает, что игрок 2, знает, что игрок 1 рационален и т.д. до бесконечности) игра пройдёт по следующему равновесному (совершенное байесовское равновесие) сценарию<ref>{{cite web|url=https://class.coursera.org/gametheory-003/lecture/109|title=Coursera|website=Coursera|lang=en|access-date=2016-06-16|archive-date=2016-08-10|archive-url=https://web.archive.org/web/20160810093845/https://class.coursera.org/gametheory-003/lecture/109|deadlink=no}}</ref><ref>{{статья |заглавие=A Generalized Quantum-Inspired Decision Making Model for Intelligent Agent |издание={{Нп3|The Scientific World Journal}} |том=2014 |doi=10.1155/2014/240983 |issn=1537-744X |pmc=3977121 |pmid=24778580 |язык=en |тип=journal |автор=Hu, Yuhuang; Loo, Chu Kiong |число=17 |месяц=3 |год=2014}}</ref>:

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

== См. также ==
* [[Игра с полной информацией]]
* [[Игра с совершенной информацией]]
* [[Игра с несовершенной информацией]]

== Примечания ==
{{Reflist}}

== Литература ==
* {{книга |заглавие=Game Theory for Applied Economists |издательство=[[Princeton University Press]] |год=1992 |страницы=144—152 |ссылка=https://books.google.com/books?id=8ygxf2WunAIC&pg=PA144 |язык=und |автор=Gibbons, Robert}}
* {{cite web|last1=Levin|first1=Jonathan|title=Games with Incomplete Information|url=http://web.stanford.edu/~jdlevin/Econ%20203/Bayesian.pdf|year=2002|accessdate=2016-08-25}}

{{Теория игр}}

[[Категория:Теория игр]]
[[Категория:Классы игр|*]]
[[Категория:Байесовская статистика]]