Jeff Edmonds
Abstract
We consider the well-known cake cutting problem in which a protocol wants to divide a cake among n ≥ 2 players in such a way that each player believes that they got a fair share. The standard Robertson-Webb model allows the protocol to make two types of queries, Evaluation and Cut, to the players. A deterministic divide-and-conquer protocol with complexity O(n log n) is known. We provide the first a Ω(n log n) lower bound on the complexity of any deterministic protocol in the standard model. This improves previous lower bounds, in that the protocol is allowed to assign to a player a piece that is a union of intervals and only guarantee approximate fairness. We accomplish this by lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width. We then introduce a version of cake cutting in which the players are able to cut with only finite precision. In this case, we can extend the Ω(n log n) lower bound to include randomized protocols.
- Brams, S. and Taylor, A. 1996. Fair Division—From Cake Cutting to Dispute Resolution. Cambridge University Press.Google Scholar
- Edmonds, J. and Pruhs, K. 2006. Balanced allocations of cake. In Proceedings of the IEEE Symposium on the Foundations of Computer Science. 623--634. Google ScholarDigital Library
- Edmonds, J., Pruhs, K., and Solanki, J. 2008. Confidently cutting a cake into approximately fair pieces. In Proceedings of the International Conference on Algorithmic Aspects in Information and Management. 155--164. Google ScholarDigital Library
- Even, S. and Paz, A. 1984. A note on cake cutting. Disc. Appl. Math. 7, 285--296.Google ScholarCross Ref
- Krumke, S. O., Lipmann, M., de Paepe, W. E., Poensgen, D., Rambau, J., Stougie, L., and Woeginger, G. J. 2002. How to cut a cake almost fairly. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 263--264. Google ScholarDigital Library
- Magdon-Ismail, M., Busch, C., and Krishnamoorthy, M. 2003. Cake cutting is not a piece of cake. In Proceedings of the Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science Series, vol. 2607. 596--607. Google ScholarDigital Library
- Robertson, J. and Webb, W. 1995. Approximating fair division with a limited number of cuts. J. Combinat. Theory, Ser. A 72, 340--344. Google ScholarDigital Library
- Robertson, J. and Webb, W. 1998. Cake-Cutting Algorithms: Be Fair If You Can. A.K. Peters, Ltd.Google Scholar
- Sgall, J. and Woeginger, G. J. 2003. A lower bound for Cake Cutting. Lecture Notes in Computer Science Series, vol. 2461. Springer-Verlag.Google Scholar
- Steinhaus, H. 1948. The problem of fair division. Econometrica 16, 101--104.Google Scholar
- Woeginger, G. J. 2002. An approximation scheme for cake division with a linear number of cuts. In Proceedings of the European Symposium on Algorithms. Springer-Verlag, 896--901. Google ScholarDigital Library
Index Terms
- Cake cutting really is not a piece of cake
Recommendations
Equilibrium analysis in cake cutting
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systemsCake cutting is a fundamental model in fair division; it represents the problem of fairly allocating a heterogeneous divisible good among agents with different preferences. The central criteria of fairness are proportionality and envy-freeness, and many ...
Cake cutting really is not a piece of cake
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithmWe consider the well-known cake cutting problem in which a protocol wants to divide a cake among n ≥ 2 players in such a way that each player believes that they got a fair share. The standard Robertson-Webb model allows the protocol to make two types of ...
Comments