Friday, August 17, 2012

The Fink lone-chooser procedure

This proportional cake-cutting procedure was proposed by Fink in 1964. It has a very nice property that the agent does not need to know the total number of agents before he cuts. Now we show the procedure on a 3 agents case.

Say the agents are Alice, Bob and Carol:

  1. Let Alice bisects the cake into two equal pieces based on his utility function.
  2. Bob chooses the larger piece for himself and leaves the other one for Alice.
  3. Now Alice and Bob trisect their pieces. Carol then selects the largest piece out of the three pieces from Alice and Bob. Leaving the remainder to Alice and Bob.

It is not hard to show that everyone gets a proportional piece from this allocation. If \(n=4\), Alice, Bob and Carol will quadrisect their three pieces at the next stage, and the fourth agent, say David, will piece the largest one from each of the three pieces. The algorithm continues in a similar way for any \(n\).


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

No comments:

Post a Comment