×

Fair division and generalizations of Sperner- and KKM-type results. (English) Zbl 1385.54013

Authors’ abstract: We treat problems of fair division, their various interconnections, and their relations to Sperner’s lemma and the Knaster-Kuratowski-Mazurkiewicz (KKM) theorem as well as their variants. We prove extensions of Alon’s necklace splitting result [N. Alon, Adv. Math. 63, 247–253 (1987; Zbl 0635.05008)] in certain regimes and relate it to hyperplane mass partitions. We show the existence of fair cake division and rental harmony in the sense of F. E. Su [Am. Math. Mon. 106, No. 10, 930–942 (1999; Zbl 1010.05077)] even in the absence of full information. Furthermore, we extend Sperner’s lemma and the KKM theorem to (colorful) quantitative versions for polytopes and pseudomanifolds.

MSC:

54H25 Fixed-point and coincidence theorems (topological aspects)
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, {\it Splitting necklaces}, Adv. Math., 63 (1987), pp. 247-253. · Zbl 0635.05008
[2] N. Alon, D. Moshkovitz, and S. Safra, {\it Algorithmic construction of sets for k-restrictions}, ACM Trans. Algorithms, 2 (2006), pp. 153-177. · Zbl 1321.68445
[3] N. Alon and D. B. West, {\it The Borsuk-Ulam theorem and bisection of necklaces}, Proc. Amer. Math. Soc., 98 (1986), pp. 623-628. · Zbl 0614.05005
[4] K. T. Atanassov, {\it On Sperner’s lemma}, Studia Sci. Math. Hungar., 32 (1996), pp. 71-74. · Zbl 1012.52501
[5] D. Avis, {\it Non-partitionable point sets}, Inform. Process Lett., 19 (1984), pp. 125-129. · Zbl 0564.51007
[6] H. Aziz and S. Mackenzie, {\it 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), IEEE, Piscataway, NJ, 2016, pp. 416-427. · Zbl 1373.68251
[7] R. B. Bapat, {\it A constructive proof of a permutation-based generalization of Sperner’s lemma}, Math. Program., 44 (1989), pp. 113-120. · Zbl 0673.55004
[8] I. Bárány, {\it A generalization of Carathéodory’s theorem}, Discrete Math., 40 (1982), pp. 141-152. · Zbl 0492.52005
[9] D. Barnette, {\it A proof of the lower bound conjecture for convex polytopes}, Pacific J. Math., 46 (1973), pp. 349-354. · Zbl 0264.52006
[10] P. V. M. Blagojevic, F. Frick, A. Haase, and G. M. Ziegler, {\it Topology of the Grünbaum-Hadwiger-Ramos Hyperplane Mass Partition Problem}, preprint, , 2015. · Zbl 1396.52011
[11] P. V. M. Blagojevic, F. Frick, A. Haase, and G. M. Ziegler, {\it Hyperplane mass partitions via relative equivariant obstruction theory}, Doc. Math., 21 (2016), pp. 735-771. · Zbl 1361.55007
[12] P. V. M. Blagojević and P. Soberón, {\it Thieves can make sandwiches}, Bull. Lond. Math. Soc., to appear. · Zbl 1390.52008
[13] J. A. De Loera, E. Peterson, and F. E. Su, {\it A polytopal generalization of Sperner’s lemma}, J. Combin. Theory Ser. A, 100 (2002), pp. 1-26. · Zbl 1015.05089
[14] M. De Longueville and R. Živaljević, {\it Splitting multidimensional necklaces}, Adv. Math., 218 (2008), pp. 926-939. · Zbl 1154.05006
[15] T. Epping, W. Hochstättler, and P. Oertel, {\it Complexity results on a paint shop problem}, Discrete Appl. Math., 136 (2004), pp. 217-226. · Zbl 1036.90035
[16] A. Fogelsanger, {\it The Generic Rigidity of Minimal Cycles}, Dissertation, Cornell University, Ithaca, NY, 1988.
[17] D. Gale, {\it Equilibrium in a discrete exchange economy with money}, Internat. J. Game Theory, 13 (1984), pp. 61-64. · Zbl 0531.90011
[18] C. H. Goldberg and D. B. West, {\it Bisection of circle colorings}, SIAM J. Algebr. Discrete Methods, 6 (1985), pp. 93-106. · Zbl 0558.05008
[19] B. Grünbaum, {\it On the facial structure of convex polytopes}, Bull. Amer. Math. Soc., 71 (1965), pp. 559-560. · Zbl 0137.18002
[20] H. Hadwiger, {\it Simultane Vierteilung zweier Körper}, Arch. Math. (Basel), 17 (1966), pp. 274-278. · Zbl 0137.41501
[21] G. Kalai, {\it Rigidity and the lower bound theorem 1}, Invent. Math., 88 (1987), pp. 125-151. · Zbl 0624.52004
[22] R. Karasev, E. Roldán-Pensado, and P. Soberón, {\it Measure partitions using hyperplanes with fixed directions}, Israel J. Math., 212 (2016), pp. 705-728. · Zbl 1344.52006
[23] B. Knaster, C. Kuratowski, and S. Mazurkiewicz, {\it Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe}, Fund. Math., 14 (1929), pp. 132-137.
[24] P. Mani-Levitska, S. Vrećica, and R. Živaljević, {\it Topology and combinatorics of partitions of masses by hyperplanes}, Adv. Math., 207 (2006), pp. 266-296. · Zbl 1110.68155
[25] J. Matoušek, {\it Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry}, 2nd ed., Springer, Heidelberg, 2008. · Zbl 1234.05002
[26] F. Meunier, {\it Sperner labellings: A combinatorial approach}, J. Combin. Theory Ser. A, 113 (2006), pp. 1462-1475. · Zbl 1108.52012
[27] F. Meunier, {\it Discrete splittings of the necklace}, Math. Oper. Res., 33 (2008), pp. 678-688. · Zbl 1232.05248
[28] M. Mirzakhani and J. Vondrák, {\it Sperner’s colorings, hypergraph labeling problems and fair division}, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 873-886. · Zbl 1371.05094
[29] O. R. Musin, {\it Around Sperner’s Lemma}, preprint, , 2014.
[30] O. R. Musin, {\it Extensions of Sperner and Tucker’s lemma for manifolds}, J. Combin. Theory Ser. A, 132 (2015), pp. 172-187. · Zbl 1307.05195
[31] O. R. Musin, {\it KKM type theorems with boundary conditions}, J. Fixed Point Theory Appl., 19 (2017), pp. 2037-2049. · Zbl 1383.54050
[32] E. A. Ramos, {\it Equipartition of mass distributions by hyperplanes}, Discrete Comput. Geom., 15 (1996), pp. 147-167. · Zbl 0843.68120
[33] E. Sperner, {\it Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes}, in Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, Vol. 6, Springer, Berlin, 1928, pp. 265-272.
[34] F. E. Su, {\it Rental harmony: Sperner’s lemma in fair division}, Amer. Math. Monthly, 106 (1999), pp. 930-942. · Zbl 1010.05077
[35] T.-S. Tay, {\it Lower-bound theorems for pseudomanifolds}, Discrete Comput. Geom., 13 (1995), pp. 203-216. · Zbl 0817.52016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.