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. w 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. y, we give a sequence of two equal d-dimensional Scarf oiks on 2d vertices such that the pivoting path of the algorithm grows exponentially with d.