Orientation in Complementary Pivot Algorithms

Abstract

Shapley introduced an index theory for bimatrix games that oriented the paths generated by the Lemke-Howson algorithm and thus partitioned equilibrium points into two sets. Here we develop a similar orientation theory for a generalized complementary pivot algorithm and apply our results to bimatrix games, the linear complementarity problem, and fixed point algorithms. We provide the weakest known general sufficiency conditions (based on those of Garcia) for Lemke's algorithm to process the linear complementarity problem. We also show that if the linear complementarity version of a quadratic programming problem is solved and gives a Kuhn-Tucker solution, then the hessian of the objective function restricted to the subspace of active constraints has positive determinant. Finally we show that fixed point algorithms will only approximate fixed points of f at which the determinant of the Jacobian of f minus the identity has the appropriate sign.