Cutting the Cake Problem

Question

The traditional method for two children to divide a piece of cake fairly between them is "you cut, I choose". What process accomplishes this is intuitively clear. Is there a similar process which works for $3$ children?

Suppose that three children $(1),(2)$ and $(3)$ have associated measures (ways of evaluating the pieces of cake) $\alpha_{1},\alpha_{2}$ and $\alpha_{3}$. Assume for the simplicity of the notation that the sum of total pieces of the cake is equal to $1$.

Question : Does the cake have three subsets $C_{1},C_{2}$ and $C_{3}$ that are pairwise disjoint and their union is equal to $C$, and that have moreover the property that $$\alpha(C_{1}) \geq \frac{1}{3}, \quad \alpha(C_{2} )\geq \frac{1}{3} , \quad \alpha(C_{3}) \geq \frac{1}{3}?$$

Solution: Let one of the three children, say $(1)$, divide the cake into what he regards as three equal pieces $C_{1},C_{2}$ and $C_{3}$: In other words $\alpha(C_{1})= \alpha(C_2)=\alpha(C_{3})=\frac{1}{3}$. Let each of $(2)$ and $(3)$ claim dibs on one of those three pieces, the one he prefers the most, the one he would be quite satisfied to have. It is possible that $(2)$ and $(3)$ will claim different pieces, and it is possible that they will claim the same one, but no matter, atleast one of the three pieces, $C_{1},C_{2},C_{3}$ will be left unclaimed. Let $(1)$ remove that piece (one of those pieces) and eat it. So far everyone is satisfied. Child (1) got what he believes to be exactly a third, and in the judgement of the children $(2)$ and $(3)$ the best piece (the claimed piece) is still available. The problem reduces therefore, to dividing whats fairly left, - and that's the classical problem of dividing a piece of cake between two claimants. Let that problem be solved by "you cut, i choose" and everybody is happy.

---

Solution The Proposed solution is wrong; Whats wrong with it?

Answer 1

After giving to (1) one of unclaimed pieces, less than 2/3 of cake can be left (in measure of (2) or (3)), so one of them will be unsatisfied.

Edit: The right solution is the following.
1. Let (1) divide cake into three equal pieces.
2. Ask (2) and (3) "What is the best one?". If their answers are different, we are done: each one of (2) and (3) gets what he (or she) wants, and (1) takes unclaimed piece. Otherwise go to step 3.
3. Ask (2) and (3) "Is there any other piece, you would satisfied with?". If at least one of the answers is "Yes" we are done similar to step 2. Otherwise go to step 4.
4. (1) takes any of two unclaimed pieces.
5. Thanks to the answer "No" at the step 3 we know, that at least 2/3 of the cake left in both measures (the one of (2) and the one of (3)). Therefore we can apply "you cut, I choose" method to the leaving 2 pieces.

Edit: This problem can be solved with arbitrary number of children using the algorithm for finding maximum matching in a bipartite graph. Suppose, number of children is n. Cutting the cake algorithm is the following.
1. Let (1) divide cake into three equal pieces.
2. Ask others the following: "Please, list all the pieces, you will be satisfied with."
3. Consider bipartite graph with 2n-1 vertices: n pieces of cake and all children except (1). Children is connected with a cake iff it will be satisfied with it. 4. Find maximum matching in this graph. Lets call vertex "free" iff it is not matched in this matching with another one.
5. If there are no free children, give pieces of the cake according to the matching (and free piece of cake is for (1)). In this case we are done. Otherwise go to step 6.
6. In the algorithm of maximum matching we are able to find its certificate, i.e. pair of sets (U,V) with U containing all free children and some non-free, and V containing some pieces of cake, such that 1) amount of elements in V is equal to amount of non-free elements in U; 2) every vertex in U has edges only to vertexes form V 3) there are no edges from chosen matching, connecting vertex from V to some vertex outside U. In our case it means that every piece of cake outside V is less than 1/n in all measures of children from U.
7. Give pieces of cake to children outside U (except (1) ) according to chosen matching.
8. Give any free piece of cake outside V to (1).
9. Note, that according to 6, all pieces of cake given at 7 and 8 are unimportant for elements of U. Therefore there is enough cake left for them. Divide it according to this algorithm between elements of U (note, that (1) is not in U, and, therefore size of U is less than n).

Answer 2

Two things:

1. You are assuming that (1) cut the cake into three pieces of equal value to him, and then took one piece. Now there are two pieces left for (2) and (3) to choose between, and you claimed that this problem could be solved by the original "you cut, I choose" method. But, since the cake is already cut, they cannot use that method.

2. (1) cut the cake into three pieces of equal value to himself and then took a piece for himself, but this piece may have been more valuable to (2) or (3) than any of the other pieces, so they would not be satisfied.

I have an idea of how to do it, but its not complete:

Let (1) take three pieces of string to mark off where he intends to cut the cake into three slices of what he believes are equally valued. Then there are two cases for people (2) and (3). If (2) and (3)'s optimal slices are different, then they should just take those slices and (1) can take the last one- everyone is satisfied.

If both (2) and (3) want the same slice, then remove the string and start again with (2) setting the string on the cake this time instead.

By doing this eventually you reduce the problem to the case where when any person cuts the cake into equal slices, the other two people will want the same piece.

Answer 3

Fiktor is correct. In proportional division, you want to achieve the result, that each of the n player will end up with at lest 1/n cake in her own valuation. The procedure above does not achieve this.

Counter example:

Total valuation of cake

Value P1 P2 P3
       3  5  8

So each player should end up with at least

Value P1 P2 P3 1 5/3 8/3

Player 1 makes first cut, valuation after first cut:

Value P1 P2 P3
C1    1   3  1
C2    1   2  4
C3    1   1  3

P3 always chooses C2, P2 chooses C1. So P1 is chooses C3. So it remains:

   Value P2 P3
    C1    3   1
    C2    2   4

Say P3 now makes the second cut, so that C1 and C2 have same valuation:

   Value P2 P3
    C1    >3   5/2
    C2    <2   5/2

so P2 chooses C1. Now P3 is left with a piece that she values at 5/2 which is less than the proportional 8/3.