Towards Optimal Subsidy Bounds for Envy-Freeable Allocations
Authors: Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Makoto Yokoo
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we improve upon these bounds, even in a wider model. Namely, we show that, given an EF1 allocation, we can compute in polynomial time an envy-free allocation with a subsidy of at most n 1 per agent and a total subsidy of at most n(n 1)/2. Moreover, we present further improved bounds for monotone valuations. and To prove these improved bounds, we reveal that the structure of the minimum subsidy vectors satisfies: (i) the minimum subsidy vector remains unchanged irrespective of the maximum weight matching (Lemma 2), and (ii) how the subsidies alter when the weights are changed (Lemma 4). |
| Researcher Affiliation | Academia | 1University of Tokyo 2Kyoto University 3Tokyo Institute of Technology 4Keio University 5Kyushu University |
| Pseudocode | No | The paper describes algorithms and their computational complexity but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that open-source code for the described methodology is available. |
| Open Datasets | No | This is a theoretical paper that does not use datasets for training, validation, or testing. |
| Dataset Splits | No | This is a theoretical paper that does not use datasets for training, validation, or testing, and thus no dataset splits are provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe any experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper and does not describe any implementation details that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that does not describe any experiments, and therefore no experimental setup details like hyperparameters or training settings are provided. |