Truthful Fair Division without Free Disposal
Authors: Xiaohui Bei, Guangda Huzhang, Warut Suksompong
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional assumptions are made. Moreover, we give truthful mechanisms for multiple agents with restricted classes of valuations. |
| Researcher Affiliation | Academia | 1 School of Physical and Mathematical Sciences, Nanyang Technological University 2 Department of Computer Science, Stanford University |
| Pseudocode | Yes | Mechanism 1 (alternative formulation) ... Mechanism 2 (for chore division between two agents) ... Mechanism 3 (for cake cutting among n agents) ... Mechanism 4 (for chore division among n agents) |
| Open Source Code | No | The paper does not provide an unambiguous statement about releasing source code for the described methodology, nor does it include a direct link to a code repository. |
| Open Datasets | No | This is a theoretical paper that focuses on algorithm design and proofs, and does not involve the use of datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve experimental validation splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe empirical experiments requiring specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not list specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not include details on experimental setup, hyperparameters, or system-level training settings. |