Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting

Given a so called “Sperner coloring” of a triangulation of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$D$</tex> -dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$D+1$</tex> 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 - <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">${D}+1$</tex> colors” to allow some fraction of missing colors: in fact, for any constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$D$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log^{1-\Omega(1)}(\varepsilon)$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).