Supervisors info:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Phokion G. Kolaitis, Distinguished Professor, Department of Computer Science and Engineering, UC Santa Cruz
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Summary:
We present various formal approaches to the theory of judgement aggregation, where no/yes positions of a group of individuals over a set of m issues need to be aggregated into a collective one, and show that these approaches are in a sense "equivalent". Then, we focus on two of these approaches: the abstract framework where the domain of the aggregation process is a subset of {0,1}^m, thought to represent the "rational" judgements and the integrity constraint framework, where a formula of propositional logic, called the integrity constraint defines which ballots are considered "rational", in the sense that the domain of the aggregation process is the set of its satisfying truth assignments. We are only interested in aggregation procedures that preserve this notion of rationality, without giving all decision power to a single voter. These procedures are called non-dictatorial aggregators. We provide necessary and sufficient conditions, regarding the syntactic type of an integrity constraint, so that the domain it describes admits a non-dictatorial aggregator. We call this type of formulas possibility integrity constraints. We show that possibility integrity constraints are easily recognisable and provide algorithms that, given a domain D \subseteq {0,1}^m, check in time polynomial in its size whether it admits a non-dictatorial aggregator, and actually produce a possibility integrity constraint that describes it in case it does. We also study various sub-classes of non-dictatorial aggregators, namely locally non-dictatorial aggregators, aggregators that are not generalized dictatorships, anonymous, monotone, StrongDem and systematic aggregators. We syntactically characterize the corresponding integrity constraints and show that each of these types of integrity constraints can be recognized efficiently. Finally, we show that given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it.
