{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:36:26Z","timestamp":1764131786266,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-2045354"],"award-info":[{"award-number":["CCF-2045354"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,9]]},"DOI":"10.1145\/3580507.3597740","type":"proceedings-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T14:19:22Z","timestamp":1688739562000},"page":"90-110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Distortion in metric matching with ordinal preferences"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4394-3530","authenticated-orcid":false,"given":"Nima","family":"Anari","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0807-3389","authenticated-orcid":false,"given":"Moses","family":"Charikar","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8853-3578","authenticated-orcid":false,"given":"Prasanna","family":"Ramakrishnan","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, United States of America"}]}],"member":"320","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"School choice: A mechanism design approach. American economic review 93, 3","author":"Abdulkadiro\u011flu Atila","year":"2003","unstructured":"Atila Abdulkadiro\u011flu and Tayfun S\u00f6nmez . 2003. School choice: A mechanism design approach. American economic review 93, 3 ( 2003 ), 729--747. Atila Abdulkadiro\u011flu and Tayfun S\u00f6nmez. 2003. School choice: A mechanism design approach. American economic review 93, 3 (2003), 729--747."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538271"},{"key":"e_1_3_2_1_3_1","volume-title":"Don't Roll the Dice","author":"Amanatidis Georgios","year":"1872","unstructured":"Georgios Amanatidis , Georgios Birmpas , Aris Filos-Ratsikas , and Alexandros A Voudouris . 2022a. Don't Roll the Dice , Ask Twice : The Two-Query Distortion of Matching Problems and Beyon . arXiv preprint arXiv:2203.0 1872 (2022). Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. 2022a. Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyon. arXiv preprint arXiv:2203.01872 (2022)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12690"},{"volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"An Hyung-Chan","key":"e_1_3_2_1_5_1","unstructured":"Hyung-Chan An , Robert D Kleinberg , and David B Shmoys . 2010. Approximation algorithms for the bottleneck asymmetric traveling salesman problem . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 1--11. Hyung-Chan An, Robert D Kleinberg, and David B Shmoys. 2010. Approximation algorithms for the bottleneck asymmetric traveling salesman problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 1--11."},{"key":"e_1_3_2_1_6_1","volume-title":"2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 20--39","author":"Anari Nima","year":"2015","unstructured":"Nima Anari and Shayan Oveis Gharan . 2015 . Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP . In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 20--39 . Nima Anari and Shayan Oveis Gharan. 2015. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 20--39."},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"29","author":"Anshelevich Elliot","year":"2015","unstructured":"Elliot Anshelevich , Onkar Bhardwaj , and John Postl . 2015 . Approximating Optimal Social Choice under Metric Preferences . In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 29 . Elliot Anshelevich, Onkar Bhardwaj, and John Postl. 2015. Approximating Optimal Social Choice under Metric Preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 29."},{"key":"e_1_3_2_1_8_1","volume-title":"Distortion in Social Choice Problems: The First 15 Years and Beyond. arXiv preprint arXiv:2103.00911","author":"Anshelevich Elliot","year":"2021","unstructured":"Elliot Anshelevich , Aris Filos-Ratsikas , Nisarg Shah , and Alexandros A Voudouris . 2021. Distortion in Social Choice Problems: The First 15 Years and Beyond. arXiv preprint arXiv:2103.00911 ( 2021 ). Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A Voudouris. 2021. Distortion in Social Choice Problems: The First 15 Years and Beyond. arXiv preprint arXiv:2103.00911 (2021)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3176764.3176784"},{"key":"e_1_3_2_1_10_1","volume-title":"Thirtieth AAAI Conference on Artificial Intelligence.","author":"Anshelevich Elliot","year":"2016","unstructured":"Elliot Anshelevich and Shreyas Sekar . 2016 a. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information . In Thirtieth AAAI Conference on Artificial Intelligence. Elliot Anshelevich and Shreyas Sekar. 2016a. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Thirtieth AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_2_1_11_1","volume-title":"International Conference on Web and Internet Economics. Springer, 265--278","author":"Anshelevich Elliot","year":"2016","unstructured":"Elliot Anshelevich and Shreyas Sekar . 2016 b. Truthful mechanisms for matching and clustering in an ordinal world . In International Conference on Web and Internet Economics. Springer, 265--278 . Elliot Anshelevich and Shreyas Sekar. 2016b. Truthful mechanisms for matching and clustering in an ordinal world. In International Conference on Web and Internet Economics. Springer, 265--278."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434417"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1287\/opre.2017.1603","article-title":"An O(log n\/log log n)-approximation algorithm for the asymmetric traveling salesman problem","volume":"65","author":"Asadpour Arash","year":"2017","unstructured":"Arash Asadpour , Michel X Goemans , Aleksander Madry , Shayan Oveis Gharan , and Amin Saberi . 2017 . An O(log n\/log log n)-approximation algorithm for the asymmetric traveling salesman problem . Operations Research 65 , 4 (2017), 1043 -- 1061 . Arash Asadpour, Michel X Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi. 2017. An O(log n\/log log n)-approximation algorithm for the asymmetric traveling salesman problem. Operations Research 65, 4 (2017), 1043--1061.","journal-title":"Operations Research"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_3_2_1_15_1","volume-title":"International Conference on Web and Internet Economics. Springer, 236--250","author":"Caragiannis Ioannis","year":"2016","unstructured":"Ioannis Caragiannis , Aris Filos-Ratsikas , S\u00f8ren Kristoffer Stiil Frederiksen , Kristoffer Arnsfelt Hansen , and Zihan Tan . 2016 . Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship . In International Conference on Web and Internet Economics. Springer, 236--250 . Ioannis Caragiannis, Aris Filos-Ratsikas, S\u00f8ren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, and Zihan Tan. 2016. Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship. In International Conference on Web and Internet Economics. Springer, 236--250."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2986--3004","author":"Charikar Moses","year":"2022","unstructured":"Moses Charikar and Prasanna Ramakrishnan . 2022 . Metric Distortion Bounds for Randomized Social Choice . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2986--3004 . Moses Charikar and Prasanna Ramakrishnan. 2022. Metric Distortion Bounds for Randomized Social Choice. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2986--3004."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1080--1097","author":"Chekuri Chandra","year":"2011","unstructured":"Chandra Chekuri , Jan Vondr\u00e1k , and Rico Zenklusen . 2011 . Multi-budgeted matchings and matroid intersection via dependent rounding . In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1080--1097 . Chandra Chekuri, Jan Vondr\u00e1k, and Rico Zenklusen. 2011. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1080--1097."},{"key":"e_1_3_2_1_18_1","volume-title":"International Symposium on Algorithmic Game Theory. Springer, 1--12","author":"Filos-Ratsikas Aris","year":"2014","unstructured":"Aris Filos-Ratsikas , S\u00f8ren Kristoffer Stiil Frederiksen , and Jie Zhang . 2014 . Social welfare in one-sided matchings: Random priority and beyond . In International Symposium on Algorithmic Game Theory. Springer, 1--12 . Aris Filos-Ratsikas, S\u00f8ren Kristoffer Stiil Frederiksen, and Jie Zhang. 2014. Social welfare in one-sided matchings: Random priority and beyond. In International Symposium on Algorithmic Game Theory. Springer, 1--12."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133111"},{"key":"e_1_3_2_1_21_1","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1427--1438","author":"Gkatzelis Vasilis","year":"2020","unstructured":"Vasilis Gkatzelis , Daniel Halpern , and Nisarg Shah . 2020 . Resolving the optimal metric distortion conjecture . In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1427--1438 . Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. 2020. Resolving the optimal metric distortion conjecture. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1427--1438."},{"key":"e_1_3_2_1_22_1","unstructured":"Luis A. Goddyn. 2004. Some Problems I Like. (2004). https:\/\/www.sfu.ca\/~goddyn\/Problems\/problems.html  Luis A. Goddyn. 2004. Some Problems I Like. (2004). https:\/\/www.sfu.ca\/~goddyn\/Problems\/problems.html"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1086\/260757"},{"volume-title":"Finite and infinite sets","author":"Jaeger Fran\u00e7ois","key":"e_1_3_2_1_24_1","unstructured":"Fran\u00e7ois Jaeger . 1984. On circular flows in graphs . In Finite and infinite sets . Elsevier , 391--402. Fran\u00e7ois Jaeger. 1984. On circular flows in graphs. In Finite and infinite sets. Elsevier, 391--402."},{"key":"e_1_3_2_1_25_1","volume-title":"Nowhere-zero flow problems. Selected topics in graph theory 3","author":"Jaeger Fran\u00e7ois","year":"1988","unstructured":"Fran\u00e7ois Jaeger . 1988. Nowhere-zero flow problems. Selected topics in graph theory 3 ( 1988 ), 71--95. Fran\u00e7ois Jaeger. 1988. Nowhere-zero flow problems. Selected topics in graph theory 3 (1988), 71--95."},{"key":"e_1_3_2_1_26_1","first-page":"21","article-title":"Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm","volume":"93","author":"Karger David R","year":"1993","unstructured":"David R Karger . 1993 . Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm .. In Soda , Vol. 93. 21 -- 30 . David R Karger. 1993. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm.. In Soda, Vol. 93. 21--30.","journal-title":"Soda"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"34","author":"Kempe David","year":"2020","unstructured":"David Kempe . 2020 a. An analysis framework for metric voting based on LP duality . In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 34 . 2079--2086. David Kempe. 2020a. An analysis framework for metric voting based on LP duality. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 2079--2086."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"34","author":"Kempe David","year":"2020","unstructured":"David Kempe . 2020 b. Communication, distortion, and randomness in metric voting . In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 34 . 2087--2094. David Kempe. 2020b. Communication, distortion, and randomness in metric voting. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 2087--2094."},{"key":"e_1_3_2_1_29_1","volume-title":"Plurality veto: A simple voting rule achieving optimal metric distortion. arXiv preprint arXiv:2206.07098","author":"Kizilkaya Fatih Erdem","year":"2022","unstructured":"Fatih Erdem Kizilkaya and David Kempe . 2022. Plurality veto: A simple voting rule achieving optimal metric distortion. arXiv preprint arXiv:2206.07098 ( 2022 ). Fatih Erdem Kizilkaya and David Kempe. 2022. Plurality veto: A simple voting rule achieving optimal metric distortion. arXiv preprint arXiv:2206.07098 (2022)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329550"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_32_1","volume-title":"On the Randomized Metric Distortion Conjecture. arXiv preprint arXiv:2111.08698","author":"Pulyassary Haripriya","year":"2021","unstructured":"Haripriya Pulyassary and Chaitanya Swamy . 2021. On the Randomized Metric Distortion Conjecture. arXiv preprint arXiv:2111.08698 ( 2021 ). Haripriya Pulyassary and Chaitanya Swamy. 2021. On the Randomized Metric Distortion Conjecture. arXiv preprint arXiv:2111.08698 (2021)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3925"}],"event":{"name":"EC '23: 24th ACM Conference on Economics and Computation","sponsor":["SIGecom Special Interest Group on Economics and Computation"],"location":"London United Kingdom","acronym":"EC '23"},"container-title":["Proceedings of the 24th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597740","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580507.3597740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:56Z","timestamp":1750182536000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":33,"alternative-id":["10.1145\/3580507.3597740","10.1145\/3580507"],"URL":"https:\/\/doi.org\/10.1145\/3580507.3597740","relation":{},"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"2023-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}