Равновесие Нэша, совершенное на подыграх

Равновесие Нэша, совершенное на подыграх Дмитрий Дагаев НИУ Высшая школа экономики Равновесие Нэша, совершенное на подыграх ▶ На прошлой неделе мы познакомились с играми в развернутой форме и научились их решать с помощью обратной индукции. ▶ На этой неделе мы поговорим о том, как связаны игры в развернутой и нормальной формах, а также познакомимся с концепцией равновесия Нэша, совершенного на подыграх. Дмитрий Дагаев НИУ ВШЭ 2 / 97 День рождения Иа-Иа ▶ На прошлой неделе в качестве одного из примеров мы обсудили стратегическое взаимодействие, происходящее между Винни-Пухом и осликом Иа-Иа. ▶ Мы выяснили, что это взаимодействие можно представить в виде игры в развернутой форме. Дмитрий Дагаев НИУ ВШЭ 3 / 97 День рождения Иа-Иа ▶ Мы построили дерево игры: Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 4 / 97 Представление игры в нормальной форме ▶ А также описали множество стратегий Винни-Пуха: ▶ ▶ SВинни-Пух = {С, Н}. И множество стратегий Иа-Иа: ▶ SИа-Иа = {ПП, ПН, НП, НН}. Дмитрий Дагаев НИУ ВШЭ 5 / 97 Представление игры в нормальной форме По развернутой форме игры можно записать матрицу игры в нормальной форме. Для этого нужно: 1. Записать по горизонтали и по вертикали стратегии игроков. 2. Записать в ячейках матрицы платежи, соответствующие каждому из профилей стратегий. Дмитрий Дагаев НИУ ВШЭ 6 / 97 Представление игры в нормальной форме Какие платежи получат игроки, если сыграют профиль стратегий (Н, НП)? ▶ Винни-Пух получит платеж 5, а ослик Иа-Иа –– платеж 10. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 7 / 97 Представление игры в нормальной форме Принять Съесть Не принимать B Пух 10 5 Иа-Иа Принять A Не есть 5 10 Иа-Иа Не принимать C –5 –10 0 Зная, какие платежи получают игроки в зависимости от того, какой профиль стратегий сыгран, составим матрицу платежей для нашей игры: С Н Дмитрий Дагаев ПП 10; 5 5; 10 ПН 10; 5 −10; 0 НИУ ВШЭ НП −5; 0 5; 10 НН −5; 0 −10; 0 8 / 97 Представление игры в нормальной форме ▶ Найдем теперь все равновесия Нэша в нашей игре в нормальной форме. ▶ Отметим точками наилучшие ответы Винни-Пуха на все стратегии Иа-Иа, а звездочками –– наилучшие ответы Иа-Иа на все стратегии Винни-Пуха. ПП С Н ▶ • 10; 5 ∗ 5; 10 ∗ ПН • 10; 5 ∗ −10; 0 НП −5; 0 • 5; 10 ∗ НН 5; 0 −10; 0 •− В нашей игре есть 3 равновесия Нэша: (С, ПП), (С, ПH), (Н, НП). Дмитрий Дагаев НИУ ВШЭ 9 / 97 Равновесие, совершенное на подыграх Однако на прошлой неделе, решая игру с конца, мы поняли, что игроки сыграют профиль стратегий (С, ПП). ▶ Дело в том, что когда мы решали игру с конца, мы предполагали, что игроки ведут себя оптимально на каждой подыгре при фиксированной стратегии другого игрока. ▶ Это более сильное требование, чем требование к профилю в определении равновесия Нэша. ▶ Не все равновесия Нэша удовлетворяют этому свойству. Дмитрий Дагаев НИУ ВШЭ 10 / 97 Равновесие, совершенное на подыграх ▶ Профиль стратегий (С, ПH) является равновесием Нэша. ▶ Но ослик Иа-Иа ведет себя неоптимально в том случае, если Пух решает не есть мед, так как тогда Иа-Иа отказывается от подарка. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 11 / 97 Равновесие, совершенное на подыграх ▶ Профиль стратегий (Н, НП) также является равновесием Нэша. ▶ Но ослик Иа-Иа ведет себя неоптимально в том случае, если Пух съедает весь мед, так как в этом случае Иа-Иа опять отказывается от подарка. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 12 / 97 Равновесие, совершенное на подыграх ▶ Рассмотрим теперь профиль стратегий (С, ПП), также являющийся равновесием Нэша. ▶ В нем ослик Иа-Иа ведет себя оптимально на каждой подыгре. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 13 / 97 Равновесие, совершенное на подыграх ▶ Решение, найденное с помощью алгоритма Цермело –– Куна, в некотором смысле лучше двух других равновесий Нэша. ▶ Оно удовлетворяет дополнительному условию –– оптимальности поведения игроков при фиксированных стратегиях остальных игроков на каждой подыгре. ▶ Такие профили стратегий называются равновесиями Нэша, совершенными на подыграх. Дмитрий Дагаев НИУ ВШЭ 14 / 97 Равновесие, совершенное на подыграх Определение Профиль стратегий называется равновесием Нэша, совершенным на подыграх (SPNE), если его ограничение на любую подыгру является равновесием Нэша. Дмитрий Дагаев НИУ ВШЭ 15 / 97 Последовательная игра трех лиц Найдем равновесие Нэша, совершенное на подыграх, в следующей игре: t1 1 –2 1 r1 s1 t2 2 3 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 16 / 97 Последовательная игра трех лиц ▶ Множество стратегий первого игрока: S1 = {s1 , s2 }. ▶ Множество стратегий второго игрока: S2 = {t1 , t2 , t3 }. ▶ Множество стратегий третьего игрока: S3 = {r1 , r2 }. t1 1 –2 1 r1 s1 t2 2 3 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 17 / 97 Последовательная игра трех лиц Будем решать игру с конца. Рассмотрим подыгру, в которой третий игрок делает ход: ▶ Третьему игроку лучше выбрать стратегию r2 . t1 s1 t2 2 1 –2 1 3 r1 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 18 / 97 Последовательная игра трех лиц Рассмотрим подыгру, в которой второй игрок делает ход: ▶ ▶ Выбрав стратегию t2 , второй игрок получит выигрыш, равный (−1), так как третий игрок выберет стратегию r2 . Значит, для второго игрока лучше всего сыграть стратегию t3 , так как тогда его выигрыш будет равен 5. t1 s1 1 –2 1 r1 2 t2 3 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 19 / 97 Последовательная игра трех лиц Рассмотрим теперь подыгру, совпадающую со всей игрой: ▶ ▶ Выбрав стратегию s1 , первый игрок получит выигрыш равный (−4), так как второй игрок тогда заведомо сыграет стратегию t3 . Значит, для первого игрока лучше всего сыграть стратегию s2 , так как тогда его выигрыш будет равен 0. t1 1 –2 1 r1 s1 t2 2 3 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 20 / 97 Последовательная игра трех лиц ▶ Таким образом, SPNE будет профиль стратегий (s2 , t3 , r2 ). t1 1 –2 1 r1 s1 t2 2 3 r2 1 t3 s2 Дмитрий Дагаев 2 1 –3 3 –1 –2 –4 5 –5 0 –2 3 НИУ ВШЭ 21 / 97 Игры с коммитментом Вернемся к нашему примеру с Винни-Пухом. ▶ Предположим, Иа-Иа попросил Кристофера Робина написать Пуху такое письмо: «Я аткажусь от падарка, эсли в гаршочьке не будит мёда. Иа-Иа» ▶ А затем ослик попросил Сову проследить за тем, чтобы он действительно отказался от подарка, если вдруг Пух все-таки съест весь мед. Что это изменит? Дмитрий Дагаев НИУ ВШЭ 22 / 97 Игры с коммитментом Если Винни-Пух будет знать, что Иа-Иа не примет его подарок, если в нем не будет меда, то оптимальной стратегией Пуха будет не есть мед, и тогда Иа-Иа получит полный горшочек! Съесть Иа-Иа B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев Не принимать НИУ ВШЭ –5 0 5 10 –10 0 23 / 97 Игры с коммитментом ▶ Очень часто люди сознательно ограничивают свой выбор, как ослик Иа-Иа в нашем примере, чтобы, в итоге, оказаться в выигрыше. ▶ Например, люди покупают дорогие абонементы в тренажерный зал или заключают договоры, согласно которым обязуются сделать часть работы не к дедлайну, а к более раннему сроку. Дмитрий Дагаев НИУ ВШЭ 24 / 97 Игры с коммитментом ▶ Даже женитьба является примером такого ограничения, которое экономисты обычно называют связывающим обязательством или коммитментом. ▶ Рассмотрим этот пример подробнее. Дмитрий Дагаев НИУ ВШЭ 25 / 97 Женитьба Предыстория ▶ В одном высокоморальном обществе существует правило: если парень начинает ухаживать за девушкой, и девушка принимает его ухаживания, то парень обязан жениться на ней. ▶ А в соседнем либеральном обществе все парни сами выбирают, продолжать ли отношения с девушкой и жениться на ней или расстаться с ней. Дмитрий Дагаев НИУ ВШЭ 26 / 97 Женитьба Предыстория ▶ Можно предположить, что во втором обществе жизнь парней будет лучше, ведь они сами хозяева своей судьбы. ▶ Однако формализуем сначала вышеописанную ситуацию в виде игры и решим ее. Дмитрий Дагаев НИУ ВШЭ 27 / 97 Женитьба Постановка игры ▶ Рассмотрим сначала либеральное общество. ▶ Пусть Саше понравилась Маша, а Маше понравился Саша. ▶ Сначала Саша решает, ухаживать за Машей или нет. ▶ Затем Маша решает, принимать ухаживания Саши или нет. ▶ Если пара начинает встречаться, то через некоторое время перед Сашей снова встает выбор: продолжить отношения с Машей или расстаться с ней. Дмитрий Дагаев НИУ ВШЭ 28 / 97 Женитьба Платежи Саши ▶ Лучше всего Саше в ситуации, когда он начинает ухаживать за Машей и Маша принимает его ухаживания, а затем он расстается с ней. ▶ Однако продолжить отношения с Машей и жениться на ней для него лучше, чем не начинать ухаживать совсем или получить отказ в ухаживаниях, что для него самый худший исход. Дмитрий Дагаев НИУ ВШЭ 29 / 97 Женитьба Платежи Маши ▶ Маше лучше всего, когда Саша начинает за ней ухаживать, она принимает ухаживания Саши, а затем они женятся. ▶ Отказ Саше в ухаживаниях приносит ей такую же полезность, как и решение Саши не ухаживать за ней вообще. ▶ Хуже всего для Маши –– принять ухаживания Саши, а затем получить от него предложение расстаться. Дмитрий Дагаев НИУ ВШЭ 30 / 97 Женитьба ▶ Построим дерево игры: Расстаться Принимать С Жениться Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев 3 –3 2 2 –1 0 0 0 НИУ ВШЭ 31 / 97 Женитьба ▶ Найдем в нашей игре SPNE. Будем решать игру с конца. ▶ Если Саша решил ухаживать за Машей и Маша приняла его ухаживания, то после этого Саше лучше всего расстаться с ней. Принимать Расстаться С Жениться Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев 3 –3 2 2 –1 0 0 0 НИУ ВШЭ 32 / 97 Женитьба ▶ Но тогда Маше лучше всего не принимать ухаживаний Саши cовсем. Расстаться Принимать Ухаживать Жениться М С Не принимать Не ухаживать Дмитрий Дагаев С 3 –3 2 2 –1 0 0 0 НИУ ВШЭ 33 / 97 Женитьба ▶ Тогда Саше лучше вообще не ухаживать за Машей, ведь она всё равно не примет его ухаживаний. Расстаться Принимать С Жениться Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев 3 –3 2 2 –1 0 0 0 НИУ ВШЭ 34 / 97 Женитьба ▶ В равновесии Нэша, совершенном на подыграх, Саша даже не пытается ухаживать за Машей, и они оба получают платеж 0. ▶ Но им обоим было бы лучше, если бы Саша начал ухаживать за Машей, Маша приняла бы его ухаживания, а Саша затем женился бы на ней. Расстаться Принимать С Жениться Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев 3 –3 2 2 –1 0 0 0 НИУ ВШЭ 35 / 97 Женитьба Оставим либеральное общество и обратимся к обществу высокоморальному. Как изменится от этого наша игра? ▶ Саша больше не сможет расстаться с Машей, если начнет ухаживать за ней. Принимать С Жениться 2 2 Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев –1 0 0 0 НИУ ВШЭ 36 / 97 Женитьба ▶ Решим игру с конца. ▶ Если Саша решил ухаживать за Машей и Маша приняла его ухаживания, то после этого Саше ничего не остается, кроме как жениться на ней. Принимать С Жениться 2 2 Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев –1 0 0 0 НИУ ВШЭ 37 / 97 Женитьба ▶ Но тогда наилучшее решение для Маши –– принять ухаживания Саши. Принимать Ухаживать Жениться 2 2 М С Не принимать Не ухаживать Дмитрий Дагаев С –1 0 0 0 НИУ ВШЭ 38 / 97 Женитьба ▶ Тогда Саше лучше начать ухаживать за Машей. Принимать С Жениться 2 2 Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев –1 0 0 0 НИУ ВШЭ 39 / 97 Женитьба ▶ Получаем, что в новом равновесии Нэша, совершенном на подыграх, Саша и Маша счастливы вместе. ▶ Таким образом, коммитмент в виде женитьбы помог Маше и Саше попасть в равновесие, в котором им обоим стало лучше. Принимать С Жениться 2 2 Ухаживать М С Не принимать Не ухаживать Дмитрий Дагаев –1 0 0 0 НИУ ВШЭ 40 / 97 Работник и менеджер Постановка игры ▶ Рассмотрим игру, описывающую взаимодействие работника и менеджера. ▶ Сначала работник решает, прилагать ли ему усилия или работать спустя рукава. ▶ Потом менеджер решает, увольнять ли работника или продолжить работать с ним. Дмитрий Дагаев НИУ ВШЭ 41 / 97 Работник и менеджер Платежи ▶ Если работник прикладывает усилия и остается на работе, то платежи работника и менеджера равны (1, 2). ▶ Если работник не прикладывает усилия и остается на работе, то платежи работника и менеджера равны (2, 1). ▶ Увольнение работника сопряжено с издержками для обоих агентов: работник получает (−5), менеджер получает (−3). Дмитрий Дагаев НИУ ВШЭ 42 / 97 Работник и менеджер ▶ Дерево игры: Увольнять Прикладывать усилия М Не увольнять P Увольнять Не прикладывать М Не увольнять Дмитрий Дагаев НИУ ВШЭ –4 –1 1 2 –3 –2 2 1 43 / 97 Работник и менеджер Стратегии работника У работника 2 стратегии: ▶ прикладывать усилия (П); ▶ не прикладывать усилий (П). Дмитрий Дагаев НИУ ВШЭ 44 / 97 Работник и менеджер Стратегии менеджера У менеджера 4 стратегии: ▶ УУ –– уволить работника в любом случае; ▶ УН –– уволить, только если работник прикладывал усилия; ▶ НУ –– уволить, только если работник не прикладывал усилий; ▶ НН –– не увольнять в любом случае. Дмитрий Дагаев НИУ ВШЭ 45 / 97 Работник и менеджер Найдем SPNE в этой игре. Будем решать игру с конца. ▶ Какую бы стратегию ни выбрал работник, менеджеру выгоднее не увольнять его. Увольнять Прикладывать усилия М Не увольнять P Увольнять Не прикладывать М Не увольнять Дмитрий Дагаев НИУ ВШЭ –4 –1 1 2 –3 –2 2 1 46 / 97 Работник и менеджер ▶ Зная, что менеджер в любом случае не уволит его, работник выберет стратегию «не прикладывать усилий». Увольнять Прикладывать усилия М Не увольнять P Увольнять Не прикладывать М Не увольнять Дмитрий Дагаев НИУ ВШЭ –4 –1 1 2 –3 –2 2 1 47 / 97 Работник и менеджер Равновесием Нэша, совершенным на подыграх, в этой игре будет профиль стратегий (Н, НН). Менеджеру невыгодно увольнять работника, даже если работник работает спустя рукава, так как издержки на увольнение слишком высоки. А у работника нет мотивации для активного труда: над ним не висит угроза потери работы. Дмитрий Дагаев НИУ ВШЭ 48 / 97 Работник и менеджер ▶ Предположим теперь, что менеджер и работник подписывают контракт перед началом игры. ▶ Условия контракта обязательно должны быть выполнены. ▶ Менеджеру было бы выгодно включить в контракт пункт со следующим содержанием: «Если работник не прикладывает усилий, то менеджер обязан уволить работника». Дмитрий Дагаев НИУ ВШЭ 49 / 97 Работник и менеджер ▶ Теперь единственное действие, доступное менеджеру, если работник сыграл стратегию «не прикладывать усилий», –– уволить работника. ▶ Новое дерево игры: Увольнять Прикладывать усилия М Не увольнять P Не прикладывать Дмитрий Дагаев М НИУ ВШЭ Увольнять –4 –1 1 2 –3 –2 50 / 97 Работник и менеджер ▶ Если работник прикладывает усилия, то менеджеру выгоднее не увольнять работника. ▶ Если работник не прикладывает усилий, то у менеджера нет выбора: он обязан уволить работника. Увольнять Прикладывать усилия М Не увольнять P Не прикладывать Дмитрий Дагаев М НИУ ВШЭ Увольнять –4 –1 1 2 –3 –2 51 / 97 Работник и менеджер ▶ Тогда работнику выгоднее выбрать стратегию «прикладывать усилия». Увольнять Прикладывать усилия М Не увольнять P Не прикладывать Дмитрий Дагаев М НИУ ВШЭ Увольнять –4 –1 1 2 –3 –2 52 / 97 Работник и менеджер ▶ В получившемся равновесии Нэша, совершенном на подыграх, работник прикладывает усилия и менеджер не увольняет его. ▶ В нашем примере заключение контракта с работником помогло менеджеру получить больший платеж. ▶ Тем не менее в реальном мире существуют проблемы с реализацией условия: «Если работник не прикладывал усилий в первом периоде, то менеджер обязан уволить работника». Дмитрий Дагаев НИУ ВШЭ 53 / 97 Работник и менеджер Первая проблема ▶ Не всегда можно точно оценить, прикладывал ли усилия работник или не прикладывал: результат работы может зависеть не только от уровня усилий, но и от других ненаблюдаемых факторов. Пример ▶ Успех брокера на бирже зависит не только от его усилий и мастерства, но и от удачи. Дмитрий Дагаев НИУ ВШЭ 54 / 97 Работник и менеджер Вторая проблема ▶ Если о контракте известно только работнику и менеджеру, у обоих будут стимулы передоговориться и отменить контракт. ▶ Работник может не прикладывать усилия, а потом предложить менеджеру отказаться от условия контракта. ▶ Менеджеру будет выгодно отказаться от контракта из-за высоких издержек на увольнение работника. Дмитрий Дагаев НИУ ВШЭ 55 / 97 SPNE ▶ Во всех играх, которые мы обсуждали до этого, существовало равновесие Нэша, совершенное на подыграх. ▶ Верно ли, что в любой последовательной игре существует SPNE? ▶ Ответ на этот вопрос дает теорема Цермело. Дмитрий Дагаев НИУ ВШЭ 56 / 97 Теорема Цермело Теорема Цермело В любой конечной последовательной игре с полной информацией существует равновесие Нэша, совершенное на подыграх. Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theory des Schachspiels, Proc. Fifth Congress Mathematicians, 501—504. Дмитрий Дагаев НИУ ВШЭ 57 / 97 Единственность SPNE ▶ Всегда ли это равновесие единственное? Нет! Рассмотрим в качестве контрпримера следующую игру: s1 t1 2 t2 1 s2 Дмитрий Дагаев 2 0 3 0 1 –1 НИУ ВШЭ 58 / 97 Единственность SPNE ▶ Будем решать игру с конца. ▶ Второму игроку все равно, какую стратегию выбрать, так как стратегии t1 и t2 приносят ему одинаковый платеж. s1 t1 2 t2 1 s2 Дмитрий Дагаев 2 0 3 0 1 –1 НИУ ВШЭ 59 / 97 Единственность SPNE ▶ Первому игроку лучше выбрать стратегию s1 , так как она приносит ему больший платеж, чем s2 , какую бы стратегию ни выбрал второй игрок. s1 t1 2 t2 1 s2 Дмитрий Дагаев 2 0 3 0 1 –1 НИУ ВШЭ 60 / 97 Единственность SPNE ▶ В этой игре два SPNE: (s1 , t1 ) и (s1 , t2 ). s1 t1 2 t2 1 s2 Дмитрий Дагаев 2 0 3 0 1 –1 НИУ ВШЭ 61 / 97 Единственность SPNE ▶ При каких условиях равновесие Нэша, совершенное на подыграх, в игре будет единственным? ▶ Например, если все платежи, получаемые каждым из игроков, различны, то в конечной последовательной игре с полной информацией существует единственное SPNE 1 . 1 Zermelo, E., Über eine Anwendung der Mengenlehre auf die Theory des Schachspiels, Proc. Fifth Congress Mathematicians, 1913: 501-504 Дмитрий Дагаев НИУ ВШЭ 62 / 97 Единственность SPNE ▶ Рассмотрим некоторую подыгру. ▶ Предположим, что ход в ней принадлежит первому игроку. ▶ Если существуют по крайней мере две стратегии, такие что первому игроку безразлично, какую из них играть, то они должны приносить ему одинаковый платеж. ▶ В противном случае ему было бы выгодно выбрать стратегию, приносящую больший платеж. Дмитрий Дагаев НИУ ВШЭ 63 / 97 Единственность SPNE Вывод Если все платежи всех игроков различны, то в конечной последовательной игре с полной информацией существует единственное SPNE. Дмитрий Дагаев НИУ ВШЭ 64 / 97 SPNE в играх с нулевой суммой В игре двух лиц с нулевой суммой 2 во всех равновесиях Нэша, совершенных на подыграх, каждый игрок получает одинаковые платежи. Доказательство ▶ Рассмотрим подыгру последнего уровня. ▶ Если игрок, делающий в ней ход, безразличен в выборе между двумя стратегиями, то эти две стратегии приносят ему одинаковый платеж, как и его сопернику, так как у нас игра с нулевой суммой. ▶ Аналогично можно рассмотреть подыгру предпоследнего уровня и т. д. 2 Игра, в которой сумма платежей игроков равна 0 для любого профиля стратегий. Дмитрий Дагаев НИУ ВШЭ 65 / 97 Шашки ▶ Примером игры с нулевой суммой являются шашки. International draughts, CC BY-SA 3.0 Дмитрий Дагаев НИУ ВШЭ 66 / 97 Теорема Цермело Значит, в шашках при правильной игре обоих игроков ▶ либо победит тот, кто ходит первым, ▶ либо тот, кто ходит вторым, ▶ либо будет зафиксирована ничья. Дмитрий Дагаев НИУ ВШЭ 67 / 97 Шашки ▶ Для шашек на доске 8 × 8 существует около 5 · 1020 возможных позиций. ▶ Дерево игры в шашки огромно. ▶ Но недавно десятки компьютеров, работавшие практически без перерыва с 1989 года, наконец, довели алгоритм Цермело –– Куна для шашек до конца. ▶ И теперь известно, что при правильной игре обоих игроков в шашках будет зафиксирована ничья! 3 ▶ А вот шахматы, дерево для которых гораздо больше дерева для игры в шашки, до сих пор не решены. 3 Schaeffer, J. et. al. (2007). Checkers is solved. Science, 317(5844), 1518—1522. Дмитрий Дагаев НИУ ВШЭ 68 / 97 Игра «Диктатор» Постановка игры ▶ Играют двое. ▶ Первому игроку дают 100 рублей и предлагают поделиться этими деньгами со вторым игроком. ▶ Он выбирает целое число a от 0 до 100 –– количество рублей, которое он отдает второму игроку. ▶ Первый игрок получает (100 − a) рублей, а второй –– a рублей. Дмитрий Дагаев НИУ ВШЭ 69 / 97 Игра «Диктатор» Стратегии ▶ У первого игрока 101 стратегия: отдать второму игроку 0, 1, . . . , 100 рублей. ▶ У второго игрока нет стратегий. Предпочтения игроков ▶ Каждый игрок хочет получить как можно больше денег. Дмитрий Дагаев НИУ ВШЭ 70 / 97 Игра «Диктатор» ▶ Допустим, первый игрок выберет a > 0. ▶ Будет ли такая ситуация равновесием Нэша, совершенным на подыграх? ▶ Нет, не будет! Дмитрий Дагаев НИУ ВШЭ 71 / 97 Игра «Диктатор» ▶ Первый игрок ведет себя неоптимально на подыгре, в которой он выбирает, какую сумму a отдать второму игроку. ▶ Он может уменьшить a на 1 и увеличить свой выигрыш: 100 − (a − 1) = 100 − a + 1 > 100 − a ▶ Единственным равновесием Нэша, совершенным на подыграх, в этой игре будет ситуация, когда первый игрок отдает второму a = 0. Дмитрий Дагаев НИУ ВШЭ 72 / 97 Игра «Ультиматум» Постановка игры ▶ Играют двое. ▶ Первому игроку дают 100 рублей. ▶ Затем он выбирает целое число a от 0 до 100 –– количество рублей, которое он отдает второму игроку. ▶ Второй игрок может согласиться с дележом, тогда первый получит (100 − a) рублей, а второй –– a рублей, или запретить дележ, и тогда оба игрока не получат ничего. Дмитрий Дагаев НИУ ВШЭ 73 / 97 Игра «Ультиматум» Стратегии ▶ У первого игрока 101 стратегия: отдать второму игроку 0, 1, . . . , 100 рублей. ▶ У второго игрока теперь 2101 стратегии: ему принадлежит ход в 101 вершине, в каждой из которых он может согласиться на предложение первого игрока или не согласиться. Предпочтения игроков ▶ Каждый игрок хочет получить как можно больше денег. Дмитрий Дагаев НИУ ВШЭ 74 / 97 Игра «Ультиматум» ▶ Будем решать игру с конца. ▶ Если второму игроку предложат сумму, большую 0, ему будет выгодно согласиться на дележ. ▶ Если второму игроку предложат ровно 0, ему будет всё равно, соглашаться на предложение первого игрока или не соглашаться. Дмитрий Дагаев НИУ ВШЭ 75 / 97 Игра «Ультиматум» Значит, в SPNE второй игрок играет одну из следующих стратегий: 1. Согласиться на любое предложение первого игрока. 2. Согласиться, если первый игрок предложил a ⩾ 1, не согласиться, если первый игрок предложил a = 0. Дмитрий Дагаев НИУ ВШЭ 76 / 97 Игра «Ультиматум» Что тогда будет делать первый игрок? ▶ Если первый предложит второму больше 1, второй согласится на дележ. ▶ Но это невыгодно первому игроку: он может предложить второму ровно 1, и второй всё равно согласится. ▶ Значит, первый игрок точно не будет предлагать второму больше 1. Дмитрий Дагаев НИУ ВШЭ 77 / 97 Игра «Ультиматум» ▶ Пусть второй игрок играет стратегию «согласиться на любое предложение», тогда первому лучше всего предложить 0. ▶ Если второй игрок играет стратегию «согласиться, если первый игрок предложил a ⩾ 1, отказаться, если первый игрок предложил a = 0», то первому лучше предложить 1. ▶ В этой игре два SPNE. ▶ В одном из них платежи игроков равны (100, 0), а в другом –– (99, 1). Дмитрий Дагаев НИУ ВШЭ 78 / 97 Экспериментальные результаты В реальности люди редко играют «эгоистичные» равновесия Нэша, совершенные на подыграх, которые мы получили. В игре «Диктатор» ▶ Первый игрок отдает второму 0 лишь в 40 % случаев. ▶ А в среднем первый отдает второму 20 % от общей суммы 4 . 4 Guala, F., & Mittone, L. (2010). Paradigmatic experiments: the dictator game. The Journal of SocioEconomics, 39(5), 578–584. Дмитрий Дагаев НИУ ВШЭ 79 / 97 Экспериментальные результаты В игре «Ультиматум» ▶ Первый игрок очень редко предлагает второму 0. ▶ В среднем первый предлагает второму 40 % от общей суммы. ▶ Второй игрок запрещает дележ в 15––20 % случаев. ▶ Причем чем ниже сумма, предложенная первым игроком, тем выше вероятность, что второй не согласится на предложение первого. ▶ Очень часто вторые игроки отвергают предложения первых игроков, если первые игроки предлагают меньше 20 % от общей суммы 5 . 5 Roth, A. E. et al. (1991). Bargaining and market behavior in Jerusalem, Ljubljana, Pittsburgh, and Tokyo: An experimental study. The American Economic Review, 81(5), 1068–1095. Дмитрий Дагаев НИУ ВШЭ 80 / 97 Экспериментальные результаты ▶ Результаты экспериментов наводят на мысль, что играя в такие игры, как «Диктатор» и «Ультиматум», люди максимизируют не только свой денежный выигрыш. ▶ Важное значение имеет то, насколько «справедливо» был распределен денежный выигрыш. ▶ Например, «диктаторы» довольно часто отдают другому игроку некоторую положительную сумму. ▶ А в игре «Ультиматум» второй игрок может не согласиться на предложенную ему сумму, если она окажется, по его мнению, слишком маленькой, и таким образом наказать первого игрока за жадность. Дмитрий Дагаев НИУ ВШЭ 81 / 97 Модель Штакельберга: идея ▶ На предыдущих занятиях мы разобрали модель олигополистической конкуренции Курно. ▶ Фирмы конкурировали, выбирая свои выпуски одновременно и независимо друг от друга. ▶ Это предположение позволило нам смоделировать конкуренцию между фирмами в виде одновременной игры и найти равновесие Нэша. Дмитрий Дагаев НИУ ВШЭ 82 / 97 Модель Штакельберга: идея ▶ Будем считать, что фирмы принимают решения о том, какой выпуск произвести, последовательно. ▶ Тогда модель можно будет представить в виде игры в развернутой форме. ▶ Эта модель была предложена немецким экономистом Генрихом фон Штакельбергом спустя 96 лет после того, как была описана модель Курно 6 . 6 von Stackelberg, H. (1934). Market Structure and Equilibrium (Marktform und Gleichgewicht). Дмитрий Дагаев НИУ ВШЭ 83 / 97 Модель Штакельберга: постановка задачи Конкуренция между фирмами устроена так: 1. Сначала первая фирма выбирает свой выпуск q1 . 2. Затем вторая фирма, зная выпуск первой фирмы, выбирает свой выпуск q2 . 3. Рыночная цена устанавливается на уровне p = 1 − q1 − q2 , если q1 + q2 < 1, и на уровне p = 0, если q1 + q2 ⩾ 1. 4. Фирмы получают прибыль. Дмитрий Дагаев НИУ ВШЭ 84 / 97 Модель Штакельберга: постановка задачи Стратегия первой фирмы ▶ Cтратегия первой фирмы, делающей ход только в одной вершине, –– выпуск q1 ∈ [0, 1). Дмитрий Дагаев НИУ ВШЭ 85 / 97 Модель Штакельберга: постановка задачи Стратегия второй фирмы ▶ Стратегия второй фирмы –– это набор ее действий в каждой вершине, в которой ей принадлежит ход. ▶ Cтратегия второй фирмы должна каждому выпуску первой фирмы q1 сопоставлять некоторый выпуск второй фирмы q2 . ▶ Стратегия второй –– некоторая функция q2 (q1 ). Дмитрий Дагаев НИУ ВШЭ 86 / 97 Модель Штакельберга: постановка задачи Платежи Предположим, что обе фирмы не несут никаких издержек и их прибыли равны: ▶ π1 = pq1 = (1 − q1 − q2 )q1 ▶ π2 = pq2 = (1 − q1 − q2 )q2 Теперь, сформулировав основные предположения модели, найдем в ней равновесие Нэша, совершенное на подыграх. Дмитрий Дагаев НИУ ВШЭ 87 / 97 Модель Штакельберга: решение Чтобы найти SPNE, будем решать игру с конца. ▶ Cперва нужно понять, сколько будет выгодно производить второй фирме, если первая произвела некоторый фиксированный выпуск q1 . ▶ Запишем прибыль второй фирмы: π2 = pq2 = (1 − q1 − q2 )q2 Дмитрий Дагаев НИУ ВШЭ 88 / 97 Модель Штакельберга: решение ▶ Вторая фирма при каждом фиксированном q1 будет максимизировать π2 : π2 = pq2 = (1 − q1 − q2 )q2 → max q2 ▶ Графиком функции прибыли является парабола, ветви вниз. ▶ Функция прибыли второй фирмы достигает своего максимума в вершине параболы: 1 − q1 q∗2 = 2 ▶ Значит, оптимальной стратегией второй фирмы будет q∗2 (q1 ) = Дмитрий Дагаев НИУ ВШЭ 1 − q1 2 89 / 97 Модель Штакельберга: решение ▶ Первая фирма понимает, что если она произведет q1 , то второй фирме будет выгодно произвести q∗2 (q1 ) = ▶ 1 − q1 2 Но если первая фирма знает, какое q2 произведет вторая фирма, тогда она может посчитать, какая установится цена p, если она выпустит q1 : p = 1 − q1 − q2 = 1 − q1 − ▶ 1 − q1 1 − q1 = 2 2 Тогда ее прибыль будет равна: π1 = pq1 = Дмитрий Дагаев НИУ ВШЭ 1 − q1 q1 2 90 / 97 Модель Штакельберга: решение ▶ Первая фирма максимизирует прибыль: π1 = pq1 = ▶ 1 − q1 q1 → max q1 2 Функция прибыли первой фирмы достигает своего максимума в вершине параболы: q∗1 = ▶ 1 2 Тогда выпуск второй фирмы будет равен: q∗2 (q1 ) = Дмитрий Дагаев 1 − q1 1 = 2 4 НИУ ВШЭ 91 / 97 Модель Штакельберга: решение ▶ Профиль стратегий ( (q1 , q2 (q1 )) = 1 (1 − q1 ) , 2 2 ) будет равновесием Нэша, совершенным на подыграх. ▶ Заметим, что вторая фирма ведет себя оптимально на каждой подыгре, если выбирает стратегию производить ровно q∗2 (q1 ) = ▶ (1 − q1 ) 2 Эта стратегия –– ее наилучший ответ на любую стратегию q1 первой фирмы. Дмитрий Дагаев НИУ ВШЭ 92 / 97 Модель Штакельберга: решение ▶ Первая фирма также ведет себя оптимально на каждой подыгре. ▶ Из всех выпусков q1 она выбирает тот, который приносит ей наибольшую прибыль при условии, что стратегия второй фирмы имеет вид q∗2 (q1 ) = ▶ (1 − q1 ) 2 Таким образом в SPNE фирмы производят ( ) 1 1 ∗ ∗ (q1 , q2 ) = , 2 4 Дмитрий Дагаев НИУ ВШЭ 93 / 97 Модель Штакельберга: равновесия Нэша Существуют ли в нашей модели другие равновесия Нэша? ▶ ▶ ▶ Да, равновесие Курно будет равновесием Нэша в модели Штакельберга. 1 Пусть стратегия первой фирмы –– производить q1 = . 3 1 А стратегия второй фирмы –– производить вне зависимости от того, какой 3 выпуск q1 произвела первая фирма: q2 (q1 ) = Дмитрий Дагаев НИУ ВШЭ 1 3 94 / 97 Модель Штакельберга: равновесия Нэша ▶ Из модели Курно мы помним, что оптимальный выпуск второй фирмы, 1 если q1 = , равен 3 1 1− 1 − q 1 3 =1 q∗2 (q1 ) = = 2 2 3 ▶ Поэтому, если стратегия первой фирмы –– q1 = 1/3, то второй фирме невыгодно отклониться и выбрать другую стратегию. ▶ Стратегия q2 (q1 ) = 1 приносит ей наибольший выигрыш в ответ 3 1 на стратегию первой фирмы q1 = . 3 Дмитрий Дагаев НИУ ВШЭ 95 / 97 Модель Штакельберга: равновесия Нэша ▶ Первой фирме также невыгодно отклониться при фиксированной стратегии 1 второй фирмы производить q2 (q1 ) = . 3 ▶ Оптимальный ответ первой фирмы на решение второй фирмы всегда 1 1 производить q2 (q1 ) = –– тоже производить q1 = . 3 3 ( ) 1 2 π1 = pq1 = (1 − q1 − q2 )q1 = 1 − − q1 q1 = q1 − q21 → max q1 3 3 q∗1 = Дмитрий Дагаев НИУ ВШЭ 1 3 96 / 97 Модель Штакельберга: равновесия Нэша Однако равновесие Курно в модели Штакельберга не является равновесием Нэша, совершенным на подыграх. ▶ Вторая фирма ведет себя неоптимально на подыгре, в которой первая 1 фирма выбирает выпуск q1 = . 2 ▶ Так как тогда второй фирме лучше всего произвести ( ) 1− 1 1 2 =1 q2 = 2 2 4 1 вместо того, чтобы производить q2 = . 3 Дмитрий Дагаев НИУ ВШЭ 97 / 97