Sperner Oiks

The idea of “Lemke pivoting in a family of oiks (Euler complexes)” generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Spernerʹs Lemma. Given a “room-partitioning”, this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O = { O 1 , … , O k } can be reduced to a pair of oiks O ′ = { O 1 + … + O k , O 0 } (one of which, O 0 , is a Sperner oik) such that the exchange graphs for O and O ′ are isomorphic. Numerous applications of Spernerʹs Lemma in combinatorial topology are well known.