Параллельный глобальный поиск равновесных ситуаций в биматричных играх
Васильев И.Л., Климентова К.Б., Орлов А.В.

     Рассматривается задача поиска ситуаций равновесия по Нэшу в биматричных играх. Для решения этой задачи используется вариационный подход, базирующийся на теореме эквивалентности биматричной игры и билинейной задачи математического программирования специального вида. Последняя решается с помощью алгоритма, основанного на теории глобального поиска. Для решения вспомогательных задач линейного программирования, возникающих на шагах алгоритма, используется пакет ILOG CPLEX. Кроме того, осуществлена параллелизация алгоритма глобального поиска. Проведен вычислительный эксперимент по тестированию последовательного и параллельного алгоритмов. Полученные результаты подтверждают эффективность реализованной параллелизации. Работа выполнена при поддержке РФФИ (код проекта 05-01-00110), а также гранта Президента РФ (код проекта МК-6580.2006.1).

Васильев И.Л., Климентова К.Б., Орлов А.В. - Институт динамики систем и теории управления Сибирского отделения РАН, ул. Лермонтова, 134, 664033, Иркутск;     e-mail: vil@icc.ru,   xenia.klimentova@icc.ru,   anor@icc.ru