[Back]

A. Deligkas, E. Eiben, R. Ganian, T. Hamm, S. Ordyniak:
"The Parameterized Complexity of Connected Fair Division";
Talk: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada; 2021-08-19 - 2021-08-27; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)", (2021), ISBN: 978-0-9992411-9-6; 139 - 145.

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 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 XPalgorithms
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,
with respect to the restrictions considered here, 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.

http://dx.doi.org/10.24963/ijcai.2021/20

https://publik.tuwien.ac.at/files/publik_300281.pdf