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 and let be an real matrix such that for . Let be a non-negative vector in , such that the set is bounded. Let be an matrix such that whenever , and . Then there exists a subset of size of such that
- (feasible) : for some such that whenever .
- (subordinating) : For every there exists such that for all .
Proof of Scarf’s Lemma :
We want an which is simultaneously feasible for and subordinating for . Note that it is easy to find a feasible and a subordinating that are “almost same”. Choose . Choose where j is selected from all of the columns so as to maximize . Now and have columns in common. To find the required we shall apply the following (feasible and ordinal) pivot steps. Throughout we shall maintain this relationship of having at least 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 and the following lemmas hold. ( is said to be non-degenerate if no two elements in the same row are equal).
(i) Feasible Pivot Step : Let be a feasible basis for , and . Then there exists a unique such that is a feasible basis.
(ii) Ordinal Pivot Step : Let be a subordinating set for of size -1. Then there are precisely two elements such that is subordinating for , unless , 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 with partitions (the set of all feasible bases containing ) and (the set of all subordinating sets of size not containing . A vertex is joined to a vertex if .
Exercise : Prove that every node (except and the required solution ) in have degree two.
Since is not subordinating, the required solution which is both feasible and subordinating must exist. Note that this proof gives a membership of the computational version of Scarf’s lemma. For -membership and -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 -complete [KPRST’09]. Are there interesting applications of Scarf’s lemma that are polynomial time solvable ?
- [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)
Pingback: Open Problems from FOCS 2009 « My Brain is Open