The Complexity of Envy-Free Graph Cutting
This addresses fairness in resource allocation for multi-agent systems, but it is incremental as it builds on existing complexity analysis in computational social choice.
The paper tackles the problem of fairly dividing heterogeneous divisible resources represented as graph edges among agents with connected pieces and envy-freeness, showing it is NP-complete and providing a dichotomy for constant agents and a polynomial-time algorithm for constant edges.
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.