## Abstract

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 language | English (US) |
---|---|

Title of host publication | Relational and Algebraic Methods in Computer Science - 16th International Conference, RAMiCS 2017, Proceedings |

Editors | Peter Hofner, Damien Pous, Georg Struth |

Publisher | Springer Verlag |

Pages | 209-225 |

Number of pages | 17 |

ISBN (Print) | 9783319574172 |

DOIs | |

State | Published - 2017 |

Event | 16th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2017 - Lyon, France Duration: May 15 2017 → May 18 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10226 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 16th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2017 |
---|---|

Country/Territory | France |

City | Lyon |

Period | 5/15/17 → 5/18/17 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science