A Little Subsidy Ensures MMS Allocation for Three Agents

Wu, Xiaowei; Xue, Quan; Zhou, Shengwei

doi:10.24963/ijcai.2025/454

A Little Subsidy Ensures MMS Allocation for Three Agents

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4073-4081.

https://doi.org/10.24963/ijcai.2025/454

Keywords

Game Theory and Economic Paradigms: GTEP: Computational social choice
Game Theory and Economic Paradigms: GTEP: Fair division

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.

Xiaowei Wu, Quan Xue, and Shengwei Zhou. 2025. A Little Subsidy Ensures MMS Allocation for Three Agents. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4073–4081. https://doi.org/10.24963/ijcai.2025/454

@inproceedings{ijcai2025p454,
  title     = {A Little Subsidy Ensures MMS Allocation for Three Agents},
  author    = {Wu, Xiaowei and Xue, Quan and Zhou, Shengwei},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {4073--4081},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/454},
  url       = {https://doi.org/10.24963/ijcai.2025/454},
}

TY  - CPAPER
TI  - A Little Subsidy Ensures MMS Allocation for Three Agents
AU  - Wu, Xiaowei
AU  - Xue, Quan
AU  - Zhou, Shengwei
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 4073
EP  - 4081
DO  - 10.24963/ijcai.2025/454
UR  - https://doi.org/10.24963/ijcai.2025/454
ER  -