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.
