{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:04Z","timestamp":1750309444074,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"Kyoto University and Toyota Motor Corporation, titled \u201cAdvanced Mathematical Science for Mobility Society,\u201d JST PRESTO","award":["JPMJPR2122 and JPMJPR20C1"],"award-info":[{"award-number":["JPMJPR2122 and JPMJPR20C1"]}]},{"name":"JSPS KAKENHI","award":["JP19K22841, JP20H00609, JP20H05967, and JP22H00513"],"award-info":[{"award-number":["JP19K22841, JP20H00609, JP20H05967, and JP22H00513"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            The airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This article extends it to a more general setting involving multiple facilities. Specifically, in our model, each agent selects a facility and shares the cost with the other agents using the same facility. This scenario frequently occurs in sharing economies, such as sharing subscription costs for a multi-user license or taxi fares among customers traveling to potentially different destinations along a route. Our model can be viewed as a coalition formation game with size constraints, based on the fair cost-sharing of the airport problem. We refer to our model as\n            <jats:italic>a fair ride allocation on a line<\/jats:italic>\n            . We incorporate Nash stability and envy-freeness as criteria for solution concepts in our setting. We show that if a feasible allocation exists, a Nash stable feasible allocation that minimizes the social cost of agents exists and can be computed efficiently. Regarding envy-freeness, we provide several structural properties of envy-free allocations. Based on these properties, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show NP-completeness of determining the existence of an allocation under two relaxed envy-free concepts.\n          <\/jats:p>","DOI":"10.1145\/3708491","type":"journal-article","created":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T09:35:23Z","timestamp":1735983323000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fair Ride Allocation on a Line"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2856-302X","authenticated-orcid":false,"given":"Yuki","family":"Amano","sequence":"first","affiliation":[{"name":"Faculty of Science and Engineering, Chuo University - Korakuen Campus, Bunkyo-ku, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5304-577X","authenticated-orcid":false,"given":"Ayumi","family":"Igarashi","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Bunkyo-ku, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5626-779X","authenticated-orcid":false,"given":"Yasushi","family":"Kawase","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Bunkyo-ku, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9771-4955","authenticated-orcid":false,"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0845-3947","authenticated-orcid":false,"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[{"name":"Nagoya University, Nagoya, Japan"}]}],"member":"320","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_3_3_3_2","volume-title":"Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT\u201922)","author":"Amano Yuki","year":"2022","unstructured":"Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, and Hirotaka Ono. 2022. Fair ride allocation on a line. In Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT\u201922). 421\u2013435."},{"key":"e_1_3_3_4_2","volume-title":"Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications. 73\u201382","author":"Amano Yuki","year":"2023","unstructured":"Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, and Hirotaka Ono. 2023. An FPT algorithm for the envy-free ride allocation with respect to destination types. In Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications. 73\u201382."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"volume-title":"Hedonic games","author":"Aziz Haris","key":"e_1_3_3_6_2","unstructured":"Haris Aziz and Rahul Savani. 2016. Hedonic games. Chapter 15, In Handbook of Computational Social Choice. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.), Cambridge University Press."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219617.3219619"},{"key":"e_1_3_3_8_2","volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919)","author":"Makoto Yokoo Barrot","year":"2019","unstructured":"Nathana:el Barrot and Makoto Yokoo. 2019. Stable and envy-free partitions in hedonic games. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919). 67\u201373."},{"volume-title":"Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201920)","author":"Bodlaender Hans L.","key":"e_1_3_3_9_2","unstructured":"Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, and Tom C. van der Zanden. 2020. Hedonic seat arrangement problems. In Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201920). 1777\u20131779."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.2001.0877"},{"volume-title":"Fair allocation of indivisible goods","author":"Bouveret Sylvain","key":"e_1_3_3_11_2","unstructured":"Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. 2016. Fair allocation of indivisible goods. Chapter 12, In Handbook of Computational Social Choice. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.), Cambridge University Press."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01558-8"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10058-016-0191-3"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1111\/jpet.12190"},{"key":"e_1_3_3_15_2","first-page":"45","article-title":"Resource allocation and the public sector","volume":"7","author":"Foley Duncan K.","year":"1967","unstructured":"Duncan K. Foley. 1967. Resource allocation and the public sector. Yale Economic Essays 7 (1967), 45\u201398.","journal-title":"Yale Economic Essays"},{"key":"e_1_3_3_16_2","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2728732.2728738"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/978-3-642-33996-7_18","article-title":"Congestion games with capacitated resources","volume":"7615","author":"Gourv\u00e8s Laurent","year":"2012","unstructured":"Laurent Gourv\u00e8s, J\u00e9r\u00f4me Monnot, Stefano Moretti, and Nguyen Kim Thang. 2012. Congestion games with capacitated resources. Algorithmic Game Theory 7615 (2012), 204\u2013215.","journal-title":"Algorithmic Game Theory"},{"volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919)","author":"Kyropoulou Maria","key":"e_1_3_3_19_2","unstructured":"Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris. 2019. Almost envy-freeness in group resource allocation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919). 400\u2013406."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.3.370"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_3_3_22_2","volume-title":"Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201916)","author":"Nguyen Nhan-Tam","year":"2016","unstructured":"Nhan-Tam Nguyen and J\u00f6rg Rothe. 2016. Local fairness in hedonic games via individual threshold coalitions. In Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201916). 232\u2013241."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912444766"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832335"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1403657111"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-019-01210-9"},{"volume-title":"Contributions to the Theory of Games II","author":"Shapley Lloyd S.","key":"e_1_3_3_28_2","unstructured":"Lloyd S. Shapley. 1953. A value for n-person games. In In Contributions to the Theory of Games II. H. W. Kuhn and A. W. Tucker (Eds.), Princeton University Press: Princeton, 307\u2013317."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1765(03)00151-4"},{"volume-title":"Cost allocation and airport problems. RCER Working Papers 537","author":"Thomson William","key":"e_1_3_3_30_2","unstructured":"William Thomson. 2007. Cost allocation and airport problems. RCER Working Papers 537, University of Rochester - Center for Economic Research (RCER)."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915581863"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708491","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:54Z","timestamp":1750295394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3708491"],"URL":"https:\/\/doi.org\/10.1145\/3708491","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,2,7]]},"assertion":[{"value":"2023-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}