Академия. Теория игр. Неделя 6.
Когда-то в юности я читал книжку американского психолога и психиатра Эрика Бэрна "Игры, в которые играют люди и люди, которые играют в игры" и думал, что никогда ничего более интереснее касательно игры не узнаю. Продолжая постигать тайны курса "Теории игр" проекта Вторая академия от @ontofractal, понимаю к своей радости, что я тогда ошибался. Сегодня мы продолжим увлекательное путешествие в секреты алгоритма обратной индукции.
СВЯЗЬ МЕЖДУ ИГРАМИ В НОРМАЛЬНОЙ И РАЗВЁРНУТОЙ ФОРМАХ
Итак, нам знакомы игры в нормальной (игроки совершают свои ходы одновременно) и развёрнутой (игроки действуют последовательно друг за другом) формах. И если для первой надо строить матрицу игры, то для второй - дерево игры. Пока эти два способа интерпретации стратегических взаимодействий никак не пересекались. Настал момент, когда мы соединим, казалось бы, несоединимое.
На прошлом занятии мы построили дерево игры, описывающее ситуацию, закрученную вокруг пустого горшка из-под мёда:
Винни-Пуху принадлежит ход в одной вершине, и у него есть множество возможных стратегий Sвинни-пух={С, Н}:
1) съесть мёд (С),
2) не есть мёд (Н).
У Иа-Иа есть две вершины, в которых он может сделать ход, а множество его возможных стратегий - это Sиа-иа={ПП, ПН, НП, НН}:
1) принять подарок, если горшок пустой и принять подарок, если горшок с мёдом (ПП),
2) принять подарок, если горшок пустой и не принимать подарок, если горшок с мёдом (ПН),
3) не принимать подарок, если горшок пустой и принять подарок, если горшок с мёдом (НП),
4) не принимать подарок, если горшок пустой и не принимать подарок, если горшок с мёдом (НН).
Вообще, если у игрока есть n вершин, то его стратегию можно закодировать аббревиатурой из n букв, обозначающих его возможные действия. В случае с Иа-Иа первая буква будет соответствовать стратегии Винни-Пуха "съесть", а вторая - стратегии "не есть". Используя дерево игры и введённые обозначения стратегий, мы можем составить матрицу взаимодействия медвежонка и ослика:
Если есть матрица, то мы может воспользоваться тремя концепциями решения игр:
1) равновесие в доминирующих стратегиях,
2) равновесие, полученное исключением доминируемых стратегий,
3) равновесие Нэша.
Отметим оптимальные ответы каждого из игроков на стратегии другого, как мы это делали раньше - точками (для Винни-Пуха) и звёздочками (для Иа-Иа):
Видно, что в игре есть три равновесия Нэша: (С, ПП), (С, ПН) и (Н, НП), в которых каждый игрок играет оптимально в ответ на фиксированную стратегию соперника.
РАВНОВЕСИЕ НЭША, СОВЕРШЁННОЕ НА ПОДЫГРАХ
Если вспомнить предыдущее занятие, когда мы для решения использовали алгоритм обратной индукции, то в этой игре было одно решение - (С, ПП):
Так сколько же решений на самом деле: одно или три? Есть ли противоречие в наших рассуждениях? Дело в том, что при обратной индукции игроки играют оптимально на каждой подыгре, а в равновесии Нэша это условие вовсе необязательно, поскольку наша игра до какой-то своей подыгры может просто не добраться. Неоптимальность действий одного из игроков не нарушит равновесие Нэша.
Для примера рассмотрим профиль (С, ПН):
Видно, что Иа-Иа играет неоптимально в случае, если Винни-Пух не ест мёд - ему выгоднее принять подарок. Однако ни одному из игроков невыгодно отклониться в этом профиле. Винни-Пух получает максимальный платёж, а Иа-Иа вообще всё равно, что будет в случае, когда медвежонок не станет есть мёд - игра по этой ветке просто не пойдёт.
Итак, в равновесии Нэша игрок может играть неоптимально в подыгре, которая, собственно, не будет сыграна.
А вот в профиле, соответствующем решению, полученному с помощью алгоритма обратной индукции, каждый игрок играет оптимально на любой подыгре и такой профиль один - (С, ПП). Такие профили и называются равновесиями Нэша, совершёнными на подыграх (SPNE - Subgame Perfect Nash Equilibrium).
Можно сказать, что SPNE - это усиление обычного равновесия Нэша в результате дополнительного условия, накладываемое на него.
Чтобы закрепить новое понятие, найдём равновесие Нэша на подыграх в следующем примере, представленном в виде дерева игры:
В этой игре три игрока: 1, 2 и 3. Множества их стратегий: S1={s1, s2}, S2={t1, t2, t3}, S3={r1, r2}. Как это принято в обратной индукции - начнём с конца. Третьему игроку выгодно сыграть стратегию r2. Откатываемся назад. Второму игроку выгодно сыграть стратегию t3. Ещё шаг назад. Первому игроку выгодно сыграть стратегию s2. Значит, равновесием Нэша на подыграх будет профиль (s2, t3, r2):
И не важно, что игра закончится без участия второго и третьего игроков. Мы описываем её формально и поэтому должны учитывать действия игроков даже в тех вершинах, до которых игра не доберётся.
ИГРЫ С КОММИТМЕНТОМ
Если бы Алану Милну сказали, что на ситуациях, взятых из его произведения о Винни-Пухе, когда-то будет изучаться теория игр, писатель, скорее всего, просто принял бы это за шутку. Тем не менее, мы опять возвращаемся к дню рождения Иа-Иа.
Что изменится в игре, если ослик напишет Винни-Пуху письмо: "Я откажусь от подарка, если в горшочке не будет мёда" и попросит Сову проследить, чтобы он действительно выполнил бы данное обещание? Изменится дерево игры:
Теперь у ослика в случае, когда Винни-Пух съедает мёд, нет возможности принять подарок - мы отрезали эту ветку. Тогда у медвежонка оптимальной стратегией становится "не есть мёд", поскольку в этом случае Иа-Иа выгодно принять горшочек, и у Винни-Пуха будем максимальный платёж из возможных.
Такие ситуации, когда игрок сознательно ограничивает свой выбор, чтобы в итоге оказаться в выигрыше, называются коммитментами.
Например, выгодно, с психологической точки зрения, купить дорогой абонемент в тренажёрный зал. Теперь занимающемуся будет проще заставить себя ходить на тренировки.
Пора оставить сказки и перейти к прозе реальной жизни. А что может быть серьёзнее женитьбы? Пусть есть два общества: высокоморальное и либеральное. В первом, если парень начинает ухаживать за девушкой, а они принимает его ухаживания, то он обязан на ней жениться. А вот во втором - парень может и отказаться от брака, разорвав отношения.
Вопрос: в каком из двух обществ парням будет лучше? Казалось бы, что ответ очевиден - конечно в либеральном. Однако проанализируем ситуации с помощью методов теории игр. Начнём с более привлекательного либерального общества.
Пусть Саша пытается ухаживать за Машей, та соглашается на это внимание, и рано или поздно перед Сашей становится выбор: оборвать отношения или жениться. С точки зрения молодого шалопая девушку выгоднее бросить, но, что скажет теория? Рассмотрим возможные платежи игроков. Как я уже сказал, Саше лучше всего, чтобы Маша согласилась на их отношения, а потом расстаться с ней. Немного хуже, когда всё заканчивается свадьбой. Плохо - не пытаться начать ухаживать. И совсем отстой, если Саша начнёт проявлять знаки внимания, а Маша пошлёт его на фиг.
Теперь разберёмся с платежами Маши. Понятное дело, что самую дорогую выплату девушка получит в случае бракосочетания. Если она решает не принимать ухаживания, то ничего не приобретает, но ничего особенного и не теряет (кто такой этот Саша?). И девушка оказывается в проигрыше, если Саша бросает её. Фу-у-х! Никогда не соглашусь писать сценарии романтических мелодрам.
Взглянем на дерево игры:
Начнём с последней подыгры. Ход Саши, и ему выгоднее бросить Машу. Откатываемся назад - ход Маши. Если она примет ухаживания, то Саша её бросит, поэтому её выгодно послать ухажёра. И первая подыгра - опять ход Саши. Если он попытается обаять девушку, она проигнорирует его попытку, поэтому Саше выгодно вообще не начинать этот роман.
Итак, равновесием Нэша, совершённым на подыграх будет решение Саши не ввязываться в любовные отношения. Платежи игроков нулевые, а SPNE: (НР, Н).
Теперь рассмотрим эту ситуацию в высокоморальном обществе, где Саша в случае согласия Маши не может её бросить.
Видно, максимальные платежи игроки получат в случае, если Саша начнёт ухаживать, Маша согласится на эти ухаживания, а Саша женится на ней, и дамы в первом ряду рыдают от счастья. В этой игре SPNE: (УЖ, П).
Получается, что, уменьшая количество возможных действий Саши, мы улучшили платежи героев. Удивительным образом с помощью теории игр мы пришли к выводу, что правила романтических отношений, когда эти отношения должны заканчиваться свадьбой, гарантируют большие платежи влюблённым, нежели полная безответственность в отношениях. А ведь молодые люди об этом даже не подозревают! А жаль...
И ещё один пример, на этот раз экономического характера. Рассмотрим стратегические взаимодействия между работником и менеджером некоторой фирмы. Сначала работник принимает решение как ему работать: кое-как или добросовестно, а затем менеджер либо увольняет его, либо оставляет в фирме. Платежи игроков отметим на дереве игры:
Возможные стратегии работника Sр={П, Н}, менеджера - Sм={УУ, УН, НУ, НН}. Применяем алгоритм обратной индукции и получаем оптимальный ход игры:
Как-то не по фэншую выходит... Попробуем исправить ситуацию с помощью коммитмента. Пусть при приёме на работу работник подписывает контракт, где будет указано, что в случае плохой работы менеджер должен его уволить. Дерево игры меняется, а вместе с ним и SPNE:
Контракт всё исправил: работнику выгодно хорошо работать, если он этого не делает менеджер его увольняет. В реальной жизни не всё так просто. Во-первых, формулировка "прикладывать усилия" может быть интерпретирована как угодно или вообще не будет поддаваться проверке. И во-вторых, надо обеспечить выполнимость менеджером своих обязанностей по увольнению нерадивого работника. Ведь может получиться так, что менеджеру по какой-то причине не выгодно увольнять лентяя.
СВОЙСТВА РАВНОВЕСИЯ НЭША, СОВЕРШЁННОГО НА ПОДЫГРАХ
Теорема Цермело: в любой конечной последовательной игре с полной информацией существует равновесие Нэша, совершённое на подыграх.
Рассмотрим - всегда ли это равновесие единственно? Пусть есть дерево некоторой игры:
Очевидно, что профили (s1, t1) и (s1, t2) - равновесия Нэша. Второму игроку всё равно, что выбирать из своих стратегий, поскольку платежи, которые он получает, одинаковы.
Однако, существуют такие игры, для которых SPNE - единственно. Для этого необходимо, чтобы платежи каждого из игроков в каждой терминальной вершине, в которую приходит игра, были бы различны.
Ещё существуют игры, в которых платежи игроков противоположны, то есть в сумме равны нулю. Такие взаимодействия называют играми с нулевой суммой. Но, если в такой игре будет два SPNE, то платежи каждого из игроков будут одинаковыми.
Игрой с нулевой суммой являются шашки, так как если один игрок выигрывает, то другой. соответственно, проигрывает. А поскольку в любом SPNE платежи всех игроков одинаковы, то либо в любом равновесии выигрывают белые, либо - чёрные, либо - никто. С помощью компьютера, трудящегося практически непрерывно в течение 11 лет, просчитали дерево игры и выяснили, что формально шашки - это ничейная игра, поскольку в любом равновесии, совершённом на подыграх, партия заканчивается вничью. Но для человека, в отличии от машины, запомнить все подыгры и стратегии в них просто невозможно. Поэтому, играя в шашки, мы по-прежнему, то выигрываем, то проигрываем, то играем вничью.
А вот обсчитать шахматы компьютерам до сих пор не хватает мощности - слишком сложным получается дерево игры.
ИГРЫ "ДИКТАТОР" И "УЛЬТИМАТУМ"
Рассмотрим две любопытные игры. Вернее вызывает интерес не сами игры, а как в них предпочитают в реальности играть люди.
1. "Диктатор". Одному игроку дают 100 рублей, и он может отдать другому любую сумму из своих денег. Всё. "А чего тут играть?" - скажите вы и будете правы. Оптимально для первого игрока сыграть профиль (100, 0), в котором он все деньги оставляет себе. Это будет единственное равновесие Нэша на подыграх в "Диктаторе".
2. "Ультиматум". Правила такие же как в предыдущей игре, но второй игрок может отказаться от предложенного профиля и тогда никто ничего не получает. Теперь в игре есть два SPNE:
а) (100, 0); второму игроку всё равно - соглашаться или отказываться, поскольку в результате выбора он не может улучшить свой платёж, а первый получает максимум;
б) (99, 1); если второй откажется, он вообще ничего не получит, а первый, если даст меньше рискует получить о.
Но все эти рассуждения имеют смысл при условии, что игроки играют рационально. В жизни таких людей не бывает. В первой игре профиль (100, 0) играется только в 40% случаев, а самый распространённый профиль - (80, 20). То есть в реальности в игре присутствуют ещё какие-то параметры, влияющие на выбор игрока. Во второй игре чаще всего играется профиль (60, 40), а равновесие (100, 0) выбирается крайне редко. При предложении первого (60, 40) 15-20% вторых игроков отвечают отказом, и никто ничего не получает. Получается, что рациональность теории корректируется психологией живых людей.
МОДЕЛЬ ШТАКЕЛЬБЕРГА
На предыдущих занятиях мы рассматривали модель Курно, описывающую олигополистическую конкуренцию. Сегодня мы немного изменим условия - пусть фирмы принимают решение не одновременно, а последовательно. Например, вторая принимает решение, на основе уже принятого решения первой фирмы. Эту модель предложил экономист Генрих фон Штакельберг.
Конкуренция в ней устроена следующим образом.
1. Первая фирма выбирает свой выпуск товара q1.
2. Вторая, зная выбор первой, выбирает свой - q2.
3. На рынке получается q1+q2 единиц товара.
4. Цена формируется как и прежде: р=1-q1-q2.
5. Фирмы получают свои прибыли.
Задача игроков - максимизировать эти прибыли. Стратегии первой фирмы - это выпуск любого количества продукции от 0 до 1 (для нашей модели), не включая 1. Стратегии второй - на каждую из стратегий первой фирмы q1 ответить оптимальной q2, то есть q2 - это функциональная зависимость от q1. Прибыли фирм описываются как произведения цены на количество товара: п1=рq1=(1-q1-q2)q1, п2=рq2=(1-q1-q2)q2. Теперь поищем SPNE.
Во всех подыграх с ходом второй фирмы, она знает q1 и старается максимизировать свою прибыль по параметру q2. Это мы уже разбирали, помним, что максимум будет в q*2=(1-q1)/2. каковым будет оптимальное поведение первой фирмы? Она знает, как отреагирует вторая на их q1 и может это учесть в своей функции прибыли.
Какова установится в этой ситуации цена товара? Посчитаем: 1-q1-(1-q1)/2=1-q1-1/2-1/2q1=1/2-1/2q1=(1-q1)/2. Тогда прибыль первой фирмы будет при q1=1/2, значит q2=1/4. Профиль (1/2, 1/4) будет равновесием Нэша на подыграх. Это равновесие будет ещё и просто равновесием Нэша. Равновесие Курно в этой модели Штакельберга также будет равновесием Нэша.
ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА
У концепции решения игр - равновесия Нэша - есть несколько разновидностей. В частности, равновесие, совершённое на подыграх, позволяющее соединить игру в нормальной и развёрнутой формах. Или игра с коммитментом, когда самоограничение игрока лишь увеличивает его платежи. Но самое интересное - разбираться в предложенных задачах и пытаться решать их самостоятельно.