Abstract
Cake cutting is one of the most fundamental settings in fair division and mechanism design without money. In this paper, we consider different levels of three fundamental goals in cake cutting: fairness, Pareto optimality, and strategyproofness. In particular, we present robust versions of envy-freeness and proportionality that are not only stronger than their standard counter-parts but also have less information requirements. We then focus on cake cutting with piecewise constant valuations and present three desirable algorithms: CCEA (Controlled Cake Eating Algorithm), MEA (Market Equilibrium Algorithm) and MCSD (Mixed Constrained Serial Dictatorship). CCEA is polynomial-time, robust envy-free, and non-wasteful. Then, we show that there exists an algorithm (MEA) that is polynomial-time, envy-free, proportional, and Pareto optimal. Moreover, we show that for piecewise uniform valuations, MEA and CCEA are group-strategyproof and are equivalent to Mechanism 1 of Chen et. al.(2013). We then present an algorithm MCSD and a way to implement it via randomization that satisfies strategyproofness in expectation, robust proportionality, and unanimity for piecewise constant valuations. We also present impossibility results that show that the properties satisfied by CCEA and MEA are maximal subsets of properties that can be satisfied by any algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Athanassoglou, S., Sethuraman, J.: House allocation with fractional endowments. International Journal of Game Theory 40(3), 481–513 (2011)
Aziz, H., Ye, C.: Cake cutting algorithms for piecewise constant and piecewise uniform valuations. Technical Report 1307.2908, arXiv.org (2013)
Aziz, H., Brandt, F., Brill, M.: The computational complexity of random serial dictatorship. Economics Letters 121(3), 341–345 (2013)
Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. Journal of Economic Theory 100(2), 295–328 (2001)
Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72(1), 257–279 (2004)
Brams, S.J.: Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton University Press (2008)
Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press (1996)
Brams, S.J., Feldman, M., Morgenstern, J., Lai, J.K., Procaccia, A.D.: On maxsum fair cake divisions. In: Proc. of 26th AAAI Conference, pp. 1285–1291. AAAI Press (2012)
Chen, Y., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Truth, justice, and cake cutting. In: Proc. of 24th AAAI Conference, pp. 756–761 (2010)
Chen, Y., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Truth, justice, and cake cutting. Games and Economic Behavior 77(1), 284–297 (2013)
Cohler, Y.J., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Optimal envy-free cake cutting. In: Proc. of 25th AAAI Conference, pp. 626–631 (2011)
Devanur, N., Papadimitriou, C.H., Saberi, A., Vazirani, V.: Market equilibrium via a primal–dual algorithm for a convex program. Journal of the ACM 55(5) (2008)
Katta, A.-K., Sethuraman, J.: A solution to the random assignment problem on the full preference domain. Journal of Economic Theory 131(1), 231–250 (2006)
Maya, A., Nisan, N.: Incentive compatible two player cake cutting. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 170–183. Springer, Heidelberg (2012)
Mossel, E., Tamuz, O.: Truthful fair division. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 288–299. Springer, Heidelberg (2010)
Reijnierse, J.H., Potters, J.A.M.: On finding an envy-free Pareto-optimal division. Mathematical Programming 83, 291–311 (1998)
Robertson, J.M., Webb, W.A.: Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters (1998)
Saban, D., Sethuraman, J.: The complexity of computing the random priority allocation matrix. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, p. 421. Springer, Heidelberg (2013)
Schummer, J.: Strategy-proofness versus efficiency on restricted domains of exchange economies. Social Choice and Welfare 14, 47–56 (1997)
Tian, Y.: Strategy-proof and efficient offline interval scheduling and cake cutting. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 436–437. Springer, Heidelberg (2013)
Zivan, R., Dudík, M., Okamoto, S., Sycara, K.: Reducing untruthful manipulation in envy-free pareto optimal resource allocation. In: IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, pp. 391–398 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Aziz, H., Ye, C. (2014). Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations. In: Liu, TY., Qi, Q., Ye, Y. (eds) Web and Internet Economics. WINE 2014. Lecture Notes in Computer Science, vol 8877. Springer, Cham. https://doi.org/10.1007/978-3-319-13129-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-13129-0_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13128-3
Online ISBN: 978-3-319-13129-0
eBook Packages: Computer ScienceComputer Science (R0)