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)

One thought on “Scarf’s Lemma”

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

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Scarf’s Lemma

One thought on “Scarf’s Lemma”

Leave a Reply Cancel reply

Share this:

Like this:

Related

One thought on “Scarf’s Lemma”

Leave a Reply Cancel reply