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
No comments:
Post a Comment