Игры с неполной информацией. Равновесие Байеса – Нэша (РБН).

Лекция 12. Тема 13. Игры с неполной информацией. Равновесие Байеса – Нэша (РБН). ( [1], Главы 20, 21; [2], Глава 3 , раздел 3.1; [7], Лекция 10 ) Неполнота информации . Что может быть неизвестно Игрокам? 1. Кто другие игроки? 2. Их стратегии. 3. Их функции выигрышей (целевая функция). 4. И т. д Чаще всего: ** Игры, в которых целевая функция одного игрока может не быть известна другим игрокам, называются играми с неполной информацией. 1 Рассмотрим примеры. 1. Табл.1 И1\И2 Дил заключённого Пример 1 C N И1\И2 C N С 0, 0 7, -2 С 0, - 2 7, 0 N -2, 7 5, 5 N -2, 5 5, 7 Тип Т Игрок 2 Разбор. …. Тип А Игрок 1 неизменен … Переговоры… Игрок 2 Решение: Игрок1 С, Игрок 2-Т - С; Игрок 2-А - Т 2. Табл. 2 И1\И2 Игрок 1 меняет стратегию в Пример 2 C N И1\И2 C N зависимости от типа Игрока 2 С 0, 0 7, -2 С - 2, -2 5, 0 ..Переговоры … N -2, 7 5, 5 N 0, 5 7, 7 Но не знает… Тип Т Игрока 2 Тип А Игрока 2 Пусть р = 0,9 в-ть , что Игрок 2-Т (С) 2 ( 0,1 - Игрок2-А) (N). Tогда: Для Игрока1 1. С ⟹ 0,9* 0 + 0,1*5 2. N ⟹ 0,9* (-2) + 0,1*7 ***Д/З показать при р ⟹ С 1/2 ⟹ N ??? 3. Ценовая конкуренция в дуополии Бертрана. Пример 3 S C ! Здесь: И2-S не имеет доминирующей стратегии (И2-С имеет ) ⟹ 3 И1 не сможет определиться. Т.е. он должен иметь предположения ……не только о типе И2, но и …… В свою очередь, выбор (вероятность) ходов И2 зависит от …….. 4. «Футбол, опера (Муж и Жена)». Табл. 4 М\Ж Здесь И2 не имеет домщих стратегий Пример 4 Ф О М\Ж Ф О Ф 3,1 0, 0 Ф 3, 0 0, 1 О 0, 0 1, 3 О 0, 3 1, 0 Ж Тип Т Ни в одном типе. Ж Тип А Подробный анализ. Поиск Равновесий Байеса – Нэша (РБН) в чистых и смешанных стратегиях. Предположения: 4 П1. Жена знает свой тип (т.е. Таблицу). П2. Муж не знает тип Жены: …ожидает с р = 0.9 Т, …. П3. Жена знает оценку (р) мужа. Обсуждение П3. …………. assumption of a common prior (общие знания) ……………………………. !! П4. Harsanyi’s proposal Он предложил интерпретировать игру с неполной информацией как игру с полной но несовершенной информацией с большим количеством игроков, в которой каждый игрок соответствует одному типу игрока в исходной игре. Первый ход делает «природа», определяя, какой тип каждого игрока будет задействован. Например, если каждый из двух игроков имеет два типа, то такую статическую игру можно представить как динамическую игру между четырьмя игроками. П5. Использовать концепцию РН в соответствующей динамической Игре с полной но несовершенной информацией . 5 Получаемое таким образом РН в игре с неполной информацией называется Равновесием Байеса–Нэша (РБН). РБН может быть: 1. В чистых стратегиях (чистое РБН) 2. В смешанных стратегиях (смешанное РБН). Найдём РБН в Примере 4. Чистые стратегии Жены; { (Ф, Ф), …………….. } Чистые стратегии Мужа: { Ф, О}. Вероятности: Пусть q определят смешанную стратегию Мужа: q ➙ Ф. m1 ➙ тип Ж – Т и играет Ф (дуга в Вершине 1) ; m2 ➙ тип Ж – А и играет Ф (Вершина 2) 6 Дерево игры, Пример 4. Выигрыш Жены первый. 7 О «смешанных» стратегиях в ИРФ! Поведенческие стратегии! Поведенческая стратегия в ИРФ – указание для каждого информационного множества (ИМ) вероятностного распределения на наборе альтернатив (ходов), которые выбираются Игроком на этом ИМ. Важные отличия и свойства Поведенческих стратегий. 1. Удобство использования. Смешанных стратегий очень много ….. Поведенческих стратегий существенно меньше …. . Пример. И1 – 4 ИМ, в каждом 3 альтернативы ⟹ 81 чистых ⟹ dim (S) = 80 …… Dim (П) = 2  4 = 8 !!! Пояснение … 2. Эквивалентность смешанным в использовании. Пояснение…………!!! 8 Равновесием Байеса–Нэша (РБН) в Игре G ( Пример 4) называется тройка (профиль) (q, m1, m2), в которой каждый Игрок играет наилучший ответ, т.е. 1. mi максимизирует выигрыш Жены в случае, если она имеет тип i и Муж выбирает Ф с вероятностью q . Это выполняется для каждого типа i . 2. q максимизирует выигрыш Мужа в случае, если он ожидает (верит) , что Жена имеет тип Т с вероятностью р, и при этом она играет Ф в своих типах Т и А с вероятностями m1 и m2 соответственно. 1) Поиск чистого РБН. 1.1 ……….. ………………………………………………………… 1.2. q =0 (О) !!!!Д/З Показать, что РБН = профиль (О, (О, Ф)) при p 3/4 9 Вывод. 1. При p 3/4 два профиля чистых РБН: (О, (О, Ф)) и 2. При 3/4 3. При p (Ф, (Ф, O)) 1/4 один профиль чистого РБН: (Ф, (Ф, O)) p 1/4 нет чистых РБН. 2) Поиск смешанного РБН Что при p (Mixed-Strategy Bayes-Nash Equilibria) 1/4 ? p ➙ 0 , при p = 0 игра с полной инф. Таблица 4(Тип А) Табл. 4 М\Ж Тип А: Пример 4 Ф О М\Ж Ф О Ф 3,1 0, 0 Ф 3, 0 0, 1 О 0, 0 1, 3 О 0, 3 1, 0 Ж Тип Т РН в смешанных стр – ях. (q = 3/4 ; m2 = 1/4) Ж Тип А 10 Пусть р 1. 0 (мало). Ищем смешанное РБН. М ( q) : 1.1. Ж-Т ⇒ когда смешивание? ⇒ если Ж-Т – Ф ⇒ её выигрыш q; Ж-Т – О ⇒ её выигрыш 3(1- q) ???; ⇒ q = 3(1- q), Индеферентность! (Смешивание) q = 3/4. 1.2. !: u ( Ж-А – О) = u ( Ж-Т – Ф), u( Ж-А – Ф) = Тоже при q = 3/4. 2. Ж (m1, m2) ⇒ 2.1 ⇒ если M – Ф Индеферентность! (Смешивание) когда смешивание? ⇒ 2.2 ⇒ если M – O u ( Ж-Т – А), ???? ⇒ 3m1p + 3m2(1-p) (1 - m1)p + (1- m2)(1 – p) p(4m1 – 1) = (1 – p)(1 – 4m2) (1) q = 3/4 ! Итог : 1. При каждом р РБН q = 3/4 2. q = 3/4 , (m1, m2) = …. , (m1, m2) = (1/4, 1/4) (1) 11 Пояснение и Вывод ……. Более общий случай (продолжение Примера 4) Пусть: М – два Типа: Т1 (пессимист) и Т2 (оптимист) ……… М –Т1 - р1, что Ж-Т; М –Т2 - р2, что Ж-А; Общие знания: Ж и М знают, что М –Т1 Стратегия М: (q1, q2), р2 р1 (2) с вероятностью v ! q1 , q2 – вероятности выбора Ф для М-Т1 и М-Т2 Стратегия Ж : (m1, m2) ……– Общие знания: р1, р2, v 12 Равновесием Байеса–Нэша (РБН) в Игре G ( Пример 4, более общий случай) называется профиль ((q1, q2); (m1, m2)), в которой каждый Игрок играет наилучший ответ, т.е. 1. mi максимизирует выигрыш Жены в случае: если она имеет тип i , Муж выбирает стратегию (q1, q2), и известна вероятность v , что Муж имеет тип Т1. Это выполняется для каждого типа i . 2. qi максимизирует выигрыш Мужа в случае, если он имеет тип Тi , а Жена 1 выбирает стратегию (m1, m2). При этом М –Т1 верит, что Жена имеет тип Т с вероятностью - р1, А М –Т2 верит, что Жена имеет тип Т с вероятностью р2. 13 Рассмотрим простой вариант РБН в чистых стратегиях. Пусть оба М-Т1 и М-Т2 играют Ф. Ж-Т ответит Ф (….). Ж-Т - О ( та же логика). Проверим: Ф для М – лучший ли ответ на (Ф. О) ???? Ранее показали, что это верно при р1 1/4 ! (Почему??) ((Ф, Ф); (Ф, О)) - РБН !!! Д/З Показать, что при р1 3/4 , для любого v , ((O, O); (О, Ф)) - РБН 14 Построения для более общего случая. Условные вероятности. Пусть И1 и И2. И1: типы Т1, …, Тi ,….Тn . для каждого Т свои предпочтения и выигрыши. И2: типы Н1, …, Нj ,….Нm . для каждого Т свои предпочтения и выигрыши. …. Игра G – в ИРФ G*: 1. Природа выбирает (Тi, Нj). Игроки знают свои , но не знают чужие. 2. Игрок 2 , зная Нj, максимизирует свой (ожидаемый) выигрыш, используя свои представления о вероятностном распределении Типов Игрока1. То же – и Игрок1 3. Распределение на множестве всех пар (Тi, Нj) является, обычно, общим знанием. В Примерах 1 – 4 …… 15 В модифицированном Примере 4 начальное распределение: М\Ж Т Т1 v  p1 Т2 (1-v)  p2 А v  (1-p1) (1-v) (1- p2) Для Ж-А вероятность ,что М-Т1: На основе этого – условные вероятности. Например: Ж-Т находит вероятность ,что  М-Т1:   ,    16 Реализация концепции доминирования в Играх с неполной информацией. (На примерах). Пусть И1 и И2. a, b – стратегии (чистые или смешанные) И1. a ≽ b, если для каждой стратегии L И2 ̃(a, L) ̃(b, L). ̃ (a, L) – ожидаемый ! Табл. 2 И1\И2 Пример 2 И1\И2 C N С 0, 0 7, -2 С - 2, -2 N -2, 7 5, 5 N 0, 5 Тип Т Игрока 2 C Тип А N 5, 0 если р 7, 7 Игрока 2 1. (С , N): ̃ 1(С, (С , N), р) = 5(1-р) У каждого есть доминирующая, т.е. есть решение в доминирующих стратегиях, 1/2 , (В чистых) ??? Например: И1 – С или N ? И2: 1. (С , N), 2. (N, С ), 3. …… ̃ 1(N, (С , N), р) = 7 - 9р, Показать, что это верно и для всех других ….. 17 Утверждение (Для Примера 2): 1. При р 1/2 (С, (С , N), р) решение в доминирующих стратегиях. 2. При р 1/2 (N, (С , N), р) решение в доминирующих стратегиях. 3. Ценовая конкуренция в дуополии Бертрана. Пример 3 S р = 1/2 C Показать, что Фирма1 не имеет доминирующих стратегий (в чистых). 18 Термины и формальные определения в Играх с неполной информацией. Общий случай. Игра: N – игроков. =∏ , – множество типов для игрока i, T = ∏ T, t = ( , , t , … ,… ), , , P – распределение вероятностей на множестве T. Мы предполагаем, что игроку i известен его собственный тип . Свое представление о типах остальных игроков игрок i формирует согласно формуле Байеса, наблюдая свой собственный тип : P( )= , Ai множество действий игрока i, A = ∏ =∑ , , (3) - множество профилей действий. Тогда функция выигрышей для игрока i долж-на определять его выигрыш в зависимости от его типа и от профиля действий, выбранного игроками, т.е. 19 : A×Ti → R. u: A×T → R = ( , , … ,… ) - профиль функций выигрышей игроков. Различие между стратегией и действием. Действие игрока — это один из возможных доступных ему ходов. Стратегия — это зависимость хода, который сделает игрок, от его типа (и параметров) Пусть : — стратегия игрока i, определяющая, какой ход он должен совершить в зависимости от его типа . s=( , , … ,… ) профиль стратегий игроков. При данном профиле стратегий s ожидаемый выигрышигрока i,имеющего тип ̃ ( , )=∑ , равен ( ( ), ( ), ) (2) *** Набор (I, A,T, P, u) называется игрой с неполной (или асимметричной) информацией или байесовой игрой. Понятие байесовой игры было введено Харшаньи [Harsanyi, 1967–1968]. Обсуждение ………… Замена на ИРФ с несовершенной информацией. 20 ***Пусть (I, A, T, P, u) - игра с неполной информацией. Равновесием в этой игре является набор стратегий Игроков (профиль) что для всех i, для всех , s*, такой, выполняется: (3) Равновесие в такой игре называется байесовым равновесием или Равновесием Байеса–Нэша (РБН). *** Теорема (о существовании РБН) В конечной игре с неполной информацией всегда существует РБН в смешанных (поведенческих) стратегиях. 21