{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:32Z","timestamp":1750221092756,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            We consider the problem of aggregating votes cast by a society on a fixed set of issues, where each member of the society may vote for one of several positions on each issue, but the combination of votes on the various issues is restricted to a set of feasible voting patterns. We follow the aggregation framework used by Dokow and Holzman [Aggregation of non-binary evaluations,\n            <jats:italic>Advances in Applied Mathematics<\/jats:italic>\n            , 45:4, 487--504, 2010], in which both preference aggregation and judgment aggregation can be cast. We require the aggregation to be independent on each issue, and also supportive, i.e., for every issue, the corresponding component of every aggregator, when applied to a tuple of votes, must take as value one of the votes in that tuple. We prove that, in such a setup, non-dictatorial aggregation of votes in a society of an arbitrary size is possible if and only if either there is a non-dictatorial aggregator for two voters or there is an aggregator for three voters such that, for each issue, the corresponding component of the aggregator, when restricted to two-element sets of votes, is a majority operation or a minority operation. We then introduce a notion of a uniform non-dictatorial aggregator, which is an aggregator such that on every issue, and when restricted to arbitrary two-element subsets of the votes for that issue, it differs from all projection functions. We first give a characterization of sets of feasible voting patterns that admit a uniform non-dictatorial aggregator. After this and by making use of Bulatov\u2019s dichotomy theorem for conservative constraint satisfaction problems, we connect social choice theory with the computational complexity of constraint satisfaction by proving that if a set of feasible voting patterns has a uniform non-dictatorial aggregator of some arity, then the multi-sorted conservative constraint satisfaction problem on that set (with each issue representing a different sort) is solvable in polynomial time; otherwise, it is NP-complete.\n          <\/jats:p>","DOI":"10.1145\/3296675","type":"journal-article","created":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T14:01:39Z","timestamp":1548684099000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Aggregation of Votes with Multiple Positions on Each Issue"],"prefix":"10.1145","volume":"7","author":[{"given":"Lefteris","family":"Kirousis","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Livieratos","sequence":"additional","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"volume-title":"Social Choice and Individual Values","author":"Arrow Kenneth J.","key":"e_1_2_1_1_1","unstructured":"Kenneth J. Arrow . 1951. Social Choice and Individual Values . Wiley , New York . Kenneth J. Arrow. 1951. Social Choice and Individual Values. Wiley, New York."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.25"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.07.004"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_13"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-008-9306-x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-006-0196-x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-008-0320-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2007.10.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2010.02.005"},{"volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Endriss Ulle","key":"e_1_2_1_12_1","unstructured":"Ulle Endriss . 2016. Judgment aggregation . In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D . Procaccia (Eds.). Cambridge University Press , 399--426. Ulle Endriss. 2016. Judgment aggregation. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 399--426."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Ulle Endriss Umberto Grandi and Daniele Porello. 2012. Complexity of judgment aggregation. J. Artif. Intell. Res. (2012) 481--514.   Ulle Endriss Umberto Grandi and Daniele Porello. 2012. Complexity of judgment aggregation. J. Artif. Intell. Res. (2012) 481--514.","DOI":"10.1613\/jair.3708"},{"key":"e_1_2_1_14_1","volume-title":"IJCAI Proceedings\u2014International Joint Conference on Artificial Intelligence","volume":"22","author":"Grandi Umberto","year":"2011","unstructured":"Umberto Grandi and Ulle Endriss . 2011 . Binary aggregation with integrity constraints . In IJCAI Proceedings\u2014International Joint Conference on Artificial Intelligence , Vol. 22 . 204. Umberto Grandi and Ulle Endriss. 2011. Binary aggregation with integrity constraints. In IJCAI Proceedings\u2014International Joint Conference on Artificial Intelligence, Vol. 22. 204."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.05.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Umberto Grandi Ulle Endriss etal 2010. Lifting rationality assumptions in binary aggregation. In AAAI.   Umberto Grandi Ulle Endriss et al. 2010. Lifting rationality assumptions in binary aggregation. In AAAI.","DOI":"10.1609\/aaai.v24i1.7603"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2621956"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/ext009"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57418-9_13"},{"key":"e_1_2_1_20_1","volume-title":"On the computational complexity of non-dictatorial aggregation. CoRR abs\/1711.01574","author":"Kirousis Lefteris M.","year":"2017","unstructured":"Lefteris M. Kirousis , Phokion G. Kolaitis , and John Livieratos . 2017. On the computational complexity of non-dictatorial aggregation. CoRR abs\/1711.01574 ( 2017 ). arxiv:1711.01574 http:\/\/arxiv.org\/abs\/1711.01574. Lefteris M. Kirousis, Phokion G. Kolaitis, and John Livieratos. 2017. On the computational complexity of non-dictatorial aggregation. CoRR abs\/1711.01574 (2017). arxiv:1711.01574 http:\/\/arxiv.org\/abs\/1711.01574."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-011-0025-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0266267102001098"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SYNT.0000029950.50517.59"},{"volume-title":"Handbook of Rational and Social Choice","author":"List Christian","key":"e_1_2_1_24_1","unstructured":"Christian List and Clemens Puppe . 2009. Judgment aggregation: A survey . In Handbook of Rational and Social Choice , Christian List and Clemens Puppe (Eds.). Oxford University Press . Christian List and Clemens Puppe. 2009. Judgment aggregation: A survey. In Handbook of Rational and Social Choice, Christian List and Clemens Puppe (Eds.). Oxford University Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2006.04.008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2010.01.010"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10992-005-9011-x"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635508"},{"volume-title":"The Two-valued Iterative Systems of Mathematical Logic. Number 5 in Annals of Mathematics Studies","author":"Post Emil Leon","key":"e_1_2_1_29_1","unstructured":"Emil Leon Post . 1941. The Two-valued Iterative Systems of Mathematical Logic. Number 5 in Annals of Mathematics Studies . Princeton University Press . Emil Leon Post. 1941. The Two-valued Iterative Systems of Mathematical Logic. Number 5 in Annals of Mathematics Studies. Princeton University Press."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_31_1","volume-title":"Impossibility theorems and the universal algebraic toolkit. CoRR abs\/1506.01315","author":"Szegedy Mario","year":"2015","unstructured":"Mario Szegedy and Yixin Xu. 2015. Impossibility theorems and the universal algebraic toolkit. CoRR abs\/1506.01315 ( 2015 ). http:\/\/arxiv.org\/abs\/1506.01315. Mario Szegedy and Yixin Xu. 2015. Impossibility theorems and the universal algebraic toolkit. CoRR abs\/1506.01315 (2015). http:\/\/arxiv.org\/abs\/1506.01315."},{"volume-title":"Clones in Universal Algebra","author":"Szendrei \u00c1gnes","key":"e_1_2_1_32_1","unstructured":"\u00c1gnes Szendrei . 1986. Clones in Universal Algebra . Vol. 99 . Presses de l\u2019Universit\u00e9 de Montr\u00e9al . \u00c1gnes Szendrei. 1986. Clones in Universal Algebra. Vol. 99. Presses de l\u2019Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(75)90062-9"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3296675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3296675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:59Z","timestamp":1750208279000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3296675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3296675"],"URL":"https:\/\/doi.org\/10.1145\/3296675","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2019,1,25]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}