文章基本信息

标题：On the Computational Complexity of Non-Dictatorial Aggregation
本地全文：下载
作者：Lefteris Kirousis ; Phokion G.Kolaitis ; John Livieratos 等
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2021
卷号：72
页码：1-47
DOI：10.1613/jair.1.12476
语种：English
出版社：American Association of Artificial
摘要：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 there is no single member of the society that always dictates the collective outcome. 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 a non-dictatorial aggregator for X. Furthermore we show that the question of whether a Boolean domain X is a possibility domain is in NLOGSPACE. 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. Then we turn our attention to the case where X is given implicitly either as the set of assignments satisfying a propositional formula or as a set of consistent evaluations of a sequence of propositional formulas. In both cases we provide bounds to the complexity of deciding if X is a (uniform) possibility domain. Finally we extend our results to four types of aggregators that have appeared in the literature: generalized dictatorships whose outcome is always an element of their input anonymous aggregators whose outcome is not affected by permutations of their input monotone whose outcome does not change if more individuals agree with it and systematic which aggregate every issue in the same way.
关键词：constraint satisfaction;multiagent systems