In classical fair division, we often assume that any subset of indivisible goods—such as office spaces, land parcels, or equipment—can form a valid bundle for an agent. However, real-world constraints frequently dictate that these goods must be allocated in connected bundles based on their spatial or functional relationships. This paper introduces the Price of Connectivity (PoC) to quantify the fairness sacrifice required when such constraints are imposed.
Quantifying Fairness Loss
The authors focus on the Maximin Share (MMS), a standard fairness benchmark. In an unconstrained setting, an agent's MMS is the maximum value they can guarantee themselves if they were to partition all goods into $n$ bundles and receive the one they value least.
When bundles must be connected according to an underlying graph $G$, the value an agent can guarantee (the G-MMS) may decrease. The Price of Connectivity is defined as the worst-case ratio between the standard MMS and the G-MMS. This metric allows researchers to ask: How much does the structure of the graph dictate the fairness we can achieve?
The Connectivity Jump
A central finding of the research is the dramatic difference in fairness guarantees between graphs with vertex connectivity 1 (like trees) and those with connectivity 2 (biconnected graphs). In trees or star graphs, a single high-value central node can act as a bottleneck, preventing fair partitions and leading to a high PoC.
Conversely, biconnected graphs offer "detours" that significantly improve fairness. For two agents, the authors prove that if the graph is at least biconnected, each agent can always be guaranteed at least 3/4 of their MMS (a PoC of 4/3). This bound is tight; even in highly connected structures like wheel graphs, it is impossible to guarantee a better ratio in the worst case.
Summary of Results
The paper provides a comprehensive taxonomy of PoC bounds across various graph classes. While simple paths and stars can lead to a PoC that scales linearly with the number of agents or goods, more complex graph structures provide much more stable fairness guarantees.
Beyond these bounds, the authors offer several key theoretical contributions:
- General Upper Bound: For any graph with $m$ goods and $n$ agents, the PoC is at most $m - n + 1$, providing a baseline guarantee for even the most restrictive topologies.
- Linkedness Conjecture: The authors suggest that "linkedness" (the existence of disjoint paths) may be a more precise predictor of fairness than simple vertex connectivity.
- Algorithmic Efficiency: The results are supported by polynomial-time algorithms that can actively find allocations satisfying these PoC-based fairness guarantees.
Future Directions
While this work establishes a foundation for connectivity-constrained fair division, several avenues remain open. The current results assume additive utilities, where the value of a bundle is the sum of its parts. Future research could explore more complex utility functions (e.g., substitutes or complements), other fairness notions like Envy-Freeness up to one item (EF1), or the division of "chores" (items with negative utility).
Summary updated