Simmons–Su protocols

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.^[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:

1. Independence on other partners: The preference depends on the partner and the entire cut-set, but not on choices made by the other partners.
2. Hungry partners: Partners never prefer an empty piece.
3. 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 monotonous.

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 x_i, i = 1, ..., n, where x_i is the length of the ith piece. We assume that the total length of the cake is 1, so x₁ + ... + x_n = 1. The space of possible partitions is thus an (n − 1)-dimensional simplex with n vertices in Rⁿ. The protocol works on this simplex in the following way:

1. Triangulate the simplex-of-partitions to smaller simplices of any desired size.
2. Assign each vertex of the triangulation to one partner, such that each sub-simplex has n different labels.
3. 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,^[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.

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:^[5]

• When the utility functions are accessible only through oracles, the number of queries for achieving an envy of less than ϵ is $\Theta ({\frac {1}{\epsilon ^{n}}})$.
• When the utility functions are given explicitly by polynomial-time algorithms, the envy-free cake-cutting problem has the same complexity as finding a Brouwer fixed-point, i.e. PPAD-complete.

Rental Harmony

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)$-dimensional simplex with $n$ vertices in $\mathbb {R} ^{n}$. 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.

^[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.

Chore division

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]

Multi-cake cutting

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 = k^m. A generalization of Sperner's lemma to polytopes^[11] guarantees that, if this polytope is trianguated 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.

References

1. Su, F. E. (1999). "Rental Harmony: Sperner's Lemma in Fair Division". The American Mathematical Monthly. 106 (10): 930. doi:10.2307/2589747. JSTOR 2589747.
2. Stromquist, Walter (1980). "How to Cut a Cake Fairly". The American Mathematical Monthly. 87 (8): 640. doi:10.2307/2320951.
3. Stromquist, Walter (2008). "Envy-free cake divisions cannot be found by finite protocols" (PDF). Electronic Journal of Combinatorics (January 2008) Key: Stromquist2008Envyfree. Retrieved 26 August 2014.
4. An implementation by Francis Su, Elisha Peterson and Patrick Winograd is available at: https://www.math.hmc.edu/~su/fairdivision/
5. Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting". Operations Research. 60 (6): 1461. doi:10.1287/opre.1120.1116.
6. Sun, Albert. "To Divide the Rent, Start With a Triangle". NY Times. Retrieved 26 August 2014.
7. Procaccia, Ariel. "Fair division and the whining philosophers problem". Turing's Invisible Hand. Retrieved 26 August 2014.
8. https://www.math.hmc.edu/~su/fairdivision/
9. http://www.nytimes.com/interactive/2014/science/rent-division-calculator.html
10. Cloutier, J.; Nyman, K. L.; Su, F. E. (2010). "Two-player envy-free multi-cake division". Mathematical Social Sciences. 59: 26. doi:10.1016/j.mathsocsci.2009.09.002.
11. De Loera, J. A.; Peterson, E.; Edward Su, F. (2002). "A Polytopal Generalization of Sperner's Lemma". Journal of Combinatorial Theory, Series A. 100: 1. doi:10.1006/jcta.2002.3274.