Abstract
We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces; for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We also show that envy-free feasible allocations where each agent receives a polynomially bounded number of intervals exist for any number of agents and layers under mild conditions on agents' preferences. We further devise an algorithm for computing proportional allocations for any number of agents and layers.
Introduction
In traditional fair division literature, the "cake cutting" problem involves partitioning a single heterogeneous resource among multiple agents. However, many real-world scheduling and allocation problems involve multiple resources—such as conference rooms, hospital shifts, or specialized laboratory equipment. This paper, "Fair Division of Time: Multi-layered Cake Cutting," by Hadi Hosseini, Ayumi Igarashi, and Andrew Searns, extends the classic framework to handle these multi-layered scenarios.
The central challenge is the feasibility constraint: an agent cannot be in two places at once. If an agent is assigned a specific time interval on one layer, they cannot be assigned an overlapping interval on any other layer. This constraint distinguishes multi-layered cake cutting from simply solving multiple independent single-layer problems.
The Feasibility Constraint
A feasible allocation ensures that for every agent, the union of their assigned intervals across all layers does not contain any overlapping time segments. This is critical for applications like shift scheduling, where an employee's physical presence is required at only one location at a time.
Beyond feasibility, agents often prefer contiguous pieces—single, unbroken blocks of time—rather than fragmented intervals. Balancing fairness (envy-freeness or proportionality), feasibility, and contiguity is the primary focus of this research.
Methodology: Diagonal Partitions and Switching Points
To adapt existing fair division protocols to multiple layers, the authors introduce diagonal partitions. In a two-layer setting, they define two types of pieces:
- $LR(x)$: A piece consisting of the interval $[0, x]$ on the bottom layer and $[x, 1]$ on the top layer.
- $RL(x)$: A piece consisting of the interval $[0, x]$ on the top layer and $[x, 1]$ on the bottom layer.
A switching point $x$ is defined as the location where an agent is indifferent between $LR(x)$ and $RL(x)$.
By utilizing these switching points, the authors can transform a multi-layered problem into a structure that can be handled by modified versions of classic protocols, such as the Stromquist moving-knife protocol. For proportionality, they employ a recursive decomposition strategy, which is particularly effective when the number of layers is a power of two, allowing for clean binary splits of both agents and resources.
Key Results and Insights
The paper provides several existence proofs and algorithmic results:
- Envy-Freeness (EF): For two agents and two layers, an envy-free, contiguous, and feasible allocation is always guaranteed. For three agents and two layers, existence is guaranteed if agents have at most two distinct types of preferences. For general $n$ agents and $m$ layers, EF feasible allocations exist if contiguity is relaxed to allow a polynomial number of cuts.
- Proportionality (Prop): Proportional feasible allocations can be computed efficiently in $O(nm^2)$ time when $n=m$. Contiguous proportional allocations are guaranteed when the number of layers $m$ is a power of two.
- The Power of Two: A significant insight is that proportionality is much more tractable when $m = 2^a$, facilitating recursive binary partitioning.
- Non-Monotonicity: The authors note that the value of diagonal pieces may not change monotonically as the knife moves, which complicates the application of standard topological tools like Sperner’s Lemma.
Conclusion and Future Work
This research initiates the formal study of multi-layered fair division with temporal constraints. While it establishes foundational results for envy-free and proportional allocations, several challenges remain. Future work aims to bridge the "contiguity gap" for more than three agents and to generalize the proportionality algorithms for any number of layers. Additionally, incorporating economic efficiency (Pareto optimality) alongside fairness remains an important open problem.
Summary updated