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

Game theory concept

В теории игр байесовская игра — это стратегическая модель принятия решений, которая предполагает, что игроки имеют неполную информацию. Игроки могут иметь личную информацию, относящуюся к игре, что означает, что выигрыши не являются общедоступными знаниями. ^[1] Байесовские игры моделируют результат взаимодействия игроков, используя аспекты байесовской вероятности . Они примечательны тем, что впервые в теории игр позволили определить решения для игр с неполной информацией .

Венгерский экономист Джон К. Харшани представил концепцию байесовских игр в трех работах 1967 и 1968 годов: ^{[2] [3] [4]} За эти и другие вклады в теорию игр он был удостоен Нобелевской премии по экономике в 1994 году. Грубо говоря, Харшани определил байесовские игры следующим образом: игрокам в начале игры природой назначается набор характеристик. Сопоставляя распределения вероятностей с этими характеристиками и вычисляя результат игры с использованием байесовской вероятности, результатом является игра, решение которой по техническим причинам гораздо проще вычислить, чем аналогичную игру в небайесовском контексте. По этим техническим причинам см. раздел «Спецификация игр» в этой статье.

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

Элементы

Байесовская игра определяется как (N,A,T,p,u) и состоит из следующих элементов: ^[5]

1. Набор игроков, N : набор игроков в игре.
2. Наборы действий, a _i : набор действий, доступных игроку i . Профиль действий a = (a ₁ , . . . , a _N ) — это список действий, по одному для каждого игрока
3. Наборы типов, t _i : Набор типов игроков i . "Типы" фиксируют личную информацию, которую может иметь игрок. Профиль типа t = (t ₁ , . . . , t _N ) — это список типов, по одному для каждого игрока
4. Функции выплат, u : Назначить выплату игроку, учитывая его тип и профиль действий. Функция выплат, u= (u ₁ , . . . , u _N ) обозначает полезности игрока i
5. Приоритеты, p : распределение вероятностей по всем возможным профилям типов, где p(t) = p(t ₁ , . . . ,t _N ) — вероятность того, что Игрок 1 имеет тип t ₁ , а Игрок N — тип t _N .

Чистые стратегии

В стратегической игре чистая стратегия — это выбор действия игрока в каждой точке, где игрок должен принять решение. ^[6]

Три этапа

Байесовские игры состоят из трех этапов, каждый из которых описывает знание игроками типов в игре.

1. Игра на этапе ex-ante. Игроки не знают свои собственные типы или типы других игроков. Игрок распознает выплаты как ожидаемые значения на основе предварительного распределения всех возможных типов.
2. Промежуточная стадия игры. Игроки знают свой тип, но только распределение вероятностей других игроков. Игрок изучает ожидаемое значение типа другого игрока при рассмотрении выплат.
3. Игра после стадии. Игроки знают свои типы и типы других игроков. Выплаты известны игрокам. ^[7]

Улучшения по сравнению с небайесовскими играми

Есть два важных и новых аспекта байесовских игр, которые сами были определены Харсани. ^[8] Первый заключается в том, что байесовские игры должны рассматриваться и структурироваться идентично играм с полной информацией. За исключением того, что при добавлении вероятности к игре, финальная игра функционирует так, как если бы это была игра с неполной информацией. Поэтому игроки могут быть по существу смоделированы как имеющие неполную информацию, и вероятностное пространство игры по-прежнему следует закону полной вероятности . Байесовские игры также полезны тем, что они не требуют бесконечных последовательных вычислений. Бесконечные последовательные вычисления возникали бы, когда игроки (по сути) пытались бы «залезть друг другу в головы». Например, можно задать вопросы и решить: «Если я ожидаю какого-то действия от игрока B, то игрок B будет ожидать, что я ожидаю этого действия, поэтому я должен ожидать этого ожидания» до бесконечности . Байесовские игры позволяют вычислять эти результаты за один ход, одновременно назначая разные веса вероятности разным результатам. В результате байесовские игры позволяют моделировать ряд игр, которые в небайесовских условиях было бы нерационально вычислять.

Байесовское равновесие Нэша

Равновесие Байеса-Нэша байесовской игры — это равновесие Нэша связанной с ней игры в нормальной форме ex-ante.

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

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

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

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

• Рассмотрим двух игроков с нулевой суммой целевой функции. Можно сформировать линейную программу для вычисления BNE. ^[11]

Расширенные формы игр с неполной информацией

Элементы игр развернутой формы

Игры развернутой формы с полной или несовершенной информацией имеют следующие элементы: ^[12]

1. Набор игроков
2. Набор узлов принятия решений
3. Функция игрока, назначающая игрока каждому узлу принятия решения
4. Набор действий для каждого игрока в каждом из узлов принятия решений
5. Набор конечных узлов
6. Функция выигрыша для каждого игрока

Природа и информационные наборы

Узел природы обычно обозначается незаполненным кругом. Его стратегия всегда определена и всегда полностью смешана. Обычно природа находится в корне дерева, однако природа может перемещаться и в других точках.

Информационный набор игрока i — это подмножество узлов принятия решений игрока i , которые он не может различить. То есть, если игрок i находится в одном из своих узлов принятия решений в информационном наборе, он не знает, в каком узле внутри информационного набора он находится.

Чтобы два узла принятия решений находились в одном и том же информационном наборе , они должны ^[13]

1. Принадлежат одному и тому же игроку; и
2. Имеют тот же набор действий

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

Роль убеждений

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

Если у игроков нет личной информации, распределение вероятностей по типам известно как общее априорное распределение . ^[1]

Правило Байеса

Оценкой игры развернутой формы является пара <b, μ>

1. Профиль стратегии поведения ; и
2. Система верований

Оценка <b, μ> удовлетворяет правилу Байеса , если ^[14] μ(x|h _i ) = Pr[x достигается при условии b−i ] / Σ Pr[x' достигается при условии b _−i ] всякий раз, когда h _i достигается со строго положительной вероятностью согласно b _−i .

Идеальное байесовское равновесие

Идеальное байесовское равновесие в игре в развернутой форме представляет собой комбинацию стратегий и спецификацию убеждений, при которой выполняются следующие два условия: ^[15]

1. Байесовская согласованность: убеждения согласуются с рассматриваемыми стратегиями;
2. Последовательная рациональность: игроки делают оптимальный выбор, исходя из своих убеждений.

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

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

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

Стохастические байесовские игры ^[16] объединяют определения байесовских игр и стохастических игр для представления состояний среды (например, состояний физического мира) со стохастическими переходами между состояниями, а также неопределенностью относительно типов различных игроков в каждом состоянии. Полученная модель решается с помощью рекурсивной комбинации байесовского равновесия Нэша и уравнения оптимальности Беллмана . Стохастические байесовские игры использовались для решения различных проблем, включая планирование обороны и безопасности, ^[17] кибербезопасность электростанций, ^[18] автономное вождение, ^[19] мобильные периферийные вычисления, ^[20] самостабилизацию в динамических системах, ^[21] и лечение неправильного поведения в краудсорсинге IoT. ^[22]

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

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

Пример

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

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

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

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

• N = {Подозреваемый, Шериф}
• Подозреваемый = {Стреляй, нет} , Шериф = {Стреляй, _{нет }}
• T _{Подозреваемый} = {Преступник, Гражданский} , T _Шериф = {*}
• p _{Преступник} = p , p _{Гражданский} = (1 - p)
• Предполагается, что выигрыши u определяются следующим образом:

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

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

Рынок лимонов

Рынок лимонов связан с концепцией, известной как неблагоприятный отбор .

Настраивать

Есть подержанный автомобиль. Игрок 1 — потенциальный покупатель, который заинтересован в автомобиле. Игрок 2 — владелец автомобиля и знает стоимость v автомобиля (насколько он хорош и т. д.). Игрок 1 не знает и считает, что стоимость v автомобиля для владельца (Игрока 2) распределена равномерно между 0 и 100 (т. е. каждый из двух подинтервалов стоимости [0, 100] одинаковой длины одинаково вероятен).

Игрок 1 может сделать ставку p от 0 до 100 (включительно) I Игрок 2 может затем принять или отклонить предложение. Выплаты следующие:

• Выигрыш игрока 1: Принятая ставка — 3/2v-p , Отклоненная ставка — 0
• Выигрыш игрока 2: ставка принята — p , ставка отклонена — v

Дополнительный момент: стратегия отсечения

Стратегия игрока 2: принять все ставки выше определенного порогового значения P* и отклонить их и сделать ставку ниже P* , известна как стратегия отсечения, где P* называется пороговым значением.

• Торгуются только «лимоны» (подержанные автомобили в плохом состоянии, в частности, имеющие максимальную стоимость, равную p ).
• Игрок 1 может гарантировать себе выигрыш, равный нулю, сделав ставку 0, следовательно, в равновесии p = 0.
• Поскольку на рынке продаются только «лимоны» (подержанные автомобили в плохом состоянии), рынок рушится.
• Торговля невозможна, даже если она была бы экономически эффективной ^[27]

Выход на монополизированный рынок

Новая компания (player1), которая хочет выйти на рынок, монополизированный крупной компанией, столкнется с двумя типами монополистов (player2), type1 не допускается, а type2 допускается. Player1 никогда не будет иметь полной информации об player2, но может вывести вероятность появления type1 и type2 из того, была ли заблокирована предыдущая фирма, выходящая на рынок, это байесовская игра. Причина этих суждений заключается в том, что существуют издержки блокировки для player2, которому может потребоваться значительно снизить цены, чтобы не допустить player1 к выходу на рынок, поэтому он заблокирует player1, когда прибыль, которую он украдет от выхода на рынок, превысит издержки блокировки.

Смотрите также

• Байесовский-оптимальный механизм
• Байесовско-оптимальное ценообразование
• Байесовское программирование
• Байесовский вывод

Ссылки

1. Zamir, Shmuel (2009). "Байесовские игры: игры с неполной информацией" (PDF) . Энциклопедия сложности и системной науки . стр. 426. doi :10.1007/978-0-387-30440-3_29. ISBN 978-0-387-75888-6. S2CID  14218591.
2. Харсани, Джон К., 1967/1968. «Игры с неполной информацией, в которые играют байесовские игроки, I-III». Management Science 14 (3): 159-183 (часть I), 14 (5): 320-334 (часть II), 14 (7): 486-502 (часть III).
3. Харсани, Джон К. (1968). «Игры с неполной информацией, в которые играют «байесовские» игроки, I-III. Часть II. Точки байесовского равновесия». Management Science . 14 (5): 320–334. doi :10.1287/mnsc.14.5.320. ISSN  0025-1909. JSTOR  2628673.
4. Харсани, Джон К. (1968). «Игры с неполной информацией, в которые играют «байесовские» игроки, I-III. Часть III. Основное распределение вероятностей игры». Management Science . 14 (7): 486–502. doi :10.1287/mnsc.14.7.486. ISSN  0025-1909. JSTOR  2628894.
5. Kajii, A.; Morris, S. (1997). «Устойчивость равновесий к неполной информации». Econometrica . 65 (6): 1283–1309. doi :10.2307/2171737. JSTOR  2171737.
6. Грюне-Янофф, Тилль; Лехтинен, Аки (2012). «Философия теории игр». Философия экономики : 532.
7. Конорчик, Матьяш; Бодор, Андраш; Пинтер, Миклош (29 июня 2020 г.). «Равновесие ex ante и ex post в классических байесовских играх с нелокальным ресурсом». Физический обзор А. 1 (6): 2–3. arXiv : 2005.12727 . Бибкод : 2020PhRvA.101f2115K. doi :10.1103/PhysRevA.101.062115. S2CID  218889282.
8. Харсани, Джон К. (2004). «Игры с неполной информацией, в которые играют «байесовские» игроки, I-III: Часть I. Базовая модель». Management Science . 50 (12): 1804–1817. doi :10.1287/mnsc.1040.0270. ISSN  0025-1909. JSTOR  30046151.
9. Машлер, Майкл; Солан, Эйлон; Замир, Шмуэль (2013). Теория игр. Кембридж: Cambridge University Press. doi : 10.1017/cbo9780511794216. ISBN 978-0-511-79421-6.
10. Шохам, Йоав; Лейтон-Браун, Кевин (2008). Многоагентные системы . Кембридж: Издательство Кембриджского университета. doi :10.1017/cbo9780511811654. ISBN 978-0-511-81165-4.
11. Понссар, Ж. -П.; Сорин, С. (июнь 1980 г.). «ЛП-формулировка конечных игр с нулевой суммой и неполной информацией». International Journal of Game Theory . 9 (2): 99–105. doi :10.1007/bf01769767. ISSN  0020-7276. S2CID  120632621.
12. Нарахари, Y (июль 2012 г.). «Игры в расширенной форме» (PDF) . Кафедра компьютерных наук и автоматизации : 1.
13. «Стратегические игры», Теория игр , Издательство Кембриджского университета, стр. 75–143, 21.03.2013, doi :10.1017/cbo9780511794216.005, ISBN 9780511794216, получено 2023-04-23
14. "Правило Байеса: введение в байесовский анализ". Choice Reviews Online . 51 (6): 51–3301–51-3301. 2014-01-21. doi :10.5860/choice.51-3301. ISSN  0009-4978.
15. Петерс, Ханс (2015). Теория игр . Тексты Springer по бизнесу и экономике. Берлин: Springer. С. 60. doi :10.1007/978-3-662-46950-7. ISBN 978-3-662-46949-1.
16. Альбрехт, Стефано; Крэндалл, Джейкоб; Рамамурти, Субраманиан (2016). «Вера и истина в гипотетических поведениях». Искусственный интеллект . 235 : 63–94. arXiv : 1507.07688 . doi : 10.1016/j.artint.2016.02.004. S2CID  2599762.
17. Кабальеро, Уильям Н.; Бэнкс, Дэвид; Ву, Керу (2022-08-08). «Планирование обороны и безопасности в условиях неопределенности ресурсов и многопериодных обязательств». Naval Research Logistics (NRL) . 69 (7): 1009–1026. doi :10.1002/nav.22071. ISSN  0894-069X. S2CID  251461541.
18. Maccarone, Lee Tylor (2021). Стохастические байесовские игры для кибербезопасности атомных электростанций . Докторская диссертация, Университет Питтсбурга.
19. Бернхард, Джулиан; Поллок, Стефан; Кнолл, Алоис (2019). «Устранение внутренней неопределенности: генерация поведения, чувствительного к риску, для автоматизированного вождения с использованием распределенного обучения с подкреплением». Симпозиум IEEE по интеллектуальным транспортным средствам (IV) 2019 года . Париж, Франция: IEEE. стр. 2148–2155. arXiv : 2102.03119 . doi :10.1109/IVS.2019.8813791. ISBN 978-1-7281-0560-4. S2CID  201811314.
20. Ашералиева, Алия; Ниято, Дусит (2021). «Быстрая и безопасная вычислительная разгрузка с помощью мобильных периферийных вычислений с кодированием Лагранжа». Труды IEEE по транспортным технологиям . 70 (5): 4924–4942. doi : 10.1109/TVT.2021.3070723. ISSN  0018-9545. S2CID  234331661.
21. Рамтин, Амир Реза; Тоусли, Дон (2021). «Теоретико-игровой подход к самостабилизации с эгоистичными агентами». arXiv : 2108.07362 [cs.DC].
22. Су, Рунбо; Сфар, Арбия Риахи; Наталицио, Энрико; Мойал, Паскаль; Сонг, Йе-Цюн (2023-09-11). «Теоретическая игровая модель, решающая проблему неправильного поведения в краудсорсинге Интернета вещей». 20-я ежегодная международная конференция IEEE по зондированию, связи и сетям (SECON) 2023 г. (PDF) . IEEE. стр. 195–203. doi :10.1109/SECON58729.2023.10287527. ISBN 979-8-3503-0052-9.
23. Бахарак, М. (1999). «Интерактивное командное рассуждение: вклад в теорию сотрудничества». Исследования в области экономики . 53 (2): 117–47. doi :10.1006/reec.1999.0188.
24. Ньютон, Дж. (2019). «Агентское равновесие». Игры . 10 (1): 14. doi : 10.3390/g10010014 . hdl : 10419/219237 .
25. "Coursera". Coursera . Получено 2016-06-16 .
26. Ху, Юхуан; Лу, Чу Кионг (2014-03-17). «Обобщенная квантово-вдохновленная модель принятия решений для интеллектуального агента». Журнал Scientific World . 2014 : 240983. doi : 10.1155/2014/240983 . ISSN  1537-744X. PMC 3977121. PMID  24778580 . 
27. Акерлоф, Джордж А. (август 1970 г.). «Рынок «лимонов»: неопределенность качества и рыночный механизм». The Quarterly Journal of Economics . 84 (3): 488–500. doi :10.2307/1879431. JSTOR  1879431.

Дальнейшее чтение

• Гиббонс, Роберт (1992). Теория игр для прикладных экономистов. Princeton University Press. С. 144–52. ISBN 1400835887.
• Левин, Джонатан (2002). "Игры с неполной информацией" (PDF) . Получено 25 августа 2016 .