Journal article icon

Journal article

Contiguous cake cutting: hardness results and approximation algorithms

Abstract:

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:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1613/jair.1.12222

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0002-5436-7890
More by this author
Institution:
University of Oxford
Oxford college:
St Anne's College
Role:
Author
ORCID:
0000-0001-5255-9349
Publisher:
AI Access Foundation Publisher's website
Journal:
Journal of Artificial Intelligence Research Journal website
Volume:
69
Pages:
109-141
Publication date:
2020-09-22
Acceptance date:
2020-08-23
DOI:
EISSN:
1943-5037
ISSN:
1076-9757
Language:
English
Keywords:
Pubs id:
1127999
Local pid:
pubs:1127999
Deposit date:
2020-08-24

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP