3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is a huge area of research about this type of question, so I don't think it really qualifies as a puzzle. Look up subjects like fair division and envy-free for some pointers. There are many subtly different ways of formalising what it means for a division procedure to be considered fair. $\endgroup$ – Marc van Leeuwen Jun 10 '14 at 9:36
  • $\begingroup$ This is a duplicate of this question from math $\endgroup$ – Ross Millikan Jun 10 '14 at 18:42
  • $\begingroup$ @RossMillikan, I know "fair" solution for N. I need here solution for envy people, that's why i bolded this point. $\endgroup$ – klm123 Jun 10 '14 at 18:47
  • $\begingroup$ @klm123 - "Equal or more" = "not less than". I think you mean to write it so that everyone thinks they got more, rather than equal or more. $\endgroup$ – Bobson Jun 10 '14 at 20:08
  • $\begingroup$ @Bobson, no. why? $\endgroup$ – klm123 Jun 10 '14 at 20:13
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is one solution I personally know that addresses N people but it has several issues. That is why as Mr. Leeuwen mentions, there is alot of discussion on finding better algorithms. This answer nevertheless should be mentioned here. $\endgroup$ – kaine Jun 10 '14 at 16:14
  • $\begingroup$ If understand this correctly this solution will not always achieve the asked result and therefore is not related to my question (have you seen the bolded condition in my question?). Ones player is "out of the game" he can look on the other players and see that they got (in his opinion) twice bigger piece than he got. $\endgroup$ – klm123 Jun 10 '14 at 17:30
  • $\begingroup$ This is very much relevant to your question. Admittedly though I do not take into account the possibility that someone later in the game could take piece much smaller than he should granting any other remaining players a larger share. $\endgroup$ – kaine Jun 10 '14 at 18:27
  • $\begingroup$ The question is not about probability and subjective "much" or "not so much", the question is how Guarantee that the man will think that his part is Exactly "equal or bigger" than all others parts. That's why I can't understand how your answer is related. Do you understand me? $\endgroup$ – klm123 Jun 10 '14 at 20:28
  • $\begingroup$ But I heard that "moving knife" solution can be applied to answer my question with N=3. But I don't see how... If you would explain how I would upvote your answer. $\endgroup$ – klm123 Jun 10 '14 at 20:29
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.