TY - GEN

T1 - On the computational complexity of non-dictatorial aggregation

AU - Kirousis, Lefteris

AU - Kolaitis, Phokion G.

AU - Livieratos, John

N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2018.

PY - 2018

Y1 - 2018

N2 - We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society can be aggregated in such a way that the collective outcome is not simply the choices made by a single member of the society. We consider the setting in which the members of a society take a position on a fixed collection of issues, where for each issue several different alternatives are possible, but the combination of choices must belong to a given set X of allowable voting patterns. Such a set X is called a possibility domain if there is an aggregator that is non-dictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomial-time algorithm that decides, given a set X of voting patterns, whether or not X is a possibility domain. Furthermore, if X is a possibility domain, then the algorithm constructs in polynomial time such a non-dictatorial aggregator for X. We also design a polynomial-time algorithm that decides whether X is a uniform possibility domain, that is, whether X admits an aggregator that is non-dictatorial even when restricted to any two positions for each issue. As in the case of possibility domains, the algorithm also constructs in polynomial time a uniform non-dictatorial aggregator, if one exists.

AB - We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society can be aggregated in such a way that the collective outcome is not simply the choices made by a single member of the society. We consider the setting in which the members of a society take a position on a fixed collection of issues, where for each issue several different alternatives are possible, but the combination of choices must belong to a given set X of allowable voting patterns. Such a set X is called a possibility domain if there is an aggregator that is non-dictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomial-time algorithm that decides, given a set X of voting patterns, whether or not X is a possibility domain. Furthermore, if X is a possibility domain, then the algorithm constructs in polynomial time such a non-dictatorial aggregator for X. We also design a polynomial-time algorithm that decides whether X is a uniform possibility domain, that is, whether X admits an aggregator that is non-dictatorial even when restricted to any two positions for each issue. As in the case of possibility domains, the algorithm also constructs in polynomial time a uniform non-dictatorial aggregator, if one exists.

UR - http://www.scopus.com/inward/record.url?scp=85055774306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055774306&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-02149-8_21

DO - 10.1007/978-3-030-02149-8_21

M3 - Conference contribution

AN - SCOPUS:85055774306

SN - 9783030021481

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

SP - 350

EP - 365

BT - Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Proceedings

A2 - Guttmann, Walter

A2 - Desharnais, Jules

A2 - Joosten, Stef

PB - Springer Verlag

T2 - 17th International Conference on Relational and Algebraic Methods in Computer Science, RAMiCS 2018

Y2 - 29 October 2018 through 1 November 2018

ER -