Maximin Share Guarantees for Few Agents with Subadditive Valuations

Christodoulou, George; Christoforidis, Vasilis; Mastrakoulis, Symeon; Sgouritsa, Alkmini

doi:10.24963/ijcai.2025/421

Maximin Share Guarantees for Few Agents with Subadditive Valuations

George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, Alkmini Sgouritsa

Download BibTeX Cite

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

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

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division

Abstract

We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an improved lower bound of 1/2 (which is tight) for the case of subadditive valuations when the number of agents is at most four. We also provide a tight lower bound for the case of multiple agents, when they are equipped with one of two possible types of valuations. Moreover, we propose a new model that extends previously studied models in the area of fair division, which will hopefully give rise to further research. We demonstrate the usefulness of this model by employing it as a technical tool to derive our main result, and we provide a thorough analysis for this model for the case of three agents. Finally, we provide an improved impossibility result for the case of three submodular agents.

George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa. 2025. Maximin Share Guarantees for Few Agents with Subadditive Valuations. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3788–3795. https://doi.org/10.24963/ijcai.2025/421

@inproceedings{ijcai2025p421,
  title     = {Maximin Share Guarantees for Few Agents with Subadditive Valuations},
  author    = {Christodoulou, George and Christoforidis, Vasilis and Mastrakoulis, Symeon and Sgouritsa, Alkmini},
  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     = {3788--3795},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/421},
  url       = {https://doi.org/10.24963/ijcai.2025/421},
}

TY  - CPAPER
TI  - Maximin Share Guarantees for Few Agents with Subadditive Valuations
AU  - Christodoulou, George
AU  - Christoforidis, Vasilis
AU  - Mastrakoulis, Symeon
AU  - Sgouritsa, Alkmini
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  - 3788
EP  - 3795
DO  - 10.24963/ijcai.2025/421
UR  - https://doi.org/10.24963/ijcai.2025/421
ER  -