Linear Complementarity Problem

Linear Complementarity Problem (LCP) is a generalization of Linear Programming and a special case of quadratic programming. I stumbled upon LCP theory due to my interest in complexity problems in game theory and PPAD-completeness. As we will see these concepts are very closely related.

Let M be a n \times n square matrix and q an n dimensional vector. Let LCP(q,M) be the following problem : Find two vectors w and z satisfying

LCP

LCP(q,M) consists of linear constraints and complementary conditions. Since w{\geq}0, z{\geq}0 the complementary conditions {w_i}{z_i}=0 is equivalent to {w^T}{z}=0. There is an obvious exponential time algorithm to solve LCP. For every i, set either w_i=0 or z_i=0 and solve the resulting system of linear equations. If one of these linear systems has a solution then the corresponding LCP is solvable. Deciding if a given LCP has a solution is NP-complete. The following exercise shows that LCP is a generalization of LP.

Exercise : Every LP can solved by solving a corresponding LCP, representing the complementary slackness of the LP.

LCP can also be expressed in the following equivalent form :

LCPobj

Lemke’s algorithm is a “path-following” algorithm (similar to simplex algorithm) to solve LCP. Unfortunately, Lemke’s algorithm can sometimes fail to produce a solution even if one exists !! There are many special instances of LCP on which Lemke’s algorithm always produces a solution or a certificate that no solution exists.

As mentioned earlier, solving an LCP is NP-complete. What about special cases ? i.e., when the input matrix M is special.

  • If M is a Positive Semi-Definite matrix, then LCP(q,M) can be solved in polynomial time. In fact, every LCP with a PSD matrix is a convex quadratic program and every convex quadratic program can be expressed as an LCP with a PSD matrix.
  • If M is a Z-matrix, Chandrasekaran’s algorithm solves LCP(q,M) in polynomial time [Chandrasekaran’70].
  • If M is a triangular P-matrix, LCP(q,M) can be solved in polynomial time by using a back substitution method.
  • If M is a P-matrix, LCP(q,M) has a unique solution for every q.

Following is one of the coolest applications of LCP.

Exercise : Finding a Nash Equilibrium in a bimatrix game can be expressed as an LCP.

Lemke-Howson’s algorithm [Lemke,Howson’64] to solve a bimatrix game is known to take exponential number of steps in the worst case [Savani, vonStengel’04]. It is also known that finding Nash equilibrium in a bimatrix game is PPAD-complete [Chen,Deng’09].

Open Problems :

  • The complexity of solving LCP with a P-matrix (P-LCP) is open for more than two decades !! P-LCP is known to be in PPAD [Papadimitriou’94]. Note that recognizing Z-matrices and PSD-matrices can be done in polynomial-time but recognizing P-matrices is coNP-complete [Coxson’94].
  • Are there other interesting classes of matrices M for which LCP(q,M) is solvable in polynomial time ?
  • Savani and von Stengel’s instance of bimatrix game has “full support mixed equilibrium”, which can easily solved using linear programming techniques. It is an open problem to construct an instance of a bimatrix game that does not have full-support mixed equilibrium and the Lemke-Howson algorithm takes exponential number of steps on this instance.
    Savani and von Stengel’s instance of bimatrix game has full support.
    It is open problem to construct an instance of bimatrix game that
    does not have full-support mixed equilibrium and the Lemke-Howson algorithm
    takes exponential number of steps.

References :

  • [Chandrasekaran’70] R. Chandrasekaran. “A Special Case of the Complementary Pivot Problem“, Opsearch, 7(1970) 263 268.
  • [Coxson’94] G. E. Coxson. The P-matrix problem is co-NP-complete. Math. Programming, 64(2):173–178, 1994.
  • [Chen,Deng’09] Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)
  • [Savani, vonStengel’04] Rahul Savani, Bernhard von Stengel: Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. FOCS 2004: 258-267
  • [Lemke,Howson’64] Lemke, C. E. and J. T. Howson, Jr. (1964), Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 413–423.
  • [Papadimitriou’94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)
Advertisements

Scarf’s Lemma

Proof and Applications of Scarf’s Lemma…….

Today’s post is about Scarf’s Lemma, my recent obsession. I learnt about Scarf’s Lemma while reading Haxell & Wilfong’s paper [HW’08] on Fractional Stable Paths Problem (FSPP). I will write about FSPP in a future post. Today’s post is about the elegant proof of Scarf’s Lemma and its wonderful applications.

Scarf’s Lemma : Let m < n and let B be an m \times n real matrix such that b_{ij} = \delta_{ij} for 1 \leqslant i, j \leqslant m. Let b be a non-negative vector in {\mathbb{R}}^m,  such that the set \{\alpha\in{\mathbb{R}}_{+}^n : B{\alpha}=b\} is bounded. Let C be an m \times n matrix such that c_{ii} \leqslant c_{ik} \leqslant c_{ij} whenever i,j \leqslant m, i \neq j and k > m. Then there exists a subset J of size m of [n] such that

  • (feasible) : B{\alpha}=b for some \alpha\in{\mathbb{R}}_{+}^n such that \alpha_j=0 whenever j\notin{J}.
  • (subordinating) : For every k \in [n] there exists i \in [m] such that c_{ik} \leqslant c_{ij} for all j \in J.

Proof of Scarf’s Lemma :

We want an \alpha\in{\mathbb{R}}_{+}^n which is simultaneously feasible for B and subordinating for C. Note that it is easy to find a feasible x and a subordinating y that are “almost same”. Choose x = [m]. Choose y = (2,3,....,m,j) where j is selected from all of the columns k > n so as to maximize c_{1k}. Now x and y have m-1 columns in common. To find the required \alpha we shall apply the following (feasible and ordinal) pivot steps. Throughout we shall maintain this relationship of having at least m-1 common columns. This elegant and powerful idea was first introduced in the Lemke-Howson Algorithm. I will talk about Lemke-Howson algorithm it in a future post.

Assuming non-degeneracy for matrices B and C the following lemmas hold. (C is said to be non-degenerate if no two elements in the same row are equal).

(i) Feasible Pivot Step : Let J be a feasible basis for (B, b), and k\in[n]\setminus{J}. Then there exists a unique j \in J such that J+k-j (i.e., J\cup\{k\}{\setminus}\{j\}) is a feasible basis.

(ii) Ordinal Pivot Step : Let K be a subordinating set for C of size m-1. Then there are precisely two elements j \in [n]{\setminus}K such that K+j is subordinating for C, unless K\subseteq[m], in which case there exists precisely one such j.

Proof of (i) is well-known. For Proof of (ii), refer to [Schrijver’s Book]. To prove Scarf’s lemma we construct a bipartite graph \mathcal{G} with partitions A (the set of all feasible bases containing 1) and B (the set of all subordinating sets of size m not containing 1. A vertex a \in A is joined to a vertex b \in B if a\setminus b = \{1\}.

Exercise : Prove that every node (except [m] and the required solution \alpha) in \mathcal{G} have degree two.

Since [m] is not subordinating, the required solution \alpha which is both feasible and subordinating must exist. Note that this proof gives a PPA membership of the computational version of Scarf’s lemma. For PPAD-membership and PPAD-completeness of Scarf’s lemma and its applications (mentioned below) see [KPRST’09].

Applications of Scarf’s Lemma :

Scarf’s lemma provides an elegant proof for a number of “fractional stability type” problems. Here is the list, starting with Scarf’s original paper that introduced the Scarf’s lemma.

Theorem (Scarf’67) : Every balanced game with non-transferable utilities has a non-empty core.

Theorem (AH’98) : Every clique-acyclic digraph has a strong fractional kernel.

Theorem (AF’03) : Every hypergraphic preference system has a fractional stable solution.

Theorem (HW’08) : Every instance of Stable Paths Problem has a fractional stable solution.

Open Problems : Are there other unexplored applications of Scarf’s lemma ? It is known [Scarf’67] that Scarf’s lemma provides a combinatorial proof of Brower’s fixed point theorem. Can we use Scarf’s lemma to prove other fixed-point theorems, for example, geometric stability theorems from topology. The above mentioned applications are all PPAD-complete [KPRST’09]. Are there interesting applications of Scarf’s lemma that are polynomial time solvable ?

References :

  • [Scarf’67] Herbert E. Scarf : The Core of an N Person Game. Econometrica, Vol 69, 35-50 (1967)
  • [AH’98] Ron Aharoni, Ron Holzman : Fractional Kernels in Digraphs. J. Comb. Theory, Ser. B 73(1): 1-6 (1998)
  • [AF’03] Ron Aharoni, Tamás Fleiner : On a lemma of Scarf. J. Comb. Theory, Ser. B 87(1): 72-80 (2003)
  • [HW’08] Penny E. Haxell, Gordon T. Wilfong : A fractional model of the border gateway protocol (BGP). SODA 2008: 193-199
  • [KPRST’09] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng Reducibility Among Fractional Stability Problems Electronic Colloquium on Computational Complexity (ECCC) TR09-041 (2009) [pdf]
  • [Schijver’s Book] Alexander Schrijver : Combinatorial Optimization, Polyhdera and Efficiency, Volume B Springer-Verlag Berlin Heidelberg, (2003)