Scarf Oiks

We formulate the famous Scarf Lemma in terms of oiks. This lemma has two fundamental applications in game and graph theory. In 1967, Scarf derived from it core-solvability of balanced cooperative games. Recently, it was shown that kernel-solvability of perfect graphs also results from this lemma.We show that Scarf's combinatorially defined oiks are in fact realized by polytopes, and also that Scarf's algorithm for proving the Scarf Lemma is an instance of the Lemke-Howson algorithm for finding an equilibrium of a bimatrix game.Finally, we give a sequence of two equal d-dimensional Scarf oiks on 2. d vertices such that the pivoting path of the algorithm grows exponentially with d.