Алгоритм Лемке-Хаусона: комбинаторный поиск равновесия Нэша в биматричных играх

Математическая основа алгоритма Лемке-Хаусона базируется на сведении задачи поиска равновесия Нэша к Линейной задаче дополнительности (Linear Complementarity Problem, LCP). В биматричной игре каждый игрок стремится максимизировать свой ожидаемый выигрыш. Условие оптимальности (дополнительности) гласит: если игрок включает определенную чистую стратегию в свой смешанный профиль (назначает ей вероятность строго больше нуля), то эта стратегия обязана приносить ему максимально возможный ожидаемый выигрыш при данных действиях оппонента. Все субоптимальные стратегии должны выбираться с вероятностью, строго равной нулю.

Алгоритм Лемке-Хаусона решает эту задачу с помощью геометрического метода, поразительно похожего на симплекс-метод линейного программирования. Пространство допустимых стратегий обоих игроков представляется в виде двух выпуклых многогранников (политопов). Алгоритм стартует из искусственной (полностью дополняющей, но не являющейся равновесием) вершины — точки, где вероятности всех действий равны нулю. Затем алгоритм начинает движение (pivoting) по ребрам этих многогранников, поочередно ослабляя одно ограничение и двигаясь вдоль ребра до тех пор, пока не упрется в новую грань, восстанавливая условие дополнительности.

Удивительной топологической особенностью алгоритма является так называемый аргумент четности (Parity Argument). Граф, по которому движется алгоритм Лемке-Хаусона, состоит из вершин и ребер таким образом, что каждая вершина имеет степень не больше двух (это набор путей и циклов). Поскольку стартовая искусственная точка является одним концом пути, этот путь обязан математически завершиться в другой вершине (другом конце). Эта конечная точка пути строго гарантированно является истинным равновесием Нэша. Более того, алгоритм доказывает, что количество равновесий Нэша (если они не вырождены) в любой биматричной игре всегда является нечетным числом!

Несмотря на свою математическую красоту, в худшем случае алгоритм Лемке-Хаусона требует экспоненциального времени работы. Современная теория сложности вычислений (работы Христоса Пападимитриу) доказала, что задача поиска равновесия Нэша относится к классу $PPAD$-полных задач. Это означает, что не существует быстрых (полиномиальных) алгоритмов для ее решения в общем виде, если только $P = NP$. Тем не менее, алгоритм Лемке-Хаусона остается золотым отраслевым стандартом и применяется в алгоритмической теории игр для анализа аукционов, политических выборов и рыночных дуополий, доказывая, что поиск компромисса — это алгебраическое движение по граням многомерных политопов.