Abstract
We study the problem of dividing a multi-layered cake among heterogeneous agents under non-overlapping constraints. This problem, recently proposed by Hosseini et al. (2020), captures several natural scenarios such as the allocation of multiple facilities over time where each agent can utilize at most one facility simultaneously, and the allocation of tasks over time where each agent can perform at most one task simultaneously. We establish the existence of an envy-free multi-division that is both non-overlapping and contiguous within each layered cake when the number n of agents is a prime power and the number m of layers is at most n, thus providing a positive partial answer to a recent open question. To achieve this, we employ a new approach based on a general fixed point theorem, originally proven by Volovikov (1996), and recently applied by Jojić, Panina, and Živaljević (2020) to the envy-free division problem of a cake. We further show that for a two-layered cake division among three agents with monotone preferences, an \(\varepsilon \)-approximate envy-free solution that is both non-overlapping and contiguous can be computed in logarithmic time of \(1/{\varepsilon }\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Asada, M., et al.: Fair division and generalizations of Sperner- and KKM-type results. SIAM J. Discrete Math. 32(1), 591–610 (2018)
Avvakumov, S., Karasev, R.: Envy-free division using mapping degree. Mathematika 67(1), 36–53 (2020)
Avvakumov, S., Karasev, R.: Equipartition of a segment. arXiv preprint arXiv:2009.09862 (2020)
Aziz, H., Mackenzie, S.: A discrete and bounded envy-free cake cutting protocol for any number of agents. In: Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pp. 416–427 (2016)
Björner, A., Lovász, L., Vrecica, S.T., Živaljević, R.T.: Chessboard complexes and matching complexes. J. London Math. Soc. 49(1), 25–39 (1994)
Cloutier, J., Nyman, K.L., Su, F.E.: Two-player envy-free multi-cake division. Math. Soc. Sci. 59(1), 26–37 (2010)
De Longueville, M.: A Course in Topological Combinatorics. Springer, New York (2012). https://doi.org/10.1007/978-1-4419-7910-0
Deng, X., Qi, Q., Saberi, A.: Algorithmic solutions for envy-free cake cutting. Oper. Res. 60(6), 1461–1476 (2012)
Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Mon. 68(1), 1–17 (1961)
Fan, K.: Simplicial maps from an orientable \(n\)-pseudomanifold into \(S^m\) with the octahedral triangulation. J. Comb. Theor. 2, 588–602 (1967)
Filos-Ratsikas, A., Hollender, A., Sotiraki, K., Zampetakis, M.: A topological characterization of modulo-p arguments and implications for necklace splitting. In: Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2615–2634 (2020)
Hosseini, H., Igarashi, A., Searns, A.: Fair division of time: multi-layered cake cutting. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 182–188 (2020)
Igarashi, A., Meunier, F.: Envy-free division of multi-layered cakes. CoRR, arXiv:2106.02262 (2021)
Jojić, D., Panina, G., Živaljević, R.: Splitting necklaces, with constraints. SIAM J. Discret. Math. 35(2), 1268–1286 (2021)
Kuhn, H.W.: Some combinatorial lemmas in topology. IBM J. Res. Dev. 4(5), 518–524 (1960)
Lebert, N., Meunier, F., Carbonneaux, Q.: Envy-free two-player m-cake and three-player two-cake divisions. Oper. Res. Lett. 41(6), 607–610 (2013)
Matoušek, J.: Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-76649-0
Meunier, F., Su, F.E.: Multilabeled versions of Sperner’s and Fan’s lemmas and applications. SIAM J. Appl. Algebra and Geom. 3(3), 391–411 (2019)
Meunier, F., Zerbib, S.: Envy-free cake division without assuming the players prefer nonempty pieces. Israel J. Math. 234(2), 907–925 (2019). https://doi.org/10.1007/s11856-019-1939-6
Nyman, K., Su, F.E., Zerbib, S.: Fair division with multiple pieces. Discret. Appl. Math. 283, 115–122 (2020)
Panina, G., Živaljević, R.T.: Envy-free division via configuration spaces. arXiv preprint arXiv:2102.06886 (2021)
Segal-Halevi, E.: Fairly dividing a cake after some parts were burnt in the oven. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1276–1284 (2018)
Segal-Halevi, E.: Fair multi-cake cutting. Discret. Appl. Math. 291, 15–35 (2021)
Steinhaus, H.: Sur la division pragmatique. Econometrica 17, 315–319 (1949)
Stromquist, W.: How to cut a cake fairly. Am. Math. Mon. 87(8), 640–644 (1980)
Stromquist, W.: Envy-free cake divisions cannot be found by finite protocols. Electron. J. Comb. 15(1), R11 (2008)
Su, F.E.: Rental harmony: Sperner’s lemma in fair division. Am. Math. Mon. 106(10), 930–942 (1999)
Volovikov, A.Y.: On a topological generalization of the Tverberg theorem. Math. Not. 59(3), 324–326 (1996)
Woodall, D.R.: Dividing a cake fairly. J. Math. Anal. Appl. 78(1), 233–247 (1980)
Živaljević, R.T.: User’s guide to equivariant methods in combinatorics. II. Publications de l’Institut Mathématique. Nouvelle Série 64, 107–132 (1998)
Acknowledgments
Ayumi Igarashi was supported by JST, PRESTO Grant Number JPMJPR20C1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Igarashi, A., Meunier, F. (2022). Envy-free Division of Multi-layered Cakes. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds) Web and Internet Economics. WINE 2021. Lecture Notes in Computer Science(), vol 13112. Springer, Cham. https://doi.org/10.1007/978-3-030-94676-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-94676-0_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-94675-3
Online ISBN: 978-3-030-94676-0
eBook Packages: Computer ScienceComputer Science (R0)