Prof Bernhard von Stengel
Department of Mathematics
London School of Economics

Geometric Views of Linear Complementarity Algorithms and
Their Complexity

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.

(Joint work with Rahul Savani.)