Chore sharing on trees ensures fair connected cost allocations
A rainbow partition theorem for trees and connected maximin share allocations of chores
Discrete Mathematics
Summary
The paper looks at how to fairly divide chores that are connected like points on a tree, so each person’s share stays under a fair limit called the maximin share. Previous work showed this was possible for goods, and this work confirms it also works for chores, even when costs are uneven. The authors prove a mathematical rule about splitting trees into connected parts matching multiple partitions, which helps them guarantee fair chore divisions. They also provide an algorithm to find such divisions efficiently for a fixed number of people.
What this means in practice
- •For task schedulers: Divide connected sets of linked tasks among multiple agents ensuring each agent’s workload is fairly bounded.
- •For maintenance planners: Allocate connected maintenance chores distributed along a networked structure so every team’s total cost stays within fair limits.
A theory result. No direct application yet.
Authors
Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek, Jarosław Grytczuk, Zbigniew Lonc, Paweł Rzążewski
Abstract
Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if $\mathcal P_1,\ldots,\mathcal P_k$ are partitions of the vertex set of a finite tree, each into at most $k$ connected parts, then the vertex set can be split into disjoint sets $B_1,\ldots,B_k$, some possibly empty, such that each nonempty $B_i$ is connected and contained in a part of $\mathcal P_i$. Equivalently, if each of $k$ colours occurs on at most $k-1$ edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time $k^{O(k)}$ plus polynomial time.