Difference between revisions of "Cake-cutting problem"
(Importing text file) |
(TeX) |
||
| Line 1: | Line 1: | ||
| + | {{TEX|done}} | ||
''fair division problem'' | ''fair division problem'' | ||
| − | A circular or rectangular cake is to be cut and divided (by radial, respectively vertical, cuts) among | + | 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 | + | i.e. by a point $x$ of the standard $n$-simplex in $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 | + | 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]]]. | 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]]]. | ||
Revision as of 10:16, 15 April 2014
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 $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 |
Cake-cutting problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cake-cutting_problem&oldid=31713