Efficient cake-cutting is a problem in economics and computer science.
It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value.
Several notions of efficiency have been studied: Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria.
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
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".
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.
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.
For example, every utilitarian-optimal cake-cutting is PO, hence also NW.
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.
Existence still holds: Finding such allocations may be hard even with strictly-positive valuations, depending on the computational model: Often, in addition to efficient and fairness, there are geometric constraints on the pieces.
With this additional requirement: From a computational perspective: 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).
If the cake is a 1-dimensional interval and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PO (note that this is not true if the agents may receive disconnected pieces).
Hence, in this case, the Simmons–Su protocols create a PO+EF division.
If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE.
Additionally, there are pairs of (non-additive) value functions for which no PO+EF division exists.
However, if there are 2 agents and at least one of them has an additive value function, then a PO+EF division exists.