Groupe d’études et de recherche en analyse des décisions

Geometric Views of Linear Complementarity Algorithms and their Complexity

Bernhard Von Stengel

The linear complementarity problem (LCP) generalizes linear programming (via the complementary slackness conditions of a pair of optimal primal and dual solutions) and finding Nash equilibria of bimatrix games. It suffices to look only for symmetric equilibria of symmetric games, which simplifies the problem setup. A famous open problem is the computational complexity of finding one equilibrium. The classical Lemke-Howson algorithm finds an equilibrium, but has exponential worst-case complexity. A related method is Lemke's algorithm for solving an LCP. Applied to linear programming, it gives the self-dual parametric simplex algorithm, which has been shown to have polynomial expected running time using a geometric description of "complementary cones".

We review two main geometric views of the algorithms by Lemke-Howson and Lemke: the polyhedral view, which describes the nonnegativity (feasilibity) constraints, and the "complementary cones" view, which maintains complementarity. Using complementary cones, Lemke's algorithm is seen as inverting a piecewise linear map along a line segment. One new result is that the underlying "LCP map" is surjective for the equilibrium problem (requiring only that the LCP matrix is positive), so the algorithm can be started anywhere. A second result shows that the Lemke-Howson algorithm is a special case of this description, giving it a unified view with Lemke's algorithm.