Mind the Gap: Cake Cutting With Separation

Introduction

The end of the year is fast approaching, and members of a city council are busy planning the traditional New Year’s fair on their city’s main street. As usual, a major part of their work is to divide the space on the street among interested vendors. Each vendor naturally has a preference over potential locations, possibly depending on the proximity to certain attractions or the estimated number of customers visiting that space. Additionally, this year is different from previous years due to the social distancing guidelines issued by the government—vendors are required to be placed at least two meters apart. How should the city council allot the space so that all vendors feel fairly treated and at the same time everyone stays safe and sound under the new guidelines?

The problem of fairly allocating a heterogeneous divisible good among a set of agents in a fair manner has a long history and is commonly known as cake cutting (Brams and Taylor 1996; Robertson and Webb 1998; Procaccia 2016). A typical fairness criterion in cake cutting is proportionality, which means that each agent should receive her proportionally fair share, i.e., $1/n$ of the agent’s value for the whole cake, where $n$ denotes the total number of agents. For any set of agents with arbitrary valuations, a proportional allocation in which each agent receives a single connected piece is guaranteed to exist. Better still, such an allocation can be found by a simple and efficient algorithm (Dubins and Spanier 1961).

In this paper, we initiate the study of cake cutting with separation requirements. Besides the social distancing example that we mentioned, our setting captures the task of allocating machine processing time, where we need time to erase data from the previous process before the next process can be started, as well as land division, where we want space between different plots in order to avoid cross-fertilization. When separation is imposed, it is no longer the case that proportionality can always be satisfied—an extreme example is when all agents value only a common small piece of length less than the minimum gap required. A similar failure of proportionality has notably been observed in the allocation of indivisible items (without separation), and a solution that has been proposed and widely studied in that context is maximin share fairness (Budish 2011; Kurokawa et al. 2018). Maximin share fairness requires each agent to receive her “maximin share” (MMS), which is the best share that the agent can secure by dividing the items into $n$ bundles and getting the worst bundle. In this work, we demonstrate that maximin share fairness is an appropriate substitute for proportionality in cake cutting with separation, and analyze this concept from a computational perspective. This is one of the first uses of maximin share fairness in cake cutting (see Section 1.2).

As is commonly done in cake cutting, we assume that the cake is represented by an interval, and each agent is to be allocated a single subinterval of the cake. We further require the pieces of any two agents to be separated by distance at least $s$, where $s>0$ is a given separation parameter. For the sake of exposition, we follow the convention in most of the literature and assume that the agents have additive valuations over the cake. However, as we discuss in Section 6, some of our positive results hold even for agents with arbitrary monotonic valuations.

In Section 3, we begin by proving that maximin share fairness can be guaranteed: there always exists an allocation that gives every agent at least her maximin share. If the maximin share of each agent is known, such an allocation can be found by a simple algorithm similar to the aforementioned algorithm by Dubins and Spanier 1961. Unfortunately, we show that no finite algorithm can compute the maximin share of an agent exactly in the standard Robertson–Webb model—this impossibility result holds even when $n=2$ and the agents have piecewise constant valuations. To establish this result, we prove that no finite number of queries can solve a basic function problem that we call FindSum1, which may be of independent interest. Nevertheless, we design an algorithm based on binary search that approximates the maximin share up to an arbitrarily small error. This enables us to compute an allocation wherein each agent obtains an arbitrarily close approximation of her maximin share. In addition, we present algorithms that decide whether the maximin share of an agent is greater than, less than, or equal to a given value, and show that if the agents have piecewise constant valuations that are given explicitly as part of the input, then we can compute their exact maximin shares, and therefore an MMS-fair allocation, in polynomial time using linear programming.

In Section 4, we consider the allocation of a “pie”, which is a one-dimensional circular cake and serves to model, for example, the streets around a city square, the shoreline of an island, or daily time slots for using a facility. In contrast to cake cutting, maximin share fairness cannot necessarily be guaranteed in pie cutting, and even the commonly studied cardinal multiplicative approximation cannot be obtained. Therefore, we focus instead on an ordinal relaxation of the maximin share, which allows each agent to partition the pie into $k$ pieces for some parameter $k>n$. We show that when $k=n+1$, the resulting fairness guarantee—called the $1$-out-of-$(n+1)$ maximin share—can be satisfied. We then investigate computational properties of maximin share fairness in pie cutting, and demonstrate several similarities and differences with cake cutting. In particular, while we can still approximate the maximin share of an agent (albeit less efficiently than in cake cutting), deciding whether the maximin share is greater than, less than, or equal to a given value is no longer possible for any finite algorithm. A summary of our results in Sections 3 and 4 can be found in Table 1.

Finally, in Section 5, we investigate two other important fairness notions: envy-freeness and equitability. While these notions can be satisfied trivially by not allocating any of the cake or pie, we show that there always exist allocations fulfilling each of these criteria while at the same time allocating the maximum possible amount of resource subject to separation constraints.

2 Related Work

Cake cutting has long been studied by mathematicians and economists, and more recently attracted substantial interest from computer scientists, as it suggests a plethora of computational challenges. In particular, a long line of work in the artificial intelligence community in recent years has focused on cake cutting and its variants (Balkanski et al. 2014; Li et al. 2015; Brânzei et al. 2016; Alijani et al. 2017; Bei et al. 2017; Menon and Larson 2017; Arunachaleswaran et al. 2019b; Hosseini et al. 2020).

In order to ensure that no agent receives a collection of tiny pieces, it is often assumed that each agent must be allocated a connected piece of the cake (Dubins and Spanier 1961; Stromquist 1980; Stromquist 2008; Su 1999; Bei et al. 2012; Cechlárová and Pillárová 2012; Cechlárová et al. 2013; Aumann and Dombb 2015; Arunachaleswaran et al. 2019a; Goldberg et al. 2020). Indeed, when we divide resources such as time or space, non-connected pieces (e.g., disconnected time intervals or land plots) may be hard to utilize, or even entirely useless. Note that we impose the connectivity constraint not only on the allocation but also in the definition of the maximin share benchmark. Similar conventions have been used in the context of indivisible items, where the items are vertices of an undirected graph and every agent must be allocated a connected subgraph (Bouveret et al. 2017; Igarashi and Peters 2019; Lonc and Truszczynski 2020; Bilò et al. 2022). Bei et al. 2022 explored the relations between the constrained and unconstrained versions of the maximin share in that context.

Most previous works on cake cutting (and pie cutting) did not explicitly consider the maximin share. This is because, with additive utilities, a proportional allocation is also an MMS-fair allocation, since each agent’s maximin share is always at most $1/n$ of the agent’s value for the entire cake (or pie). In particular, without separation constraints, classic algorithms for proportional cake cutting (Steinhaus 1948; Dubins and Spanier 1961; Even and Paz 1984) attain maximin share fairness. The maximin share only becomes interesting when a proportional allocation may not exist.

We are aware of two recent studies of the maximin share in cake cutting. Bogomolnaia and Moulin 2022 considered agents with general continuous valuations—not necessarily additive or even monotonic. They showed that the maximin share is not always attainable, but the minimax share (i.e., the worst-case share of an agent when the items are partitioned into $n$ bundles and the agent gets the best bundle) can always be guaranteed. Segal-Halevi 2021 showed that maximin share fairness can be attained when the cake is a collection of disconnected intervals and each agent should receive a connected piece. We are not aware of previous studies of maximin share fairness in pie cutting.

Iyer and Huhns 2005 presented negotiation protocols for fairly dividing a cake or a pie. Their protocols require each agent to submit a set of $n$ intervals (in cake division) or $n+1$ intervals (in pie division), and guarantee to each agent one of her intervals. While presented in a different framework, their protocols are similar in spirit to our algorithms for a cake (Theorem 3.1) and for a pie (Theorem 4.1). However, they did not consider separation, and focused on solution concepts other than the maximin share (indeed, recall that maximin share fairness is trivial in the absence of separation).

After the publication of the conference version of our work (Elkind et al. 2021a), we extended our study of separation constraints to the division of two-dimensional resources such as land (Elkind et al. 2021c) and graphical resources such as road networks (Elkind et al. 2021b). In particular, our guarantees for arbitrary graphs generalize Theorems 3.1 and 4.1 of the present paper, but the general algorithms and their analysis are much more involved. Apart from this, there is no overlap between these papers.

Preliminaries

Let $s\geq 0$ be a real parameter. We seek connected allocations in which any two pieces are separated by length at least $s$; we call such allocations $s$-separated. The case $s=0$ corresponds to the classic setting (without separation), and when $s\geq\frac{1}{n-1}$ an $s$-separated allocation must have at least one piece of length $0$. Therefore, from now on we assume that $s\in(0,\frac{1}{n-1})$. A set $\mathbf{P}=\{P_{1},\dots,P_{n}\}$ is an ($s$-separated) partition if the tuple $\mathbf{A}=(P_{1},\dots,P_{n})$ is an ($s$-separated) allocation; intuitively, a partition is a collection of pieces, without a specification of which agent gets which piece. Assume without loss of generality that in each partition the pieces $P_{1},\dots,P_{n}$ are listed in increasing order, i.e., for each $1\leq i<j\leq n$ we have $a\leq b$ for all $a\in P_{i}$, $b\in P_{j}$. The min-value of partition $\mathbf{P}$ for agent $i$ is defined as $\min_{j\in[n]}v_{i}(P_{j})$. Let $\Pi_{n,s}(x,y)$ denote the set of all $s$-separated partitions of the interval $[x,y]$ among $n$ agents (where $[x,y]\subseteq$). Note that an $s$-separated allocation or partition is incomplete, since some of the cake necessarily remains unallocated. An instance consists of the agents, cake, density functions, and a separation parameter.

A standard method for a cake-cutting algorithm to access agents’ valuations is through queries. Specifically, we use the model of Robertson and Webb 1998, which supports two types of queries:

$\textsc{Eval}_{i}(x,y)$: Asks agent $i$ to evaluate the interval $[x,y]$ and return the value $v_{i}(x,y)$.

$\textsc{Cut}_{i}(x,\alpha)$: Asks agent $i$ to return the leftmost point $y$ such that $v_{i}(x,y)=\alpha$, or to state that no such point exists.

We now define the main fairness criterion of our paper.

The maximin share of agent $i\in N$ with respect to an interval $[x,y]\subseteq$ is defined as

When $n$ and $s$ are clear from the context, we omit them from the notation and write $\text{MMS}_{i}(x,y)$ instead of $\text{MMS}_{i}^{n,s}(x,y)$. Moreover, when $[x,y]=$, we further abbreviate $\text{MMS}_{i}(x,y)$ to $\text{MMS}_{i}$.

Let $\Pi^{\prime}_{n,s}(x,y)\subseteq\Pi_{n,s}(x,y)$ be the set of all $s$-separated partitions of $[x,y]$ such that every pair of consecutive pieces is separated by length exactly $s$. We claim that the definition of the maximin share can be simplified by replacing $\Pi_{n,s}(x,y)$ with $\Pi^{\prime}_{n,s}(x,y)$; intuitively, for every partition in which the distance between some pair of adjacent pieces is larger than $s$, there is a partition with at least the same min-value in which the distance between all pairs of adjacent pieces is exactly $s$. We also claim that the supremum in the definition can be replaced with a maximum, i.e., a maximizing partition always exists.

Fix a partition $\mathbf{P}\in\Pi_{n,s}(x,y)$. Suppose that some pair of consecutive pieces of $\mathbf{P}$ is separated by length more than $s$. We can then extend one of these pieces so that they are separated by length exactly $s$. By doing so for all pairs of consecutive pieces, we obtain another partition $\mathbf{P}^{\prime}\in\Pi^{\prime}_{n,s}(x,y)$ such that $P_{j}\subseteq P^{\prime}_{j}$ for all $j\in[n]$. It follows that $\min_{j\in[n]}v_{i}(P^{\prime}_{j})\geq\min_{j\in[n]}v_{i}(P_{j})$, so in Definition 2.1 we may replace $\Pi_{n,s}(x,y)$ with $\Pi^{\prime}_{n,s}(x,y)$.

Next, we show that we can also replace $\sup$ with $\max$. Define

Intuitively, for each $i\in[n-1]$ the point $x_{i}$ is the right endpoint of the $i$-th interval in a partition where every two intervals are separated by exactly $s$ (so that the $(i+1)$-st interval starts at $x_{i}+s$). Let $g_{i}:B\to$ be a function defined by

From now on, we will work with this new definition of the maximin share. We say that an $s$-separated partition is a maximin partition for agent $i$ if every piece in the partition yields value at least $\text{MMS}^{n,s}_{i}$. Proposition 2.2 implies that every agent has at least one maximin partition. Similarly, an $s$-separated allocation $\mathbf{A}=(A_{1},\dots,A_{n})$ is said to be an MMS-fair allocation if $v_{i}(A_{i})\geq\text{MMS}^{n,s}_{i}$ for each $i\in N$.

Cake Cutting

In this section, we consider cake cutting with separation, both in the Robertson–Webb query model and in a model where the agents’ valuations are given explicitly.

We begin by showing that the maximin share is an appropriate fairness criterion in our setting: it is always possible to fulfill this criterion for every agent using a quadratic number of queries in the Robertson–Webb model. Our algorithm is similar to the famous Dubins–Spanier protocol for finding proportional allocations when separation is not required (Dubins and Spanier 1961): we process the cake from left to right and, at each stage, allocate a piece of cake to an agent who demands the smallest piece.

For any instance of cake cutting with separation, there exists an MMS-fair allocation. Moreover, given the maximin share of each agent, such an allocation can be computed using $O(n^{2})$ queries in the Robertson–Webb model.

If there are at least two agents present, we ask each agent $i$ to mark the leftmost point $x_{i}$ such that $v_{i}(0,x_{i})=\text{MMS}_{i}$. The agent who marks the leftmost $x_{i}$ is allocated the piece $[0,x_{i}]$ (with ties broken arbitrarily); we then remove this agent along with the piece $[x_{i},x_{i}+s]$, and recurse on the remaining agents and cake. If there is only one agent left, that agent receives all of the remaining cake. Since we make $n-j$ Cut queries when there are $n-j$ agents left (and no Eval queries), our algorithm uses $\sum_{j=0}^{n-2}(n-j)=O(n^{2})$ queries.

We now prove the correctness of the algorithm. Consider any agent $i$ and her maximin partition $\mathbf{P}=\{P_{1},\dots,P_{n}\}$. If agent $i$ receives the first piece allocated by the algorithm, she receives value $\text{MMS}_{i}$. Else, the allocated piece is no larger than $P_{1}$. Since the algorithm inserts a separator of length exactly $s$, the right endpoint of the first separator is either the same or to the left of the leftmost point of $P_{2}$. Applying a similar argument repeatedly, we find that if agent $i$ is not allocated any of the first $n-j$ pieces, where $j\in[n-1]$, then the remaining cake contains the last $j$ pieces of $\mathbf{P}$. In particular, for $j=1$ it follows that if agent $i$ receives the very last piece, she receives a value of at least $\text{MMS}_{i}$ in this case, too. ∎

The algorithm in Theorem 3.1 crucially relies on knowing the maximin share of each agent. Unfortunately, we show next that this knowledge is impossible to achieve in finite time, even if the valuations are piecewise constant but are not given explicitly as part of the input. Our result is similar in spirit to the non-finiteness results for connected envy-free cake cutting (Stromquist 2008), equitability with connected pieces (Cechlárová and Pillárová 2012; Brânzei and Nisan 2017) and with arbitrary pieces (Procaccia and Wang 2017), and average-proportionality (Segal-Halevi and Nitzan 2019). However, all previous impossibility results were for two or more agents with possibly different valuations. In contrast, our impossibility result is attained even for a single agent who wants to cut the cake into two $s$-separated pieces.

We prove the theorem by reducing from a more general problem, which may be of independent interest.

Problem FindSum1($s$), where $s\in[0,1)$ is a real parameter.

$g:\to$, a continuous monotonically increasing bijective function, specified by oracles that can answer two kinds of queries:

Given $\alpha\in$, what is $g^{-1}(\alpha)$?

Output:

A point $x_{0}\in[0,1-s]$ for which $g(x_{0})+g(x_{0}+s)=1$.

2 Explicit Piecewise Constant Valuations

Given an agent $i$ with a piecewise constant valuation function given explicitly, we can compute $\emph{MMS}^{n,s}_{i}$ in time polynomial in the size of the input.

At a high level, the proof of Theorem 3.10 proceeds by formulating a linear program whose solution corresponds to $\text{MMS}_{i}$. The challenge is that in order to have a linear program that returns a correct answer, we need to find out the intervals to which each endpoint of a maximin partition belongs. To accomplish this, we proceed from left to right, determining the interval for one endpoint at a time. By comparing the maximin shares between optimal subpartitions to the left and right of the potential intervals to which the next endpoint belongs, we ensure that at each step of the algorithm, there exists a maximin partition whose endpoints are consistent with the intervals we have chosen. The full details of the algorithm are rather involved; we defer them to Appendix A.

Combined with Theorem 3.1, Theorem 3.10 implies that when agents have piecewise constant valuations given explicitly, an MMS-fair allocation can be computed efficiently (cf. Corollary 3.4).

For agents with piecewise constant valuations given explicitly, an MMS-fair allocation can be computed in time polynomial in the size of the input.

Pie Cutting

In the canonical model of cake cutting, the cake is assumed to be linear. By contrast, in this section we assume that it is circular. In other words, our resource is represented by the interval $$ with its two endpoints identified with each other. The respective division problem is known in the literature as pie cutting; its applications include dividing the shoreline of an island among its inhabitants and splitting a daily cycle for using a facility (Thomson 2007; Brams et al. 2008; Barbanel et al. 2009).

The definitions of $s$-separated partitions and allocations can be readily adjusted to pie cutting—the only difference is that, due to the circular structure, there are $n$ separators in pie cutting rather than $n-1$ (so we assume that $s<1/n$). Note that, since the pie is one-dimensional, distances are measured along the circumference of the pie. We denote by $\Pi_{n,s}$ the set of $s$-separated partitions with respect to the pie, and by $\Pi^{\prime}_{n,s}\subseteq\Pi_{n,s}$ the subset of partitions for which every pair of consecutive pieces is separated by length exactly $s$. We number the parts in a partition in the clockwise order starting from $0$: that is, point $0$ is either contained in the first part or in the separator between the $n$-th part and the first part. The maximin share can then be defined similarly to how it is defined in cake cutting (Definition 2.1); just as in Proposition 2.2, we can show that $\text{MMS}^{n,s}_{i}=\max_{\mathbf{P}\in\Pi^{\prime}_{n,s}}\min_{j\in[n]}v_{i}(P_{j})$.

However, in pie cutting, unlike in cake cutting, an MMS-fair allocation does not necessarily exist. This is evident in the example in Figure 1, where $1/4<s<1/2$, $0<\varepsilon<\min\{s-1/4,1/2-s\}$, and Alice values the pieces of length $\varepsilon$ centered at the top and bottom of the pie at $1/2$ each, while Bob values similar pieces on the left and right at $1/2$ each. Since $s<1/2-\varepsilon$, the maximin share of each agent is $1/2$. However, since the distance between any point in Alice’s piece and any point in Bob’s piece is at most $1/4+\varepsilon<s$, no $s$-separated allocation gives both agents a positive value. Hence, no MMS-fair allocation exists.

It turns out that this relaxation is precisely what we need for pie cutting.

For any pie cutting instance with $n$ agents, there exists an allocation in which every agent $i$ receives a piece of value at least $\emph{MMS}^{n+1}_{i}$. Moreover, given the $1$-out-of-$(n+1)$ maximin share of each agent, such an allocation can be computed using $O(n^{2})$ queries in the Robertson–Webb model.

The idea behind our algorithm is similar to that of the analogous result for cake cutting (Theorem 3.1). Note, however, that in case of a pie there is no natural starting point; in particular, by starting at $0$, we may destroy one of the pieces in each agent’s partition. This is why we need $n+1$ pieces in the partition rather than $n$.

We ask each agent $i$ to mark the leftmost point $x_{i}$ (i.e., the first such point when moving clockwise from $0$) such that $v_{i}(0,x_{i})=\text{MMS}^{n+1}_{i}$. The agent who marks the leftmost $x_{i}$ is allocated the piece $[0,x_{i}]$ (with ties broken arbitrarily); we then remove this agent along with the piece $[x_{i},x_{i}+s]$, and recurse on the remaining agents and pie. If there is only one agent left, we still allocate to that agent a piece worth $\text{MMS}^{n+1}_{i}$ (rather than the entire remaining pie). Since we make $n-j$ Cut queries when there are $n-j$ agents left (and no Eval queries), our algorithm uses $\sum_{j=0}^{n-1}(n-j)=O(n^{2})$ queries.

We now prove the correctness of the algorithm. Consider any agent $i$ and her $1$-out-of-$(n+1)$ maximin partition $\mathbf{P}=\{P_{1},\dots,P_{n+1}\}$. For $j\in[n]$, let $Q_{j}=P_{j+1}$ if $0$ is in the interior of $P_{1}$, and $Q_{j}=P_{j}$ otherwise; we will write $Q_{j}=[x_{j},y_{j}]$. Note that the segment $[0,y_{j}]$ contains $j$ parts of $\mathbf{P}$. If agent $i$ receives the first piece allocated by the algorithm, she receives value $\text{MMS}^{n+1}_{i}$. Else, the right endpoint of the allocated piece is no further to the right than $y_{1}$. Since the algorithm inserts a separator of length exactly $s$, the right endpoint of the first separator is no further to the right than $x_{2}$. Applying a similar argument repeatedly, we find that if agent $i$ is not allocated any of the first $n-1$ pieces, then after removing the $(n-1)$-st piece and the following separator, the remaining cake contains $Q_{n}$. Now, if $0$ is in the interior of $P_{1}$, then the remaining cake also contains a positive amount of $P_{1}$ as well as the separator between $P_{n+1}=Q_{n}$ and $P_{1}$. On the other hand, if $0$ is not in the interior of $P_{1}$, then $Q_{n}=P_{n}$ and the remaining cake contains $P_{n+1}$ as well as the separator between $P_{n}$ and $P_{n+1}$. In either case, the remaining cake contains $Q_{n}$ as well as the separator that comes after $Q_{n}$. Hence, if we allocate a piece of value $\text{MMS}^{n+1}_{i}$ to $i$, its right endpoint is no further to the right than $y_{n}$ and thus the remaining cake contains an unallocated segment of length $s$, which will serve as a separator between the piece that was allocated first and the piece that was allocated last. It follows that in either case the resulting allocation is $s$-separated. ∎

Recall that for cake cutting there exists an algorithm that, given an agent $i$ and a number $r$, decides whether $\text{MMS}_{i}>r$ and whether $\text{MMS}_{i}=r$ (Theorem 3.8 and Corollary 3.9). In contrast, for pie cutting this is not the case.

Fix any $k\geq 2$. For pie cutting, there is no finite algorithm in the Robertson–Webb model that can decide, for any agent $i$ and real number $r$, whether $\emph{MMS}^{k}_{i}>r$ or whether $\emph{MMS}^{k}_{i}=r$, even when the valuation of this agent is piecewise constant (but not given explicitly).

Assume for contradiction that such an algorithm exists, and take $r=\frac{1}{k}-s$. We show how an adversary can answer the queries of the algorithm in such a way that after a finite number of queries, there exists a piecewise constant valuation function consistent with the answers for which $\text{MMS}^{k}_{i}>r$, but also one for which $\text{MMS}^{k}_{i}=r$.

The adversary records any point that appears in a query or in its own answer, and answers queries as if the valuation is uniform throughout the pie—that is, for any two consecutive recorded points on the pie, if the interval between them has length $t$, then it also has value $t$. Suppose that some finite number of queries have been answered in this manner, and consider the following two possibilities:

Possibility 1: The entire valuation function is uniform. For any $s$-separated partition $\mathbf{P}$, the sum of the lengths of the $k$ pieces in $\mathbf{P}$ is at most $1-ks$, so one of the pieces has length (and value) at most $\frac{1-ks}{k}=r$. On the other hand, there exists an $s$-separated partition $\mathbf{P}^{\prime}$ such that each of the $k$ pieces in $\mathbf{P}^{\prime}$ has length $r$. Hence $\text{MMS}^{k}_{i}=r$ in this case.

Possibility 2: Consider all $s$-separated $k$-partitions in which each of the $k$ pieces has length $r$. Among all such partitions, choose a partition $\mathbf{P}$ for which none of the $2k$ endpoints of the pieces coincides with any recorded point; since there are infinitely many partitions and only a finite number of them are forbidden, this choice is possible. If a piece or a separator does not contain a recorded point, record an arbitrary point in its interior. This ensures that each interval between two recorded points contains at most one endpoint of $\mathbf{P}$. Now, for each interval $I$ of length $z$ containing an endpoint of $\mathbf{P}$, distribute a value of $z$ uniformly within the intersection of $I$ with the associated piece of $\mathbf{P}$, so the intersection of $I$ and the associated separator has value zero. For the remaining intervals, their value (which is equal to their length) is distributed uniformly within the interval. The resulting valuation function is piecewise constant, and each of the $k$ pieces of $\mathbf{P}$ has value strictly greater than $r$. Hence $\text{MMS}^{k}_{i}>r$.

We conclude that a finite algorithm cannot distinguish between the case $\text{MMS}^{k}_{i}>r$ and the case $\text{MMS}^{k}_{i}=r$. ∎

Theorem 4.2 leaves open the question of whether it is possible to decide whether $\text{MMS}^{k}_{i}\geq r$ for a given $r$. We show next that the answer to this question, too, is negative. We do so by reducing from the following problem, which may be of independent interest.

Problem HasLowValue($s,q$), where $s,q\in[0,1)$.

A valuation function $v$ on a pie $$, accessible through Cut and Eval queries.

Output:

Yes if the pie contains an interval of length $s$ with value at most $q$, i.e., there is an $x_{0}\in$ for which $v(x_{0},x_{0}+s)\leq q$, where $x_{0}+s$ is computed modulo $1$.

Envy-Freeness and Equitability

In this section, we focus on two other well-studied fairness notions: envy-freeness and equitability.

An allocation $\mathbf{A}=(A_{1},\dots,A_{n})$ is said to be envy-free if $v_{i}(A_{i})\geq v_{i}(A_{j})$ for all $i,j\in N$.

An allocation $\mathbf{A}=(A_{1},\dots,A_{n})$ is said to be equitable if $v_{i}(A_{i})=v_{j}(A_{j})$ for all $i,j\in N$.

An empty allocation is trivially envy-free and equitable, but leaves every agent empty-handed. Thus, envy-freeness and equitability should be combined with other axioms that discourage discarding the entire cake. To this end, we will now define a class of allocations (and partitions) that do not waste the cake needlessly.

Given a separation parameter $s$, we say that an allocation or partition is exactly $s$-separated if any two consecutive pieces are separated by length exactly $s$ (and in case of a cake, the first piece starts at $0$, while the last piece ends at $1$).

We note that an envy-free or equitable allocation that is exactly $s$-separated may still leave all agents with zero value: for example, this can happen if all agents have identical valuations and their entire value is packed within an interval of length at most $s$.

The first question we investigate is whether an exactly $s$-separated envy-free or equitable allocation always exists. We first consider cake cutting and answer this question in the affirmative for both notions, by adapting the arguments of Simmons (Su 1999) and Chèze 2017 from the setting without the separation requirement. Since the former argument is well-known in the fair division literature, we only present a sketch here and refer to Section 3 of Su’s paper for more details.

For any cake cutting instance, there exists an exactly $s$-separated envy-free allocation.

$b_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>b</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">b_{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8444em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>b_{3}$ Consider a triangulation of this simplex by barycentric subdivision, and assign each vertex of this triangulation to one of the agents, so that for each small subsimplex it holds that each agent is assigned exactly one vertex of this subsimplex. (See Section 4 of Su 1999’s paper for details on this step.) Label each vertex with the index of its assigned agent’s favorite piece in the corresponding partition. If the agent has two or more favorite pieces in the partition, then choose one such piece arbitrarily, as long as it is non-empty. Note that for every vertex its corresponding partition contains at least one non-empty piece, because of the assumption that $s<\frac{1}{n-1}$. Moreover, since the valuations are monotonic, each agent has at least one non-empty favorite piece. Therefore, this tie-breaker is feasible. The tie-breaker ensures that the resulting labeling satisfies the conditions of Sperner’s lemma: each vertex is labeled with an index of a non-zero coordinate. Therefore, the triangulation has a Sperner subsimplex—a subsimplex all of whose labels are different. Repeating this process with finer triangulations gives an infinite sequence of smaller Sperner subsimplices. This sequence has a subsequence that converges to a single point. By the continuity of valuations, this limit point corresponds to a partition in which each agent prefers a different piece, thereby inducing an envy-free allocation. ∎

Next, we adapt the proof of Chèze 2017 to show the existence of an equitable allocation. Unlike for envy-freeness, for equitability we can additionally choose the order in which the agents are allocated pieces of the cake from left to right.

For any cake cutting instance and any ordering of the agents, there exists an equitable exactly $s$-separated allocation in which the agents are allocated the pieces from left to right according to the ordering.

Assume without loss of generality that the desired agent ordering is $1,2,\dots,n$. Recall that the density function of agent $i$ is $f_{i}$. Consider the sphere

The function $g$ is continuous, so by the Borsuk–Ulam theorem, there exists $\hat{e}\in S^{n-1}$ such that $g(-\hat{e})=g(\hat{e})$. Moreover, one can check that $g(-e)=-g(e)$ for all $e\in S^{n-1}$, and in particular $g(-\hat{e})=-g(\hat{e})$. Hence $g(\hat{e})$ is the zero vector, meaning that

for every $i=1,2,\dots,n-1$. Since both integrals are nonnegative, it must be the case that

for each $i$. It follows that if we allocate the piece between $\hat{e}_{1}^{2}+\dots+\hat{e}_{i-1}^{2}+(i-1)s$ and $\hat{e}_{1}^{2}+\dots+\hat{e}_{i-1}^{2}+\hat{e}_{i}^{2}+(i-1)s$ to agent $i$, we obtain an equitable exactly $s$-separated allocation. ∎

The existence guarantees carry over to pie cutting. Indeed, in order to obtain an envy-free (respectively, equitable) exactly $s$-separated allocation, we can simply insert a separator of length $s$ at an arbitrary position in the pie and apply Theorem 5.4 (respectively, Theorem 5.5) on the remaining pie (treated as a cake).

We now explore the relationship between envy-freeness/equitability and maximin share fairness. Without separation, it is known that any complete envy-free allocation is proportional, and hence also MMS-fair. In Theorem 5.7, we generalize this observation to the setting with separation. For this, we need the following lemma.

(a) In any exactly $s$-separated partition of a cake into $n$ pieces, each agent $i$ has value at least $\emph{MMS}_{i}^{n,s}$ for at least one piece.

(b) In any exactly $s$-separated partition of a pie into $n$ pieces, each agent $i$ has value at least $\emph{MMS}_{i}^{n+1,s}$ for at least one piece.

(a) We can represent an exactly $s$-separated partition $\mathbf{P}=\{P_{1},\dots,P_{n}\}$ as a list $(x_{0},x_{1},\dots,x_{n})$ where $x_{0}=-s$ and $x_{n}=1$, so that $P_{j}=[x_{j-1}+s,x_{j}]$ for each $j\in[n]$. Now, fix an arbitrary partition $\mathbf{P}$ represented as $(z_{0},z_{1},\dots,z_{n})$, and let $(y_{0},y_{1},\dots,y_{n})$ represent some exactly $s$-separated maximin partition of agent $i$ (such a partition exists by Proposition 2.2). Mark each integer $j\in\{0,\ldots,n\}$ by $L$ if $z_{j}\leq y_{j}$ and by $R$ if $z_{j}\geq y_{j}$. Note that $0$ and $n$ are marked both $L$ and $R$. Therefore, there exists at least one $j\in[n]$ such that $j-1$ is marked $L$ and $j$ is marked $R$. This means that the piece $[z_{j-1}+s,z_{j}]$ contains the piece $[y_{j-1}+s,y_{j}]$, whose value is at least $\text{MMS}_{i}^{n,s}$ since it is a piece in a maximin partition.

(b) Consider an exactly $s$-separated partition $\mathbf{P}=\{P_{1},\dots,P_{n}\}$ of the pie. We can assume without loss of generality that the leftmost point of $P_{1}$ is $0$ and hence the rightmost point of $P_{n}$ is $1-s$. Let $\mathbf{P}^{\prime}$ be some exactly $s$-separated $1$-out-of-$(n+1)$ maximin partition of the pie. Remove from the pie the interval $[1-s,1]$, and remove from $\mathbf{P}^{\prime}$ the (at most one) part that overlaps $[1-s,1]$; if no such part exists, remove a part closest to $[1-s,1]$. Extend the parts adjacent to the removed part so that one of them starts at $0$ and the other one ends at $1-s$. The resulting partition $\mathbf{P}^{\prime\prime}$ has $n$ parts, with the first part starting at $0$ and the last part ending at $1-s$, and the value of each part is at least $\textrm{MMS}_{i}^{n+1,s}$. Now, the situation (restricted to $[0,1-s]$) is exactly as in part (a), and the same proof shows that at least one part of $\mathbf{P}$ contains a part of $\mathbf{P}^{\prime\prime}$. ∎

The guarantee in part (b) cannot be improved to $\text{MMS}_{i}^{n,s}$. Indeed, consider Figure 1 with $s=1/2-\varepsilon$. For Alice each of the two parts of length $\varepsilon$ in the left figure has value $1/2$, which means that $\text{MMS}_{\textrm{Alice}}^{n,s}=1/2$, while each of the two parts of length $\varepsilon$ in the right figure has value $0$ to her.

In any exactly $s$-separated envy-free allocation, the value of each agent $i$ is

(a) at least $\emph{MMS}_{i}^{n,s}$ in case of a cake;

(b) at least $\emph{MMS}_{i}^{n+1,s}$ in case of a pie.

In any envy-free allocation, the piece allocated to agent $i$ is at least as valuable to $i$ as each of the $n$ pieces in the allocation. Therefore, by Lemma 5.6, this allocated piece yields value at least $\text{MMS}_{i}^{n,s}$ in case of a cake and $\text{MMS}_{i}^{n+1,s}$ in case of a pie. ∎

Similarly to the example following Lemma 5.6, the bound $\text{MMS}_{i}^{n+1,s}$ in part (b) cannot be improved to $\text{MMS}_{i}^{n,s}$.

2 Computation

Having established that envy-free/equitable exactly $s$-separated allocations of a cake always exist, it is natural to ask whether they can be computed by a finite algorithm. Unfortunately, it turns out that the answer to this question is ‘no’. We will show that this is the case even when there are only two agents with identical valuations; note that in this case an exactly $s$-separated allocation is envy-free if and only if both parts have exactly the same value, so in particular envy-freeness is equivalent to equitability.

The argument for the case of cake is simple: by Theorem 5.7, if we could compute an envy-free (or, equivalently, equitable) allocation in this setting, we could also deduce the maximin share with respect to the common valuation, thereby contradicting Theorem 3.2.

For cake cutting, there is no algorithm that can always compute an envy-free or an equitable exactly $s$-separated allocation by asking the agents a finite number of Robertson–Webb queries. This holds even when $n=2$ and the agents’ valuations are identical, piecewise constant, and strictly positive (but not given explicitly).

These impossibilities stand in stark contrast to the canonical setting without separation: in that setting, with two agents, an envy-free allocation for non-identical valuations and an equitable allocation for identical valuations can be found by a simple cut-and-choose algorithm.

Regarding pie cutting, it is possible to show that no finite algorithm can compute an envy-free/equitable allocation for two identical agents, by modifying the proof of Theorem 3.2. We cannot prove the impossibility by reducing from Theorem 4.2, since an envy-free or equitable division of a pie into $n$ pieces, even with identical valuations, is not necessarily 1-out-of-$n$ MMS-fair. In particular, the adversary can answer the queries made by the algorithm in such a way that after any finite number of queries, the algorithm cannot identify an exactly $s$-separated partition in which the two pieces have the same value based on the given answers.

For pie cutting, there is no algorithm that can always compute an envy-free or an equitable exactly $s$-separated allocation by asking the agents a finite number of Robertson–Webb queries. This holds even when $n=2$ and the agents’ valuations are identical, piecewise constant, and strictly positive (but not given explicitly).

In light of Corollary 5.8 and Theorem 5.9, it would be interesting to develop approximation algorithms that compute allocations with low envy—this direction has been recently pursued in cake cutting without separation (Arunachaleswaran et al. 2019a; Goldberg et al. 2020).

Conclusion and Future Work

In this paper, we have initiated the study of cake cutting under separation requirements, which capture scenarios including data erasure in machine processing, cross-fertilization prevention in land allocation, as well as social distancing. We established several existence and computational results concerning maximin share fairness, both positive and negative. Overall, our results indicate that maximin share fairness is an appropriate substitute for proportionality in this setting.

We end the paper with a number of directions for future work.

Can we improve the query complexity bounds in our results, or establish matching lower bounds? A particularly interesting question concerns Theorem 3.1, where we presented an algorithm that computes an MMS-fair allocation using $O(n^{2})$ queries given the agents’ maximin shares. Without separation, it is well-known that a proportional allocation can be found using $O(n\log n)$ queries via a divide-and-conquer approach (Even and Paz 1984), and that this is tight (Woeginger and Sgall 2007; Edmonds and Pruhs 2011). What is the optimal query complexity of computing an MMS-fair allocation in our setting?

While the canonical maximin share is a reasonable fairness requirement when agents have equal entitlements to the resource, in certain situations the agents may be endowed with different entitlements (Barbanel 1995; Cseh and Fleiner 2020; Chakraborty et al. 2021a; Chakraborty et al. 2021b). Various extensions of the maximin share have been proposed (Aziz et al. 2019; Farhadi et al. 2019; Babaioff et al. 2021; Chakraborty et al. 2022), and it may be interesting to study them in the context of cake cutting with separation. For different entitlements, a connected cake allocation may not exist even without separation (Segal-Halevi 2019; Crew et al. 2020).

What happens if we do not require each agent to receive a single connected piece, but instead allow up to $t$ connected pieces for some parameter $t$? When $t=2$, the analog of Theorem 3.1 no longer holds: one can check that the valuation functions in Figure 4 do not admit an MMS-fair allocation. It remains open whether any (ordinal or cardinal) approximation of the maximin share can be attained.

Prior work has explored the combination of fairness and economic efficiency in cake cutting without separation (Bei et al. 2012; Aumann et al. 2013; Arunachaleswaran et al. 2019a). With separation, can we achieve maximin share fairness along with certain notions of efficiency, for instance, minimizing the value of the unallocated cake? Note that maximin share fairness is always compatible with Pareto efficiency, since a Pareto improvement of an MMS-fair allocation is again MMS-fair.

At a higher level, separation requirements represent one type of constraints that arise in a number of applications of cake cutting. In other applications, it may be desirable to limit the amount of cake that certain agents receive, or ensure that the cake is allocated to agents in a given order. Suksompong 2021 surveyed different types of constraints in fair division. Examining the interplay between such constraints and fairness considerations is an important direction that will likely lead to fruitful research.

Acknowledgments

This work was partially supported by the European Research Council (ERC) under grant number 639945 (ACCORD), by the Israel Science Foundation under grant number 712/20, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and by an NUS Start-up Grant. Part of the work was done while the third author was a postdoctoral researcher at the University of Oxford. We would like to thank Iosif Pinelis, Fedor Petrov, Jochen Wengenroth, and Dieter Kadelka for their mathematical help, and the anonymous reviewers of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021) and Artificial Intelligence Journal for their valuable comments.

References

Appendix A Proof of Theorem 3.10

Let $v$ be the piecewise constant valuation function of agent $i$, described by a list of breakpoints $(p_{0},p_{1},\dots,p_{d})$ with $p_{0}=0$, $p_{d}=1$, and a list of densities $(\gamma_{1},\dots,\gamma_{d})$. For readability, we set $I_{j}:=[p_{j-1},p_{j}]$ for each $j\in[d]$, as illustrated below:

$y^{\prime}$ In what follows, we depart from the notation used in the remainder of the paper and represent an $s$-separated partition of $$into$n$parts as$(x_{0},x_{1},\dots,x_{n})$where$x_{0}=-s$and$x_{n}=1$, so that the$k$-th part of the partition is given by$[x_{k-1}+s,x_{k}]$.

Program $\text{LP}_{k}({\mathcal{I}}_{k},t)$:

To see that this approach is correct, consider two $s$-separated maximin partitions of $$, which we denote by$(x^{-}_{0},\dots,x^{-}_{n})$and$(x^{+}_{0},\dots,x^{+}_{n})$: these partitions are chosen so that for every$s$-separated maximin partition$(x_{0},\dots,x_{n})$of$$we have$x^{-}_{1}\leq x_{1}\leq x^{+}_{1}$. (These two partitions may coincide.) Since$c^{*}>0$, we have$0$and$x^{+}_{1}<1$. Suppose that$p_{j^{-}-1}$and$p_{j^{+}-1}\leq x^{+}_{1}$for some$j^{-},j^{+}\in[d]$. For every$z\in[x^{-}_{1},x^{+}_{1}]$, the partition$(x^{-}_{0},z,x^{+}_{2},\dots,x^{+}_{n})$is also an$s$-separated maximin partition of$$. Thus, for every$j$such that$j^{-}\leq j\leq j^{+}$, there exists an$s$-separated maximin partition of$$such that the right endpoint of the first part lies in$I_{j}$, i.e., any such choice of$j$is suitable for$r(1)$; we will argue that our algorithm selects$r(1)$so that$j^{-}\leq r(1)\leq j^{+}$.

$x_{1}^{-}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msubsup><mi>x</mi><mn>1</mn><mo lspace="0em" rspace="0em">+</mo></msubsup></mrow><annotation encoding="application/x-tex">x_{1}^{+}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0778em;vertical-align:-0.2564em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8213em;"><span style="top:-2.4436em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">+</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.2564em;"><span></span></span></span></span></span></span></span></span></span></span>z$ Indeed, by our choice of $x^{-}_{1}$ we have $v(0,x^{-}_{1})=c^{*}$: if $v(0,x^{-}_{1})<c^{*}$, then the value of the first part is less than $c^{*}$, and if $v(0,x^{-}_{1})>c^{*}$, we can find an $x<x^{-}_{1}$ with $v(0,x)=c^{*}$, a contradiction with our choice of $x^{-}_{1}$. By the same argument, $v(0,x)<v(0,x^{-}_{1})=c^{*}$ for every $x<x^{-}_{1}$ and hence $v(0,p_{j^{\prime}})<c^{*}$ for every $j^{\prime}<j^{-}$. On the other hand, for $j^{\prime}<j^{-}$, $[p_{j^{\prime}}+s,1]$ is a superset of $[x^{-}_{1}+s,1]$ and hence $\text{MMS}_{i}^{n-1,s}(p_{j^{\prime}}+s,1)\geq c^{*}$. Thus, $r(1)\geq j^{-}$. By a similar argument, $v(0,p_{j^{+}})\geq v(0,x^{+}_{1})\geq c^{*}$. Further, if $\text{MMS}_{i}^{n-1,s}(p_{j^{+}}+s,1)\geq c^{*}$, then, by combining the corresponding maximin partition with $[0,p_{j^{+}}]$, we obtain an $s$-separated partition of $$into$n$parts such that the value of each part is at least$c^{*}$and the first part ends at$p_{j^{+}}>x^{+}_{1}$, a contradiction with our choice of$x^{+}_{1}$. Thus, no such partition of$[p_{j^{+}},1]$exists and hence our algorithm selects$r(1)\leq j^{+}$. This concludes the proof for$k=1$.

To see the correctness of our approach, first observe that it suffices to restrict our attention to the intervals in $\mathcal{L}$. Indeed, for every maximin partition $(x_{0},\dots,x_{n})$ that is consistent with ${\mathcal{I}}_{k-1}$ we have $x_{k-1}\in I_{r(k-1)}$, and hence $p_{r(k-1)-1}+s\leq x_{k-1}+s\leq p_{r(k-1)}+s$. Thus, $x_{k-1}+s$ has to be contained in an interval $I_{j}$ such that $I_{j}\cap[p_{r(k-1)-1}+s,p_{r(k-1)}+s]\neq\emptyset$.