Implementing the modified LH algorithm

摘要

The modified Lemke-Howson algorithm is a constructive procedure which enables us to compute equilibrium points of a bimatrix game. The algorithm as described by one of the authors is based on the original version invented by Lemke and Howson. However, it differs from this version with respect to several features. It works directly with the matrices defining the bimatrix game A and B. It has an easy and very direct geometrical interpretation; hence for small games we can follow the development of the algorithm geometrically. Finally, instead of being bilinear, the algorithm behaves rather like a piecewise linear program. This presentation closes a gap: although the algorithm has been described geometrically (and with a flow diagram), there has been no constructive procedure that can be implemented on a computer. This is provided by the present paper. We give all necessary proofs and computations in order to establish the following facts: There are two tableaus accompanying the proceeding of the algorithm. As the algorithm changes, moving alternatingly in the simplices of mixed strategies, so does the computational procedure alternatingly dealing with the two different tableaus. Each tableau contains six regions, depending on the various sequences of transitions the procedure has to perform. While this all is in marked difference to linear programming, there is also consolation: The well-known rectangle rule of linear programming can be modified easily (that is, there is a family of rectangle rules) so that changing the tableau alternatingly amounts to applying the appropriate rectangle rule. Thus, there is also close similarity to the familiar LP procedure. Thus, a complete description of the modified LH algorithm is provided that can immediately be implemented on any computer. In particular, we supply an APL program that, e.g., can be run on an IBM® PC.