Mutiara Sondjaja

Harvey Mudd College Mathematics 2008

mugshot
Thesis Advisor: Prof. Francis E. Su
Second Reader: Prof. Jon Jacobsen
Thesis Proposal: Understanding Kakutani's fixed point theorem and Sperner's lemma
Poster: Sperner's Lemma implies Kakutani's Theorem
Final Report Sperner's Lemma implies Kakutani's Fixed Point Theorem

Understanding Kakutani's Fixed Point Theorem and Sperner's Lemma

Abstract

Kakutani's fixed point theorem has many applications in economics and game theory. One of its most well-known applications is in John Nash's paper in 1950, where the theorem is used to prove the existence of an equilibrium in n-person games.

Sperner's lemma, on the other hand, is a combinatorial result concerning the labeling of the vertices of simplices and their triangulations. It is known that Sperner's lemma is equivalent to a result called Brouwer's fixed point theorem, of which Kakutani's theorem is a generalization. Furthermore, many existing alrgoirhtms used to find fixed points of functions also use Sperner's lemma in their construction. A natural question that arises, then, is whether we can prove Kakutani's fixed point theoreme directly using Sperner's lemma, without going through Brouwer's theorem

In this thesis project, I aim to understand Kakutani's theorem, Sperner's lemma, and how they are related. In particular, we show that Kakutani's theorem can be proven directly from Sperner's lemma.