Maximin-Aware Allocations of Indivisible Goods
Authors: Hau Chan, Jing Chen, Bo Li, Xiaowei Wu
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations, and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisfies MMA or its relaxations. Interestingly, the returned allocation is also 1/2-approximate EFX when all agents have subadditive valuations, which improves the algorithm in [Plaut and Roughgarden, 2018]. |
| Researcher Affiliation | Academia | Hau Chan 1 , Jing Chen2 , Bo Li2 and Xiaowei Wu3 1Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA 2Department of Computer Science, Stony Brook University, USA 3Faculty of Computer Science, University of Vienna, Austria |
| Pseudocode | Yes | Algorithm 1 Divide-and-choose algorithm for three agents Algorithm 2 Algorithm for (sub-)additive valuations |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |