Simmons–Su protocols

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:

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 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 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:

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:

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.

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

and provide popularized explanations of the Rental Harmony protocol. and 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.

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