Dividing a portion three ways, fairly

[Keeves]

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.

[Boris B]

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. (C) 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%

[Boris B]

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?

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

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.

[Narile]

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

[handy]

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

[moriah]

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.

[GuanoLad]

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

[Momotaro]

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.

[Keeves]

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

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.

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.

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:

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.

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.

[StrTrkr777]

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

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.

[Bert]

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.

[HeadlessCow]

How about this?

A cuts the cake in half.
B picks one. A gets the other.
C then cuts each of the others pieces into thirds and A and B each pick which 2 thirds of their original halves they want to keep. C gets the remaing two thirds.

A feels this is fair b/c A made the original cut to create two equal pieces and took the two pieces at the end.
B feels this is fair b/c B got to pick which half they wanted and B got to pick which two thirds they wanted.
C feels this is fair b/c they cut the two halves into what they thought were equal pieces so C should be happy with whatever two are left.

[Jebediah]

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.

[TheIncredibleHolg]

HC, I think you got it! I'd just change the reasoning for C: He won't be content just because the others cut halves as best they could; they might still do a bad job and cut a big and a small piece. But whatever they do, C has the opportunity to cut a perfect third of the big piece plus a perfect third of the small piece, which will get him a perfect third of the whole pie!

That's envy-free in my book. What I love about this solution is that it doesn't require any trimmings to be mushed or discarded.

[ChrisCTP]

Envy-free and totally foolproof:

Take food to nearest Mom. Have HER make the cuts, and make it clear to all three kids that any bickering over who got the largest piece will result in MOM taking back the whole mess and eating it herself.

------------------
Veni, Vidi, Visa ... I came, I saw, I bought.

[Momotaro]

Here is another fun fact. The people that came up with the solution knew even before trying that there had to be a solution to this problem. That's because there's another theorem (proven beforehand) that stated that there had to be a configuration that would give everyone at least as much as they would feel is fair. That's not very clear, let me give an example:

If you have four people dividing a cake, there is a way to cut it so that every person gets at least 25%. Think about it, that sounds rather strange. What's taken into account is 'perceived value'. Everyone has a different way of evaluating the value of cake slices. Some people will prefer a piece that has more cream on the top, some want more cherries, others want more of those colourful things they sprinkle on cakes, etc.

What that means is that once they found the correct method of cutting the cake, not only were they sure everyone felt they would receive a fair share, but some people would feel they had received a 'better' slice than the others according to their value system.

Isn't it great? They also said that the theorem could be applied to most disagreements they could come up with in real life, not just cakes. The notable exceptions included when one of the participants tried to eliminate the others rather than cut the cake, à la Serbian-kill-the-Albanians.

------------------
Only humans commit inhuman acts.

[Doctor Jackson]

HC - Good job! Here's a solution that would work with less cutting:

A cuts a piece of pie equal to 1/3
B has 2 options:
1. Take the piece "A" cut, or
2. Refuse the piece "A" cut.

If "B" chooses option 1, then "C" cuts the remainder in half. "A" gets first choice of remaining two pieces.

If "B" chooses option 2, "A" must take the initial piece. "B" then cuts the remainder in half and "C" gets choice.

"A" knows the first cut must be very close to 1/3. Too large and "B" claims it, leaving less for "A" and "C"; too small and "B" refuses it, forcing "A" to accept the smallest piece.

Nah, I think I like yours better.

------------------
The overwhelming majority of people have more than the average (mean) number of legs. -- E. Grebenik

[TheIncredibleHolg]

Dr J: Not envy-free. Suppose A cuts too large a piece, B takes it and C is envious. HC's is better.

[TheIncredibleHolg]

Hey, let's push the envelope and see if we can generalize the solution!

I just noticed that HC solved the 3-way cut by first performing the 2-way cut and then having the third person cut all pieces into 3 sub-pieces (let me call these slices), of which the original owners can keep 2 each.

Now my generalization is as follows: To achieve an envy-free n-way cut, first perform an (n-1)-way cut among the first n-1 persons. Now the n-th person cuts all existing pieces into n slices, of which the original owners keep n-1. The rest goes to the n-th person!

Example n=3: see above.

Example n=4: A, B, and C make the proven three-way cut. Each now has two pieces. D cuts all pieces in four slices, so there's eight slices for each of the three, of which each can keep six. Two each go to D, who also has six pieces altogether. (I guess A, B, and C must keep exactly three slices of each piece, not all of one piece and just two slices of another.)

Example n=5: A, B, C, and D make the four-way cut, and each has six pieces. E cuts those into five slices each, or 30 slices per capita, or 120 slices altogether...

I see this leads to a large number of small pieces, viz. n! pieces or (n-1)! pieces per capita. Looks like mush after all...

Now how do we prove this scheme is envy-free? Would you agree with me that if n-1 persons have found an envy-free cut, and each of these makes an envy-free (though uneven) cut with the n-th guy, the whole cut is envy-free?

Induction is fun!!

("Induction, destruction -- who wants to die in a WAR?!" -- who sang that before Bruce Springsteen?)

Headless Cow says:
A cuts the cake in half.
B picks one. A gets the other.
C then cuts each of the others pieces into thirds and A and B each pick which 2 thirds of their original halves they want to keep. C gets the remaing two thirds.

As I said before, it's a lot easier to find the faults in a method that to devise a correct solution. The answer above is again not "envy-free".

Person B could end up with a larger portion than person A (in person A's opinion), because person A might think that C made two of the three pieces bigger when dividing B's half.

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

[SqrlCub]

Here's a response I came up with that pissed off a math professor when he posed the same question. (3 equal portions in 2 cuts)

Cut pie in half. Move 60 degrees to either side then cut straight through the center. It will leave two pieces totalling 120 degrees of the total a piece and two pieces totaling 60 degrees a piece (or 120 together). Altogether that totals 360 degrees and nothing for chance. The professor said it was wrong by changing what he had written on the board. He said that two pieces at 60 degrees was not the equivalent of 120 degrees.

SC

------------------
"People's Poet don't die, we'll kill ourselves if you do, but first we'll take off all our clothes." The Young Ones

TheIncredibleHolg says:
Hey, let's push the envelope and see if we can generalize the solution!
I just noticed that HC solved the 3-way cut by first performing the 2-way cut and then having the third person cut all pieces into 3 sub-pieces (let me call these slices), of which the original owners can keep 2 each.
etc...

Since HeadlessCow's solution is not "envy-free", generalizing it will not give you a correct answer for n portions.

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

[TheIncredibleHolg]

Since HeadlessCow's solution is not "envy-free", generalizing it will not give you a correct answer for n portions.Dang! All that work for nothing! Just as I thought I could almost feel the Nobel Prize in my hand...

I suppose you also answered my final question: A series of envy-free cuts between two persons each does not lead to an overall envy-free solution because one person can be unhappy with a division between two others that s/he wasn't even involved in.

("Induction, destruction..." -- even more a propos than I thought! Again: who sang that first?)

Forgive me if I get this wrong, folks; I've read every post on this thread and think I've incorporated them, but . . .

Anyway, I think what's being missed here is that it's not merely the slicing, but the selection which must be out of each individual's control to motivate them to make fair slices. Consider the primal case: A & B. A makes the cut, B selects. But think of this not as B selecting his/her piece, but as B selecting A's piece.

The way I see it, A & B do the slicing into sixths; C selects the slices for A & B, and must take what is left.

[Temujin]

Apparently this mathematic problem was solved in 1960. I did a quick search but was not immediately able to find the solution anywhere. Here's a strange related link, though: http://www.math.hmc.edu/~su/fairdivision/calc/

Apparently this mathematic problem was solved in 1960.

Yes. A short discussion of the problem can be seen at
[urlhttp://saturn.vcu.edu/~gasmerom/MAT131/fairdivision.html[/url]

At that page I found the name for the 3-way envy-free division method I quote above: The Selfridge-Conway method.

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

OK, you know what I meant:

http://saturn.vcu.edu/~gasmerom/MAT131/fairdivision.html

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