{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T05:05:19Z","timestamp":1772946319439,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,3,18]],"date-time":"2016-03-18T00:00:00Z","timestamp":1458259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"COST Action IC1205 on \u201cComputational Social Choice.\u201d"},{"name":"NSF","award":["CCF-1215883"],"award-info":[{"award-number":["CCF-1215883"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>A well-studied approach to the design of voting rules views them as maximum likelihood estimators; given votes that are seen as noisy estimates of a true ranking of the alternatives, the rule must reconstruct the most likely true ranking. We argue that this is too stringent a requirement and instead ask:<jats:italic>how many<\/jats:italic>votes does a voting rule need to reconstruct the true ranking? We define the family of<jats:italic>pairwise-majority consistent<\/jats:italic>rules and show that for all rules in this family, the number of samples required from Mallows\u2019s noise model is logarithmic in the number of alternatives, and that no rule can do asymptotically better (while some rules like plurality do much worse). Taking a more normative point of view, we consider voting rules that surely return the true ranking as the number of samples tends to infinity (we call this property<jats:italic>accuracy in the limit<\/jats:italic>); this allows us to move to a higher level of abstraction. We study families of noise models that are parameterized by distance functions and find voting rules that are accurate in the limit for all noise models in such general families. We characterize the distance functions that induce noise models for which pairwise-majority consistent rules are accurate in the limit and provide a similar result for another novel family of<jats:italic>position-dominance consistent<\/jats:italic>rules. These characterizations capture three well-known distance functions.<\/jats:p>","DOI":"10.1145\/2892565","type":"journal-article","created":{"date-parts":[[2016,3,18]],"date-time":"2016-03-18T13:50:44Z","timestamp":1458309044000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["When Do Noisy Votes Reveal the Truth?"],"prefix":"10.1145","volume":"4","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[{"name":"University of Patras &amp; CTI, Patras, Greece"}]},{"given":"Ariel D.","family":"Procaccia","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh PA, USA"}]},{"given":"Nisarg","family":"Shah","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,3,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","volume-title":"Social Choice and Individual Values","author":"Arrow K.","DOI":"10.12987\/9780300186987"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999149"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00303169"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229030"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2900728.2900909"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347112"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2893970"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095198"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020336.3020354"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2496(91)90050-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2343776.2343786"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562814.1562831"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1838206.1838259"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"E. Elkind and A. Slinko. 2015. Rationalizations of voting rules. In Handbook of Computational Social Choice F. Brandt V. Conitzer U. Endriss J. Lang and A. D. Procaccia (Eds.). Cambridge University Press Chapter 8. E. Elkind and A. Slinko. 2015. Rationalizations of voting rules. In Handbook of Computational Social Choice F. Brandt V. Conitzer U. Endriss J. Lang and A. D. Procaccia (Eds.). Cambridge University Press Chapter 8.","DOI":"10.1017\/CBO9781107446984.009"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000305540011737X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1111\/j.2517-6161.1986.tb01420.x","article-title":"Distance based ranking models","volume":"48","author":"Fligner M. A.","year":"1986","journal-title":"Journal of the Royal Statistical Society B"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645531.655830"},{"key":"e_1_2_1_18_1","volume-title":"Learning to Rank for Information Retrieval","author":"Liu T. Y."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104482.3104501"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/44.1-2.114"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2891460.2891619"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"T. Meskanen and H. Nurmi. 2008. Closeness counts in social choice. In Power Freedom and Voting M. Braham and F. Steffen (Eds.). Springer-Verlag 289--306. T. Meskanen and H. Nurmi. 2008. Closeness counts in social choice. In Power Freedom and Voting M. Braham and F. Steffen (Eds.). Springer-Verlag 289--306.","DOI":"10.1007\/978-3-540-73382-9_15"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2030470.2030481"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2900728.2900746"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020652.3020725"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386811"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283469"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1961757"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2892565","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2892565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:55Z","timestamp":1750272955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2892565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,18]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2892565"],"URL":"https:\/\/doi.org\/10.1145\/2892565","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,18]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}