{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313447,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:00:00Z","timestamp":1681516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:00:00Z","timestamp":1681516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR20C1"],"award-info":[{"award-number":["JPMJPR20C1"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece\u2014a subinterval. The analogue for the discrete case corresponds to the fair division of a graph<\/jats:italic>, where allocations must be contiguous<\/jats:italic> so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item<\/jats:italic> (EF1<\/jats:italic>) as the fairness criterion, however, positive results for three or more agents have mostly been limited to traceable graphs. We introduce tangles as a new context for fair division. A tangle is a more complicated cake\u2014a connected topological space constructed by gluing together several copies of the unit interval [0,\u00a01]\u2014and each single tangle $$\\mathcal {T}$$<\/jats:tex-math>\n T<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> corresponds in a natural way to an infinite topological class $$\\mathcal {G}(\\mathcal {T})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n T<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of graphs, linking envy-free fair division of tangles to EFk<\/jats:italic> fair division of graphs. In addition to the unit interval itself, we show that only five other stringable<\/jats:italic> tangles guarantee the existence of envy-free and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle $$\\mathcal {T}$$<\/jats:tex-math>\n T<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has a bound r<\/jats:italic> on the number of agents for which such allocations necessarily exist, and our Negative Transfer Principle<\/jats:italic> then applies to the graphs in $$\\mathcal {T}$$<\/jats:tex-math>\n T<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u2019s class; for any integer $$k \\ge 1$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, almost all graphs in this class are non-traceable and fail to guarantee EFk<\/jats:italic> contiguous allocations for $$r + 1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or more agents, even when very strict requirements are placed on the valuation functions for the agents. With bounds on the number of agents, however, we obtain positive results for some non-stringable classes. An elaboration of Stromquist\u2019s moving knife procedure shows that the non-stringable lips tangle $$\\mathcal {L}$$<\/jats:tex-math>\n L<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist\u2019s procedure in Bil\u00f2 et al. (Games Econ Behav 131:197\u2013221, 2022) to show that all graphs in the topological class $$\\mathcal {G}(\\mathcal {L})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n L<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (most of which are non-traceable) guarantee EF1 allocations for three agents.<\/jats:p>","DOI":"10.1007\/s10107-023-01945-5","type":"journal-article","created":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T11:02:02Z","timestamp":1681556522000},"page":"931-975","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fair division of graphs and of tangled cakes"],"prefix":"10.1007","volume":"203","author":[{"given":"Ayumi","family":"Igarashi","sequence":"first","affiliation":[]},{"given":"William S.","family":"Zwicker","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,15]]},"reference":[{"issue":"3","key":"1945_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.mathsocsci.2004.03.006","volume":"48","author":"JB Barbanel","year":"2004","unstructured":"Barbanel, J.B., Brams, S.: Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond. Math. Soc. Sci. 48(3), 251\u2013269 (2004)","journal-title":"Math. Soc. Sci."},{"issue":"2","key":"1945_CR2","doi-asserted-by":"publisher","first-page":"1156","DOI":"10.1137\/20M1388310","volume":"36","author":"X Bei","year":"2022","unstructured":"Bei, X., Igarashi, A., Lu, X., Suksompong, W.: The price of connectivity in fair division. SIAM J. Discret. Math. 36(2), 1156\u20131186 (2022)","journal-title":"SIAM J. Discret. Math."},{"key":"1945_CR3","doi-asserted-by":"crossref","unstructured":"Bei, X., Suksompong, W.: Dividing a graphical cake. Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5159\u20135166 (2021)","DOI":"10.1609\/aaai.v35i6.16652"},{"key":"1945_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.geb.2021.11.006","volume":"131","author":"V Bil\u00f2","year":"2022","unstructured":"Bil\u00f2, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C., Zwicker, W.S.: Almost envy-free allocations with connected bundles. Games Econom. Behav. 131, 197\u2013221 (2022)","journal-title":"Games Econom. Behav."},{"key":"1945_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory, 1st edn. Springer, Berlin (2008)","edition":"1"},{"key":"1945_CR6","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., Peters, D.: Fair division of a graph. Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 135\u2013141 (2017)","DOI":"10.24963\/ijcai.2017\/20"},{"key":"1945_CR7","unstructured":"Br\u00e2nzei, S., Nisan, N.: The query complexity of cake cutting. arXiv:1705.02946v3 (2017)"},{"key":"1945_CR8","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1090\/S0002-9939-97-03614-9","volume":"125","author":"S Brams","year":"1997","unstructured":"Brams, S., Taylor, A., Zwicker, W.S.: A moving-knife solution to the four-person envy-free cake-division problem. Proc. Am. Math. Soc. 125, 547\u2013554 (1997)","journal-title":"Proc. Am. Math. Soc."},{"key":"1945_CR9","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119, 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"1945_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3355902","volume":"7","author":"I Caragiannis","year":"2019","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7(3), 1\u201332 (2019)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1945_CR11","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Ganian, R., Hamm, T., Ordyniak, S.: The parameterized complexity of connected fair division. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 139\u2013145 (2021)","DOI":"10.24963\/ijcai.2021\/20"},{"key":"1945_CR12","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Ganian, R., Hamm, T., Ordyniak, S.: The complexity of envy-free graph cutting. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 237\u2013243 (2022)","DOI":"10.24963\/ijcai.2022\/34"},{"key":"1945_CR13","doi-asserted-by":"crossref","unstructured":"Elkind, E., Segal-Halevi, E., Suksompong, W.: Graphical cake cutting via maximin share. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 161\u2013167 (2021)","DOI":"10.24963\/ijcai.2021\/23"},{"key":"1945_CR14","doi-asserted-by":"crossref","unstructured":"Greco, G., Scarcello, F.: The complexity of computing maximin share allocations on graphs. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2006\u20132013 (2020)","DOI":"10.1609\/aaai.v34i02.5572"},{"key":"1945_CR15","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Peters, D.: Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 2045\u20132052 (2019)","DOI":"10.1609\/aaai.v33i01.33012045"},{"key":"1945_CR16","doi-asserted-by":"crossref","unstructured":"Igarashi, A.: How to cut a discrete cake fairly. arXiv:2209.01348 (2022)","DOI":"10.1609\/aaai.v37i5.25705"},{"key":"1945_CR17","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce (ACM-EC), pp. 125\u2013131 (2004)","DOI":"10.1145\/988772.988792"},{"issue":"8","key":"1945_CR18","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1080\/00029890.1980.11995109","volume":"87","author":"W Stromquist","year":"1980","unstructured":"Stromquist, W.: How to cut a cake fairly. Am. Math. Mon. 87(8), 640\u2013644 (1980)","journal-title":"Am. Math. Mon."},{"issue":"10","key":"1945_CR19","doi-asserted-by":"publisher","first-page":"930","DOI":"10.2307\/2589747","volume":"106","author":"FE Su","year":"1999","unstructured":"Su, F.E.: Rental harmony: Sperner\u2019s lemma in fair division. Am. Math. Mon. 106(10), 930\u2013942 (1999)","journal-title":"Am. Math. Mon."},{"key":"1945_CR20","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1613\/jair.1.11702","volume":"69","author":"M Truszczynski","year":"2020","unstructured":"Truszczynski, M., Lonc, Z.: Maximin share allocations on cycles. J. Artif. Intell. Res. 69, 613\u2013655 (2020)","journal-title":"J. Artif. Intell. Res."},{"issue":"2","key":"1945_CR21","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34(2), 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"1945_CR22","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0022-247X(80)90225-5","volume":"78","author":"DR Woodall","year":"1980","unstructured":"Woodall, D.R.: Dividing a cake fairly. J. Math. Anal. Appl. 78(1), 233\u2013247 (1980)","journal-title":"J. Math. Anal. Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01945-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01945-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01945-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T18:08:25Z","timestamp":1707502105000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01945-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,15]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1945"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01945-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,4,15]]},"assertion":[{"value":"31 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}