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.

Approximate Envy-Free Moving-Knife Procedure

This approximation procedure is based on the original Dubins-Spanier moving-knife procedure. Unlike the original procedure, now we allow agents to re-enter the game and call "cut" again and again. However, each time they call cut, they have to claim for a piece larger than the existing piece by \(\epsilon\), and they have to return the previous piece they have and merge it with the remaining. In this way, all the agents at last will have a piece that is smaller than the largest piece by at most \(\epsilon\).

Please note that it is impossible to get an allocation where one agent gets nothing and all the other agents get at least \(\frac{1}{n}\). Since there will always be \(n\) pieces of cakes (agent have to return their previous piece when they claim for another piece), they cannot be all smaller than \(\frac{1}{n}\) for the agent who gets nothing.

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