General Question

LostInParadise's avatar

Can you complete this technique for fairly dividing something among 3 people?

Asked by LostInParadise (17925 points ) February 22nd, 2014

I just learned about this and decided to share it in the form of a problem. Most of you probably remember from childhood the technique for splitting something, like a candy bar, between two people. One person cuts the thing into two parts and the other has first choice of which to take. Each person ends up believing that he got at least as much as the other.

About 50 years ago mathematicians worked on the problem of determining how to fairly divide something among 3 people so that each person is convinced he got as much as anybody else. There are ways of extending the technique to more than 3 people, but it gets a bit involved. The problem of dividing something among n people so that each person thinks he got at least 1/n is much simpler, but I will not be describing it here.

I will start describing the technique. See if you can complete it. Designate the 3 people as A, B and C. A divides a cake (or pizza if you prefer) into 3 equal (from his point of view) slices. If B thinks that the two larger pieces are the same size then C chooses next, then B and then A. In this case we are done since everyone should be satisfied he has as much as anyone else.

If B thinks the largest piece is bigger than the next largest piece, he cuts a portion of the largest piece so that he thinks the two largest pieces are the same size. The cutting is put on the side for the next stage. Again the order of choosing is C, B and A. The only constraint is that if C does not choose the cut piece then B must choose it. At this point everyone thinks he has at least as much as anyone else.

For the second stage, the piece on the side will be divided in 3 parts and each person chooses one of the parts. Who should do the cutting and in what order should the parts be chosen so that each person feels he ended up with at least as much as anyone else?

Observing members: 0 Composing members: 0

9 Answers

CWOTUS's avatar

I propose a much simpler division.

A makes the first cut of the cake. Just one cut.

If B and C both agree that that slice is fair, that is, no greater than any person was entitled to, then A gets to take it. This leaves the simpler problem of dividing a piece of cake in two pieces, to be shared by B & C.

If B or C decides that the slice that A made was too big, then A gets to divide the remaining piece and take the last choice of pieces. B and C still have to decide how to split the two remaining pieces. If they both agree that the two larger slices are fair, then they can take those and leave A the remainder. If B or C believes that either piece is too large (and the other person is unwilling to concede that piece to the one who so believes), then they can decide who will trim the equalizing portion from that, and the other gets first choice of “apparently equal” portions, the person who made the final cut gets his choice as second, and A, as noted earlier, gets the last choice.

Much less decision making, much quicker, and much less handling of the cake.

LostInParadise's avatar

In your method A is convinced that he has at least ⅓, but he may think that B or C ends up with more than he does. In the method in the problem, each person is convinced that he ends up with at least as much as anyone else. It is called an envy-free division.

CWOTUS's avatar

If A gets ⅓ of the split, then he can have no complaints about how B & C divide their portion.

susanc's avatar

A might look at the larger of the two B and C portions and notice that one was larger than his original slice and want it.

LostInParadise's avatar

I see I have no takers. This is not as difficult as it may at first appear. Let me provide some hints about how to look at the problem.

1. We know that one of B and C has the cut slice. Designate this person as X and the other as Y. That is all the designating that is required.

2. Note that if the person doing the dividing of the trimming goes last, then both the person who goes last and the person who goes first will both be satisfied they did as well as anyone else. The person who goes second will feel he did at least as well as the person who goes last. The only thing to be determined is how to assure that the person who goes second feels he did at least as well as the person who goes first. There is one choice of person going first and person going second that will assure this.

zenvelo's avatar

@LostInParadise Your method is tragically flawed, because then everyone ends up with little bits carved out of the large pieces. @CWOTUS has a much more sane approach, involving only two or three cuts to the whole thing to be divided.

LostInParadise's avatar

Like I said, my method guarantees that each person thinks that his portion is as good as anyone else. @CWOTUS cannot guarantee that with his method. If for example, B and C agree that A’s portion is fair, one of them may end up with a portion that A thinks is larger than his.

It is also difficult to generalize @CWOTUS‘s method to n people. The simplest generalized method guaranteeing that everyone thinks he gets at least 1/n of the cake is to have someone cut off a single slice, which he will keep if nobody objects. If anyone thinks it is too large then they cut off a part of it and will keep it unless someone thinks it is too large. Continue doing this until everyone is satisfied, leaving one person with his portion. Then the remaining n – 1 people do the same thing with the next slice taken from the remainder of the cake, including all the scraps.

A way of doing the above method without so many scraps is to have knife slowly move from left to right over the cake. Someone can get the knife to stop when he thinks the slice on the right is fair. If someone objects then the knife is started up again until that person thinks the slice is fair. This continues until everyone is satisfied. The last person to stop the knife get the slice.

LostInParadise's avatar

Here is a paper on cake cutting by the mathematicians that worked out the general solutions. I have only read parts of it, but it seems fairly readable. There is a nice description of @CWOTUS ‘s method on page 12.

ibstubro's avatar

Just cut it in 6 pieces, then let everyone choose twice, A,B,C – C,B,A.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther