Cubical sperner lemmas as applications of generalized complementary pivoting

Two cubical versions of Sperner's lemma, due to Kuhn and Fan, are proved constructively without resorting to a simplicial decomposition of the cube, presenting examples of generalized complementary pivoting discussed by Todd (Math. Programming6 (1974)). The first version is essentially equivalent to Sperner's lemma in that it implies Brouwer's fixed point theorem, thereby answering a question raised by Kuhn (IBM J. Res. Develop.4 (1960)). The second has the property that although the structure is that of generalized complementarity, there is a uniquely defined path or algorithm associated with it. The basic structure used is a cubical decomposition of the cube, a special case of a cubical pseudomanifold, presented by Fan (Arch. Math.11 (1960)). Given the existence of a constructive algorithm for Sperner's lemma (see Cohen, J. Combinatorial Theory2 (1967)) and its generalization by Fan J. Combinatorial Theory2 (1967)) allied to the large amount of recent progress in complementary pivot theory, resulting in particular from the works of Lemke (Manage. Sci.11 (1965)) and Scarf (“The Computation of Economic Equilibria”) the computational attractions of a simplicial decomposition have become apparent. However, a cubical decomposition leads to certain advantages when a search for more than one “completely labeled” region is required, and no simplicial construction for the Fan lemma is known.