Protocols were developed for solving several related problems: In the envy-free cake-cutting problem, a "cake" (a heterogeneous divisible resource) has to be divided among n partners with different preferences over parts of the cake.
A protocol for solving this problem was developed by Forest Simmons in 1980, in a correspondence with Michael Starbird.
The protocol makes the following assumptions on the preferences of the partners: The closedness condition rules out the existence of single points of cake with positive desirability.
These assumptions are very mild: in contrast to other protocols for fair cake-cutting, the utility functions are not required to be additive or monotonic.
We can now triangulate the sub-simplex to a finer mesh of sub-sub-simplices and repeat the process.
The existence of an envy-free partition has been proved before,[2] but Simmons' proof also yields a constructive approximation algorithm.
For example, assume that a certain land-estate has to be divided, and the partners agree that a difference of plus or minus 1 centimeter is irrelevant to them.
Then every point in the sub-simplex in which all labels are different corresponds to an (approximate) envy-free partition.
Several years after this algorithm has been published, it was proved that envy-free partitions with connected pieces cannot be found by finite protocols.
[4] One nice thing about the algorithm is that the queries it asks the partners are very simple: they just have to decide, in each partition, which piece they prefer.
Su's protocol operates on a dualized version of this simplex in a similar way to the Simmons–Su protocols for cake-cutting: for every vertex of a triangulation of the dual simplex, which corresponds to a certain price scheme, it asks the owning partner "which room do you prefer in that pricing scheme?".
This results in a Sperner coloring of the dual simplex, and thus there exists a small sub-simplex which corresponds an approximate envy-free assignment of rooms and rents.
Of course, if the preferences are independent (i.e. the utility from an allocation is the sum of utilities from the allocated piece in each cake), then the problem can be solved by one-cake division methods – simply do an envy-free partition on each cake separately.
A generalization of Sperner's lemma to polytopes[11] guarantees that, if this polytope is triangulated and labeled in an appropriate manner, there are at least n − d sub-simplices with a full labeling; each of these simplices corresponds to an (approximate) envy-free allocation in which each partner receives a different combination of pieces.