May 2009 – My Brain is Open

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)

The Complexity of searching for Pigeonholes…….

Today’s post is about a complexity class named $PPP$ , introduced by Papadimitriou [Papadimitriou’94]. $PPP$ stands for Polynomial Pigeonhole Principle. It is defined to capture the complexity of problems (in TFNP), whose totality is proved using the pigeonhole principle. Following is the standard problem for $PPP$ .

Definition : (EQUAL OUTPUTS) : Given a Boolean circuit $C$ with $n$ inputs and $n$ outputs, either find an input $x$ such that $C(x)=0^n$ or two inputs $x \neq x'$ such that $C(x)= C(x')$ .

Exercise : If $C$ is a monotone circuit then EQUAL OUTPUTS is in $FP$ .

Let us look at an example. 0-1 KNAPSACK is a well-known NP-complete problem. Given a set $S$ of $n$ positive integers and an integer $W$ , the goal is to find a subset $A \subseteq S$ whose elements sum to $W$ . For any set $S$ of $n$ positive integers, if the sum of elements of $S$ is less than $2^n-1$ , there exist two subsets of $S$ with the same sum. This gives rise to “TFNP version” of 0-1 KNAPSACK. It is called EQUAL SUMS.

Definition : (EQUAL SUMS) : Given a set $S$ of $n$ positive integers, such that the sum of elements of $S$ is less than $2^n-1$ , find two subsets of $S$ with the same sum.

Exercise : Prove that $EQUAL SUMS \in PPP$ .

EQUAL SUMS is not known to be in FP. Our understanding of PPP is very limited. We don’t have any natural complete problem for PPP yet. As the following exercise suggests, it is unlikely that PPP-complete problems are in FP.

Exercise : If PPP = FP then one-way permutations do not exist.

Open Problems : Is Equal Sums PPP-complete [Papadimitriou’94] ? Are there other natural problems in PPP, that are not obviously in FP ? It is known that $PPAD \subseteq PPP$ [Papadimitriou’94]. Is there a “geometric” version of Equal Sums in PPAD ?

References :

[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) [pdf]

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Month: May 2009

Scarf’s Lemma

Pigeonhole Completeness

Share this:

Like this:

Share this:

Like this: