{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T21:14:28Z","timestamp":1779916468547,"version":"3.53.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1527497"],"award-info":[{"award-number":["CCF-1527497"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            In this work, we consider general facility location and social choice problems, in which sets of agents A and facilities F are located in a metric space, and our goal is to assign agents to facilities (as well as choose which facilities to open) to optimize the social cost. We form new algorithms to do this in the presence of only\n            <jats:italic>ordinal information<\/jats:italic>\n            , i.e., when the true costs or distances of the agents from the facilities are\n            <jats:italic>unknown<\/jats:italic>\n            , and only the ordinal preferences of the agents for the facilities are available. The main difference between our work and previous work in this area is that, while we assume that only ordinal information about agent preferences is known, we also know the exact locations of the possible facilities F. Due to this extra information about the facilities, we are able to form powerful algorithms that have small\n            <jats:italic>distortion<\/jats:italic>\n            , i.e., perform almost as well as omniscient algorithms (which know the true numerical distances between agents and facilities) but use only ordinal information about agent preferences. For example, we present natural social choice mechanisms for choosing a single facility to open with distortion of at most 3 for minimizing both the total and the median social cost; this factor is provably the best possible. We analyze many general problems including matching,\n            <jats:italic>k<\/jats:italic>\n            -center, and\n            <jats:italic>k<\/jats:italic>\n            -median, and we present black-box reductions from omniscient approximation algorithms with approximation factor \u03b2 to ordinal algorithms with approximation factor 1+2\u03b2 doing this gives new ordinal algorithms for many important problems and establishes a toolkit for analyzing such problems in the future.\n          <\/jats:p>","DOI":"10.1145\/3434417","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T14:36:39Z","timestamp":1609770999000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Ordinal Approximation for Social Choice, Matching, and Facility Location Problems Given Candidate Positions"],"prefix":"10.1145","volume":"9","author":[{"given":"Elliot","family":"Anshelevich","sequence":"first","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wennan","family":"Zhu","sequence":"additional","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 894--901","author":"Abramowitz Ben","year":"2018","unstructured":"Ben Abramowitz and Elliot Anshelevich . 2018 . Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 894--901 . Ben Abramowitz and Elliot Anshelevich. 2018. Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 894--901."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-35389-6_1"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence.","author":"Amanatidis Georgios","unstructured":"Georgios Amanatidis , Georgios Birmpas , Aris Filos-Ratsikas , and Alexandros A. Voudouris . 2020. Peeking behind the ordinal curtain: Improving distortion via cardinal queries . In Proceedings of the 34th AAAI Conference on Artificial Intelligence. Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. 2020. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. In Proceedings of the 34th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.07.006"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 777--783","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 29th AAAI Conference on Artificial Intelligence. AAAI Press, 777--783 . Elliot Anshelevich, Onkar Bhardwaj, and John Postl. 2015. Approximating optimal social choice under metric preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 777--783."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3176764.3176784"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence. 383--389","author":"Anshelevich Elliot","year":"2016","unstructured":"Elliot Anshelevich and Shreyas Sekar . 2016 . Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information . In Proceedings of the 30th AAAI Conference on Artificial Intelligence. 383--389 . Elliot Anshelevich and Shreyas Sekar. 2016. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proceedings of the 30th AAAI Conference on Artificial Intelligence. 383--389."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_19"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9886-x"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence. 376--382","author":"Benade Gerdus","year":"2017","unstructured":"Gerdus Benade , Swaprava Nath , Ariel D. Procaccia , and Nisarg Shah . 2017 . Preference elicitation for participatory budgeting . In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 376--382 . Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. 2017. Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 376--382."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011788"},{"key":"e_1_2_1_12_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Bhalgat Anand","unstructured":"Anand Bhalgat , Deeparnab Chakrabarty , and Sanjeev Khanna . 2011. Social welfare in one-sided matching markets without money . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 87--98. Anand Bhalgat, Deeparnab Chakrabarty, and Sanjeev Khanna. 2011. Social welfare in one-sided matching markets without money. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 87--98."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 925--932","author":"Bhaskar Umang","year":"2018","unstructured":"Umang Bhaskar , Varsha Dani , and Abheek Ghosh . 2018 . Truthful and near-optimal mechanisms for welfare maximization in multi-winner elections . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 925--932 . Umang Bhaskar, Varsha Dani, and Abheek Ghosh. 2018. Truthful and near-optimal mechanisms for welfare maximization in multi-winner elections. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 925--932."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2004.00483.x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011804"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.06.003"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Byrka Jaros\u0142aw","year":"2014","unstructured":"Jaros\u0142aw Byrka , Thomas Pensyl , Bartosz Rybicki , Aravind Srinivasan , and Khoa Trinh . 2014 . An improved approximation for k-median, and positive correlation in budgeted optimization . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914) . Society for Industrial and Applied Mathematics, 737--756. Jaros\u0142aw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2014. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). Society for Industrial and Applied Mathematics, 737--756."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_17"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5282"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085155"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 973--980","author":"Cheng Yu","year":"2018","unstructured":"Yu Cheng , Shaddin Dughmi , and David Kempe . 2018 . On the distortion of voting with multiple representative candidates . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 973--980 . Yu Cheng, Shaddin Dughmi, and David Kempe. 2018. On the distortion of voting with multiple representative candidates. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 973--980."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46882-2_3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.28"},{"key":"e_1_2_1_24_1","volume-title":"Hinich","author":"Enelow James M.","year":"1984","unstructured":"James M. Enelow and Melvin J . Hinich . 1984 . The Spatial Theory of Voting: An Introduction . Cambridge University Press , New York, NY. James M. Enelow and Melvin J. Hinich. 1984. The Spatial Theory of Voting: An Introduction. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011893"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_13"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7908-2151-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940725"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44803-8_1"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Symposium on Algorithmic Game Theory (SAGT\u201919)","author":"Filos-Ratsikas Aris","unstructured":"Aris Filos-Ratsikas , Evi Micha , and Alexandros A. Voudouris . 2019. The distortion of distributed voting . In Proceedings of the International Symposium on Algorithmic Game Theory (SAGT\u201919) . Springer, 312--325. Aris Filos-Ratsikas, Evi Micha, and Alexandros A. Voudouris. 2019. The distortion of distributed voting. In Proceedings of the International Symposium on Algorithmic Game Theory (SAGT\u201919). Springer, 312--325."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011981"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201918)","author":"Goel Ashish","unstructured":"Ashish Goel , Reyna Hulett , and Anilesh K. Krishnaswamy . 2018. Relating metric distortion and fairness of social choice rules . In Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201918) . Ashish Goel, Reyna Hulett, and Anilesh K. Krishnaswamy. 2018. Relating metric distortion and fairness of social choice rules. In Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201918)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085138"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340230"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence. 544--550","author":"Gross Stephen","year":"2017","unstructured":"Stephen Gross , Elliot Anshelevich , and Lirong Xia . 2017 . Vote until two of you agree: Mechanisms with small distortion and sample complexity . In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 544--550 . Stephen Gross, Elliot Anshelevich, and Lirong Xia. 2017. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 544--550."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Hoefer Martin","year":"2017","unstructured":"Martin Hoefer and Bojana Kodric . 2017 . Combinatorial secretary problems with ordinal information . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) . 133:1--133:14. Martin Hoefer and Bojana Kodric. 2017. Combinatorial secretary problems with ordinal information. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). 133:1--133:14."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5581"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5582"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"e_1_2_1_41_1","volume-title":"Advances in Neural Information Processing Systems","author":"Mandal Debmalya","unstructured":"Debmalya Mandal , Ariel D. Procaccia , Nisarg Shah , and David Woodruff . 2019. Efficient and thrifty voting by any means necessary . In Advances in Neural Information Processing Systems . MIT Press , 7178--7189. Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David Woodruff. 2019. Efficient and thrifty voting by any means necessary. In Advances in Neural Information Processing Systems. MIT Press, 7178--7189."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329550"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/77"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the International Workshop on Cooperative Information Agents (CIA\u201906)","author":"Ariel","unstructured":"Ariel D. Procaccia and Jeffrey S. Rosenschein. 2006. The distortion of cardinal preferences in voting . In Proceedings of the International Workshop on Cooperative Information Agents (CIA\u201906) . Springer, 317--331. Ariel D. Procaccia and Jeffrey S. Rosenschein. 2006. The distortion of cardinal preferences in voting. In Proceedings of the International Workshop on Cooperative Information Agents (CIA\u201906). Springer, 317--331."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence. 706--712","author":"Skowron Piotr Krzysztof","year":"2017","unstructured":"Piotr Krzysztof Skowron and Edith Elkind . 2017 . Social choice under metric preferences: Scoring rules and STV . In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 706--712 . Piotr Krzysztof Skowron and Edith Elkind. 2017. Social choice under metric preferences: Scoring rules and STV. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. 706--712."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434417","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434417","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434417"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3434417"],"URL":"https:\/\/doi.org\/10.1145\/3434417","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}