Aggregation of Votes with Multiple Positions on Each Issue

摘要

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, Advances in Applied Mathematics, 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'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 themulti-sorted conservative constraint satisfaction problem on that set (with each issue representing a different sort) is solvable in polynomial time; otherwise, it is NP-c