Академия. Теория игр. Неделя 5.

Если моё первоначально представление о "Теории игр" ограничивалось какими-то хитрыми расчётами, позволяющими обыграть казино в Лас-Вегасе, то по ходу изучения этого курса в рамках проекта Вторая академия я всё больше прихожу к выводу о том, что с помощью этой теории можно описать практически любую ситуацию из реальной жизни. Поэтому ещё и ещё раз выражаю признательность @ontofractal за возможноть расширить горизонт своего представления об окружающем мире.

СТРАТЕГИИ В ИГРАХ В РАЗВЁРНУТОЙ ФОРМЕ И АЛГОРИТМ ОБРАТНОЙ ИНДУКЦИИ

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

В качестве примера рассмотрим ситуацию из знаменитого фундаментального труда Алана Милна "Винни-Пух и все-все-все".

Вспомните историю о том, как медвежонок решил сделать ослику Иа-Иа подарок на день рождения. В процессе разворачивания событий перед ним встаёт выбор: съесть мёд из горшочка или нет. После того, как голод побеждает правила хорошего тона, выбирать приходится уже Иа-Иа: принимать такой подарок или гордо отказаться от него. Итак, между героями истории возникает стратегическое взаимодействие. Каковы же предпочтения игроков на множестве возможных исходов этого взаимодействия?

Для Винни-Пуха лучше всего было бы, если бы он съел мёд, а Иа-Иа взял пустой горшок. Немного хуже: мёд не съеден, и ослик забирает горшочек с мёдом. Ещё хуже: мёд съеден, ослик отказывается от подарка. Хуже всего: и мёд не съеден, и Иа-Иа отказывается от подарка.

Для Иа-Иа лучше всего было бы взять горшочек с мёдом, немного хуже - получить пустой горшок и самый невыгодный вариант - совсем ничего не получить.

Представим данное стратегическое взаимодействие в виде дерева игры:

Напомню, что вершины, в которых заканчивается игра, называются терминальными, и около них стоят возможные платежи каждого из игроков.

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

1) Подыгра - часть дерева игры, начинающееся в одной из нетерминальных вершин. На нашем дереве видно три подыгры, начинающиеся в вершинах В, С и А (эта подыгра совпадает со всей игрой).

2) Стратегия игрока в игре в развёрнутой форме - набор действий игрока в каждой вершине, в которой ему принадлежит ход. В данной игре у Винни-Пуха две стратегии:

                                           

У ослика же целых четыре стратегии:

Теперь перейдём к решению построенной модели. Начнём с конца. Рассмотрим подыгры В и С и выберем, какой ход для Иа-Иа будет выгодным в каждом из этих вариантов. Если Винни-Пух играет "съесть", то ослик получит больший платёж, равный 5, если выберет "принять". А если медвежонок играет "не есть", то ослику опять выгодно сыграть "принять" с платежом 10. Итак, мы знаем оптимальные действия Иа-Иа в любой подыгре, в которой он может оказаться.

Переходим на уровень вверх и рассматриваем подыгру А, в которой выбор делает Винни-Пух. При этом он может использовать дерево игры и видеть оптимальные действия ослика. Если медвежонок выбирает "съесть", то его платёж будет равен 10 (поскольку ослик сыграет оптимально), а если выберет "не есть", т о платёж будет меньше - только 5 (поскольку ослик опять же сыграет оптимально). Значит Винни-Пух выберет "съесть".

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

МОДЕЛЬ ТОРГА РУБИНШТЕЙНА

Рассмотрим ещё примеры, демонстрирующие работу алгоритма обратной индукции.

1. "Делёж пирога". Мама испекла пирог и ушла, разрешив сыновьям самим поделить его между собой. Старший брат в течение 15 минут предлагает младшему вариант делёжки. Младший либо соглашается (и тогда игра закончена), либо по истечении отведённого времени предлагает свой вариант. Старший либо соглашается с ним, либо через следующие 15 минут приходит папа и всё съедает сам:

Рассмотрим возможные платежи игроков. Для старшего брата функция полезности выглядит следующим образом:

Здесь kc - доля пирога, которую получит старший брат, n - количество прошедших 15-минутных интервалов (договорились сразу, тогда n=0), а ставка дисконтирования показывает во сколько раз уменьшаются полезные свойства пирога за одни 15 минут.

Аналогично рассчитывается и функция платежей младшего брата:

С течение времени пирог теряет свои вкусовые качества, что и характеризуется ставкой дисконтирования. Если она равна 1/2, то спустя очереные 15 минут пирог теряет половину своего вкуса:

Как происходит делёж? Каждый из братьев предлагает свою пару (доля старшего брата, доля младшего брата) или (kс, kм). Очевидно, что kc+kь=1 или целый пирог. Каждый из братьев стремится максимизировать свой платёж. Будем считать, что, если одному из братьев всё равно принимать предложенный делёж или не принимать, то он его принимает. Решать начнём с конца, как и должно быть в алгоритме обратной индукции.

Младший брат предлагает свою пару. Если старший брат не соглашается, то их платежи равны нулям, если соглашается, то - предложенным младшим братом долям пирога. Поэтому старшему выгодно согласиться. Младший это понимает, поэтому предлагает вариант наиболее оптимальный для него - (0, 1), то есть он съедает пирог один, но во втором периоде игры, а значит полезность пирога уменьшается вдвое и платёж младшего брата составит 1/2:

Возвращаемся на уровень назад, к ходу старшего брата. Он понимает, что если сейчас не договорится с младшим братом, то во втором периоде не получит ничего. Поэтому он должен предложить такую пару, чтобы младшему было неинтересно играть второй период, где его выплата гарантирована равна 1/2. Значит, старший должен предложить пару (1/2, 1/2). Младший в этом случае ничего не теряет, поэтому соглашается. Пирог будет разделен в первые 15 минут:

Немного изменим правила игры. Пусть фактор дисконтирования будет равен не 1/2, а 2/3, то есть пирог будет терять не половину полезных свойств, а только треть:

Тогда во втором периоде младший брат гарантированно получает платёж, равный 2/3. Значит старший в первом периоде разделит пирог (1/3, 2/3), и папа снова останется без пирога:

Получается, что чем больше ставка дисконтирования (пирог дольше сохраняет свои первоначальные свойства), тем меньше получает старший брат. Говорят, что в этом случае у младшего брата большая "переговорная сила".

Рассмотрим ещё один вариант этой игры: увеличим число периодов до трёх, то есть папа приходит через 45 минут. Ставку дисконтирования вернём равной 1/2:

Снова начинаем решать с конца, проводя аналогичные рассуждения. В третьем периоде теперь старший заберёт весь пирог, но его платёж будет равен 1/4. Во втором периоде младшему, чтобы не доводить игру до третьего периода, надо предлагать вариант (1/2, 1/2), поскольку платёж старшего будет равен 1/4 и он, ничего не теряя, согласится на это предложение. Добираемся до первого периода. Старший понимает, что во втором периоде младший получит платёж 1/4, поэтому он и предлагает вариант (3/4, 1/4), и игра заканчивается в первом периоде. В этом варианте игры в более выгодном положении оказывается старший брат.

Модель игры, которую мы только что рассмотрели, предложил израильский экономист Ариэль Рубинштейн. Она применяется в тех случаях, когда необходимо просчитать результат торга между двумя игроками.

ДРУГИЕ ПРИМЕРЫ ИГР В РАЗВЁРНУТОЙ ФОРМЕ

1. "Сломанная ладья". На клетке а1 шахматной доски стоит ладья, которую можно двигать только вверх или вправо. Её нужно переместить в клетку h8. Кто из двух игроков при оптимальных стратегиях поставит ладью в нужное место первым? Решаем игру с конца.

Предположим, что ладья находится на h8 после хода второго игрока, значит для первого игрока (пусть это будем мы) эта клетка проигрышная. Пометим её нулём. Откатываемся назад. Если соперник поставил ладью на любую клетку из диапазонов h1 - h7 или a8 - g8, то следующим ходом мы выигрываем, значит эти клетки для нас выигрышные. Пометим их единицами. Продолжаем откатываться на подыгры назад, проводим аналогичные рассуждения и помечаем выигрышные и проигрышные для нас клетки:

Видим, что изначально ладья стоит на проигрышной для нас клетке. Значит как бы правильно не играл первый игрок, если второй не допустит ошибки - он выиграет.

2. "Палочки". На столе лежит 20 палочек, каждый игрок (их двое) может забрать 1, 2 или 3 палочки. Проигрывает тот, кто заберёт последнюю палочку. Кто выиграет при правильной игре, и как играть правильно?

Если перед нашим последним ходом на столе лежит одна палочка - мы проиграли. Если лежит две палочки, то мы забираем одну, ещё одна остаётся, и мы выигрываем. Если лежит три или четыре, то мы забираем две или три соответственно и снова выигрываем. А вот если лежит пять, то, сколько бы палочек мы не забрали - выигрышная позиция у соперника, и мы проигрываем. Откатываемся назад: если осталось шесть палочек, мы забираем одну и в проигрышной позиции уже оказывается наш соперник. Продолжаем процесс обратной индукции, помечая выигрышные для нас позиции зелёным цветом, а проигрышные - красным:

Двадцать палочек - выигрышная позиция, поэтому, если первый ход наш, то при правильной игре мы выигрываем. Как играть правильно? Соперника нужно каждый раз отправлять в проигрышную позицию. Поэтому первым ходом мы берём три палочки, отправляя соперника на 17, а затем в зависимости от его хода берём столько палочек, чтобы их количество в сумме с палочками, взятыми соперником, равнялось 4.

3. "Числа на доске". На доске через пробелы написаны числа от 1 до 11. Играют двое: Филипп и Жан. Они по очереди расставляют между числами "плюсы" и "минусы". Между 1 и 2 знак ставит Филипп, между 2 и 3 - Жан и т. д. Затем они считают значение выражения. Если оно чётное, то выиграл Жан, если нечётное - Филипп. Товарищи сыграли в эту игру один раз, и выиграл Жан. Филипп предлагает сыграть ещё раз, уверяя, что теперь он точно сможет выиграть. Прав ли Филипп?

Оказывается, что неважно какой знак поставит между 1 и 2 Филипп - результат его хода будет нечётным. Также неважно, что поставит Жан между 2 и 3. Если к нечётному числу прибавить или отнять нечётное, то результат будет чётным. Продолжая наши рассуждения, мы получим, что независимо от стратегий игроков сумма всегда будет чётной, то есть всегда выигрывает Жан:

Итак, бывают такие игры, в которых совершенно не важно насколько правильно играют игроки - на результат игры это повлиять никак не может.

ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА

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