Graphical Cake Cutting via Maximin Share
Authors: Edith Elkind, Erel Segal-Halevi, Warut Suksompong
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the recently introduced cake-cutting setting in which the cake is represented by an undirected graph. This generalizes the canonical interval cake and allows for modeling the division of road networks. We show that when the graph is a forest, an allocation satisfying the well-known criterion of maximin share fairness always exists. Our result holds even when separation constraints are imposed; however, in the latter case no multiplicative approximation of proportionality can be guaranteed. Furthermore, while maximin share fairness is not always achievable for general graphs, we prove that ordinal relaxations can be attained. |
| Researcher Affiliation | Academia | Edith Elkind1 , Erel Segal-Halevi2 and Warut Suksompong3 1Department of Computer Science, University of Oxford 2Department of Computer Science, Ariel University 3School of Computing, National University of Singapore |
| Pseudocode | No | The paper presents lemmas, theorems, and proofs. It describes theoretical procedures (e.g., 'we remove all portions of the tree that are within distance s of Ti,j, and divide the remaining cake recursively among the remaining agents.'), but it does not include formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention or provide any links to open-source code. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and concept development. It does not involve any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve any experimental setup requiring training/validation/test splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require hardware specifications. Therefore, no hardware details are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational implementation that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and concept development. It does not describe any experimental setup details such as hyperparameters or training configurations. |