Теория игр и математическое программирование: вычисление равновесия Нэша
Взаимосвязь между теорией игр и математическим программированием представляет собой один из самых плодотворных симбиозов в современной прикладной математике. Еще на заре развития этих дисциплин Джон фон Нейман доказал, что любая конечная антагонистическая игра двух лиц с нулевой суммой может быть сформулирована и решена как пара двойственных задач линейного программирования. Сегодня методы оптимизации являются основным вычислительным инструментом для нахождения равновесий Нэша в сложных стратегических взаимодействиях.
Фундаментальная теорема минимакса фон Неймана постулирует, что в играх с нулевой суммой существует смешанная стратегия, при которой ожидаемый выигрыш одного игрока в точности равен ожидаемому проигрышу другого. Для поиска этой оптимальной смешанной стратегии (вектора вероятностей выбора чистых стратегий) строится задача линейного программирования. Переменными выступают вероятности выбора стратегий, а целевой функцией — максимизация гарантированного выигрыша при наихудшем ответе оппонента (максимин). Двойственная к ней задача в точности описывает стратегию второго игрока, пытающегося минимизировать свой максимальный проигрыш (минимакс). Равенство оптимумов прямой и двойственной задач идеально математически воплощает саму суть равновесия, позволяя использовать симплекс-метод для мгновенного нахождения решения.
Для биматричных игр (игр двух лиц с ненулевой суммой) ситуация алгоритмически усложняется. Нахождение равновесия Нэша в таких играх больше не сводится к простому линейному программированию. Задача формулируется как линейная задача дополнительности (Linear Complementarity Problem, LCP). Классическим алгоритмом ее решения является алгоритм Лемке-Хаусона, который геометрически представляет собой поиск пути по ребрам многогранников, образованных пространствами стратегий обоих игроков. Метод гарантированно находит хотя бы одно равновесие Нэша за конечное число шагов, хотя в худшем случае имеет экспоненциальную временную сложность, что было доказано в рамках исследований класса сложности PPAD.
В играх с множеством участников (n-лиц) поиск равновесия сводится к решению сложных нелинейных уравнений или задач вариационных неравенств. Развитие алгоритмической теории игр показало, что вычисление равновесия Нэша для произвольной игры является вычислительно трудной задачей. Поэтому на практике применяются методы приближенной оптимизации, итеративного фиктивного разыгрывания (Fictitious Play) и алгоритмы минимизации сожалений (Regret Matching). Эти методы позволяют находить $\epsilon$-равновесия в гигантских играх, таких как покер или экономические аукционы, где пространство состояний немыслимо велико.
Особый интерес представляет дизайн механизмов (Mechanism Design) — "обратная теория игр". Здесь математическое программирование используется для проектирования правил игры (например, форматов аукционов) таким образом, чтобы эгоистичные рациональные агенты, стремясь максимизировать свою выгоду, невольно достигали глобального оптимума, заданного создателем системы. Это требует решения задач целочисленного и нелинейного программирования с ограничениями на стимулирующую совместимость (Incentive Compatibility), что является фундаментом современной экономики интернет-рекламы и рынков распределения ресурсов.
Список литературы:
1. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. — М.: Наука, 1970.
2. Данилов В.И. Лекции по теории игр. — М.: РЭШ, 2002.
3. Нисан Н., Рафгарден Т., Тардош Е., Вазирани В. Алгоритмическая теория игр. — Cambridge University Press, 2007 (рус. перевод).