The Query Complexity of Cake Cutting
Authors: Simina Branzei, Noam Nisan
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among n = 3 players and for computing perfect and equitable allocations with minimum number of cuts between n = 2 players. For ϵ-envy-free allocations with contiguous pieces, we also give an upper bound of O(n/ϵ) and lower bound of Ω(log(1/ϵ)) queries for any number n 3 of players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model. |
| Researcher Affiliation | Academia | Simina Brânzei Purdue University, USA simina.branzei@gmail.com Noam Nisan Hebrew University of Jerusalem, Israel noam@cs.huji.ac.il |
| Pseudocode | No | The paper describes procedures in text, such as 'Equitable Protocol: Player 1 slides a knife continuously across the cake, from 0 to 1.', but does not include any formally structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not mention releasing any source code for its methodology. The checklist confirms N/A for code and data reproduction. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets, training, or public data availability. The checklist confirms N/A for experiments. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies with dataset splits for training, validation, or testing. The checklist confirms N/A for experiments. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments, therefore no hardware specifications are mentioned. The checklist confirms N/A for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments, therefore no software dependencies with version numbers are mentioned. The checklist confirms N/A for experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. The checklist confirms N/A for experiments. |