Envy-Free Cake-Cutting for Four Agents
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916923858485248 |
|---|---|
| author | Hollender, Alexandros Rubinstein, Aviad |
| author_facet | Hollender, Alexandros Rubinstein, Aviad |
| contents | In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of $n$ agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the $n$ agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected $\varepsilon$-envy-free allocation.
For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient ($\textsf{poly}(\log(1/\varepsilon))$ queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Brânzei and Nisan (2022) conjectured an $Ω(1/\varepsilon)$ lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected $\varepsilon$-envy-free allocation with four monotone agents.
We also prove that as soon as valuations are allowed to be non-monotone, the problem becomes hard: it becomes PPAD-hard, requires $\textsf{poly}(1/\varepsilon)$ queries in the black-box model, and even $\textsf{poly}(1/\varepsilon)$ communication complexity. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02075 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Envy-Free Cake-Cutting for Four Agents Hollender, Alexandros Rubinstein, Aviad Computer Science and Game Theory Computational Complexity In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of $n$ agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the $n$ agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected $\varepsilon$-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient ($\textsf{poly}(\log(1/\varepsilon))$ queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Brânzei and Nisan (2022) conjectured an $Ω(1/\varepsilon)$ lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected $\varepsilon$-envy-free allocation with four monotone agents. We also prove that as soon as valuations are allowed to be non-monotone, the problem becomes hard: it becomes PPAD-hard, requires $\textsf{poly}(1/\varepsilon)$ queries in the black-box model, and even $\textsf{poly}(1/\varepsilon)$ communication complexity. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model. |
| title | Envy-Free Cake-Cutting for Four Agents |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2311.02075 |