Минимакс

Минимакс (от лат. minimus — наименьший и maximus — наибольший) — это принцип принятия решений в теории игр, статистике и исследовании операций, направленный на минимизацию максимально возможного проигрыша (или риска) в условиях неопределённости. Игрок, придерживающийся стратегии минимакса, предполагает, что его противник (или природа) действует наиболее неблагоприятным образом, и выбирает такое действие, которое даёт наилучший результат в худшем случае. В чистом виде минимаксная стратегия является консервативной и крайне осторожной, она гарантирует определённый минимальный уровень выигрыша вне зависимости от действий контрагента.

История

Корни принципа минимакса уходят в математическую теорию антагонистических игр. Первые формальные результаты были получены в 1920-х годах. В 1928 году американский математик Джон фон Нейман доказал фундаментальную теорему о минимаксе. Она гласит, что в любой конечной антагонистической игре двух лиц с нулевой суммой существует пара смешанных стратегий (вероятностное распределение на чистых стратегиях), при которых для каждого игрока его ожидаемый выигрыш (для первого игрока) и ожидаемый проигрыш (для второго) совпадают. Это значение называется ценой игры.

Фон Нейман также показал, что минимаксное значение для одного игрока в точности равно максиминному значению для другого, что делает понятия «минимакс» и «максимин» (максимизация минимального выигрыша) эквивалентными в строго определённом классе игр. Теорема стала одним из краеугольных камней теории игр и дала строгое математическое обоснование рациональному поведению в конфликтных ситуациях.

В 1940–1950-х годах идеи фон Неймана были развиты Эмилем Борелем, Оскаром Моргенштерном и Леонардом Сэвиджем. Сэвидж ввёл понятие критерия минимакса сожалений (критерий Сэвиджа) — альтернативного подхода, при котором минимизируется не сам проигрыш, а максимальная «потеря» (сожаление) от выбора неоптимального действия по сравнению с наилучшим возможным исходом в данном состоянии природы.

Математическая формулировка

В антагонистической игре двух лиц с нулевой суммой, где первый игрок (максимизатор) выбирает стратегию \( i \) из множества \( I \), а второй игрок (минимизатор) выбирает стратегию \( j \) из множества \( J \), выигрыш первого игрока задаётся функцией \( a_{ij} \) (для второго игрока выигрыш равен \( -a_{ij} \)).

• Максиминная стратегия первого игрока: выбрать такую \( i \), при которой его _гарантированный выигрыш_ максимален: \[ \max_i \min_j a_{ij} \]
• Минимаксная стратегия второго игрока: выбрать такую \( j \), при которой _максимально возможный проигрыш_ второго игрока (или выигрыш первого) минимален: \[ \min_j \max_i a_{ij} \]

В общем случае всегда выполняется неравенство: \( \max_i \min_j a_{ij} \leq \min_j \max_i a_{ij} \). Если равенство достигается, то игра имеет седловую точку, и пара минимаксных стратегий образует равновесие Нэша для чистых стратегий. Для игр без седловой точки оптимальное решение лежит в области смешанных (вероятностных) стратегий. Теорема фон Неймана гарантирует существование седловой точки для смешанного расширения любой конечной игры с нулевой суммой.

Виды и модификации

Понятие минимакса применяется в нескольких вариантах, различающихся по критерию и области использования:

• Чистый минимакс (критерий Вальда): ориентирован на наихудший сценарий. Игрок оценивает каждый из доступных исходов по его худшему значению и выбирает наилучший из худших. Является основным в теории антагонистических игр.
• Минимаксное сожаление (критерий Сэвиджа): вместо прямого выигрыша рассматривается «сожаление» — разность между максимально возможным выигрышем в данном состоянии природы и фактическим выигрышем при выбранной стратегии. Игрок минимизирует максимальное сожаление. Используется при принятии решений без учёта вероятностей состояний природы.
• Минимакс риска: в финансовой математике и статистике применяется для выбора оценок, которые минимизируют максимальное значение функции потерь (риска) при наихудшем распределении данных.
• Минимакс в машинном обучении: принцип «генеративно-состязательных сетей» (GAN), где две нейронные сети (генератор и дискриминатор) играют в минимаксную игру: генератор стремится максимизировать ошибку дискриминатора, а дискриминатор — минимизировать её.
• Адаптивный минимакс: подход в теории управления, при котором регулятор подстраивается под наихудшие параметры объекта, сохраняя устойчивость системы.

Применение

Минимаксные методы широко используются во многих дисциплинах:

• Экономика и прикладная теория игр: анализ олигополистических рынков, аукционы, страхование (оценка гарантированных доходов при неблагоприятной конъюнктуре).
• Военное дело и оборона: планирование операций, распределение ресурсов и выбор вооружения в условиях противодействия противника. Например, при расчёте противоракетной обороны минимакс позволяет оценить эффективность при наихудшем сценарии атаки.
• Статистика и проверка гипотез: минимаксные тесты и оценки параметров, сохраняющие заданный уровень ошибки при любом распределении из определённого класса.
• Искусственный интеллект: в алгоритмах для игр (шахматы, го, покер) минимакс с альфа-бета-отсечением лежит в основе перебора вариантов для выбора хода в условиях неполной информации.
• Финансовый риск-менеджмент: расчёт Value-at-Risk (VaR) и построение портфелей с гарантированным минимальным доходом при наихудшем стечении обстоятельств.
• Проектирование технических систем: в робастном управлении (H∞-оптимизация) и в проектировании надежных машин, где параметры окружающей среды или самих элементов системы могут изменяться в широких пределах.

Критика

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

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

Интересные факты

• Принцип минимакса лежит в основе знаменитой стратегии «Тише едешь — дальше будешь».
• Теорема фон Неймана о минимаксе считается первым строгим математическим результатом в теории игр и была доказана всего через год после создания самого формального аппарата этой теории.
• В 1944 году фон Нейман и Моргенштерн популяризировали минимакс в книге «Теория игр и экономическое поведение».
• В России и бывшем СССР теория игр и минимакс активно развивалась в контексте военных приложений и теории принятия решений в условиях противодействия.
• Минимаксная оценка часто оказывается состоятельной в робастных статистических процедурах, где требуется устойчивость к выбросам.

См. также

• Теория игр
• Максимин
• Седловая точка
• Равновесие Нэша
• Критерий Вальда
• Критерий Сэвиджа

Источники

• Нейман Дж. фон, Моргенштерн О. «Теория игр и экономическое поведение». М.: Наука, 1970.
• Вальд А. «Статистические решающие функции». М.: Мир, 1967.
• Сэвидж Л.Дж. «Фонды статистики» (в русском переводе: Сэвидж Л.Дж. «Теория статистических решений». М.: Наука, 1976).
• Воробьев Н.Н. «Теория игр». М.: Высшая школа, 1985.
• Математическая энциклопедия / Гл. ред. И.М. Виноградов. — М.: Советская энциклопедия, 1982.