Simmons–Su protocols

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 (very mild) 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.
The partners are hungry. That is, partners never prefer an empty piece.
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.

Note that, in contrast to other protocols for fair cake-cutting, the utility functions are not required to be additive or monotonous.

References

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

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

[1]