A parallel search of equilibrium points in bimatrix games

Authors

  • I.L. Vasilyev
  • K.B. Klimentova
  • A.V. Orlov

Keywords:

биматричные игры
равновесие по Нэшу
локальный поиск
глобальный поиск
параллельные вычисления
математическое программирование

Abstract

The paper is focused on a search for the Nash equilibrium in bimatrix games. In order to solve this problem, we apply the so-called variational approach based on the equivalence theorem of bimatrix games and on a special bilinear programming problem. This bilinear problem is solved using the global search theory. We use the ILOG CIPLEX package to solve auxiliary linear programming problems arising at various stages of the global search algorithm. In addition, a parallel version of this algorithm has been developed. Both the parallel and sequential algorithms have been extensively tested. Our numerical results confirm the efficiency of the implemented parallel version of the algorithm.

New computational technologies

Downloads

Published

2007-06-25

Issue

Vol. 8 (2007): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biographies

I.L. Vasilyev

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)

K.B. Klimentova

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)

A.V. Orlov

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)

References

  1. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.
  2. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1993.
  3. Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005.
  4. Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003.
  5. Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М.: Физматлит, 2007 (в печати).
  6. Mills H. Equilibrium points in finite games // J. of the Society for Industrial and Applied Mathematics. 1960. 8, N 2. 397-402.
  7. Орлов А.В., Стрекаловский А.С. О численном поиске ситуаций равновесия в биматричных играх // Журн. вычисл. матем. и матем. физики. 2005. 45, № 6. 983-997.
  8. Strekalovsky A.S., Orlov A.V. A new approach to nonconvex optimization // Вычислительные методы и программирование. 2007. 8, № 2. Раздел 1. 160-176 (https://num-meth.rcc.msu.ru/).
  9. 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.
  10. CPLEX user’s manual. ILOG, Inc. Version 9.1. 2005 (www.ilog.com).
  11. Installation and User’s Guide to MPICH. Argonne National Laboratory, Univ. of Chicago. Argonne, 2003.
  12. MPI standard 1.1. Univ. of Tennessee. Knoxville, 1995.
  13. Gropp W., Lusk E., Skjellum A. Using MPI: portable parallel programming with the message-passing interface. Boston: MIT Press, 1999.
  14. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.