Искусство побеждать: Теория игр с нулевой суммой 0:11
В лекции 14 курса MIT OpenCourseWare рассматривается концепция игр с нулевой суммой — фундаментальной модели в теории игр, где выигрыш одного участника в точности равен проигрышу другого. Ведущий объясняет, как с помощью линейного программирования можно анализировать стратегии в таких играх, доказывает существование равновесия Нэша и демонстрирует знаменитую теорему фон Неймана о минимаксе.
🎲 Основы игр с нулевой суммой 0:11
Игра с нулевой суммой — это математическая абстракция, которая описывает взаимодействие двух сторон: «игрока строки» (часто называемого Алисой) и «игрока столбца» (Боба). Основные компоненты такой игры:
- Стратегии: У Алисы есть $M$ доступных стратегий, у Боба — $N$.
- Матрица выигрышей (C): Матрица размером $M \times N$, где элемент $C_{ij}$ определяет чистую выплату от Боба к Алисе при выборе ими стратегий $i$ и $j$.
- Принцип суммы: Если сложить все выигрыши и проигрыши Алисы и Боба, итоговая сумма всегда будет равна нулю.
В качестве простого примера приводится игра «Matching Pennies» (совпадающие монетки). Алиса и Боб одновременно выбирают «Орла» (H) или «Решку» (T). Если монеты совпадают, Алиса получает $1 от Боба; если нет — Алиса платит $1 Бобу. В этой симметричной игре ни у одного игрока нет преимущества, так как в долгосрочной перспективе они выигрывают и проигрывают поровну.
♟️ Что значит «решить» игру? 14:06
Ведущий выделяет два основных понятия равновесия, которые помогают определить оптимальный способ поведения участников.
Чистое равновесие Нэша 14:33
Это состояние, при котором пара стратегий $(i, j)$ такова, что ни у одного игрока нет стимула отклоняться от выбранного курса, если другой игрок не меняет свою стратегию. Математически, для игрока строки это означает, что выбранная стратегия $i$ максимизирует его доход при фиксированном $j$.
Однако, по словам лектора, многие игры, включая «Matching Pennies», не имеют чистого равновесия Нэша, так как всегда найдется сторона, желающая изменить ход для получения выгоды.
Смешанное равновесие Нэша 21:06
Чтобы преодолеть недостатки детерминированных стратегий, вводится понятие смешанного равновесия, где игроки выбирают свои действия случайным образом согласно заданному распределению вероятностей. В данном случае Алиса выбирает вектор вероятностей $X$, а Боб — $Y$, такие что никто не может увеличить свой ожидаемый выигрыш путем изменения стратегии.
📉 Теорема фон Неймана о минимаксе 33:57
Теорема о минимаксе — это один из ключевых результатов теории игр, доказанный Джоном фон Нейманом. Она утверждает, что при смешанных стратегиях результат игры не зависит от того, кто из игроков «объявляет» свою стратегию первым.
Математически это выражается через равенство максимина и минимакса:
$$\max_{X} \min_{Y} X^T C Y = \min_{Y} \max_{X} X^T C Y = \lambda^*$$
где $\lambda^*$ — значение игры. По мнению автора, эта теорема глубока тем, что она доказывает: для любой игры с нулевой суммой существует смешанное равновесие Нэша, гарантирующее оптимальный результат для обоих рациональных игроков.
🛠️ Практическое применение и линейное программирование 1:03:18
В завершение лекции преподаватель показывает, как использовать полученные знания на примере игры с матрицей $3 \times 3$.
- Поиск стратегии: С помощью инструментов линейного программирования было определено, что «ценность игры» ($\lambda^*$) составляет $1/3$ доллара, что дает преимущество игроку строки.
- Слабая двойственность: Теорема о минимаксе тесно связана с теорией линейного программирования, где решение одной задачи (максимизация выигрыша) служит «сертификатом» для другой (минимизация потерь).
- Случай из практики: Автор лекции поделился историей из своей PhD-диссертации, где он доказал существование сложных объектов в теории графов, переведя задачу в формат игры с нулевой суммой против своего научного руководителя. По его словам, такие методы незаменимы для решения задач в комбинаторной оптимизации, которые кажутся интуитивно невозможными.
