A generalization of the linear complementarity problem

AbstractThe linear complementarity problem: find z∈Rp satisfying w=q+Mzw⩾0,z⩾0(LCP)zTw=0 is generalized to a problem in which the matrix M is not square. A solution technique similar to C. E. Lemke's (1965) method for solving (LCP) is given. The method is discussed from a graph-theoretic viewpoint and closely parallels a proof of Sperner's lemma by D. I. A. Cohen (1967) and some work of H. Scarf (1967) on approximating fixed points of a continuous mapping of a simplex into itself