AAAI 2024technical7 citations
Towards Optimal Subsidy Bounds for Envy-Freeable Allocations
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Makoto Yokoo
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.
BibTeX
@article{Kawase_Makino_Sumita_Tamura_Yokoo_2024, title={Towards Optimal Subsidy Bounds for Envy-Freeable Allocations}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/28842}, DOI={10.1609/aaai.v38i9.28842}, abstractNote={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.}, number={9}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Kawase, Yasushi and Makino, Kazuhisa and Sumita, Hanna and Tamura, Akihisa and Yokoo, Makoto}, year={2024}, month={Mar.}, pages={9824-9831} }