Namespaces
Variants
Actions

Cake-cutting problem

From Encyclopedia of Mathematics
Revision as of 10:16, 15 April 2014 by Ivan (talk | contribs)
Jump to: navigation, search

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, giving better and better approximations by means of Sperner labelings of finer and finer subdivisions, [a4].

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

References

[a1] S.J. Brams, A.D. Taylor, "Fair division: from cake-cutting to dispute resolution" , Cambridge Univ. Press (1996)
[a2] M. Gardner, "Aha! Insight" , Freeman (1978)
[a3] J.M. Robertson, W.A. Webb, "Cake-cutting algorithms: be fair if you can" , A.K. Peters (1998)
[a4] F.E. Su, "Rental harmony: Sperner's lemma in fair division" Amer. Math. Monthly , 106 (1999) pp. 930–942
How to Cite This Entry:
Cake-cutting problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cake-cutting_problem&oldid=31714
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article