Efficient cake-cutting is a problem in economics and computer science. It involves a heterogenous 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. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The division should be Pareto-efficient.
Contents
Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria.
Assumptions
There is a cake
There are
Example cake
In the following lines we consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations:
Efficiency
A division
A Pareto efficient (PE) division is a division that is not Pareto-dominated by any other division, i.e., it cannot be improved without objection. In the example cake, many PE divisions are possible. For example, every division that gives the entire cake to a single person is PE, since every change in the division will raise the objection of that single person. Of course a PE division is not necessarily fair.
A division that is both Pareto-efficient and proportional will be called PEPR and a division that is both PE and envy-free will be called PEEF for short.
PEPR division
A PE division can be achieved trivially by giving the entire cake to a single partner. But, a PE division which is also proportional cannot be found by a finite algorithm. The proof is essentially the same as for utilitarian-maximal divisions.
PEEF division
For n partners with additive value functions, when pieces may be disconnected, a PEEF division always exists. This is Weller's theorem.
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 PE (note that this is not true if the agents may receive disconnected pieces). Hence, in this case, the Simmons–Su protocols create a PEEF 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 PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists.