Truthful Cake Sharing
Authors: Xiaohui Bei, Xinhang Lu, Warut Suksompong4809-4817
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main technical result establishes the truthfulness of the solution for any number of agents with arbitrary piecewise uniform utilities. At a high level, our proof proceeds by showing that the leximin solution is immune to certain types of manipulations, and then arguing that this immunity is sufficient to protect the solution against all possible manipulations. Along the way, we introduce the notion of an ε-change a tiny change from one utility vector or allocation towards another which may be useful in related settings. Additionally, we show that each agent receives the same utility in all leximin allocations (which means that tie-breaking is inconsequential) and that such an allocation can be computed in polynomial time. We will therefore show that the solution attains the highest possible ratio among all truthful mechanisms satisfying a natural condition. |
| Researcher Affiliation | Academia | Xiaohui Bei,1 Xinhang Lu,2 Warut Suksompong3 1 School of Physical and Mathematical Sciences, Nanyang Technological University 2 School of Computer Science and Engineering, University of New South Wales 3 School of Computing, National University of Singapore |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks (clearly labeled algorithm sections or code-like formatted procedures). |
| Open Source Code | No | The paper does not provide concrete access to source code (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | Our setting includes a set of agents denoted by N = {1, 2, . . . , n} and a heterogeneous divisible good (or cake) represented by the normalized interval [0, 1]. A piece of cake is a union of finitely many disjoint (closed) intervals. [...] We assume that the agents have piecewise uniform utilities: for each agent i, each part of the cake is either desired or undesired, and the density function fi takes on the value 1 for all desired parts and 0 for all undesired parts. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments requiring dataset splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not describe any experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate experiments, as it is a theoretical work. |
| Experiment Setup | No | This paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |