Параллельный глобальный поиск равновесных ситуаций в биматричных играх
Ключевые слова:
Аннотация
Рассматривается задача поиска ситуаций равновесия по Нэшу в биматричных играх. Для решения этой задачи используется вариационный подход, базирующийся на теореме эквивалентности биматричной игры и билинейной задачи математического программирования специального вида. Последняя решается с помощью алгоритма, основанного на теории глобального поиска. Для решения вспомогательных задач линейного программирования, возникающих на шагах алгоритма, используется пакет ILOG CPLEX. Кроме того, осуществлена параллелизация алгоритма глобального поиска. Проведен вычислительный эксперимент по тестированию последовательного и параллельного алгоритмов. Полученные результаты подтверждают эффективность реализованной параллелизации. Работа выполнена при поддержке РФФИ (код проекта 05-01-00110), а также гранта Президента РФ (код проекта МК-6580.2006.1).
Загрузки
Опубликован
Выпуск
Раздел
Библиографические ссылки
- Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.
- Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1993.
- Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005.
- Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003.
- Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М.: Физматлит, 2007 (в печати).
- Mills H. Equilibrium points in finite games // J. of the Society for Industrial and Applied Mathematics. 1960. 8, N 2. 397-402.
- Орлов А.В., Стрекаловский А.С. О численном поиске ситуаций равновесия в биматричных играх // Журн. вычисл. матем. и матем. физики. 2005. 45, № 6. 983-997.
- Strekalovsky A.S., Orlov A.V. A new approach to nonconvex optimization // Вычислительные методы и программирование. 2007. 8, № 2. Раздел 1. 160-176 (https://num-meth.rcc.msu.ru/).
- Hiriart-Urruty J.-B. Generalized differentiability, duality and optimization for problems dealing with difference of convex functions // Lecture Notes in Economics and Mathematical Systems. Vol. 256. Berlin: Springer-Verlag, 1985. 37-69.
- CPLEX user’s manual. ILOG, Inc. Version 9.1. 2005 (www.ilog.com).
- Installation and User’s Guide to MPICH. Argonne National Laboratory, Univ. of Chicago. Argonne, 2003.
- MPI standard 1.1. Univ. of Tennessee. Knoxville, 1995.
- Gropp W., Lusk E., Skjellum A. Using MPI: portable parallel programming with the message-passing interface. Boston: MIT Press, 1999.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.
