View source for Cake-cutting problem

''fair division problem''

A circular or rectangular cake is to be cut and divided (by radial, respectively vertical, cuts) among <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300201.png" /> persons. Setting the total size (volume) of the cake to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300202.png" />, each division among <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300203.png" /> persons is given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300204.png" /> real numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300205.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300206.png" /></td> </tr></table>

i.e. by a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300207.png" /> of the standard <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300208.png" />-simplex in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c1300209.png" />. Each of the persons involved can have his/her own preferences: a choice of a segment for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c13002010.png" />. Different parts of the cake may have different values for each of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c13002011.png" /> different persons.

The question is whether there is a fair division (or envy-free division), i.e. one for which each of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130020/c13002012.png" /> persons gets a piece that for him/her is optimal. The answer is yes.

A unifying approach to this and similar problems (such as rent partitioning and dispute resolution) can be based on the [[Sperner lemma|Sperner lemma]], giving better and better approximations by means of Sperner labelings of finer and finer subdivisions, [[#References|[a4]]].

Recently (2000), there has been quite a bit of interest in fair division and cake cutting; see, e.g., [[#References|[a1]]], [[#References|[a3]]]. The problem has found its way into recreational mathematics under the name chore-division problem, [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.J. Brams,   A.D. Taylor,   "Fair division: from cake-cutting to dispute resolution" , Cambridge Univ. Press  (1996)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Gardner,   "Aha! Insight" , Freeman  (1978)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.M. Robertson,   W.A. Webb,   "Cake-cutting algorithms: be fair if you can" , A.K. Peters  (1998)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F.E. Su,   "Rental harmony: Sperner's lemma in fair division"  ''Amer. Math. Monthly'' , '''106'''  (1999)  pp. 930–942</TD></TR></table>