The Parameterized Complexity of Connected Fair Division

Deligkas, Argyrios; Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Ordyniak, Sebastian

doi:10.24963/ijcai.2021/20

The Parameterized Complexity of Connected Fair Division

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 139-145.

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

Keywords

Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation

Abstract

We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. 2021. The Parameterized Complexity of Connected Fair Division. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 139–145. https://doi.org/10.24963/ijcai.2021/20

@inproceedings{ijcai2021p20,
  title     = {The Parameterized Complexity of Connected Fair Division},
  author    = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Ordyniak, Sebastian},
  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     = {139--145},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/20},
  url       = {https://doi.org/10.24963/ijcai.2021/20},
}

TY  - CPAPER
TI  - The Parameterized Complexity of Connected Fair Division
AU  - Deligkas, Argyrios
AU  - Eiben, Eduard
AU  - Ganian, Robert
AU  - Hamm, Thekla
AU  - Ordyniak, Sebastian
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 139
EP  - 145
DO  - 10.24963/ijcai.2021/20
UR  - https://doi.org/10.24963/ijcai.2021/20
ER  -