Namespaces
Variants
Actions

Difference between revisions of "Cake-cutting problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m
 
(2 intermediate revisions by the same user not shown)
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 <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
+
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
  
<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>
+
$$x_1+\dots+x_n=1,$$
  
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.
+
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 <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.
+
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]]].

Latest revision as of 16:50, 30 December 2018

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+\dots+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=15331
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article