🧠 Введение в теорию игр: представления и стратегии 4:15
Лекция Йена Болла из курса MIT OpenCourseWare посвящена переходу от анализа принятия решений одним человеком к интерактивному взаимодействию, где выбор каждого игрока зависит от действий других участников. Основная цель занятия — детально рассмотреть способы моделирования игр в «экстенсивной» (дерево решений) и «стратегической» (нормальной) формах, а также фундаментальное понятие стратегии как полного плана действий.
🌳 Игры в экстенсивной форме 4:31
Экстенсивная форма игры представляет собой подробную «карту» всех возможных путей развития событий. Для её описания используется структура «корневого дерева» (rooted tree), где каждый узел представляет историю игры, а пути от корня отражают последовательность решений.
Основные элементы, определяющие игру (аббревиатура PAPI):
- Игроки (Players): Стратегические агенты, принимающие решения, а также «Природа» (Nature), которая моделирует случайные события.
- Действия (Actions/Moves): Варианты выбора, доступные игрокам в конкретных точках.
- Результаты/Платёжи (Payoffs/Utilities): Отражают полезность (по шкале фон Неймана-Моргенштерна) для каждого игрока при достижении терминальных узлов.
- Информация (Information sets): Моделирует осведомленность игроков о том, что происходило ранее.
🤝 Конфликт и координация: пример игры BoS 10:36
Преподаватель разобрал классическую игру под названием «Битва полов» (Battle of the Sexes, BoS), предложив нейтральное название — «Бостонская игра». В ней два друга должны выбрать мероприятие (баскетбол или бейсбол), чтобы провести время вместе.
Основные характеристики:
- Координация: Игроки получают полезность только в том случае, если выбирают одно и то же событие.
- Конфликт: У каждого игрока есть предпочтение: один хочет баскетбол, другой — бейсбол.
- Наблюдаемость: Если один игрок делает ход первым и его выбор наблюдается, он получает стратегическое преимущество — возможность «диктует» место встречи, так как второму игроку выгоднее подстроиться, чем остаться в одиночестве.
При одновременном выборе (или отсутствии информации о первом ходе) экстенсивная форма визуализируется с помощью пунктирной линии между узлами, объединяющей их в одно информационное множество.
ℹ️ Информационные множества и стратегии 30:10
Информационные множества позволяют точно моделировать, что игрок знает в момент принятия решения. Если несколько узлов объединены в одно множество, игрок понимает, что находится в одном из них, но не знает точно, в каком именно.
Для корректного математического описания игры наложены два строгих условия:
- Согласованность действий: Игрок должен иметь одинаковый набор допустимых действий во всех узлах одного информационного множества.
- Инициализация: Корневой узел всегда должен быть единственным в своем информационном множестве (игрок должен знать, что игра началась).
♟️ Что такое стратегия? 44:36
Йен Болл подчеркивает: стратегия — это полный и условный (контингентный) план действий. Игрок обязан заранее расписать свой выбор для каждого возможного информационного множества, где он может оказаться, даже если вероятность попадания туда кажется низкой.
📊 Переход к стратегической форме 50:10
Стратегическая форма — это сокращенная запись, фокусирующаяся на стратегических компонентах игры, а не на её подробной временной структуре.
Основные шаги преобразования:
- Определение набора стратегий ($S_i$): Создание всех возможных комбинаций действий для каждого игрока.
- Расчет ожидаемой полезности: Поскольку профиль стратегий (набор планов всех игроков) определяет лотерею над терминальными узлами, необходимо вычислить ожидаемый результат для каждой комбинации.
Преподаватель отмечает, что даже для простых игр количество стратегий растет экспоненциально, что делает анализ сложных систем (например, шахмат) невозможным простым перебором.
