Hybrid method for solving bi–matrix games
Table of contents
Share
Metrics
Hybrid method for solving bi–matrix games
Annotation
PII
S042473880000015-5-1
DOI
10.7868/s0424738818020073
Publication type
Article
Status
Published
Authors
Evgeny Golshtein 
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Nikolay Sokolov
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Ustav Malkov
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation, Moscow
Pages
89-103
Abstract
In order to find optimal mixed strategies of a bi-matrix game one can use the approximate algorithm for solving bi-matrix games (2LP-algorithm) and/or the Lemke–Howson algorithm (LHalgorithm). When solving a bi-matrix game the 2LP-algorithm provides finding the global minimum of the Nash function by processing (numerous) local minima of the same function. The point is that every successive (alternating) minimization of this function with respect to one of the two variables (while the other variable is fixed) can be easily reduced to a linear programming problem. By making use of a trial of the initial pure strategies and solving two linear programs at each iteration the 2LPalgorithm either establishes the game’s exact solution (if a complementarity slackness condition holds) or finds an approximation to the set of Nash points (when the complementarity slackness condition is slightly broken). The algorithm is very easy to implement, however, it loses its efficiency whenever the payoff matrices are scarce and/or (mutually) linearly dependent on each other. On the contrary, the LH-algorithm reduces the bi-matrix game to the solution of a related linear equations system. Starting from the basis of the unit vectors, the method makes simplex-type steps aiming to decrease the number of broken complementarity slackness conditions. As a rule (but not always) the algorithms finds the exact solution of the game. The proposed hybrid method uses the LH-algorithm to re-optimize an approximate solution produced by the 2LP-algorithm starting with the basis of the latter. The efficiency of the Lemke–Howson algorithm and the proposed hybrid approach has proved to be about the same. Moreover, the hybrid method has managed to find exact solutions to several test games for which both the 2LP- and LH-procedures failed.
Keywords
bi-matrix games, convex structures, pure strategies, mixed strategies, Nash points, Nash function, complementarity slackness condition, Lemke-Howson algorithm, hybrid method
Received
09.10.2017
Date of publication
29.06.2018
Number of purchasers
6
Views
641
Readers community rating
0.0 (0 votes)
Cite Download pdf 1 RUB / 0.0 SU

To download PDF you should sign in

1 123

References

1. Golshtein E. G., Malkov U. H., Sokolov N. A. (2013). A Numerical Method for Solving Bimatrix Games. Economics and Mathematical Methods, 49, 4, 94–104.

2. IBM ILOG CPLEX Optimization Studio (2011). Available at: http://www‑03.ibm.com/software/products /ru/ ibmilogcpleoptistud, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).

3. Lemke C. E., Howson J. T. Jr. (1964). Equilibrium Points of Bimatrix Games. Journal of the Society for Industrial and Applied Mathematics, 12, 778–780.

4. MATLAB (2012). The Language of Technical Computing. Available at: http://www.mathworks.com/products / matlab/, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).