Thursday, August 16, 2012

The Steinhaus-Kuhn lone-divider Procedure

The lone-divider procedure is another classic proportional cake-cutting procedures. It was presented by Kuhn back in 1967. This procedure has an interesting property, that throughout the process, we only need one agent to make multiple cuts.

To illustrate the procedure, here we present an example for 3 agents, say Alice, Bob and Carol.

1. Let Alice cut the cake into 3 pieces of equal value based on her utility function.
2. Now let Bob and Carol to indicate which pieces are acceptable to them (at least of value 1/3 based on their own utility functions).
3. Then we have two mutually exclusive cases:
    Case I: Either Bob or Carol finds two or more pieces are acceptable. Say Bob finds more than 1 piece acceptable. Then choosing in order of Carol, Bob and Alice will result in a proportional allocation.
    Case II: Both Bob and Carol indicate at most one piece is acceptable. We first gives the piece that both Bob and Carol find unacceptable to Alice, then we do a Cut-and-Choose between Bob and Carol. In this way, we will end up with a proportional allocation.

Kuhn extended this procedure to any number of players in 1967 with the help of some combinatorial theorem. The basic logic still remains the same.

Reference: S. J. Brams, A. D. Taylor, 1996, Fair Division: From cake-cutting to dispute resolution, pp. 31, 2.2



No comments:

Post a Comment