Cutting the Cake Problem

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).

There is a result due to Dubins and Spanier (JSTOR required) that says that if $(M,\mathcal{M})$ is a measurable space and $\alpha_1,\alpha_2,\ldots,\alpha_n$ are atomless probability measures on $(M,\mathcal{M})$ and $c_1,c_2,\ldots,c_m$ are finitely many nonnegative numbers such that $\sum_{j=1}^m c_j=1$, then there exists a partition $\Pi$ of $M$ into measurable sets such that all the probability measures agree on $\Pi$ and have exactly measures $c_1,\ldots,c_m$. The result has been independently rediscovered by Aumann in the context of game theory, (Lemma 4.1).

One can even show that there exists a sub-$\sigma$-algebra of $\mathcal{M}$ on which all measures agree and are atomless.

There is a simple and elegant solution for N children, suggested by Banach and Knaster (Steinhaus, 1948):

"The partners being ranged A, B, C, ... N, A cuts from the cake an arbitrary part. B has now the right, but is not obliged, to diminish the slice cut off. Whatever he does, C has the right (without obligation) to diminish still the already diminished (or not diminished) slice, and so on up to N. The rule obliges the "last diminisher" to take as his part the slice he was the last to touch. This partner being thus disposed of, the remaining n-i persons start the same game with the remainder of the cake. After the number of participants has been reduced to two, they apply the classical rule for halving the remainder.

The rules are obvious; as to the methods, they are the following ones: If in any stage of the procedure you have to cut a slice, do it in a way to give to it a value of 1/n-th of the whole cake in your subjective es- timation; if you are asked to diminish a slice already cut off by another person, diminish it to the size you consider to be 1/n-th of the whole in value but abstain from action if it has already this value or a smaller one in your estimation. It is easy to prove that the methods explained here secure to every partner at least a part equal in value to the 1/n-th of the whole. The greed, the ignorance, and the envy of other partners can not deprive him of the part due to him in his estimation; he has only to keep to the methods described above. Even a conspiracy of all other partners with the only aim to wrong him, even against their own interests, could not damage him.

The hypotheses underlying the procedure described are: (1) the ideal shares due to the partners are not contested by any of them; (2) the object is continuous, so as to make it possible to cut off it a slice of value pV, V being the value of the whole and p any fraction between 0 and 1; the same applies to every part which can be cut off the object; (3) the sum of values of parts is equal to the value of the whole; the same applies to every part. The postulates (2) and (3) have to be valid for every individual estimation."