PROPm Allocations of Indivisible Goods to Multiple Agents

Baklanov, Artem; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel

doi:10.24963/ijcai.2021/4

PROPm Allocations of Indivisible Goods to Multiple Agents

Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 24-30.

https://doi.org/10.24963/ijcai.2021/4

Keywords

Agent-based and Multi-agent Systems: Resource Allocation

Abstract

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin. 2021. PROPm Allocations of Indivisible Goods to Multiple Agents. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 24–30. https://doi.org/10.24963/ijcai.2021/4

@inproceedings{ijcai2021p4,
  title     = {PROPm Allocations of Indivisible Goods to Multiple Agents},
  author    = {Baklanov, Artem and Garimidi, Pranav and Gkatzelis, Vasilis and Schoepflin, Daniel},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {24--30},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/4},
  url       = {https://doi.org/10.24963/ijcai.2021/4},
}

TY  - CPAPER
TI  - PROPm Allocations of Indivisible Goods to Multiple Agents
AU  - Baklanov, Artem
AU  - Garimidi, Pranav
AU  - Gkatzelis, Vasilis
AU  - Schoepflin, Daniel
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 24
EP  - 30
DO  - 10.24963/ijcai.2021/4
UR  - https://doi.org/10.24963/ijcai.2021/4
ER  -