Лекция 3. Итеративное исключение и теорема о медианном избирателе

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

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

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

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

Совет: сначала найди доминируемые стратегии у всех игроков, потом удаляй, потом смотри заново.
Модель выборов. Два кандидата выбирают позицию от 1 (крайне левые) до 10 (крайне правые). Избиратели — по 10% на каждой позиции, голосуют за ближайшего, при равенстве делятся. Выигрыш — доля голосов.
Позиция 2 строго доминирует 1: против соперника на 1 — 90% против 50%, на 2 — 50% против 10%, дальше всегда на 5 пунктов больше. «Доминирует» не значит «побеждает»: сравниваем свои доли против одной и той же позиции соперника.
3 не доминирует 2 в исходной игре (против соперника на 1: 90% против 85%), но доминирует после удаления 1 и 10. Удаляются стратегии кандидатов, а не избиратели.
Раунды: 1 и 10 → 2 и 9 → 3 и 8 → 4 и 7. Остаются 5 и 6. Это теорема о медианном избирателе.
Примеры: Кеннеди и Никсон (1960), Никсон (1968), Клинтон (1992). В экономике — заправки на одном перекрёстке. Хотеллинг (1929), Даунс (1957).
Что модель упускает: неравномерных избирателей (вывод сохраняется), неявку, третьего кандидата (задача в домашнем задании), праймериз, многомерность политики, недоверие к заявленной позиции (Тони Блэр в 1997 году объявил своим финансовый план консерваторов).
Мысль о моделях: модель — абстракция для проверки интуиции; дальше её обогащают и смотрят, меняется ли вывод.
Лучший ответ. Игра без доминируемых стратегий (Up, Middle, Down против Left и Right). Аудитория выбрала Down. Оправдать Down можно только убеждениями: при вероятности ½ на каждый ход соперника Down даёт 3 против 2,5 у остальных. График ожидаемых выигрышей от вероятности: Up лучше при p < 1/3, Down — между 1/3 и 3/5, Middle — дальше.

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

Итеративное исключение доминируемых стратегий (iterative deletion) — удалять доминируемое, пока есть что удалять.
Теорема о медианном избирателе (median voter theorem) — два кандидата сходятся к центру распределения избирателей.
Лучший ответ (best response) — стратегия, дающая наибольший ожидаемый выигрыш при данных убеждениях о действиях соперника.
Убеждения (beliefs) — вероятности, с которыми, по-твоему, соперник выберет каждый ход.

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

Игроки сбегаются к «центру»: самому безопасному билду, самой выгодной точке карты. Если хочешь разнообразия, награждай края: уникальные ресурсы, задачи, роли.
Цепочка исключений объясняет «мету»: после того как игроки отказались от плохого, становятся плохими следующие варианты. Баланс проверяют с учётом того, что игроки уже отбросили.
Лучший ответ на убеждения — модель для ИИ-противника: он оценивает, что вероятнее сделает игрок, и отвечает лучшим ходом.
Подход к моделям годится и для прототипов: простая версия игры проверяет одну интуицию, потом её усложняют.

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

«Мороженщики на пляже»: двое ставят тележки на пляж из 10 клеток, покупатели идут к ближайшей. Несколько раундов: каждый может передвинуть тележку. Ученик замечает, что тележки сходятся в центр, хотя покупателям с краёв это неудобно.

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

«Доминирует» = «побеждает в лоб». Нет: это сравнение своих вариантов против одного и того же ответа соперника.
«Модель неточна, значит, бесполезна». Модель проверяет интуицию, а неточности становятся следующими вопросами.
«Нет доминируемых ходов — нечего анализировать». Есть лучший ответ на убеждения.

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

Гарольд Хотеллинг, «Stability in Competition» (1929); Энтони Даунс, «An Economic Theory of Democracy» (1957).
Рационализуемость (Бернхейм, Пирс, 1984) — удаление стратегий, которые никогда не являются лучшим ответом; лекция 4.
Задача о трёх кандидатах в модели Хотеллинга — классический пример, где равновесия может не быть.