Mathematics – Combinatorics
Scientific paper
2009-09-02
Mathematics
Combinatorics
15 pages, 7 figures, see related work at http://www.math.hmc.edu/~su/papers.html
Scientific paper
We introduce a generalized cake-cutting problem in which we seek to divide multiple cakes so that two players may get their most-preferred piece selections: a choice of one piece from each cake, allowing for the possibility of linked preferences over the cakes. For two players, we show that disjoint envy-free piece selections may not exist for two cakes cut into two pieces each, and they may not exist for three cakes cut into three pieces each. However, there do exist such divisions for two cakes cut into three pieces each, and for three cakes cut into four pieces each. The resulting allocations of pieces to players are Pareto-optimal with respect to the division. We use a generalization of Sperner's lemma on the polytope of divisions to locate solutions to our generalized cake-cutting problem.
Cloutier John
Nyman Kathryn L.
Su Francis Edward
No associations
LandOfFree
Two-player envy-free multi-cake division does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Two-player envy-free multi-cake division, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-player envy-free multi-cake division will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-11681