Jump to content

Simmons–Su protocols

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 14:19, 26 August 2014 (external links). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Simmons-Su protocols are several protocols for envy-free division based on the Sperner lemma. The merits of these protocols is that they put very few restrictions on the utility functions of the partners, and the partitions they output are simple and elegant.

Cake-cutting

The first protocol was developed by Forest Simmons in 1980 and publicized by Francis Su in 1999.[1] It involves a cake (a heterogeneous resource) and n partners with different preferences over parts of the resource. 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.

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. The partners are hungry. That is, partners never prefer an empty piece.
  3. Preference sets are closed. This means that any piece that is preferred for a convergent sequence of cut-sets is preferred at the limiting cut-set. This condition rules out the existence of single points of cake with positive desirability.[why?]

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

  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 simpliecs with side length less than 1 cm. Then every point in the sub-simplex in which all labels are different correponds 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.[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]

Chores and Rent-partitioning

[to be continued]

References

  1. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.2307/2589747, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.2307/2589747 instead.
  2. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.2307/2320951, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.2307/2320951 instead.
  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/
Retrieved from "https://en.wikipedia.org/w/index.php?title=Simmons–Su_protocols&oldid=622887777"