{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:51:14Z","timestamp":1765176674703,"version":"3.46.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T00:00:00Z","timestamp":1749600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T00:00:00Z","timestamp":1749600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V032305\/1"],"award-info":[{"award-number":["EP\/V032305\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s10458-025-09710-y","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T05:18:59Z","timestamp":1749619139000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Cost and Complexity of Minimizing Envy in House Allocation"],"prefix":"10.1007","volume":"39","author":[{"given":"Jayakrishnan","family":"Madathil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aditi","family":"Sethia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,11]]},"reference":[{"issue":"2","key":"9710_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1006\/jeth.1999.2553","volume":"88","author":"A Abdulkadiro\u011flu","year":"1999","unstructured":"Abdulkadiro\u011flu, A., & S\u00f6nmez, T. (1999). House allocation with existing tenants. Journal of Economic Theory, 88(2), 233\u2013260.","journal-title":"Journal of Economic Theory"},{"key":"9710_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, D.\u00a0J., Cechl\u00e1rov\u00e1, K., Manlove, D.\u00a0F., & Mehlhorn, K. (2004). Pareto optimality in house allocation problems. In International symposium on algorithms and computation, (pp. 3\u201315). Springer.","DOI":"10.1007\/978-3-540-30551-4_3"},{"key":"9710_CR3","doi-asserted-by":"crossref","unstructured":"Aigner-Horev, E., & Segal-Halevi, E. (2021). Envy-free matchings in bipartite graphs and their applications to fair division. Information Sciences.","DOI":"10.1016\/j.ins.2021.11.059"},{"key":"9710_CR4","doi-asserted-by":"crossref","unstructured":"Barman, S., Bhaskar, U., & Shah, N. (2020). Optimal bounds on the price of fairness for indivisible goods. In Proceedings of the 16th international conference on web and internet economics, (pp. 356\u2013369).","DOI":"10.1007\/978-3-030-64946-3_25"},{"key":"9710_CR5","unstructured":"Barman, S., Krishnamurthy, S.\u00a0K., & Vaish, R. (2018). Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, AAMAS \u201918, Richland, SC (pp. 7-13). International Foundation for Autonomous Agents and Multiagent Systems."},{"issue":"7","key":"9710_CR6","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1007\/s00224-021-10039-8","volume":"65","author":"X Bei","year":"2021","unstructured":"Bei, X., Lu, X., Manurangsi, P., & Suksompong, W. (2021). The price of fairness for indivisible goods. Theory of Computing Systems, 65(7), 1069\u20131093.","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"9710_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/opre.1100.0865","volume":"59","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Farias, V. F., & Trichakis, N. (2011). The price of fairness. Operations Research, 59(1), 17\u201331.","journal-title":"Operations Research"},{"issue":"5","key":"9710_CR8","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., Harutyunyan, A., Lesca, J., Maudet, N., & Wilczynski, A. (2019). Local envy-freeness in house allocation problems. Autonomous Agents and Multi-Agent Systems, 33(5), 591\u2013627.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9710_CR9","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-031-43254-5_16","volume-title":"Algorithmic game theory","author":"U Bhaskar","year":"2023","unstructured":"Bhaskar, U., Misra, N., Sethia, A., & Vaish, R. (2023). The price of equity with binary valuations and few agent types. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic game theory (pp. 271\u2013289). Cham. Springer Nature Switzerland."},{"issue":"4","key":"9710_CR10","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2012). The efficiency of fair division. Theory of Computing Systems, 50(4), 589\u2013610.","journal-title":"Theory of Computing Systems"},{"key":"9710_CR11","doi-asserted-by":"publisher","first-page":"107103","DOI":"10.1016\/j.orl.2024.107103","volume":"54","author":"D Choo","year":"2024","unstructured":"Choo, D., Ling, Y. H., Suksompong, W., Teh, N., & Zhang, J. (2024). Envy-free house allocation with minimum subsidy. Operations Research Letters, 54, 107103.","journal-title":"Operations Research Letters"},{"key":"9710_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Springer."},{"key":"9710_CR13","doi-asserted-by":"crossref","unstructured":"Downey, R.\u00a0G., & Fellows, M.\u00a0R. (2013). Fundamentals of parameterized complexity. Texts in Computer Science. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"9710_CR14","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2019). Solving integer quadratic programming via explicit and structural restrictions. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019 (pp. 1477\u20131484). AAAI Press.","DOI":"10.1609\/aaai.v33i01.33011477"},{"key":"9710_CR15","unstructured":"Elkind, E., & Lackner, M. (2015). Structure in dichotomous preferences. In Proceedings of the 24th international conference on artificial intelligence, IJCAI\u201915 (pp. 2019-2025). AAAI Press."},{"key":"9710_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.mathsocsci.2019.07.005","volume":"101","author":"J Gan","year":"2019","unstructured":"Gan, J., Suksompong, W., & Voudouris, A. A. (2019). Envy-freeness in house allocation problems. Mathematical Social Sciences, 101, 104\u2013106.","journal-title":"Mathematical Social Sciences"},{"key":"9710_CR17","doi-asserted-by":"crossref","unstructured":"Halpern, D., Procaccia, A.\u00a0D., Psomas, A., & Shah, N. (2020). Fair division with binary valuations: One rule to rule them all. In Web and internet economics: 16th international conference, WINE 2020, Beijing, China, December 7\u201311, 2020, Proceedings 16 (pp. 370\u2013383). Springer.","DOI":"10.1007\/978-3-030-64946-3_26"},{"key":"9710_CR18","doi-asserted-by":"crossref","unstructured":"Hosseini, H., Kumar, M., & Roy, S. (2024a). The degree of fairness in efficient house allocation. CoRR, abs\/2407.04664.","DOI":"10.3233\/FAIA240920"},{"key":"9710_CR19","unstructured":"Hosseini, H., McGregor, A., Sengupta, R., Vaish, R., & Viswanathan, V. (2024b). Tight approximations for graphical house allocation. In Proceedings of the 23rd international conference on autonomous agents and multiagent systems, AAMAS \u201924, Richland, SC (pp. 825-833). International Foundation for Autonomous Agents and Multiagent Systems."},{"key":"9710_CR20","doi-asserted-by":"crossref","unstructured":"Hosseini, H., Payan, J., Sengupta, R., Vaish, R., & Viswanathan, V. (2023). Graphical house allocation. In 22nd international conference on autonomous agents and multiagent systems, AAMAS.","DOI":"10.1007\/s10458-024-09672-7"},{"issue":"2","key":"9710_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1086\/260757","volume":"87","author":"A Hylland","year":"1979","unstructured":"Hylland, A., & Zeckhauser, R. (1979). The efficient allocation of individuals to positions. Journal of Political Economy, 87(2), 293\u2013314.","journal-title":"Journal of Political Economy"},{"issue":"4","key":"9710_CR22","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1198513.1198520","volume":"2","author":"RW Irving","year":"2006","unstructured":"Irving, R. W., Kavitha, T., Mehlhorn, K., Michail, D., & Paluch, K. E. (2006). Rank-maximal matchings. ACM Transactions on Algorithms, 2(4), 602\u2013610.","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"9710_CR23","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1016\/j.orl.2021.06.006","volume":"49","author":"N Kamiyama","year":"2021","unstructured":"Kamiyama, N., Manurangsi, P., & Suksompong, W. (2021). On the complexity of fair house allocation. Operations Research Letters, 49(4), 572\u2013577.","journal-title":"Operations Research Letters"},{"issue":"9","key":"9710_CR24","doi-asserted-by":"publisher","first-page":"3422","DOI":"10.1007\/s00453-019-00584-7","volume":"81","author":"P Krysta","year":"2019","unstructured":"Krysta, P., Manlove, D. F., Rastegari, B., & Zhang, J. (2019). Size versus truthfulness in the house allocation problem. Algorithmica, 81(9), 3422\u20133463.","journal-title":"Algorithmica"},{"key":"9710_CR25","doi-asserted-by":"crossref","unstructured":"Lackner, M., & Skowron, P. (2023). Multi-winner voting with approval preferences. Springer Nature.","DOI":"10.1007\/978-3-031-09016-5"},{"issue":"4","key":"9710_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H. W., Jr. (1983). Integer programming with a fixed number of variables. Mathematical Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematical Operations Research"},{"key":"9710_CR27","unstructured":"Lokshtanov, D. (2015). Parameterized integer quadratic programming: Variables and coefficients. CoRR, abs\/1511.00310."},{"key":"9710_CR28","doi-asserted-by":"crossref","unstructured":"Manlove, D.\u00a0F. (2013). Algorithmics of matching under preferences, volume\u00a02 of Series on theoretical computer science. WorldScientific.","DOI":"10.1142\/8591"},{"key":"9710_CR29","doi-asserted-by":"crossref","unstructured":"Manurangsi, P. (2018). Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms, 11(1).","DOI":"10.3390\/a11010010"},{"key":"9710_CR30","doi-asserted-by":"crossref","unstructured":"Mathieson, L., & Szeider, S. (2012). Editing graphs to satisfy degree constraints: A parameterized approach. Journal of Computer and System Sciences, 78(1), 179\u2013191. JCSS Knowledge Representation and Reasoning.","DOI":"10.1016\/j.jcss.2011.02.001"},{"key":"9710_CR31","doi-asserted-by":"crossref","unstructured":"Nguyen, T. T., & Rothe, J. (2013). How to decrease the degree of envy in allocations of indivisible goods. In Algorithmic decision theory: third international conference, ADT 2013, Bruxelles, Belgium, November 12\u201314, 2013, Proceedings (pp. 271\u2013284). Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/978-3-642-41575-3_21"},{"key":"9710_CR32","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., & Steurer, D. (2010). Graph expansion and the unique games conjecture. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC \u201910, New York, NY, USA (pp. 755-764). Association for Computing Machinery.","DOI":"10.1145\/1806689.1806792"},{"key":"9710_CR33","doi-asserted-by":"crossref","unstructured":"Shams, P., Beynier, A., Bouveret, S., & Maudet, N. (2021). Minimizing and balancing envy among agents using Ordered Weighted Average. In 7th international conference on algorithmic decision theory, Toulouse, France.","DOI":"10.1007\/978-3-030-87756-9_19"},{"issue":"1","key":"9710_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-4068(74)90033-0","volume":"1","author":"L Shapley","year":"1974","unstructured":"Shapley, L., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23\u201337.","journal-title":"Journal of Mathematical Economics"},{"key":"9710_CR35","doi-asserted-by":"publisher","first-page":"105712","DOI":"10.1016\/j.jet.2023.105712","volume":"213","author":"P Shende","year":"2020","unstructured":"Shende, P., & Purohit, M. (2020). Strategy-proof and envy-free mechanisms for house allocation. Journal of Economic Theory, 213, 105712.","journal-title":"Journal of Economic Theory"},{"key":"9710_CR36","doi-asserted-by":"crossref","unstructured":"Sun, A., Chen, B., & Doan, X. V. (2023). Equitability and welfare maximization for allocating indivisible items. Autonomous Agents and Multi-Agent Systems, 37(8).","DOI":"10.1007\/s10458-023-09618-5"},{"key":"9710_CR37","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S. (2010). A 4k2 kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2).","DOI":"10.1145\/1721837.1721848"},{"issue":"1","key":"9710_CR38","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0022-0531(90)90070-Z","volume":"52","author":"L Zhou","year":"1990","unstructured":"Zhou, L. (1990). On a conjecture by gale about one-sided matching problems. Journal of Economic Theory, 52(1), 123\u2013135.","journal-title":"Journal of Economic Theory"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09710-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-025-09710-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09710-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:46:52Z","timestamp":1765176412000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-025-09710-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,11]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["9710"],"URL":"https:\/\/doi.org\/10.1007\/s10458-025-09710-y","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2025,6,11]]},"assertion":[{"value":"19 May 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 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":"29"}}