We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the ag...Expand abstract
- Publication status:
- Peer review status:
- Peer reviewed
- Copyright holder:
- AI Access Foundation.
- Copyright date:
- Rights statement:
- © 2020 AI Access Foundation. All rights reserved.
- This is the accepted manuscript version of the article. The final version is forthcoming from the AI Access Foundation.
Contiguous cake cutting: hardness results and approximation algorithms
If you are the owner of this record, you can report an update to it here: Report update to this record