2019/01/01 by Josep Dı́az, Díaz, Josep, Lefteris M. Kirousis +5
Computer Science · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1901.00138
openalex publication_date 2019/01/01 · openalex created_date 2019/08/13 · openalex updated_date 2026/07/28
In the field of Judgment Aggrgation, a domain, that is a subset of a\nCartesian power of 0,1 , is considered to reflect abstract rationality\nrestrictions on vectors of two-valued judgments on a number of issues. We are\ninterested in the ways we can aggregate the positions of a set of individuals,\nwhose positions over each issue form vectors of the domain, by means of\nunanimous (idempotent) functions, whose output is again an element of the\ndomain. Such functions are called non-dictatorial, when their output is not\nsimply the positions of a single individual. Here, we consider domains\nadmitting various kinds of non-dictatorial aggregators, which reflect various\nproperties of majority aggregation: (locally) non-dictatorial, generalized\ndictatorships, anonymous, monotone, StrongDem and systematic. We show that\ninteresting and, in some sense, democratic voting schemes are always provided\nby domains that can be described by propositional formulas of specific\nsyntactic types we define. Furthermore, we show that we can efficiently\nrecognize such formulas and that, given a domain, we can both efficiently check\nif it is described by such a formula and, in case it is, construct it. Our\nresults fall in the realm of classical results concerning the syntactic\ncharacterization of domains with specific closure properties, like domains\nclosed under logical AND which are the models of Horn formulas. The techniques\nwe use to obtain our results draw from judgment aggregation as well as\npropositional logic and universal algebra.\n