View source for Cake-cutting problem

{{TEX|done}}
''fair division problem''

A circular or rectangular cake is to be cut and divided (by radial, respectively vertical, cuts) among $n$ persons. Setting the total size (volume) of the cake to $1$, each division among $n$ persons is given by $n$ real numbers $x_i\geq0$ such that

$$x_1+\ldots+x_n=1,$$

i.e. by a point $x$ of the standard $n$-simplex in $\mathbf R^{n+1}$. Each of the persons involved can have his/her own preferences: a choice of a segment for each $x$. Different parts of the cake may have different values for each of the $n$ different persons.

The question is whether there is a fair division (or envy-free division), i.e. one for which each of the $n$ 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>