A parallel search of equilibrium points in bimatrix games

Authors

  • 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)

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.

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.
New computational technologies

Downloads

Published

25-06-2007

How to Cite

Васильев И., Климентова К., Орлов А. A Parallel Search of Equilibrium Points in Bimatrix Games // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2007. 8. 233-243

Issue

Vol. 8 (2007): Issue 3.

Section

Section 1. Numerical methods and applications