Using oriented volume to prove Sperner’s lemma

Authors: Yakar Kannai

Publish Date: 2013/04/05

Volume: 1, Issue: 1, Pages: 11-19

PDF Link

Abstract

Sperner’s 1928 wellknown lemma is used to prove the Brouwer fixed point theorem and is actually equivalent to it and has been used frequently along with various generalizations to establish fundamental results in game theory and in economics see eg in Kannai 1992 McLennan and Tourky 2008 Scarf 1982 Shapley and Vohra 1991 and in the references quoted there Motivated by the wish to provide a proof “sufficiently short or intuitively appealing to be attractive in the context of texts on mathematical economics” a proof which can be “reasonably be assumed to be part of the prior knowledge of students studying mathematical economics at least at the advanced level” was supplied in McLennan and Tourky 20081 The proof of Sperner’s lemma provided in Kannai 1992 is based via Kannai 1981 on an argument involving volume as in McLennan and Tourky 2008 but involves “advanced calculus” unfortunately not too familiar to the present generation of students studying mathematical economics In the present note we provide an elementary proof of Sperner’s lemma inspired both by McLennan and Tourky 2008 and the method of Kannai 1992 and Kannai 1981 This proof uses the concept of oriented volume2 rather than the volume itself but requires no extra parameter for homotopy Observe that we actually prove a stronger form of Sperner’s lemma the oriented version due to Brown and Cairns 1961 see Sect 4Sperner’s lemma is stated and proved in Sect 2 where the necessary concepts are recalled for convenience of the reader For completeness we follow McLennan and Tourky 2008 and define affine dependence simplices and triangulations The main technical tool is the Main Lemma establishing equality 2 of the oriented volume of the image of a simplex with the sum of the oriented volumes of images of the simplices in a triangulation of the simplex under a Sperner labeling In Sect 3 a proof along similar lines is provided for generalizations of Sperner’s lemma such as the Sperner–Shapley’s lemma this generalization is useful eg in proving Scarf’s theorem on nonemptyness of the core of a balanced game see Shapley 1973 and also Kannai 1992 and for more general forms used for example in Section 7 of Scarf 1982 In addition the Main Lemma is generalized to a certain class of pseudomanifolds with boundaries In Sect 4 we comment on relations between arguments and results described in this note and wellknown ideasAn affine combination of points p 0ldots p i in Rd is a sum a 0 p 0+cdots + a i p i where a 0ldots a i are real numbers with a 0+cdots +a i = 1 We say that p 0 ldots p i are affinely independent if it is not possible to write one of them as an affine combination of the others equivalently p 1 p 0 ldots p i p 0 are linearly independent A subset M of Rd is an affine space if it is closed under affine combinations It is easy to see that an affine space is just a translation of a linear space The dimension of an affine space M is the maximal number of elements in affinely independent subsets of MA simplex sigma is the convex hull of affinely independent points p 0ldots p i The points p 0 ldots p i are the vertices of sigma If the points are not affinely independent we say that the simplex is degenerate The dimension of a simplex is the dimension of the smallest affine space that contains it equivalently the number of its vertices minus one A face of simplex is a possibly empty subsimplex Note that a proper face of a simplex sigma ie a face of sigma other than sigma itself is the intersection of sigma with a hyperplane that bounds a halfspace of Rd that contains sigma A finite simplicial complex is a finite collection T of simplices in Rd such that any face including emptyset of an element of T is an element of T and the intersection of any two elements of T is a possibly empty common face The underlying space T of T is the union of all simplices in T

Keywords: