S042473880000015-5-1

Article

Published

Volume 54 Issue 2

89-103

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.

09.10.2017

29.06.2018

14

2063