{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:21:36Z","timestamp":1744258896920,"version":"3.40.4"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Anusandhan National Research Foundation","award":["CRG\/2022\/006140"],"award-info":[{"award-number":["CRG\/2022\/006140"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00224-024-10210-x","type":"journal-article","created":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T05:26:11Z","timestamp":1736832371000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["One-Sided Markets with Externalities"],"prefix":"10.1007","volume":"69","author":[{"given":"Sagar","family":"Massand","sequence":"first","affiliation":[]},{"given":"Sunil","family":"Simon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,14]]},"reference":[{"issue":"6","key":"10210_CR1","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":"10210_CR2","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair Allocation of Indivisible Goods. Handbook of Computational Social Choice, pp. 284\u2013310. Cambridge University Press, Cambridge, UK (2016). Chap. 12","DOI":"10.1017\/CBO9781107446984.013"},{"key":"10210_CR3","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s10458-019-09417-x","volume":"33","author":"A Beynier","year":"2019","unstructured":"Beynier, A., Chevaleyre, Y., Gourv\u00e8s, L., Lesca, J., Maudet, N., Wilczynski, A.: Local envy-freeness in house allocation problems. Auton. Agent. Multi-Agent Syst. 33, 591\u2013627 (2019)","journal-title":"Auton. Agent. Multi-Agent Syst."},{"key":"10210_CR4","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irvin, R.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA (1989)"},{"key":"10210_CR5","doi-asserted-by":"crossref","unstructured":"Roth, A.E., Vate, J.H.V.: Random paths to stability in two-sided matching. Econometrica: J. Econ. Soc. 1475\u20131480 (1990)","DOI":"10.2307\/2938326"},{"issue":"1","key":"10210_CR6","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-4068(74)90033-0","volume":"1","author":"LS Shapley","year":"1974","unstructured":"Shapley, L.S., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1(1), 23\u201337 (1974)","journal-title":"J. Math. Econ."},{"key":"10210_CR7","unstructured":"Kearns, M., Littman, M., Singh, S.: Graphical models for game theory. In: Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI\u201901), pp. 253\u2013260 (2001)"},{"key":"10210_CR8","first-page":"381","volume":"8","author":"EB Janovskaya","year":"1968","unstructured":"Janovskaya, E.B.: Equilibrium points in polymatrix games. Litovskii Matematicheskii Sb. 8, 381\u2013384 (1968)","journal-title":"Litovskii Matematicheskii Sb."},{"key":"10210_CR9","doi-asserted-by":"crossref","unstructured":"Cai, Y., Daskalakis, C.: On minmax theorems for multiplayer games. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911), pp. 217\u2013234 (2011)","DOI":"10.1137\/1.9781611973082.20"},{"key":"10210_CR10","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Fearnley, J., Savani, R., Spirakis, P.: Computing approximate nash equilibria in polymatrix games. In: Proceedings of the Tenth Conference on Web and Internet Economics (WINE\u201914), pp. 58\u201371 (2014)","DOI":"10.1007\/978-3-319-13129-0_5"},{"key":"10210_CR11","doi-asserted-by":"crossref","unstructured":"Rahn, M., Sch\u00e4fer, G.: Efficient equilibria in polymatrix coordination games. In: Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201915), pp. 529\u2013541 (2015)","DOI":"10.1007\/978-3-662-48054-0_44"},{"key":"10210_CR12","doi-asserted-by":"crossref","unstructured":"Arcaute, E., Vassilvitskii, S.: Social networks and stable matchings in the job market. In: Proceedings of the Fifth Workshop on Internet and Network Economics (WINE\u201909), pp. 220\u2013231 (2009)","DOI":"10.1007\/978-3-642-10841-9_21"},{"key":"10210_CR13","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.ic.2012.10.005","volume":"222","author":"M Hoefer","year":"2013","unstructured":"Hoefer, M.: Local matching dynamics in social networks. Inf. Comput. 222, 20\u201335 (2013)","journal-title":"Inf. Comput."},{"key":"10210_CR14","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Bhardwaj, O., Hoefer, M.: Friendship and stable matching. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA\u201913), pp. 49\u201360 (2013)","DOI":"10.1007\/978-3-642-40450-4_5"},{"key":"10210_CR15","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., Peters, D.: Fair division of a graph. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI\u201917), pp. 135\u2013141 (2017)","DOI":"10.24963\/ijcai.2017\/20"},{"key":"10210_CR16","doi-asserted-by":"crossref","unstructured":"Lonc, Z., Truszczynski, M.: Maximin share allocations on cycles. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI\u201918), pp. 410\u2013416 (2018)","DOI":"10.24963\/ijcai.2018\/57"},{"key":"10210_CR17","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. In: Proceedings of the 10th ITCS. LIPIcs, vol. 124, pp. 1\u201321 (2018)"},{"key":"10210_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.005","volume":"242","author":"Y Chevaleyre","year":"2017","unstructured":"Chevaleyre, Y., Endriss, U., Maudet, N.: Distributed fair allocation of indivisible goods. Artif. Intell. 242, 1\u201322 (2017)","journal-title":"Artif. Intell."},{"key":"10210_CR19","unstructured":"Damamme, A., Beynier, A., Chevaleyre, Y., Maudet, N.: The power of swap deals in distributed resource allocation. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915), pp. 625\u2013633 (2015)"},{"key":"10210_CR20","doi-asserted-by":"crossref","unstructured":"Gourves, L., Lesca, J., Wilczynski, A.: Object allocation via swaps along a social network. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI\u201917), pp. 213\u2013219 (2017)","DOI":"10.24963\/ijcai.2017\/31"},{"key":"10210_CR21","unstructured":"Sun, Z., Hata, H., Todo, T., Yokoo, M.: Exchange of indivisible objects with asymmetry. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI\u201915), pp. 97\u2013103 (2015)"},{"key":"10210_CR22","doi-asserted-by":"crossref","unstructured":"Fujita, E., Lesca, J., Sonoda, A., Todo, T., Yokoo, M.: A complexity approach for core-selecting exchange with multiple indivisible goods under lexicographic preferences. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI\u201915), pp. 907\u2013913 (2015)","DOI":"10.1609\/aaai.v29i1.9318"},{"key":"10210_CR23","unstructured":"Branzei, S., Procaccia, A.D., Zhang, J.: Externalities in cake cutting. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913), pp. 55\u201361 (2013)"},{"key":"10210_CR24","doi-asserted-by":"crossref","unstructured":"Aziz, H., Suksompong, W., Sun, Z., Walsh, T.: Fairness concepts for indivisible items with externalities. In: Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI\u201923), pp. 5472\u20135480 (2023)","DOI":"10.1609\/aaai.v37i5.25680"},{"key":"10210_CR25","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Korchemna, V., Schierreich, S.: The complexity of fair division of indivisible items with externalities. In: Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI\u201924), pp. 9653\u20139661 (2024)","DOI":"10.1609\/aaai.v38i9.28822"},{"key":"10210_CR26","doi-asserted-by":"crossref","unstructured":"Ghodsi, M., Saleh, H., Seddighin, M.: Fair allocation of indivisible items with externalities. CoRR. arXiv:1805.06191 (2018)","DOI":"10.1145\/3219166.3219238"},{"key":"10210_CR27","unstructured":"Hosseini, H., Payan, J., Sengupta, R., Vaish, R., Viswanathan, V.: Graphical house allocation. In: Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems(AAMAS\u201923), pp. 161\u2013169 (2023)"},{"key":"10210_CR28","doi-asserted-by":"crossref","unstructured":"Lesca, J., Todo, T.: Service exchange problem. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI\u201918), pp. 354\u2013360 (2018)","DOI":"10.24963\/ijcai.2018\/49"},{"key":"10210_CR29","unstructured":"Ishizuka, T.: Graphical one-sided matching markets with exchange costs. CoRR. arXiv:2305.12604 (2023)"},{"key":"10210_CR30","doi-asserted-by":"crossref","unstructured":"Chauhan, A., Lenzner, P., Molitor, L.: Schelling segregation with strategic agents. In: Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT\u201918), pp. 137\u2013149 (2018)","DOI":"10.1007\/978-3-319-99660-8_13"},{"key":"10210_CR31","doi-asserted-by":"publisher","first-page":"103576","DOI":"10.1016\/j.artint.2021.103576","volume":"301","author":"A Agarwal","year":"2021","unstructured":"Agarwal, A., Elkind, E., Gan, J., Igarashi, A., Suksompong, W., Voudouris, A.A.: Schelling games on graphs. Artif. Intell. 301, 103576 (2021)","journal-title":"Artif. Intell."},{"key":"10210_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2021.05.032","volume":"880","author":"P Kanellopoulos","year":"2021","unstructured":"Kanellopoulos, P., Kyropoulou, M., Voudouris, A.A.: Modified Schelling games. Theor. Comput. Sci. 880, 1\u201319 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"10210_CR33","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1613\/jair.1.12771","volume":"71","author":"M Bullinger","year":"2021","unstructured":"Bullinger, M., Suksompong, W., Voudouris, A.A.: Welfare guarantees in Schelling segregation. J. Artif. Intell. Res. 71, 143\u2013174 (2021)","journal-title":"J. Artif. Intell. Res."},{"key":"10210_CR34","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Elkind, E., Gan, J., Voudouris, A.A.: Swap stability in Schelling games on graphs. In: Proceedings of the The Thirty-Fourth Conference on Artificial Intelligence (AAAI\u201919), pp. 1758\u20131765 (2019)","DOI":"10.1609\/aaai.v34i02.5541"},{"key":"10210_CR35","doi-asserted-by":"crossref","unstructured":"Bil\u00f3, D., Bil\u00f3, V., Lenzner, P., Molitor, L.: Topological influence and locality in swap Schelling games. Auton. Agent. Multi-Agent Syst. 36(47) (2022)","DOI":"10.1007\/s10458-022-09573-7"},{"issue":"4","key":"10210_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3569704","volume":"10","author":"N Gross-Humbert","year":"2023","unstructured":"Gross-Humbert, N., Benabbou, N., Beynier, A., Maudet, N.: Sequential and swap mechanisms for public housing allocation with quotas and neighbourhood-based utilities. ACM Trans. Econ. Comput. 10(4), 1\u201324 (2023)","journal-title":"ACM Trans. Econ. Comput."},{"key":"10210_CR37","doi-asserted-by":"crossref","unstructured":"Massand, S., Simon, S.: Graphical one-sided markets. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI\u201919), pp. 492\u2013498 (2019)","DOI":"10.24963\/ijcai.2019\/70"},{"key":"10210_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316779309","volume-title":"Twenty Lectures on Algorithmic Game Theory","author":"T Roughgarden","year":"2016","unstructured":"Roughgarden, T.: Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, Cambridge, UK (2016)"},{"key":"10210_CR39","doi-asserted-by":"publisher","DOI":"10.1515\/9780691187563","volume-title":"Local Search in Combinatorial Optimization","author":"E Aarts","year":"2003","unstructured":"Aarts, E., Lenstra, J.K.: Local Search in Combinatorial Optimization. Princeton University Press, Princeton, US (2003)"},{"key":"10210_CR40","unstructured":"Christopoulos, P., Zissimopoulos, V.: An overview of what we can and cannot do with local search. Annales Du Lamsade No 2. (2004)"},{"issue":"1","key":"10210_CR41","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"AA Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20(1), 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"10210_CR42","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1613\/jair.1683","volume":"24","author":"G Gottlob","year":"2005","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: Hard and easy games. J. Artif. Intell. Res. 24, 357\u2013406 (2005)","journal-title":"J. Artif. Intell. Res."},{"key":"10210_CR43","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Tscheuschner, T.: Settling the complexity of local max-cut (almost) completely. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP\u201911), pp. 171\u2013182 (2011)","DOI":"10.1007\/978-3-642-22006-7_15"},{"issue":"3","key":"10210_CR44","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0001-8708(87)90055-7","volume":"63","author":"N Alon","year":"1987","unstructured":"Alon, N.: Splitting necklaces. Adv. Math. 63(3), 247\u2013253 (1987)","journal-title":"Adv. Math."},{"key":"10210_CR45","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1613\/jair.2467","volume":"32","author":"S Bouveret","year":"2008","unstructured":"Bouveret, S., Lang, J.: Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. J. Artif. Intell. Res. 32, 525\u2013564 (2008)","journal-title":"J. Artif. Intell. Res."},{"key":"10210_CR46","unstructured":"Abebe, R., Kleinberg, J., Parkes, D.C.: Fair division via social comparison. In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201917), pp. 281\u2013289 (2017)"},{"issue":"4","key":"10210_CR47","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/S0097539793245350","volume":"24","author":"S Poljak","year":"1995","unstructured":"Poljak, S.: Integer linear programs and local search for max-cut. SIAM J. Comput. 24(4), 822\u2013839 (1995)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10210-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10210-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10210-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:46:18Z","timestamp":1744217178000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10210-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,14]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10210"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10210-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,1,14]]},"assertion":[{"value":"23 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2025","order":2,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"3"}}