Sperner Lemma, Cake Cutting, Rental Harmony, and the Brouwer Fixed Point Theorem
A Talk by Dr. Sarmad Abbasi
Three roommates have rented a house that has three different rooms. They want to decide who gets which room and how much share of the rent should each of them pay. This fair division problem is typical in algorithmic game theory.
The surprisingly elegant solution to this problem is given by the Sperner Lemma. This simple combinatorial theorem has deep consequences: It is used to prove the celebrated Brouwer Fixed point theorem.
In this lecture we will see a complete proof of the Sperner Lemma and show how some fair division problems are solved using it. We will also discuss how to prove the Brouwer Fixed point theorem using this result.
The lecture will be self-contained and elementary: 10th grade mathematics will be enough to understand it.