# Dividing a portion three ways, fairly

I once received the following question on an entance test into a computer course. It was the only question I couldn’t answer. After I was accepted, I asked for the answer, but forgot it only a few hours later. Does anyone else know the answer? The question went like this:

When two children want to share a piece of food, a common procedure is for one of them to divide it into two supposedly-equal portions, and the other can choose whichever he wants.

With this system, neither child can complain of recieving the smaller piece. The first one can’t complain, because he signed off on their being equal. And the second can’t complain, because he had the option of choosing whichever he thought was the larger.

The question: How can this logic be adapted to allow THREE children to divide something so that none can complain of unfairness?

I read this answer somewhere, I believe the method is named after Conway and someone else, and is hence known as the ?-Conway envy-free division.

Assume three people, A B C and one pie.

A divides pie into three pieces and hands pieces to B.

If B thinks that one of the pieces is larger than the others, B can trim (at most) one piece to make (in B’s opinion) two pieces tying for largest. The three pieces are then handed to C (and the trimmings are discarded).

C takes a piece of their choice.

B takes a piece of their choice, except if a piece had been trimmed by B, and not taken by C, then it must be taken by B.

A gets remaining piece.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

I think I might be missing something here. Why not just have one person make two cuts, and then each of the other two pick first. (A) makes the cuts. (B) picks first. © picks second. C’s piece might be smaller than B’s, but A’s will be smallest of all. Thus A has an incentive to make as equal cuts as possible.

This of course precludes some sort of secret deal between two parties. Otherwize, A could cut e.g. an 80% piece and two 10% pieces; B picks the big piece and kicks back 35% of the original to A. A and B each get 45%; poor C is stuck with 10%

I didn’t mean “precludes”. I meant, “this of course would be messed up by the possibility of a secret deal; we must ban secret deals from consideration.” Beter?

That would not be “envy-free”, because C might claim that B’s piece is bigger than C’s.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

I believe that it should go, A makes a cut, then B makes a cut and possible trim, then C gets first choice, followed by A, B gets last choice.

>>Being Chaotic Evil means never having to say your sorry…unless the other guy is bigger than you.<<

—The dragon observes

Just put it in a blender, blend it, seperate into three equal amounts.

A cuts the pie into thirds.

B cuts each third in half.

C picks two pieces (two sixths = one third).

A picks two pieces.

B picks two pieces.

This gives both A & B an equal responsibilitly and incentive to partition fairly. And since C chooses which pieces to take first, C is happy.

I don’t know if this is the official answer, but it works for me!

Peace.

Put the pie back in the fridge and buy a bag of chips each.

“So what you are telling me, Percy, is that something you have never seen is slightly less blue than something else that you have never seen.”

M cuts the pie into three pieces, gives A,B, and C each a piece, and says “If you kids don’t stop arguing, it’s no TV for a week.”

I’ll just complete JRK’s explanation. After the three pieces are taken, the trim is divided using the same method and so on until what’s left is not worth trimming anymore.

Only humans commit inhuman acts.

Thanks all. JRK’s doesn’t sound familiar, but I do think it would work.

Again, not “envy-free”.
Suppose A cuts three “equal parts”, P1, P2, P3.
B botches the job.
P1 is cut into two parts: P11 and P12.
P2 is cut into two parts: P21 and P22.
P3 is cut into three parts: P31 and P32.

Suppose P11 and P21 are bigger? Then C takes those, and A would “envy” C since C got more of the pie (in A’s estimation). The problem is to arrange it so that everyone has control of the portion which they inherit.

P.S. It’s not “JRK’s explanation”, but as I mentioned above, the Somebody-Conway 3-way envy-free division. I wish I was smart enough to come up with that answer! There are probably other methods.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

Narile says:

Again, not an “envy-free” division. It’s a lot easier picking holes into a solution than finding the correct one!

A makes a cut, ending up (in A’s estimation) with 1/3 and 2/3.

Suppose B cuts the 2/3 piece, ending (in B’s estimation) in 1/3, 1/3 and 1/3. But A might not agree, and think the pieces are 1/3 (= 4/12, A’s original piece), 1/4 (= 3/12), and 5/12.

C then picks up largest piece, 5/12. A is left with choosing either 4/12 or 3/12, so A would “envy” C.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

momotaro says:

[quote]
I’ll just complete JRK’s explanation. After the three pieces are taken, the trim is divided using the same method and so on until what’s left is not worth trimming anymore.

[quote]

Thank you for the rectification. I had said “the trimmings are discarded”, which is probably not correct.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

OK, we have children A, B, and C.

A cuts as close to one third out of the pie as he can.
B cuts the remaining two thirds into two thirds.
C picks first.
A picks second.
B picks last.

If A cuts more than a third, it will go to C and his peice will be too small.

If A cuts less than a third, B realizes this will end up his peice if it is smallest, so he would cut the remaining two thirds so that one of the slices was the same size as A’s slice. A and B would get small slices, C would cash in.

If A cuts even then B will get the smaller of the two peices that he cuts. So he will want to cut as close as even as possible.

The idea is not to make sure all thirds are equal, but rather to insure that an inequal cutting is to the detriment of the cutter.

Actually when no one is looking A will take the pie and eat it all. If someone is looking then A will kick the butts of B and C and still eat the pie, but this scenario gives A more of an appetite than does the first one.

Problem solved. A is full and happy and B and C are happy that they did not get beaten up worse.

Jeffery

Jebediah says:

That is the same method that Narile proposed above, and for the reasons mentioned above, is not an “envy-free” division. Depending on B’s cutting, C might get (in A’s opinion) a larger piece.

Jacques Kilchoer
Workers of the world, unite! You have nothing to lose but your chains.

How about this… Individual A makes an initial cut from the center of the pie to the edge. A then holds the knife above the pie (tip of the knife abive the pie’s center) and slowly rotates it about the center point at a constant pace. Whenever someone (including A) says stop, their piece is cut at the knifes current position. The remaining pie could be divided using the previously described two-person method.