Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912043637932032 |
|---|---|
| author | Gao, Ruiquan Roghani, Mohammad Rubinstein, Aviad Saberi, Amin |
| author_facet | Gao, Ruiquan Roghani, Mohammad Rubinstein, Aviad Saberi, Amin |
| contents | 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 $\mathsf{PPAD}$ (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 $\mathsf{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 $\mathsf{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-Ω(1)}(ε)$, where $ε$ is the precision parameter (side length for Sperner and approximate envy-free for cake cutting). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15713 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting Gao, Ruiquan Roghani, Mohammad Rubinstein, Aviad Saberi, Amin Computational Complexity Computer Science and Game Theory 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 $\mathsf{PPAD}$ (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 $\mathsf{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 $\mathsf{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-Ω(1)}(ε)$, where $ε$ is the precision parameter (side length for Sperner and approximate envy-free for cake cutting). |
| title | Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.15713 |