Локальный поиск в билинейной игре двух лиц

Рассматривается подход, позволяющий с помощью функции Никайдо-Исода свести задачу поиска равновесия по Нэшу к минимаксной задаче для достаточно широкого класса игр. При этом минимаксная задача может быть записана как задача оптимизации с, вообще говоря, невыпуклой и неявно заданной целевой функцией. Таким образом, множество равновесий по Нэшу исходной игры совпадает с множеством глобальных решений полученной задачи оптимизации. Для билинейной игры двух лиц с квадратичными функциями потерь и независимыми множествами стратегий делается предположение о строгой выпуклости функций потерь по собственным переменным игроков, и затем в минимаксной задаче «внутренняя» экстремальная выпуклая задача заменяется двойственной по Лагранжу задачей. Таким образом, целевая функция представляется в виде разности двух выпуклых функций (d.c-разложение целевой функции), одна из которых, образующая вогнутую часть, по-прежнему задана неявно. Предлагается способ линеаризации вогнутого слагаемого и, на основе этого, применение известного итеративного метода локального поиска для d.c-функций. В данном методе локального поиска очередная точка выбирается как решение выпуклой задачи оптимизации, в которой целевая функция получается из исходной целевой функции путём линеаризации вогнутого слагаемого в d.c-разложении. В силу невыпуклости рассматриваемой нами задачи, предлагается использовать локальный поиск в сочетании с мультистартом. В завершение представлены результаты численного эксперимента.