Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
- Ruiquan Gao, Stanford University
- Time: 2024-09-02 15:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
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 (1994). In this talk, we will consider a natural relaxation of this problem in which we relax "all D+1 colors" to allow some fraction of missing colors. We show that this relaxation does not make the problem easier: in fact, for any constant D, finding even a simplex with just three different colors remains PPAD-complete!
This hardness 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.
The paper will appear at FOCS 2024.
Biography
Ruiquan Gao is a second-year Ph.D. student in the theory group at Stanford Computer Science Department, advised by Prof. Aviad Rubinstein and Prof. Moses Charikar. His research interests lie broadly in theoretical computer science, including algorithmic game theory and approximation algorithms. Prior to that, he received his B.Eng. degree in computer science from Institute for Interdisciplinary Information Sciences (Yao Class) at Tsinghua University.