## Monday, August 13, 2012

### Dubins-Spanier Moving-knife Method

This is one of the classic proportional procedures. It is proposed by L. E. Dubins and E. H Spanier back in 1961.

Given a group of $$n$$ agents and a bar cake, a referee holds a knife parallel to edge of the cake and moves slowly across the whole cake from left to right. When an agent calls "cut", he will get the piece to the left of the blade. The claim is, in this way, the best strategy for agents is to call cut exactly at $$\frac{1}{n}$$ position based on their own utility functions. For the last two agents, we do a cut-and-choose. This will give us a proportional allocation.

This procedure is based on one key assumption, that the agents are maximum risk averse. In other words, the agent care only about the maxmin value. Given this assumption, it is not hard to see that calling cut at $$\frac{1}{n}$$ gives us the highest maxmin value.

As we can see earlier, the last two agents who call "cut" will get a piece larger than $$\frac{1}{n}$$. Therefore, it is possible that all agents may wait for others to call "cut" at the same time, and thus it ends up no one calls throughout the whole procedure. To avoid this, we can simple make a random allocation if no one calls. Since agents are maximum risk averse, this will drive them to call "cut" in order to guarantee a $$\frac{1}{n}$$ maxmin value.

Reference: L. E. Dubins, E. H. Spanier, 1961, How to Cut A Cake Fairly, The American Mathematical Monthly.