Новый алгоритм находит равновесие Нэша в 5600 играх с точностью 1e-5

Вычисление равновесия Нэша в играх с общей суммой давно считается одной из неудобных задач на стыке теории игр и машинного обучения. Универсальных алгоритмов с глобальной гарантией сходимости почти нет. Хунбо Сун в статье arXiv:2609.16158 предлагает метод, который закрывает значительную часть этого пробела: алгоритм решает произвольные игры m игроков с n действиями с любой заданной точностью и наследует глобальную линейную сходимость. На 5600 случайно сгенерированных экземплярах зазор упал ниже 1e-5 во всех случаях.

От одного симплекса к произведению симплексов

Основа работы — фреймворк следования по пути на расслоениях (fiber bundle), описанный в предыдущей статье автора arXiv:2606.00778. Он решал конечномерные вариационные неравенства на симплексе: множестве вероятностных распределений по набору вариантов. Для игр этого мало. В игре с несколькими участниками у каждого игрока своё распределение по действиям, и допустимая область превращается в произведение симплексов.

Прямолинейный путь — заново доказывать все свойства сходимости для новой области. Сун выбрал другой. Он строит эквивалентное вариационное неравенство на одном симплексе и устанавливает изоморфизм расслоений между двумя фреймворками. Затем добавляет аргумент о продолжении сечений (slice-extension), который переносит все гарантии из исходной работы. Новой теории сходимости не нужно, потому что старая действует через геометрическую эквивалентность.

Получившийся объект — составное расслоение. По словам автора, оно позволяет делать прыжки вдоль слоёв в обход особых точек. Именно вокруг них обычные гарантии методов следования по пути перестают работать.

Что именно гарантирует метод

Глобальная линейная сходимость здесь имеет две формы, и различие принципиально:

• для неособых равновесий решение находится точно;
• для особых равновесий достигается любая заранее заданная точность.

Такое разделение честно отражает природу задачи. Вырожденные случаи в общих играх встречаются, и многие численные методы в них теряют устойчивость или зацикливаются. Здесь же прыжки по слоям должны удерживать траекторию от особых точек.

Тест на 5600 играх

Экспериментальная часть строится на сравнении крайних конфигураций. Размерности охватывают диапазон от игры на двух участников со 128 действиями у каждого до игры на 128 участников с двумя действиями. Эти режимы устроены по-разному:

• 2 игрока × 128 действий: небольшое число участников, широкое пространство стратегий;
• 128 игроков × 2 действия: огромное число участников с бинарным выбором, где общее число комбинаций действий растёт экспоненциально;
• промежуточные конфигурации между этими полюсами;
• всего 5600 случайных экземпляров, критерий успеха — зазор ниже 1e-5.

Алгоритм достиг этого порога в каждом случае. Из заявленных результатов следует, что отказов, зацикливаний и неудачных запусков в серии не было. Для случайных игр это сильный сигнал, хотя случайные экземпляры не заменяют структурированные задачи вроде покерных абстракций или рыночных механизмов.

Зачем это инженерам ИИ

Равновесие Нэша лежит в основе мультиагентного обучения, самоигры, состязательных постановок вроде GAN, аукционных механизмов и анализа взаимодействия автономных агентов. Если агентов много и их цели расходятся, вопрос «где система остановится» превращается в задачу о равновесии. Сегодня на практике чаще применяют динамики обучения, которые сходятся не всегда. Метод с глобальной гарантией даёт альтернативу: решатель, который можно использовать как эталон при проверке эвристик.

Практическая сторона проста. Код и данные выложены в репозитории FiberBundle_VI на GitHub, так что результаты можно воспроизвести и прогнать на собственных играх. Первое, что стоит проверить командам, работающим с мультиагентными системами, — как метод ведёт себя на структурированных играх и насколько масштабируется по времени при росте числа игроков. Для исследователей теории игр работа интересна и сама по себе: приём с изоморфизмом расслоений показывает, как переносить гарантии между областями, не переписывая доказательства.

Статья набрала пока скромные два голоса на Hugging Face Daily Papers, но тема из тех, что редко попадают в заголовки и регулярно решают, будет ли мультиагентная система вести себя предсказуемо.