A Little Subsidy Ensures MMS Allocation for Three Agents
Abstract
We consider the problem of fair allocation of m indivisible items to a group of n agents with subsidies (money). We address scenarios where agents have general additive cost/utility functions. Our work primarily focuses on the special case of three agents. Assuming that the maximum cost/utility of an item to an agent can be compensated by one dollar, we demonstrate that a total subsidy of 1/6 dollars is sufficient to ensure the existence of Maximin Share (MMS) allocations for both goods and chores. Additionally, we provide examples to establish the lower bounds of the required subsidies.
Cite
Text
Wu et al. "A Little Subsidy Ensures MMS Allocation for Three Agents." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/454Markdown
[Wu et al. "A Little Subsidy Ensures MMS Allocation for Three Agents." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/wu2025ijcai-little/) doi:10.24963/IJCAI.2025/454BibTeX
@inproceedings{wu2025ijcai-little,
title = {{A Little Subsidy Ensures MMS Allocation for Three Agents}},
author = {Wu, Xiaowei and Xue, Quan and Zhou, Shengwei},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {4073-4081},
doi = {10.24963/IJCAI.2025/454},
url = {https://mlanthology.org/ijcai/2025/wu2025ijcai-little/}
}