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 PPAD-complete in Papadimitriou's classical paper introducing the class PPAD [1]. In this paper, we prove that the problem does not become easier if we relax “all -${D}+1$colors” to allow some fraction of missing colors: in fact, for any constant$D$, finding even a simplex with just three colors remains PPAD-complete! Our result has an interesting application for the envy-free cake cutting from fair division. It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (“a non-empty piece is better than an empty piece of cake”), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is PPAD-complete to find an allocation -even using any constant number of possibly disconnected pieces- that makes just three agents envy-free. Our results extend to super-constant dimension, number of agents, and number of pieces, as long as they are asymptotically bounded by any$\log^{1-\Omega(1)}(\varepsilon)$, where$\varepsilon$is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).