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)
About these ads

One thought on “Scarf’s Lemma

  1. Pingback: Open Problems from FOCS 2009 « My Brain is Open

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s