Hardness of Approximate Sperner and Applications to Envy-Free Cake
Cutting
Hardness of Approximate Sperner and Applications to Envy-Free Cake
Cutting
Given a so called ''Sperner coloring'' of a triangulation of the $D$-dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by all $D+1$ colors. However, finding a rainbow simplex was the first problem to be proven $\mathsf{PPAD}$-complete in Papadimitriou's classical paper introducing the class …