How to generalise Partition of the pie for N envy people?

Question

There is well known task:

How to divide a pie between two people, so each will think that he got equal or more that the other one?

It has the following solution:

First person divide the pie on 2 equal (in his opinion) parts. Second one chooses the biggest one.

I know that it is possible to generalise in a way that N people will divide a pie on N pieces and each one will think that his part is not less than 1/N.

Is it possible to generalise this on N envy people? That means to divide a pie between N people in such a way that each one will think that his part is not less than part of any other man. In this case, when a man has got a part bigger than 1/N, he will still be following the rest of the division between the others - may be some one will get even bigger part (in this case the man will not calm down until the situation changes).

Answer 1

Example moving knife cake cutting method

Assumptions:

1) we assume that all players will accept that if they had as much opportunity to a given cake as every other player they are satisfied.

2) everyone will be fine with someone taking a small piece if that person is doing so under the impression that it is the same size

3) cakes are combinable...two small pieces can be pressed together to make one of the same size as them separately and everyone accepts that the new cake is the same as the old. This would work better if we were splitting a beer or wine.

4) People can cut perfectly and don't try to cheat when performing step 3. A referee might work for that. This is by far the weakest part of the method.

Method:

Step 1) A particpant is chosen at random to cut his piece of cake. He cuts off a piece he thinks is fair.

Step 2) Everyone is given the option to claim his piece is too big. The players who feel that way particpate in step 3. If no one feels that way, he can keep his piece, skip step 3, and be no longer part of the game.

Step 3) He holds his knife over the cake in an exact steady nature over the left hand side and slowly moves the knife to right above the cake. When each person feels he would cut it accurately if he cuts there they yell "STOP". He cuts when the last person says stop and that person gets the remaining right hand side of the cake. The player is no longer part of the game.

Step 4) The cake and all scrap is pressed together to make one big cake.

Step 5) Repeat all steps until there is only one player. He gets all remaining cake.

Note:

When N=2, this is equivalent to the standard answer you describe in your question as he will say "STOP" immediately.

Variation:

If cakes cannot be pressed together, assume that any scrap will be given to the person to be awarded cake on the next round. If any players don't say stop until after the knife has passes over the piece of cake they are playing for, the knife will proceed over the scrap pile.

If you must allow for people to want pieces that are produced after they are given their piece the problem gets unsolvable for all N. For N=3, however, there are solutions. For example, if all players hold a knife over what they consider to be the center of the right hand side of a cake while a referee moves his knife from left to right, both cuts can effectively happen at the same time. When any player yells "CUT" the referee cuts and the yeller gets the cake to the left of the referee's knife. The other cut (on the right hand side of the cake) is made at the knife in the middle of the other 3 players. Besides the yeller the player with the leftmost knife gets the middle cake while the other player gets the rightmost cake.

Answer 2

I think the standard solution is:

First person slices off a piece of cake.

Second person has two choices: let first person take that piece and slice off a new piece for herself, or slice off a portion of the first piece (to be added back to the whole) and keep the piece for herself. In the second option, the first person goes back to the end of the line.

After second person makes her choice, each successive person has the same option until each person has a piece. If the second person chose to take a new slice, then the third person will be deciding on that; the first person will take her slice and walk away.

No one would choose to slice off a piece smaller than $1/N$, as they would get stuck with that piece and have less than the others. If anyone selects more than $1/N$, that piece would get taken away by the next person and whittled down.

This method only works if no one is willing to give someone else a larger share if it means cutting into their own share.