Suppose you have N people and one cake. How can you cut the cake such that each person is satisfied that the pieces have been distributed fairly? This is an old problem that Martin Gardner wrote up in his column for Scientific American and in the case of two people it is quite simple: One person gets to cut the cake into two and the other person gets to select the piece they want. (But see later for a problem with this.)
But what if there are more than two people? Below the fold, I give Gardner’s explanation on how to do it, starting with the case where N=3, quoted by Walter Stromquist in an issue of The American Mathematical Monthly.
One person moves a large knife slowly over a cake. The cake may be any shape, but knife must move so that the amount of cake on one side continuously increases from zero to the maximum amount. As soon as anyone of the three believes that the knife is in a position to cut a first slice equal to 1/3 of the cake, he/she shouts ‘Cut!’ The cut is made at that instant, and the person who shouted gets the piece. Since he/she is satisfied that he/she got 1/3, he/she drops out of the cutting ritual. In case two or all three shout ‘Cut!’ simultaneously the piece is given to any one of them.
“The remaining two persons are, of course, satisfied that at least 2/3 of the cake remain. The problem is thus reduced to the previous case …
“This clearly generalizes to N persons.
Note that fairness in this case does not mean that each person gets exactly the same amount. It is very likely that the resulting N pieces will not be exactly equal. It is a slightly different concept of fairness that is based on the fact that each person gets to choose the piece they want and if it turns out that the pieces are not exactly equal and they got less than their 1/N share, they have no one to blame but themselves for their poor judgment. They cannot blame bad luck or collusion by the others. If one uses other methods like a lottery, people may still feel aggrieved that they were the victims of circumstance. After all, when it comes to life in general, telling poor people that it was just their bad luck that they happened to be born into poor families and thus they should be satisfied with their lot will hardly convince them that life is fair, nor should it.
But back to this problem, I am not sure if Gardner ever actually tried his solution out on children. But I did and immediately ran into a problem. When my two daughters were little, I encountered this situation of having to divide something between the two of them and, being the nerdy father that I am and always on the look out, often to their annoyance, of sneaking in ways to teach them science, math, logic, and fairness using everyday events, I told them about the ‘one person cuts, the other person chooses’ method.
They both thought about this for a short while and spotted the flaw in the system. The method’s success depends on the ability of the cutter to cut exactly (or very close to) two equal pieces. They each felt that neither of them would be able to cut the cake into two equal pieces, however hard they tried, but that they could easily decide which of the two unequal pieces was the larger. Hence choosing became the clearly better option. Neither one wanted to be the cutter and wanted the other to do it.
I was stymied. There was no way I could think of to resolve this impasse. Of course, one could toss a coin or something to decide who gets to cut but that seemed to defeat the purpose since it brought chance back into it. But I could see no other way and in the end it was decided that I would cut (since I was more likely to be able to get close to two equal pieces) and then toss a coin as to who got to choose first.
Too bad Gardner was not a member of my household. He may have figured out something better.
Your daughters are smarter than my sister and I, for we used the “one-cuts, the other chooses” technique for years. Maybe it was because it was usually an exceptional occasion when it ever came up. Probably less than once/year. Since we were getting something special anyway, as long as it was close to be equal, we really didn’t care. I think we also both assumed that we honorable intentions and would do our best to cut fairly.
But you touch on another interesting aspect of psychology, albeit obliquely. The idea that someone who has made a choice is more likely to be willing to live with the consequences can be a very potent tool for manipulation. What is even more amazing is that once someone has made a choice, they are generally willing to defend their choice. Once a person has made a choice, it takes a more work to convince them that their choice was in error that it took for them to make the choice in the first place.
People speculate that fairness was one of the reasons for Egyptian fractions. In order to, say, split 4 loaves among 5 people, they would not cut each loaf into one piece that’s 1/5 and one piece that’s 4/5, because one person gets stuck with 5 1/5 pieces. Rather, they’d cut 3 of the loaves in half, each person getting a half loaf. The half loaf left over gets cut in fifths, each person getting a fifth of a half, which is a tenth of a loaf. The last loaf is cut in fifths, and each person gets a fifth. Hence, each person has a half, a fifth, and a tenth, and the whole process seems more fair.
My brother and I would try to outwit each other with the “one cuts, the other chooses” method by cutting irregular shapes or odd angles, hoping that it would be difficult to judge which piece is bigger (or better so that the smaller looking piece was actually bigger). I don’t know how successful we were, but at least it was fun.
Get a tape-measure.
If any of you are into boardgames, Booty is a game I helped playtest that deals with exactly this sort of scenario. Short version: each turn, a bunch of cards get flipped up representing pirate loot. Before long, each card will be worth a different amount to each player. One of the players, the quartermaster, chooses a group of cards, and hopes someone else will take them. If no one else takes the share, then the quartermaster is stuck with it and a new quartermaster takes over.
If you’re a good quartermaster, you find a group of cards that will make everyone else happy, so that you can save the cards you want for yourself.
Here’s a link: http://www.boardgamegeek.com/thread/1505921/review-negotiation-game-no-negotiation
1. One cuts.
2. Other chooses.
3. In the event steps 1 & 2 are not completed with zero whining within 5 minutes, Daddy gets all.
1. use the opportunity to teach a little science.
2. buy an electronic/digital gram scale.
3. Weigh the whole and divide by the number of portions.
4. cut slices/pieces/whatever that match the target weight (trim as necessary and add back into the remainder.
5. Contents are sold by weight, not volume, some settling my occur during transport.
Jeff Hess
Have Coffee Will Write
Trust and acceptance.
Obviously, the original cutter does their best to estimate equality, knowing the other does their best to discern the largest piece.
The point is its fairness, not its outcome.
The way I heard this problem solved is:
Everybody stands in line. Order is not supposed to matter.
BEGIN LOOP
Head of line cuts a slice.
Next person optionally puts some of the slice back.
Repeat until all remaining persons have had the option to remove some cake.
Last person to touch the slice gets it and is removed from the line.
END LOOP
(Last two may use the one person cuts, other chooses.)
#6
Say rather:
1. One cuts.
2. Other chooses.
3. If this cannot be completed without whining, Dad does the cutting but cuts it into thirds, and gets one of the slices. Outsourcing labour = reduced profit.
A lesson on cooperating and capitalism in one! John Galt would be proud.
Peter B:
Failure mode: when your turn comes, you cut all but a sliver from the slice*.
(How many crumbs constitute a slice, asks Sorites)
—
Or: what I wrote earlier about missing the point.
It’s not about either some algorithm or game-theoretical process to maximise cake.
—
* If you’re first, you cut the tiniest possible sliver.
Make/buy cupcakes instead.
@ #9:
I really like you’re algorithm (maybe include random choosing of order used), but in many situations, it will be impractical, because the cutting slices or putting cake back steps destroy the cake; plus there will be some losses due to cake sticking to the knife and getting cleaned off and so forth …
Well you could incentivize it as cutter gets to lick the knife (or gets more of the frosting or whatever)
You dont really need a cutter chooser scheme anyway for 2 people -- if the two agree that the one piece is bigger , you simply cut out a piece of it till everyone is happy- If one party believes a piece is bigger but the other doesnt then the other gets the supposedly smaller piece. (The riddle specified single cut if i remember correctly)
My version:
1) Cut the cake into the requisite number of pieces. Do it as accurately as practical but don’t sweat the details.
2) Have the people draw straws, play rock-paper-scissors, or any other open method to select the first person to pick. Either record the order and stick to it allowing each in turn to pick from the selection of remaining pieces. Or redo the competition to select the next person to pick.
This works, I’ve used it. Funny thing is that people used many different methods to select. Some wanted absolute size. Others wanted more icing. A few want a flower, or some particular color icing.
Keep it light, have fun.