Expert: Scott A Wilson - 12/17/2009

Question
QUESTION: Hi Scott,

Could you tell me what is the algorithm to divide up a pie between 2, 3, 4, ... N number of people so that all are satisfied?  

I read about this a long time ago and I hope it can help me and my 3 roommates divide up the rent on our new apartment.  However, the details escape me.  It goes something like this:

2 People - One person divides the pie into two halves which he believes are even.  The other person chooses between the two halves.  Satisfaction is guaranteed to be >=100%.  The first person thinks he/she got an even deal and the second believes he/she got an even deal or better.  

3+ People - This is more complicated.  Person #1 divides the pie into 3 equal slices.  Person #2 judges the slices and shaves a portion off the largest one to make it even with the second largest. Person #3 chooses? ... The process goes on but this is where my memory escapes me.  

Thanks You!

ANSWER: n people: Let the 1st person cut out an nth of the pie.
Let each next person cut out another nth of the pie.

Note that the slices have all been made when it gets down to the last person,
so let the last person decide which piece he gets.

Starting with the 1st person, let them all choose which piece of pie they want.

If anyone tries to make a piece bigger than the rest,
he'll be the last one to decide on getting that piece.


---------- FOLLOW-UP ----------

QUESTION: Thanks very much for the answer.  After thinking about this for a while, I think there is also a more complex, though perhaps less known, algorithm.  Or perhaps I'm misunderstanding the one you posted.  The one you posted ensures that no one gets what they think is the smallest piece, but the algorithm I'm thinking of ensures that everyone gets what they think is the largest piece.  

Let me illustrate my issue with the above algorithm with a 3 person scenario:
1) Person 1 is blind and instead of cutting a 1/3 slice of the pie, he cuts a large 4/9 slice.  
2) Person 2 decides to cut the remainder into two equal 5/18 slices. He could cut it differently, but no matter how he divides up the remainder, he is not going to get the largest slice in the end.   
3) Per the above algorithm, person 3 now gets to choose a slice, and he of course picks the 4/9 slice.  
4) Person 1 is next and chooses one of the two 5/18 slices.  That's OK with him because he's blind and thinks he cut the original slice fairly, so from his view he is still getting an even deal.  
5) Person 2 is last and is stuck with a 5/18 slice.  He's not happy because it's clear to him that person 1 got the better end of the deal.  Had he decided not to cut the remainder evenly at Step #2, he would still be stuck with a 2nd largest slice, at best.  

Again, the algorithm I'm thinking of gets exponentially more complicated as you add more people / slices, but it ensures a fair outcome.  Thanks!  

Answer
I'm not sure if this was suppose to be answered, but I've got to answer everything I get.
Now I could have just sent a, "You're Welcome," but I think this needs a little more.

Yes, the first few people could make a biased choice, but if you're the first one to choose,
you're the last one to decided.  It might not be fair, but if a bad choice is made,
there are other people who get to decide which one they get.

In other words, if a bad choice is made by someone, they surely won't get it.
As far as the blind person, don't tell him about it.

That last was just a thought to make you smile....