Towards Optimal Subsidy Bounds for Envy-Freeable Allocations
Abstract
We study the fair division of indivisible items with subsidies among n agents, where the absolute marginal valuation of each item is at most one. Under monotone valuations (where each item is a good), it is known that a maximum subsidy of 2(n-1) and a total subsidy of 2(n-1)² are sufficient to guarantee the existence of an envy-freeable allocation. 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.
Cite
Text
Kawase et al. "Towards Optimal Subsidy Bounds for Envy-Freeable Allocations." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I9.28842Markdown
[Kawase et al. "Towards Optimal Subsidy Bounds for Envy-Freeable Allocations." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/kawase2024aaai-optimal/) doi:10.1609/AAAI.V38I9.28842BibTeX
@inproceedings{kawase2024aaai-optimal,
title = {{Towards Optimal Subsidy Bounds for Envy-Freeable Allocations}},
author = {Kawase, Yasushi and Makino, Kazuhisa and Sumita, Hanna and Tamura, Akihisa and Yokoo, Makoto},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {9824-9831},
doi = {10.1609/AAAI.V38I9.28842},
url = {https://mlanthology.org/aaai/2024/kawase2024aaai-optimal/}
}