Chore division on a graph
This addresses the challenge of fair chore division in networked environments, such as task assignment in distributed systems, but is incremental as it builds on prior work for goods allocation.
The paper tackles the problem of fairly allocating indivisible chores arranged on a graph, where each agent's share must be connected, showing that this setting differs fundamentally from goods allocation and cannot be derived from it. They prove that deciding the existence of fair allocations under proportionality, envy-freeness, and equitability is computationally hard even for simple graphs like paths or stars, while also identifying some efficiently solvable special cases.
The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent's share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.