{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T18:13:05Z","timestamp":1778004785054,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T00:00:00Z","timestamp":1760486400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T00:00:00Z","timestamp":1760486400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/ Y003624\/1"],"award-info":[{"award-number":["EP\/ Y003624\/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]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study matching settings in which a set of agents have private utilities over a set of items. Each agent reports a partition of the items into approval sets of different threshold utility levels. Given this limited information on input, the goal is to compute an assignment of the items to the agents (subject to cardinality constraints depending on the application) that (approximately) maximizes the social welfare (the total utility of the agents for their assigned items). We first consider the well-known, simple one-sided matching problem in which each of\n                    <jats:italic>n<\/jats:italic>\n                    agents is to be assigned exactly one of\n                    <jats:italic>n<\/jats:italic>\n                    items. We show that with\n                    <jats:italic>t<\/jats:italic>\n                    threshold utility levels, the distortion of deterministic matching algorithms is\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Theta (\\root t \\of {n})$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    while that of randomized algorithms is\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Theta (\\root t+1 \\of {n})$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . We then show that our distortion bounds extend to a more general setting in which there are multiple copies of the items, each agent can be assigned a number of items (even copies of the same one) up to a capacity, and the utility of an agent for an item depends on the number of its copies that the agent is given.\n                  <\/jats:p>","DOI":"10.1007\/s10458-025-09724-6","type":"journal-article","created":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T04:49:02Z","timestamp":1760503742000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The distortion of threshold approval matching"],"prefix":"10.1007","volume":"39","author":[{"given":"Mohamad","family":"Latifian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandros A.","family":"Voudouris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,15]]},"reference":[{"key":"9724_CR1","doi-asserted-by":"crossref","unstructured":"Abramowitz, B., Anshelevich, E. (2018). Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 894\u2013901.","DOI":"10.1609\/aaai.v32i1.11453"},{"key":"9724_CR2","doi-asserted-by":"crossref","unstructured":"Ahuja, R\u00a0K., Magnanti, T\u00a0L, Orlin, J\u00a0B. (1988). Network flows.","DOI":"10.21236\/ADA594171"},{"key":"9724_CR3","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. A. (2021). Peeking behind the ordinal curtain: improving distortion via cardinal queries. Artificial Intelligence, 296, 103488","DOI":"10.1016\/j.artint.2021.103488"},{"key":"9724_CR4","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A\u00a0A. (2022). A few queries go a long way: Information-distortion tradeoffs in matching. Journal of Artificial Intelligence Research, 74","DOI":"10.1613\/jair.1.12690"},{"key":"9724_CR5","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1137\/23M1545677","volume":"38","author":"The Two-Query Distortion of Matching Problems and Beyond","year":"2024","unstructured":"The Two-Query Distortion of Matching Problems and Beyond. (2024). Georgios amanatidis, georgios birmpas, aris filos-ratsikas, and alexandros a voudouris. don\u2019t roll the dice, ask twice. SIAM Journal on Discrete Mathematics, 38, 1007\u20131029.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9724_CR6","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Sekar, S. (2016). Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 390\u2013396","DOI":"10.1609\/aaai.v30i1.10032"},{"key":"9724_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.artint.2018.07.006","volume":"264","author":"E Anshelevich","year":"2018","unstructured":"Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., & Skowron, P. (2018). Approximating optimal social choice under metric preferences. Artificial Intelligence, 264, 27\u201351.","journal-title":"Artificial Intelligence"},{"key":"9724_CR8","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Filos-Ratsikas, A., Shah, N., Voudouris, A\u00a0A. (2021). Distortion in social choice problems: The first 15 years and beyond. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4294\u20134301.","DOI":"10.24963\/ijcai.2021\/589"},{"key":"9724_CR9","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Filos-Ratsikas, A., Jerrett, C., & Voudouris, A. A. (2025). Improved metric distortion via threshold approvals. Artificial Intelligence, 341, Article 104295.","DOI":"10.1016\/j.artint.2025.104295"},{"issue":"2","key":"9724_CR10","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/3381329.3381337","volume":"17","author":"H Aziz","year":"2019","unstructured":"Aziz, H. (2019). Justifications of welfare guarantees under normalized utilities. SIGecom Exchanges, 17(2), 71\u201375.","journal-title":"SIGecom Exchanges"},{"issue":"5","key":"9724_CR11","doi-asserted-by":"publisher","first-page":"2813","DOI":"10.1287\/mnsc.2020.3666","volume":"67","author":"G Benad\u00e8","year":"2021","unstructured":"Benad\u00e8, G., Nath, S., Procaccia, A. D., & Shah, N. (2021). Preference elicitation for participatory budgeting. Management Science, 67(5), 2813\u20132827.","journal-title":"Management Science"},{"key":"9724_CR12","doi-asserted-by":"crossref","unstructured":"Bhaskar, U., Dani, V., Ghosh, A. (2018). Truthful and near-optimal mechanisms for welfare maximization in multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, (AAAI), pp. 925\u2013932","DOI":"10.1609\/aaai.v32i1.11480"},{"key":"9724_CR13","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.artint.2015.06.003","volume":"227","author":"C Boutilier","year":"2015","unstructured":"Boutilier, C., Caragiannis, I., Haber, S., Tyler, L., Procaccia, A. D., & Sheffet, O. (2015). Optimal social choice functions: a utilitarian view. Artificial Intelligence, 227, 190\u2013213.","journal-title":"Artificial Intelligence"},{"key":"9724_CR14","doi-asserted-by":"crossref","unstructured":"Burkhardt, J., Caragiannis, I., Fehrs, K., Russo, M, Schwiegelshohn, C., Shyam, S. (2024). Low-distortion clustering with ordinal and limited cardinal information. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 9555\u20139563","DOI":"10.1609\/aaai.v38i9.28811"},{"key":"9724_CR15","unstructured":"Caragiannis, I., Fehrs, K. (2023). Beyond the worst case: Distortion in impartial culture electorate. CoRR, arXiv:2307.07350"},{"issue":"9\u201310","key":"9724_CR16","doi-asserted-by":"publisher","first-page":"1655","DOI":"10.1016\/j.artint.2011.03.005","volume":"175","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis, I., & Procaccia, A. D. (2011). Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9\u201310), 1655\u20131671.","journal-title":"Artificial Intelligence"},{"key":"9724_CR17","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1613\/jair.5282","volume":"58","author":"I Caragiannis","year":"2017","unstructured":"Caragiannis, I., Nath, S., Procaccia, A. D., & Shah, N. (2017). Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58, 123\u2013152.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9724_CR18","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Shah, N., & Voudouris, A. A. (2022). The metric distortion of multiwinner voting. Artificial Intelligence, 313, Article 103802.","DOI":"10.1016\/j.artint.2022.103802"},{"key":"9724_CR19","doi-asserted-by":"crossref","unstructured":"Charikar, M., Ramakrishnan, P. (2022). Metric distortion bounds for randomized social choice. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2986\u20133004","DOI":"10.1137\/1.9781611977073.116"},{"key":"9724_CR20","doi-asserted-by":"crossref","unstructured":"Charikar, M., Ramakrishnan, P., Wang, K., Wu, H. (2024). Breaking the metric voting distortion barrier. Journal of the ACM, 71 (6), 42:1\u201342:33,","DOI":"10.1145\/3689625"},{"key":"9724_CR21","unstructured":"Ebadian, S., Latifian, M., Shah, N. (2023). The distortion of approval voting with runoff. In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1752\u20131760"},{"key":"9724_CR22","doi-asserted-by":"crossref","unstructured":"Ebadian, S., Kahng, A., Peters, D., Shah, N. (2024) Optimized distortion and proportional fairness in voting. ACM Transactions on Economics and Computation, 12 (1): 3:1\u20133:39.","DOI":"10.1145\/3640760"},{"key":"9724_CR23","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Frederiksen, S. K. S., Zhang, J. (2014) Social welfare in one-sided matchings: Random priority and beyond. In: Proceedings of the 7th Symposium of Algorithmic Game Theory (SAGT), pp. 1\u201312.","DOI":"10.1007\/978-3-662-44803-8_1"},{"key":"9724_CR24","doi-asserted-by":"crossref","unstructured":"Gkatzelis, V., Halpern, D., Shah , N. (2020). Resolving the optimal metric distortion conjecture. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1427\u20131438.","DOI":"10.1109\/FOCS46700.2020.00134"},{"key":"9724_CR25","doi-asserted-by":"crossref","unstructured":"Gkatzelis, V., Latifian, M., Shah, N. (2023). Best of both distortion worlds. In: Proceedings of the 24th ACM Conference on Economics and Computation, (EC), pp. 738\u2013758.","DOI":"10.1145\/3580507.3597739"},{"key":"9724_CR26","doi-asserted-by":"crossref","unstructured":"Kempe, D. (2020). Communication, distortion, and randomness in metric voting. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pp. 2087\u20132094.","DOI":"10.1609\/aaai.v34i02.5582"},{"key":"9724_CR27","doi-asserted-by":"crossref","unstructured":"Kizilkaya, F\u00a0E., Kempe, D. (2022). Plurality veto: A simple voting rule achieving optimal metric distortion. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 349\u2013355.","DOI":"10.24963\/ijcai.2022\/50"},{"key":"9724_CR28","doi-asserted-by":"crossref","unstructured":"Ma, T., Menon, V., Larson, K. (2021). Improving welfare in one-sided matchings using simple threshold queries. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 321\u2013327.","DOI":"10.24963\/ijcai.2021\/45"},{"key":"9724_CR29","unstructured":"Mandal, D., Procaccia, A.\u00a0D., Shah, N., Woodruff, D\u00a0P. (2019). Efficient and thrifty voting by any means necessary. In: Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), pp. 7178\u20137189."},{"key":"9724_CR30","doi-asserted-by":"crossref","unstructured":"Mandal, D., Shah, N., Woodruff, D\u00a0P. (2020). Optimal communication-distortion tradeoff in voting. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp. 795\u2013813.","DOI":"10.1145\/3391403.3399510"},{"key":"9724_CR31","doi-asserted-by":"crossref","unstructured":"Procaccia, A.\u00a0D., Rosenschein, J.\u00a0S. (2006). The distortion of cardinal preferences in voting. In: International Workshop on Cooperative Information Agents (CIA), pp. 317\u2013331.","DOI":"10.1007\/11839354_23"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09724-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-025-09724-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09724-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:47:19Z","timestamp":1765176439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-025-09724-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,15]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["9724"],"URL":"https:\/\/doi.org\/10.1007\/s10458-025-09724-6","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,15]]},"assertion":[{"value":"16 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2025","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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"42"}}