Fair Division Under Contiguity Constraints

104 concepts52 papers2 proposals

Traditional fair division theory operates under a convenient mathematical abstraction: resources can be sliced, fragmented, and distributed in any arbitrary combination of pieces. Whether dividing a continuous "cake" (representing time or land) or a set of discrete items (such as corporate assets), classical algorithms focus almost exclusively on optimizing fairness and social welfare.

However, in the real world, fragmented allocations are often useless. A participant cannot easily utilize three disconnected minutes of a supercomputer's schedule, two non-adjacent plots of land, or a scattered collection of advertising slots. To bridge this gap, a prominent research direction introduces contiguity and connectivity constraints, requiring that the resource allocated to each agent forms a single, unbroken component.

Enforcing contiguity fundamentally alters the mathematical landscape of resource allocation. It transforms easily solvable optimization problems into highly complex combinatorial challenges, forcing a deep trade-off between structural usability and perfect fairness.

The Practical Flaw of Unconstrained Allocation

To understand why contiguity constraints are necessary, consider the classic "cake-cutting" metaphor for dividing a heterogeneous, divisible resource. Without constraints, standard protocols like the moving-knife procedure can achieve envy-freeness or proportionality by making arbitrary cuts. However, as noted by Dombb et al. in Computing Socially-Efficient Cake Divisions, requiring that each participant receives exactly one connected interval shifts the problem of maximizing social welfare from a straightforward linear programming task into an NP-hard combinatorial search.

This structural requirement spans numerous real-world domains:

  • Digital Advertising: In rich media markets, advertisers require consecutive blocks of ad slots to display large banners effectively. As shown by Deng et al. in Pricing Ad Slots with Consecutive Multi-unit Demand, this requirement for consecutive allocation introduces geometric complexities that standard independent auction models cannot handle.
  • Operations Scheduling: At major transit hubs, assigning physical assets requires strict proximity rules. For instance, the constraint programming framework developed by Falque et al. in Check-In Desk Scheduling Optimisation at CDG International Airport demonstrates that ensuring allocated units are contiguous within specific operational zones drastically restricts the feasible search space.
  • Time Allocation: When dividing time across multiple shared facilities, agents cannot be in two places at once. Hosseini et al. demonstrate in Fair Division of Time: Multi-layered Cake Cutting that requiring an unbroken interval across multiple resource layers introduces severe geometric constraints that complicate standard envy-free allocations.

Why Contiguity Introduces Combinatorial Hardness

Why does adding a simple connectivity constraint break traditional fair division frameworks? The core issue is boundary interdependency.

In an unconstrained discrete allocation, items can be distributed using a simple greedy approach or a round-robin draft: each agent takes their favorite remaining item, independent of what they have already received. But when bundles must be contiguous, an agent's choices are tightly constrained by what has already been taken. If items are arranged linearly (1, 2, 3, 4, 5) and Agent A takes item 3, the remaining resource is split into two isolated components (1–2 and 4–5). Agent B can no longer receive a contiguous bundle of three items.

This combinatorial explosion manifests in several ways:

  1. Strategic Manipulation: In Truth, Justice, and Cake Cutting, Chen et al. show that the mathematical restrictions imposed by contiguous shares make it exceptionally difficult to design deterministic mechanisms that are simultaneously fair and truthful (immune to strategic lying).
  2. Systemic Inefficiency: For discrete items, Igarashi et al. demonstrate in Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints that a greedy assignment strategy fails because maximizing individual utility often leaves behind disconnected fragments of items that cannot be legally assigned to any other agent, causing systemic Pareto-inefficiency.
  3. Dynamic Instability: When resources arrive sequentially over time, maintaining fairness requires reallocating existing items. Yang et al. prove in Fairly Allocating (Contiguous) Dynamic Indivisible Items with Few Adjustments that contiguity constraints drastically increase this "cost of change," sometimes requiring a quadratic number of reallocations compared to unconstrained settings.

From Lines to Graphs: Topological Bottlenecks

When moving beyond simple one-dimensional lines to model complex physical infrastructures—such as road networks, utility grids, or fiber-optic lines—the resource is represented as an undirected graph. Here, contiguity means that each agent's allocated share must form a connected subgraph.

In this graph-based setting, the underlying topology dictates the bounds of what is fair. In traditional 1D cake cutting, it is always possible to guarantee each of $n$ agents a proportional share (at least $1/n$ of the total value). However, Bei et al. demonstrate in Dividing a Graphical Cake that when dividing a graph where agents require connected pieces, the maximum value that can be guaranteed to every agent drops to a tight bound of $1/(2n-1)$.

Linear Cake (1D Interval):
[------- Agent 1 -------][------- Agent 2 -------][------- Agent 3 -------]
Guaranteed Share: 1/n

Graphical Cake (Topological Bottleneck):
(Node)---[Bridge]---(Node)---(Node)
If the central link is severed, the graph fragments. 
Guaranteed Share drops to 1/(2n-1) due to structural constraints.

This reduction occurs because graphs contain topological bottlenecks, such as "bridges" or "cutsets." Severing a single bridge to give a piece to Agent A might isolate a high-value cluster of nodes, making it impossible to divide the remainder into connected components for the remaining agents.

To handle these structural limitations, researchers adapt alternative fairness benchmarks. For instance, Segal-Halevi et al. show in Graphical Cake Cutting via Maximin Share that while perfect proportionality is often impossible on graphs, a "maximin share" (MMS) allocation—the best worst-case share an agent could secure if they were the one splitting the resource—is guaranteed to exist on forest (acyclic) topologies, even when mandatory buffer zones are placed between pieces.

Despite these theoretical guarantees, finding these allocations remains computationally daunting. As mapped out by Deligkas et al. in The Complexity of Envy-Free Graph Cutting and The Parameterized Complexity of Connected Fair Division, enforcing connectivity constraints makes finding envy-free allocations NP-hard even on highly simplified structures like star graphs.

Balancing Fairness and Efficiency: The Price of Connectivity

Because contiguity requirements restrict the space of valid allocations, they inevitably reduce the maximum achievable social welfare. This systemic loss is formalized as the Price of Connectivity (PoC).

In Welfare Loss in Connected Resource Allocation, Lam et al. quantify this exact reduction, mapping the fundamental trade-off between the practical necessity of item contiguity and the theoretical maximum of unconstrained resource distribution.

To navigate this trade-off, modern social choice theory frequently relaxes strict fairness criteria. As Warut Suksompong outlines in Expanding the Reach of Social Choice Theory, incorporating physical constraints like connectivity requires shifting from idealized mathematical models to approximate fairness notions.

A primary example of this relaxation is moving from absolute envy-freeness to Envy-Freeness up to One Item (EF1), where an agent might envy another's bundle, but that envy would disappear if a single item were removed from the envied bundle. Bilò et al. demonstrate the power of this relaxation in Almost Envy-Free Allocations with Connected Bundles, proving that an EF1 allocation with connected bundles is always guaranteed to exist for up to four agents when items are arranged in a simple path.

By analyzing these relaxed criteria, researchers continue to discover specific "islands of tractability"—identifying the exact boundaries where restrictions on graph topology, agent preferences, and approximate fairness metrics align to make contiguous resource allocation both fair and computationally feasible.

Key Foundational Work

Computing Socially-Efficient Cake Divisions (2012) — contributed 3 concept elements to this direction.
Optimal Proportional Cake Cutting with Connected Pieces (2012) — contributed 1 concept elements to this direction.
Truth, Justice, and Cake Cutting (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_contiguous_resource_allocation_3ee99394,
  title = {contiguous resource allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/contiguous-resource-allocation/rdr_3ee993946a1541b386d6c6466e70d355},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_contiguous_resource_allocation_3ee99394_v1,
  title = {contiguous resource allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/contiguous-resource-allocation/rdr_3ee993946a1541b386d6c6466e70d355/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake