Последовательные игры: моральный риск, стимулы и голодные львы

Важность для курса: высокая — обратная индукция, стимулы и обязательства лежат в основе головоломок, ИИ-противников и честной торговли между игроками.

Суть простыми словами

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

Что было на лекции

• «Деньги в шляпе» на настоящие деньги. Игрок I кладёт 0, 1 или 3 доллара. Игрок II видит сумму и либо добавляет столько же, либо забирает всё. Если добавил, I удваивает вклад, а II получает 1,5 доллара прибыли при вкладе 1 и 2 доллара при вкладе 3.
• Джастин и Кэти положили по доллару, Нейт и Стивен добавили свои. Оба «заёмщика» признались, что три доллара забрали бы.
• Обратная индукция: II добавит к одному доллару (1,5 больше 1) и заберёт три (3 больше 2). Значит, I выбирает из 0, 1 и −3 и кладёт доллар. Так и вышло.
• Это модель кредита. Исход (3; 2) лучше для обоих, но достижим только (1; 1,5). Это моральный риск, как у застрахованной машины, которую лень запирать.
• Средства: маленький кредит, законы, отчёт о тратах, выдача денег частями. У каждого есть пределы.
• По идее Нейта договор меняют: при успехе заёмщик получает 3,1, кредитор 1,9. Возвращать теперь выгодно, и кредитор получает 1,9 вместо 1. Брайан заметил, что доходность на доллар выше у маленького проекта.
• Стимулы легко написать плохо. Дочке Полака разрешили сразу есть только раздавленную малину, и она объявляла раздавленной каждую ягоду.
• Залог, например дом родителей, бьёт по заёмщику, если тот сбежит. Поэтому ему дают большой кредит: снизив свой выигрыш в плохом исходе, он выиграл.
• 1066 год. По расчёту саксы атакуют, а норманны бегут. Вильгельм сжигает корабли, бежать некуда, и саксам выгоднее отступить. Полак уточнил, что при Гастингсе саксы всё же атаковали. В «Докторе Стрейнджлаве» машина судного дня бесполезна, потому что о ней не сказали врагу.
• «Голодные львы»: ряд студентов назначили львами, Алекс овцой. Есть овцу может только вожак Райан, но потом он уснёт и станет добычей следующего льва, и так далее. Райан отказался есть. Разбор с конца ряда показал, что ему стоило есть. Обратную индукцию никто не применил, хотя пятью минутами раньше Полак назвал её главным уроком.

Главные понятия

• Последовательная игра (sequential game) — игра, где следующий игрок видит предыдущие ходы.
• Обратная индукция (backward induction) — решаем с последнего хода к первому, считая, что каждый поступит лучшим для себя образом.
• Моральный риск (moral hazard) — тот, кто получил деньги или защиту, может действовать против интересов того, кто их дал.
• Дизайн стимулов (incentive design) — выплаты, которые делают нужное поведение выгодным.
• Обязательство (commitment) — заранее лишить себя части выборов, чтобы изменить поведение других. Залог (collateral) тоже обязательство.

Зерно для создателя игр

• Думай с конца. Так проверяют головоломки, ветки диалогов и бои с боссом: начни с последнего шага и иди назад. Так же работает ИИ пошаговых игр, перебирая дерево ходов.
• Стимулы пишет дизайнер. Игроки идут за выплатами, а не за намерениями автора. Если правило верит игроку на слово, как с «раздавленной» малиной, им обязательно злоупотребят. Ищи такие дыры на плейтесте.
• Доверие нужно строить механикой. Если один игрок обязательно отдаёт вещь первым, крупных сделок не будет. Работают окно безопасного обмена, залог, оплата частями, репутация и честный делёж большой добычи.
• Видимые обязательства. Ход «сжечь корабли» нужен громкий: соперник обязательно его увидит. Скрытая угроза никого не останавливает. Так работают объявленные ставки, блокировка выбора и предупреждения босса.
• Знать приём ещё не значит уметь. Студенты забыли обратную индукцию через пять минут. В обучении игрока нужна задача, которую без нового приёма не решить.

Мини-игра для урока

«Шляпа с жетонами», игра Полака, суммы умножены на 10. Пары, 10 минут.

1. Инвестор кладёт в шляпу 0, 1 или 3 жетона. Изобретатель видит их и либо добавляет столько же, либо забирает жетоны.
2. Очки: 1 и добавил: инвестор +10, изобретатель +15. 1 и забрал: −10 и +10. 3 и добавил: +30 и +20. 3 и забрал: −30 и +30.
3. Раунд 2, «новый договор»: если в шляпе 3 и изобретатель добавил, очки делим 19 и 31.
4. Раунд 3, «залог»: изобретатель заранее кладёт карточку «дом» ценой 20 очков и теряет её, если забирает жетоны.

Что заметить: в первом раунде умный инвестор кладёт 1, потому что думает за партнёра. Договор или залог делают честность выгодной, и оба получают больше. Бонус: «Голодные львы» с 2, 3 и 4 львами, ответ зависит от чётности.

Ошибки и заблуждения

• «Последовательная игра значит, что кто-то ходит первым». Главное, что второй видит ход первого.
• «Залог нужен, чтобы банк получил дом». Он работает, потому что бьёт по заёмщику при обмане.
• «Больше вариантов всегда лучше». Сожжённые корабли меняют поведение врага.

Для продвинутых

• Дерево игры: узлы решений (decision nodes) принадлежат игрокам, конечные узлы (end nodes) несут выигрыши, рёбра (edges) это ходы, путь (path) ведёт от начала к концу.
• Теорему Цермело (1913) о шахматах обычно доказывают обратной индукцией. Кун (1953): в конечной игре с совершенной информацией обратная индукция даёт равновесие. Минимакс в игровом ИИ устроен так же.
• Моральный риск изучает теория контрактов (задача «принципал и агент»). Полак ждал в этой области новой Нобелевской премии через 5–10 лет. В 2016 году премию за теорию контрактов получили Оливер Харт и Бенгт Хольмстрём.
• Обязательства: Т. Шеллинг, «Стратегия конфликта» (1960), Нобелевская премия 2005 года.
• Голодные львы: при нечётном числе львов вожак ест, при чётном нет.