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

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

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

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

Спецификация игр [ править ]

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

Формально такая игра дается формулой: ^[2] , где${\ displaystyle G = \ langle N, \ Omega, p, \ langle A_ {i}, u_ {i}, T_ {i}, \ tau _ {i} \ rangle _ {i \ in N} \ rangle}$

1. ${\ displaystyle N}$ это набор игроков.
2. ${\ displaystyle \ Omega}$ это набор состояний природы.
3. ${\ displaystyle A_ {i}}$набор действий для игрока . Пусть .${\ displaystyle i}$${\displaystyle A=A_{1}\times A_{2}\times \dotsb \times A_{N}}$
4. ${\displaystyle T_{i}}$набор типов для игрока . Учитывая состояние, тип игрока задается функцией . Итак, для каждого состояния природы в игре будут разные типы игроков.${\displaystyle i}$${\displaystyle i}$${\displaystyle \tau _{i}\colon \Omega \rightarrow T_{i}}$
5. ${\displaystyle u_{i}\colon T_{i}\times A\rightarrow \mathbb {R} }$- функция выигрыша для игрока .${\displaystyle i}$
6. ${\displaystyle p}$- (априорное) распределение вероятностей по .${\displaystyle \Omega }$

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

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

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

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

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

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

Для конечных байесовских игр, т. Е. Когда и действие, и пространство типов конечны, существуют два эквивалентных представления. Первая называется игрой в форме агента (см. Теорему 9.51 книги по теории игр ^[3] ), в которой количество игроков увеличивается с до , т. Е. Каждый тип каждого игрока становится игроком. Вторая называется индуцированной нормальной формой (см. Раздел 6.3.3 Многоагентных систем ^[4] ), в которой все еще есть игроки, но количество действий каждого игрока i увеличивается с до , т.е. чистая политика представляет собой комбинацию действий, которые игрок должен беру по разным видам. Мы можем вычислить равновесие Нэша (NE) в этих двух эквивалентных представлениях, а затем восстановить BNE из NE.${\displaystyle |N|}$${\textstyle \sum _{i=1}^{|N|}|T_{i}|}$${\displaystyle |N|}$${\displaystyle |A_{i}|}$${\textstyle |A_{i}|^{|T_{i}|}}$

• Если мы дополнительно рассмотрим двух игроков с целевой функцией с нулевой суммой, то мы можем сформировать линейную программу для вычисления BNE. ^[5]
• Если мы далее рассмотрим двух игроков с целевой функцией общей суммы, то мы можем сформировать математическую программу с билинейной целевой функцией и линейными ограничениями для вычисления BNE (см. Теорему 1 в статье ^[6] ). Хотя ни один нелинейный решатель не может гарантировать глобальный оптимум, мы можем проверить, достигается ли BNE, посмотрев на значение целевой функции программы, которое должно равняться 0 в BNE. Таким образом, значение, близкое к 0, представляет меньшую ошибку, которая может служить показателем качества решения. Мы можем напрямую распространить вышеупомянутый метод математического программирования на игры для N игроков.

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

Идеальное байесовское равновесие [ править ]

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

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

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

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

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

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

Пример [ править ]

Дилемма шерифа [ править ]

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

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

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

Если оба игрока рациональны и оба знают, что оба игрока рациональны, и все, что известно любому игроку, известно каждому игроку (т.е. игрок 1 знает, что игрок 2 знает, что игрок 1 рациональный, а игрок 2 знает это и т. Д.) до бесконечности - общеизвестно ), согласно идеальному байесовскому равновесию, ход в игре будет следующим: ^{[10] [11]}

Когда тип «гражданский», доминирующая стратегия для подозреваемого - не стрелять, а когда тип «преступник», доминирующая стратегия для подозреваемого - стрелять; Таким образом, можно исключить альтернативную стратегию со строгим доминированием. При этом, если шериф стреляет, он будет иметь выигрыш 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 .