Mind the Gap: Cake Cutting With Separation
Authors: Edith Elkind, Erel Segal-Halevi, Warut Suksompong5330-5338
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then establish several computational properties of maximin share fairness for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. A summary of our results can be found in Table 1. |
| Researcher Affiliation | Academia | 1 Department of Computer Science, University of Oxford 2 Department of Computer Science, Ariel University 3 School of Computing, National University of Singapore |
| Pseudocode | No | The paper describes algorithms in prose (e.g., in the proofs of Theorem 3.1 and Theorem 3.4) but does not provide structured pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not contain any statement about releasing source code or provide any links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets or training. Therefore, there is no mention of publicly available datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data. There is no mention of dataset splits (train/validation/test) or cross-validation. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report on computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or system-level training settings. |