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 mathsfPPAD-complete in Papadimitriou's classical paper introducing the class mathsfPPAD (1994). 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 mathsfPPAD-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 mathsfPPAD-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 log1-Omega(1)(ε), where ε is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).