Efficient cake-cutting

There is a cake ${\displaystyle C}$. It is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane ${\displaystyle \mathbb {R} ^{d}}$.

There are ${\displaystyle n}$ partners. Each partner ${\displaystyle i}$ has a subjective value function ${\displaystyle V_{i}}$ which maps subsets of ${\displaystyle C}$ to numbers.

${\displaystyle C}$ has to be divided into ${\displaystyle n}$ disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person ${\displaystyle i}$ is called ${\displaystyle X_{i}}$, so that ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$.

In the following lines we consider a cake with four parts: chocolate, vanilla, lemon and sugar, and two agents: Alice and George, with the following valuations:

An allocation ${\displaystyle X}$is called wasteful if it allocates to some agent a piece that is worth 0 to that agent but worth more than 0 to another agent. In symbols:

${\displaystyle \exists {i,j}:\exists Z\subseteq X_{i}:V_{i}(Z)=0~~{\text{and}}~~V_{j}(Z)>0}$ and ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$.

Otherwise it is called non-wasteful (NW). In the example cake, an allocation giving all the cake to Alice is NW, but an allocation giving all the cake to George is wasteful since the lemon part is "wasted". There are many other NW allocations, for example, giving the chocolate to George and the remaining cake to Alice is NW.

An allocation ${\displaystyle Y}$ Pareto-dominates an allocation ${\displaystyle X}$, if at least one person feels that ${\displaystyle Y}$ is better than ${\displaystyle X}$, and no person feels that ${\displaystyle Y}$ is worse than ${\displaystyle X}$. In symbols:

${\displaystyle \forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})}$ and ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$

An allocation ${\displaystyle X}$is called Pareto optimal (PO) if it is not Pareto-dominated by any other division, i.e., it cannot be improved without objection. In the example cake, giving the entire cake to Alice is PO, but giving the entire cake to Bob is Pareto-dominated by the allocation where the lemon part is given to Alice. In general (when there are no connectivity requirements on the pieces), every wasteful allocation is Pareto-dominated, therefore every PO allocation is NW. However, the opposite is not true. For example, the allocation giving the chocolate to George and the remaining cake to Alice is NW but it is not PO - it is Pareto-dominated by the allocation giving to George the vanilla and half the chocolate. This is because, in the original allocation the utilities of (Alice, George) are (3, 6), while in the alternative allocation the utilities are (5.5, 7).

Efficient allocations always exist. For example, every utilitarian-optimal cake-cutting is PO, hence also NW.

However, finding such allocations may be hard. It may be impossible to find a NW cake-allocation using a finite number of "mark" and "eval" queries, even if there are only two agents with piecewise-uniform valuations.[1]^{: 9, Clm.3} This is because, after any finite number of such queries, the algorithm has information regarding only a finite number of intervals, and thus it cannot prevent waste inside the intervals: for any allocation of an interval to an agent, it is possible that this agent values a part of this interval at 0 while the other agent values the same part at 1. Hence, PO too is not attainable by a finite protocol.[2]^{: 560, Thm.5}

The problem becomes easy under the assumption of strict positivity (each agent values each point of the cake at strictly more than 0): every allocation is trivially NW, and every allocation that gives all the cake to a single agent is trivially PO (since every other allocation gives this agent strictly lower utility).

The problem is also easy for an algorithm that uses direct revelation instead of queries. In a direct revelation algorithm, each agent reveals his/her entire valuation function to the algorithm; this is possible, for example, with piecewise-constant valuations. With direct revelation, it is easy to find a utilitarian-optimal allocation (by giving each piece to an agent who values it the most), and such an allocation is also PO and NW.

Often, it is required to find an allocation that is not only efficient but also fair according to various fairness notions. Existence still holds:

• A PO allocation that is also proportional always exists. For example, an allocation maximizing the sum of values subject to proportionality always exists (since the set of all proportional allocations is compact), and it is PO (since proportionality is preserved by Pareto improvements).
• Moreover, a PO allocation that is also envy-free always exists. This does not follow directly from the above argument, since envy-freeness is not preserved by Pareto improvements. However, it is proved explicitly as Weller's theorem.

Finding such allocations may be hard even with strictly-positive valuations, depending on the computational model:

• In the query model, no finite algorithm that gives each agent a positive fraction of the cake can be PO, even with only two agents with strictly-positive valuations. This is because a finite algorithm always knows the values of finitely many intervals, so it cannot avoid inefficiencies inside intervals: for any allocation of the intervals, there may be a profitable exchange of sub-intervals that the algorithm cannot detect.
• In the direct revelation model (with piecewise-constant valuations), the Market Equilibrium Algorithm[3] yields a PO and envy-free (hence proportional) allocation in polynomial time for any number of agents.

Often, in addition to efficient and fairness, there are geometric constraints on the pieces. For example, if the cake is an interval, then each agent may require a piece that is a contiguous interval. With this additional requirement:

• A PO allocation that is also proportional still always exists. This is because the set of all proportional contiguous allocations is still compact, and proportionality is still preserved by Pareto improvements.
• A PO allocation that is also envy-free might not exist when there are at least three agents, even if they have piecewise-constant valuations.[4]^{: Example 5.1}

From a computational perspective:

• With general valuations, when the value-densities are strictly positive, divide and choose is PO and proportional for two agents. Suppose w.l.o.g. that Alice cuts, George chooses the leftmost piece and Alice gets the rightmost piece. Any alternative allocation where George gets the left and Alice gets the right cannot be a Pareto improvement, as (by the assumption of strict positivity) any movement of the cut location to the left hurts George, and any movement to the right hurts Alice. Any alternative allocation where George gets the right and Alice gets the left cannot be a Pareto improvement, since in any such allocation, at least one of them must get less than 1/2 of the total value, while in the original allocation both get at least 1/2.
• With piecewise-constant valuations, the Market Equilibrium Algorithm does not necessarily produce connected pieces, so it does not work. However, an algorithm similar to [5]^{: 317, Thm.5} can be used to find a proportional allocation that maximizes the sum of utilities for any number of agents, by solving ${\displaystyle O(m^{n})}$ linear programs (where m is the number of pieces).

It is currently not known whether, for 3 or more agents with strictly-positive valuations, a connected proportional PO allocation can be found using a finite number of queries (in the query model) or using a polynomial algorithm (in the direct revelation model).

• Utilitarian cake-cutting
• Fair cake-cutting
• Price of fairness