{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T10:34:47Z","timestamp":1791196487862,"version":"4.1.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Greek national funds through the Research Funding Program Heracleitus II"},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>In 1876, Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodgson\u2019s rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view\u2014it is NP-hard even to approximate the Dodgson score within sublogarithmic factors\u2014and from the social choice point of view\u2014it fails basic social choice desiderata such as monotonicity and homogeneity. However, this does not preclude the existence of approximation algorithms for Dodgson that are monotonic or homogeneous, and indeed it is natural to ask whether such algorithms exist.<\/jats:p>\n          <jats:p>\n            In this article, we give definitive answers to these questions. We design a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(log\n            <jats:italic>m<\/jats:italic>\n            )-approximation algorithm (where\n            <jats:italic>m<\/jats:italic>\n            is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation on a known voting rule yields a monotonic, homogeneous, polynomial-time O(\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>m<\/jats:italic>\n            )-approximation algorithm and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity. We complete the picture by studying several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on\n            <jats:italic>m<\/jats:italic>\n            do not exist.\n          <\/jats:p>","DOI":"10.1145\/2556950","type":"journal-article","created":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T12:09:07Z","timestamp":1395144547000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Socially desirable approximations for dodgson\u2019s voting rule"],"prefix":"10.1145","volume":"10","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[{"name":"CTI and University of Patras, Rio, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[{"name":"CTI and University of Patras, Rio, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikos","family":"Karanikolas","sequence":"additional","affiliation":[{"name":"CTI and University of Patras, Rio, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel D.","family":"Procaccia","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060692"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"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.1016\/j.ic.2009.10.001"},{"key":"e_1_2_1_5_1","unstructured":"D. Black. 1958. Theory of Committees and Elections. Cambridge University Press.  D. Black. 1958. Theory of Committees and Elections. Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200810017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200810027"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1058--1067","author":"Caragiannis I."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109642"},{"key":"e_1_2_1_10_1","unstructured":"M. D. Condorcet 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 de d\u00e9cisions rendues \u00e0 la pluralit\u00e9 de voix. Imprimerie Royal. Facsimile published in 1972 by Chelsea Publishing Company New York.  M. D. Condorcet 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 de d\u00e9cisions rendues \u00e0 la pluralit\u00e9 de voix. Imprimerie Royal. Facsimile published in 1972 by Chelsea Publishing Company New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016945.2016954"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0133030"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914083"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-007-9068-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0282-8"},{"key":"e_1_2_1_18_1","volume-title":"Algorithmic Game Theory, N. Nisan, T. Roughgarden, \u00c9","author":"Nisan N."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen. 2001. Algorithmic mechanism design. Games and Economic Behavior 35(1--2) 166--196.  N. Nisan and A. Ronen. 2001. Algorithmic mechanism design. Games and Economic Behavior 35(1--2) 166--196.","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(75)90050-2"},{"key":"e_1_2_1_21_1","first-page":"9","article-title":"A new monotonic and clone-independent single-winner election method","volume":"17","author":"Schulze M.","year":"2003","journal-title":"Voting Matters"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00433944"},{"key":"e_1_2_1_23_1","unstructured":"N. Tideman. 2006. Collective Decisions and Voting. Ashgate.  N. Tideman. 2006. Collective Decisions and Voting. Ashgate."},{"key":"e_1_2_1_24_1","unstructured":"V. V. Vazirani. 2001. Approximation Algorithms. Springer.   V. V. Vazirani. 2001. Approximation Algorithms. Springer."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556950","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2556950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:41Z","timestamp":1750232081000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2556950"],"URL":"https:\/\/doi.org\/10.1145\/2556950","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2011-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}