{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T00:20:36Z","timestamp":1782778836003,"version":"3.54.5"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR20C1"],"award-info":[{"award-number":["JPMJPR20C1"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJER2301"],"award-info":[{"award-number":["JPMJER2301"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05795"],"award-info":[{"award-number":["JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE-T2EP20221-0001"],"award-info":[{"award-number":["MOE-T2EP20221-0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE-T2EP20221-0001"],"award-info":[{"award-number":["MOE-T2EP20221-0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required.<\/jats:p>","DOI":"10.1007\/s00453-024-01271-y","type":"journal-article","created":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T06:02:05Z","timestamp":1726898525000},"page":"3653-3683","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reachability of Fair Allocations via Sequential Exchanges"],"prefix":"10.1007","volume":"86","author":[{"given":"Ayumi","family":"Igarashi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Naoyuki","family":"Kamiyama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheung Man","family":"Yuen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,9,21]]},"reference":[{"key":"1271_CR1","doi-asserted-by":"crossref","unstructured":"Akrami, H., Alon, N., Chaudhury, B.R., Garg, J., Mehlhorn, K., Mehta, R.: EFX: a simpler approach and an (almost) optimal guarantee via rainbow cycle number. In: Proceedings of the 24th ACM Conference on Economics and Computation (EC), p.\u00a061 (2023)","DOI":"10.1145\/3580507.3597799"},{"issue":"2","key":"1271_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. Discrete Math. 36(2), 1156\u20131186 (2022)","journal-title":"SIAM J. Discrete Math."},{"key":"1271_CR3","unstructured":"Berendsohn, B.A., Boyadzhiyska, S., Kozma, L.: Fixed-point cycles and approximate EFX allocations. In: Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 17:1\u201317:13 (2022)"},{"key":"1271_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 Econ. Behav. 131, 197\u2013221 (2022)","journal-title":"Games Econ. Behav."},{"key":"1271_CR5","unstructured":"Bonamy, M., Bousquet, N., Heinrich, N., Ito, T., Kobayashi, Y., Mary, A., M\u00fchlenthaler, M., Wasa, K.: The perfect matching reconfiguration problem. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 80:1\u201380:14 (2019)"},{"key":"1271_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975","volume-title":"Fair Division: From Cake-Cutting to Dispute Resolution","author":"SJ Brams","year":"1996","unstructured":"Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press (1996)"},{"issue":"6","key":"1271_CR7","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(6), 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"key":"1271_CR8","doi-asserted-by":"crossref","unstructured":"Freeman, R., Micha, E., Shah, N.: Two-sided matching meets fair division. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 203\u2013209 (2021)","DOI":"10.24963\/ijcai.2021\/29"},{"key":"1271_CR9","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s, L., Lesca, J., Wilczynski, A.: Object allocation via swaps along a social network. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 213\u2013219 (2017)","DOI":"10.24963\/ijcai.2017\/31"},{"issue":"4","key":"1271_CR10","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput. 10(4), 713\u2013717 (1981)","journal-title":"SIAM J. Comput."},{"key":"1271_CR11","doi-asserted-by":"crossref","unstructured":"Huang, S., Xiao, M.: Object reachability via swaps under strict and weak preferences. Auton. Agents Multi-Agent Syst. 34(2), 51:1\u201351:33 (2020)","DOI":"10.1007\/s10458-020-09477-4"},{"key":"1271_CR12","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Kawase, Y., Suksompong, W., Sumita, H.: Fair division with two-sided preferences. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2756\u20132764 (2023)","DOI":"10.24963\/ijcai.2023\/307"},{"key":"1271_CR13","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Kamiyama, N., Suksompong, W., Yuen, S.M.: Reachability of fair allocations via sequential exchanges. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 9773\u20139780 (2024)","DOI":"10.1609\/aaai.v38i9.28836"},{"issue":"12\u201314","key":"1271_CR14","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1271_CR15","doi-asserted-by":"publisher","first-page":"114196","DOI":"10.1016\/j.tcs.2023.114196","volume":"979","author":"T Ito","year":"2023","unstructured":"Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Nozaki, Y., Okamoto, Y., Ozeki, K.: On reachable assignments under dichotomous preferences. Theor. Comput. Sci. 979, 114196 (2023)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1271_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-015-0009-7","volume":"75","author":"M Johnson","year":"2016","unstructured":"Johnson, M., Kratsch, D., Kratsch, S., Patel, V., Paulusma, D.: Finding shortest paths between graph colourings. Algorithmica 75(2), 295\u2013321 (2016)","journal-title":"Algorithmica"},{"issue":"2","key":"1271_CR17","first-page":"8:1","volume":"64","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A.D., Wang, J.: Fair enough: guaranteeing approximate maximin shares. J. ACM 64(2), 8:1-8:27 (2018)","journal-title":"J. ACM"},{"key":"1271_CR18","unstructured":"Li, F., Plaxton, C.G., Sinha, V.B.: Object allocation over a network of objects: mobile agents with strict preferences. In: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1578\u20131580 (2021)"},{"key":"1271_CR19","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 (EC), pp. 125\u2013131 (2004)","DOI":"10.1145\/988772.988792"},{"key":"1271_CR20","doi-asserted-by":"crossref","unstructured":"Manurangsi, P., Suksompong, W.: Differentially private fair division. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pp. 5814\u20135822 (2023)","DOI":"10.1609\/aaai.v37i5.25721"},{"key":"1271_CR21","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2954.001.0001","volume-title":"Fair Division and Collective Welfare","author":"H Moulin","year":"2003","unstructured":"Moulin, H.: Fair Division and Collective Welfare. MIT Press (2003)"},{"key":"1271_CR22","doi-asserted-by":"crossref","unstructured":"M\u00fcller, L., Bentert, M.: On reachable assignments in cycles. In: Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT), pp. 273\u2013288 (2021)","DOI":"10.1007\/978-3-030-87756-9_18"},{"key":"1271_CR23","doi-asserted-by":"crossref","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52:1\u201352:25 (2018)","DOI":"10.3390\/a11040052"},{"key":"1271_CR24","unstructured":"Obraztsova, S., Elkind, E., Faliszewski, P., Slinko, A.: On swap-distance geometry of voting rules. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 383\u2013390 (2013)"},{"key":"1271_CR25","doi-asserted-by":"crossref","unstructured":"Obraztsova, S., Elkind, E., Faliszewski, P.: On swap convexity of voting rules. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 1910\u20131917 (2020)","DOI":"10.1609\/aaai.v34i02.5560"},{"issue":"1","key":"1271_CR26","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/19M1244305","volume":"49","author":"B Plaut","year":"2020","unstructured":"Plaut, B., Roughgarden, T.: Communication complexity of discrete fair division. SIAM J. Comput. 49(1), 206\u2013243 (2020)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1271_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1271_CR28","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus, H.: The problem of fair division. Econometrica 16(1), 101\u2013104 (1948)","journal-title":"Econometrica"},{"key":"1271_CR29","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1017\/CBO9781107446984.012","volume-title":"Handbook of Computational Social Choice, Chapter 11","author":"W Thomson","year":"2016","unstructured":"Thomson, W.: Introduction to the theory of fair allocation. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, Chapter 11, pp. 261\u2013283. Cambridge University Press (2016)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01271-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01271-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01271-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T20:01:58Z","timestamp":1731528118000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01271-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,21]]},"references-count":29,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1271"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01271-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,21]]},"assertion":[{"value":"14 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}