Approaches to the theory of aggregation

Postgraduate Thesis uoadl:2898139 61 Read counter

Unit:
Κατεύθυνση Θεωρητικά Μαθηματικά
Library of the School of Science
Deposit date:
2020-02-25
Year:
2020
Author:
Kokonezi Sofia
Supervisors info:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Phokion G. Kolaitis, Distinguished Professor, Department of Computer Science and Engineering, UC Santa Cruz
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Original Title:
APPROACHES TO THE THEORY OF AGGREGATION
Languages:
English
Translated title:
Approaches to the theory of aggregation
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.
Main subject category:
Science
Keywords:
Judgment aggregation, collective decision making, computational social choice
Index:
No
Number of index pages:
0
Contains images:
No
Number of references:
36
Number of pages:
88
master_s_thesis_Kokonezi_FINAL.pdf (961 KB) Open in new window