HYBRID METHOD FOR SOLVING BI-MATRIX GAMES
Share
Metrics
HYBRID METHOD FOR SOLVING BI-MATRIX GAMES
Annotation
PII
S042473880000487-4-1
Publication type
Article
Status
Published
Authors
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 (LH-algorithm). 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 2LP-algorithm 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 LHalgorithm 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
Date of publication
01.04.2018
Number of purchasers
1
Views
51
Full text is available to subscribers only
Subscribe right now
Only article
100 RUB / 1.0 SU
Whole issue
0 RUB /  SU
All issues for
0 RUB /  SU
1

## References

### Additional sources and materials

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 (in Russian).
IBM ILOG CPLEX Optimization Studio (2011). Available at: http://www-03.ibm.com/software/products /ru/ ibmilogcpleoptistud, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).
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.
MATLAB (2012). The Language of Technical Computing. Available at: http://www.mathworks.com/products / matlab/, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).