Contiguous cake cutting: hardness results and approximation algorithms
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12526
- Type
- D - Journal article
- DOI
-
10.1613/jair.1.12222
- Title of journal
- Journal of Artificial Intelligence Research
- Article number
- -
- First page
- 109
- Volume
- 69
- Issue
- -
- ISSN
- 1076-9757
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The article extends a conference version at AAAI’20. It is in the field of Algorithmic Game Theory, an interdisciplinary literature combining AI, economic theory, and computational complexity. Problems of fair division date back to ancient history and were mathematically modelled and intensively studied in social choice theory, beginning in the mid-20th century. The paper obtains the first computational hardness results for an envy-free solution concept that was introduced in 1980. It improves on results by other authors at the 2017 IJCAI conference. The paper introduces the concept of approximate envy-freeness as a means to model a viable solution concept.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -