Georgia Institute of Technology College of Sciences

It is well known that many optimization problems, ranging from linear programming to hard combinatorial problems, as well as many engineering and economics problems, can be formulated as linear complementarity problems (LCP). One particular problem, finding a Nash equilibrium of a bimatrix game (2 NASH), which can be formulated as LCP, motivated the elegant Lemke algorithm to solve LCPs. While the algorithm always terminates, it can generates either a solution or a so-called ‘secondary ray’. We say that the algorithm resolves a given LCP if a secondary ray can be used to certify, in polynomial time, that no solution exists. It turned out that in general, Lemke-resolvable LCPs belong to the complexity class PPAD and that, quite surprisingly, 2 NASH is PPAD-complete. Thus, Lemke-resolvable LCPs can be formulated as 2 NASH. However, the known formulation (which is designed for any PPAD problem) is very complicated, difficult to implement, and not readily available for potential insights. In this talk, I’ll present and discuss a simple reduction of Lemke-resolvable LCPs to bimatrix games that is easy to implement and have the potential to gain additional insights to problems (including several models of market equilibrium) for which the reduction is applicable.