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:
Cake cutting 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. 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:
Independence on other partners: The preference depends on the partner and the entire cut-set, but not on choices made by the other partners. Hungry partners: Partners never prefer an empty piece. Topologically closed preference sets: Any piece that is preferred for a convergent sequence of cut-sets, is preferred at the limiting cut-set. So for example, if a partner prefers the first piece in all cut-sets where the first cut is done at x > 0.2 and prefers the second piece in all cut-sets where the first cut is at x < 0.2, then at the cut-set where the first cut is at x = 0.2 that partner prefers both pieces equally. 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:
Triangulate the simplex-of-partitions to smaller simplices of any desired size. Assign each vertex of the triangulation to one partner, such that each sub-simplex has n different labels. For each vertex of the triangulation, ask its owner: “Which piece would you choose if the cake were cut with the cut-set represented by this point?”. Label that vertex by the number of the piece that is desired. The generated labeling satisfies the requirements of Sperner's lemma coloring:
Each vertex of the original simplex corresponds to a cut-set in which one piece contains the entire cake and all other pieces are empty. By the "hungry partners" assumption, the owner of that vertex must prefer that piece. Hence the labels of the vertices of the large simplex are all different. Each side/face of the original simplex corresponds to the cut-sets in which some pieces are empty, and the non-empty pieces correspond to the vertices of that side. By the "hungry partners" assumption, the owners must prefer only non-empty pieces, so the triangulation vertices on these sides can have only one of the labels that appear in the corresponding vertices. 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, 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. 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. 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.
Run-time complexity 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:
… excerpt ends here. Continue reading the full article.
