Geodesic
Cooperative envy-free division
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXXV, Tome 528 (2023), pp. 116-133 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Relying on configuration spaces and equivariant topology, we study a general “cooperative envy-free division problem” where the players have more freedom of expressing their preferences (compared to the classical setting of the Stromquist-Woodall-Gale theorem). A group of players want to cut a “cake” $I=[0,1]$ and divide among themselves the pieces in an envy-free manner. Once the cake is cut and served in plates on a round table (at most one piece per plate), each player makes her choice by pointing at one (or several) plates she prefers. The novelty is that her choice may depend on the whole allocation configuration. In particular, a player may choose an empty plate (possibly preferring one of the empty plates over the other), and take into account not only the content of her preferred plate, but also the content of the neighbouring plates. We show that if the number of players is a prime power, in this setting an envy-free division still exists under standard assumptions that the preferences are closed. 
@article{ZNSL_2023_528_a7,
     author = {D. Joji\'c and G. Panina and R. \v{Z}ivaljevi\'c},
     title = {Cooperative envy-free division},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {116--133},
     year = {2023},
     volume = {528},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2023_528_a7/}
}
TY  - JOUR
AU  - D. Jojić
AU  - G. Panina
AU  - R. Živaljević
TI  - Cooperative envy-free division
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2023
SP  - 116
EP  - 133
VL  - 528
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2023_528_a7/
LA  - en
ID  - ZNSL_2023_528_a7
ER  - 
%0 Journal Article
%A D. Jojić
%A G. Panina
%A R. Živaljević
%T Cooperative envy-free division
%J Zapiski Nauchnykh Seminarov POMI
%D 2023
%P 116-133
%V 528
%U http://geodesic.mathdoc.fr/item/ZNSL_2023_528_a7/
%G en
%F ZNSL_2023_528_a7
D. Jojić; G. Panina; R. Živaljević. Cooperative envy-free division. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXXV, Tome 528 (2023), pp. 116-133. http://geodesic.mathdoc.fr/item/ZNSL_2023_528_a7/

[1] R. N. Anderson, M. M. Marjanović, R. M. Schori, “Symmetric products and higher dimensional dunce hats”, Topology Proceedings, 18 (1993), 7–17

[2] S. Avvakumov, R. Karasev, “Envy-free division using mapping degree”, Mathematika, 67:1 (2021), 36–53

[3] A. Björner, L. Lovász, S. T. Vrećica, and R. T. Živaljević, “Chessboard complexes and matching complexes”, J. London Math. Soc. (2), 49 (1994), 25–39

[4] D. Gale, “Equilibrium in a discrete exchange economy with money”, International Journal of Game Theory, 13:1 (1984), 61–64

[5] F. Frick, K. Houston-Edwards, F. Meunier, “Achieving Rental Harmony with a Secretive Roommate”, The American Mathematical Monthly, 126 (2017), 18–32

[6] M. D. Hirsch, M. Magill and A. Mas-Colell, “A geometric approach to a class of equilibrium existence theorems”, J. Math. Econom., 19 (1990), 95–106

[7] S. Y. Husseini, J.-M. Lasry, M. J. P. Magill, “Existence of equilibrium with incomplete markets”, J. Math. Econom., 19 (1990), 39–67

[8] D. Jojić, G. Panina, R.T. Živaljević, “Splitting necklaces, with constraints”, SIAM J. Discret. Math., 35:2 (2021), 1268–1286

[9] D. Jojić, G. Panina, R. T. Živaljević, “Optimal colored Tverberg theorems for prime powers”, Homology, Homotopy and Applications, 24:2 (2022), 69–92

[10] D. N. Kozlov, “Topology of scrambled simplices”, Journal of Homotopy and Related Structures, 14 (2019), 371–391

[11] J. Matoušek, Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, Heidelberg, 2003 (Corrected 2nd printing 2008)

[12] F. Meunier, S. Zerbib, Envy-free cake division without assuming the players prefer nonempty pieces, Israel J. Math., 2019 (to appear) , arXiv: 1804.00449v2

[13] G. Panina, R. T. Živaljević, “Envy-free division via configuration spaces”, Topol. Methods Nonlinear Anal., 2022

[14] G. Panina, R. Živaljević, “Envy-free division in the presence of a dragon”, J. Fixed Point Theory Appl., 24 (2022), 81 | DOI

[15] E. Segal-Halevi, “Fairly dividing a cake after some parts were burnt in the oven”, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, 2018, 1276–1284

[16] P. Soberón, Fair distributions for more participants than allocations, arXiv: 2110.03600

[17] W. Stromquist, “How to cut a cake fairly”, The American Mathematical Monthly, 87:8 (1980), 640–644

[18] S. Todorčević, Topics in Topology, Lecture Notes in Mathematics, 1652, Springer-Verlag, Berlin–Heidelberg, 1997

[19] A. Y. Volovikov, “On a topological generalization of the Tverberg theorem”, Math. Notes, 59 (1996), 324–326

[20] S. Vrećica, R. Živaljević, “Chessboard complexes indomitable”, Journal of Combinatorial Theory, Series A, 118 (2011), 2157–2166

[21] D. R. Woodall, “Dividing a cake fairly”, J. Math. Anal. Appl., 78:1 (1980), 233–247

[22] R.T. Živaljević, “Topological methods in discrete geometry”, Handbook of Discrete and Computational Geometry, Chapter 21, third edition, eds. J.E. Goodman, J. O'Rourke, C. D. Tóth, CRC Press LLC, 2017, 551–580

[23] R. T. Živaljević, S.T. Vrećica, “The colored Tverberg's problem and complexes of injective functions”, J. Combin. Theory Ser. A, 61 (1992), 309–318