During my military service in Ankara, in one of the lectures at the military academy, a commander was talking about how to command the team in a fair manner. And he asked "How do you think 2 guys share a cake without envying to each other's piece?" Our answers involved the use of measurement tools but the commander gave the prerequisite that they cannot use any measurement tools, but the knife, hands and eyes. Then, the answer was very clever: "I cut, you choose" procedure works pretty fine for two guys. The first one cuts the cake into 2 equal pieces according to his perception of equity. And the second guy chooses the piece to pick for himself. No one envies.
When you are dealing with such a problem, and when you are a young engineer, your brain generates subsequent problems immediately: What if there are 3 guys to share the cake? I was not able to google this under those circumstances so I and a couple of my "brother-in-arms" discussed the problem and offered some premature solutions. Most successful one was reducing the problem t0 2 guys model after 1 arbitrary guy cuts the cake into 3 pieces. Procedure was like this for players A, B, C:
- One of the guys, let's say A, cuts the cake into 3 pieces
- B chooses one of the pieces
- C chooses one of the pieces
- A picks the last piece on the table
- A-C, A-B, C-B pairs try to agree that all the pieces are equal. If they cannot agree, they use the "I cut, you choose" procedure for their pieces.
For example, after step 4, A checks the piece which belongs to B and if he envies B's piece, B cuts his piece into two and A picks one of the pieces and then, A cuts his piece into two and B picks one of the A's pieces and at the end they end up with an envy-free division. As a conclusion, A and B have 4 smaller pieces. After that, player C may want to do "I cut, you choose" with B and this operation results in C and B having 6 pieces. And the round goes...
The problem with this approach was this procedure tends to last forever because after A-B, B-C, A-C agreements, B might envy C's pieces and they start sharing again, the second tour... Perhaps, in practice it never goes too far but the procedure must be able to halt in a meaningful fashion.
After all the discussions, I have not focused on the problem for about 4 years.
Then suddenly the problem grabbed me again. But this time, I googled :)) And of course, I found all the literature about envy-free cake division problem. There are more than 6 algorithms designed. To me, two of them are very good: The first one was announced by Selfridge & Conway in 1960s. The latter is called "moving knives" and devised by Stromquist. I will explain the first one here.
The problem: Parties A, B and C want to share the cake fairly. They will use just a knife.
Figure 1. Selfridge & Conway stage 1.
The procedure comprises 2 stages. In stage 1,
- Party A cuts the cake into 3 pieces regarding just his feelings of equity (step II in fig. 1).
- Party B controls the pieces, if he thinks that at least two of the pieces are good for choosing (means those two are equal), he does nothing.
- Party C picks a piece.
- Party B picks a piece.
- Party A picks the remaining piece.
Everything is perfect. However, if party B thinks that one piece is quite bigger than the other ones, in the second bullet above, he takes the knife and trims the biggest piece in order to produce at least 2 tied pieces. (See the III in fig. 1) Then, no one can pick the "trm" bit in the stage 1. And procedure goes:
- Party C chooses a piece.
- If party C did not choose the trimmed piece (piece number 3 in fig. 1), party B has to pick trimmed piece.
- Party A picks the remaining one.
Stage 1 is done. No one envies the other. Now, it is time to divide the "trm" bit.
Figure 2. Selfridge & Conway stage 2.
- Among B and C, the party who did not pick the trimmed piece in stage 1 cuts the trm bit into 3 by his knife.
- If the party who cuts the trimming into 3 is B, then the parties pick the pieces (t1, t2, t3 in fig. 2) in C, A, B order. If the party that cuts the trm bit is C then the picking order is B, A, C.
Stage 2 ends. It is an envy-free division process. We're all done with this.
The problem, of course, goes too far by considering n parties to share the cake :)) but let us leave the rest of the story to the mathematicians.
No comments:
Post a Comment