The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple queries such as "which piece do you prefer?".
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. The cake has to be divided to n pieces such that: (a) each partner receives a single connected piece, and (b) each partner believes that his piece is (weakly) better than all other pieces. A protocol for solving this problem was developed by Forest Simmons in 1980, in a correspondence with Michael Starbird. It was first publicized by Francis Su in 1999.[1]
Given a cut-set (i.e. a certain partition of the cake to n pieces), we say that a partner prefers a given piece if he believes that this piece is weakly better than all other pieces. "Weakly" means that the partner may be indifferent between the piece and one or more other pieces, so he may (in case of ties) "prefer" more than one piece.
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.
The protocol considers 1-dimensional cut-sets. For example, the cake may be the 1-dimensional interval [0,1] and each piece is an interval; or, the cake may be a rectangle cut along its longer side so that each piece is a rectangle. Every cut-set can be represented by n numbers xi, i = 1, ..., n, where xi is the length of the ith piece. We assume that the total length of the cake is 1, so x1 + ... + xn = 1. The space of possible partitions is thus an (n - 1)-dimensional simplex with n vertices in Rn. The protocol works on this simplex in the following way:
The generated labeling satisfies the requirements of Sperner's lemma coloring:
Hence, by Sperner's lemma there must be at least one sub-simplex in which the labels are all different. In step #2 we assigned each vertex of this sub-simplex to a different partner. Hence we have found n very similar cut-sets in which different partners prefer different pieces of cake.
We can now triangulate the sub-simplex to a finer mesh of sub-sub-simplices and repeat the process. We get a sequence of smaller and smaller simplices which converge to a single point. This point corresponds to a single cut-set. By the "Preference sets are closed" assumption, in this cut-set each partner prefers a different piece. This is an envy-free partition!
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 the original simplex can be triangulated to simplices with side length less than 1 cm. Then every point in the sub-simplex in which all labels are different corresponds to an (approximate) envy-free partition.
In contrast to other envy-free protocols, which may assign each partner a large number of crumbs, Simmons' protocol gives each partner a single connected piece. Moreover, if the original cake is rectangular then each piece is a rectangle.
Several years after this algorithm has been published, it was proved that envy-free partitions with connected pieces cannot be found by finite protocols.[3] Hence, an approximation algorithm is the best that we can hope for in finite time. Currently, Simmons' algorithm is the only approximation algorithm for envy-free cake-cutting with connected pieces.
Simmons' algorithm is one of the few fair division algorithms which have been implemented and put online.[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. This is in contrast to other algorithm, which ask numerical queries such as "cut a piece with a value of 1/3" etc.
While an envy-free division with connected pieces can be approximated to any precision using the above protocol, the approximation might take a long time. In particular:[5]
| \Theta( | 1 |
| \epsilonn |
)
In this problem, n housemates have decided to rent an n-bedroom house for rent fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view, etc. The following two problems should be solved simultaneously: (a) Assign a room to each partner, (b) Determine the rent that each partner should pay, such that the sum of payments equals to the total rent. The assignment should be envy-free in that every partner weakly prefers his parcel of room+rent over the other parcels, i.e. no partner would like to take another room at the rent assigned to that room. A protocol for solving this problem was developed by Francis Su in 1999.[1]
The idea is as follows. Normalize the total rent to 1. Then each pricing scheme is a point in an
(n-1)
n
Rn
[6] and [7] provide popularized explanations of the Rental Harmony protocol.[8] and [9] provide on-line implementations.
See Rental harmony for more solutions to this problem.
In this problem, there is a chore that has to be divided among n partners, e.g., lawn-mowing in a large area.
The Rental Harmony protocol can be used to achieve approximate envy-free assignment of chores by simply thinking of the rent payments as chores and ignoring the rooms. Divisibility of chores can be achieved by dividing the time spent on them.[1]
In this problem, two or more cakes have to be divided simultaneously among two or more partners, giving each partner a single piece from each cake. 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. The question becomes interesting when the partners have linked preferences over the cakes, in which the portion of one cake that partner prefers is influenced by the portion of another cake allocated to him. For example, if the "cakes" are the times of work-shifts in two consecutive days, a typical employee may prefer to have the same shift every day (e.g. morning-morning or evening-evening) then to have different shifts.
A solution to this problem for the case of 2 partners and 2 or 3 cakes was published in 2009.[10] If the number of cakes is m, and each cake is divided to k pieces, then the space of partitions can be represented by an n-vertex d-dimensional polytope, where d=m(k - 1) and n = km. 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. However, the combinations might overlap: one partner might get the "morning" and "evening" shifts while another partner might get "evening" and "evening". Although these are different selections, they are incompatible. section 4 of [10] proves that an envy-free division to two partners with disjoint pieces might be impossible if m = k = 2, but is always possible if m = 2 and k = 3 (i.e. at least one cake is divided to three pieces, each partner receives a single piece from each cake, and at least one piece is discarded). Similar results are proved for three cakes.