Aggregation of votes with multiple positions on each issue

Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 require the aggregation to be 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 set-up, non-dictatorial aggregation of votes in a society of an arbitrary size is possible if and only if a non-dictatorial binary aggregator exists or a non-dictatorial ternary aggregator exists such that, for each issue, the corresponding component of the aggregator, when restricted to twoelement 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, 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’s 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.

Original languageEnglish (US)
Title of host publicationRelational and Algebraic Methods in Computer Science - 16th International Conference, RAMiCS 2017, Proceedings
EditorsPeter Hofner, Damien Pous, Georg Struth
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783319574172
StatePublished - 2017
Event16th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2017 - Lyon, France
Duration: May 15 2017May 18 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10226 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2017

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Aggregation of votes with multiple positions on each issue'. Together they form a unique fingerprint.

Cite this