Παρουσιάζουμε διάφορες επίσημες προσεγγίσεις στη θεωρία συμψηφισμού απόψεων, όπου οι όχι/ναι θέσεις μιας ομάδας ατόμων πάνω σε μια σειρά από m θέματα πρέπει να συναθροιστούν σε μια συλλογική απόφαση, και δείχνουμε ότι αυτές οι προσεγγίσεις είναι κατά μία έννοια «ισοδύναμες». Στη συνέχεια, εστιάζουμε σε δύο από αυτές τις προσεγγίσεις: το αφαιρετικό πλαίσιο (abstract framework) όπου το πεδίο της διαδικασίας συμψηφισμού είναι ένα υποσύνολο του {0,1}^m, το οποίο θεωρείται ότι αντιπροσωπεύει τις «λογικές» ψήφους και το πλαίσιο που βασίζεται στους περιοριστές της ακαιρεότητας (integrity constraint based framework), όπου ένας τύπος της προτασιακής λογικής, που ονομάζεται περιοριστής της ακαιρεότητας (integrity constraint), καθορίζει ποια διανύσματα θεωρούνται «λογικά», υπό την έννοια ότι το πεδίο της διαδικασίας συμψηφισμού είναι το σύνολο των απονομών αληθοτιμών που τον ικανοποιούν. Ενδιαφερόμαστε μόνο για διαδικασίες συμψηφισμού που διατηρούν αυτή την έννοια λογικότητας, χωρίς όμως να δίνουν όλη τη δύναμη απόφασης σε έναν μόνο ψηφοφόρο. Αυτές οι διαδικασίες ονομάζονται μη-δικτατορικοί συμψηφιστές. Παρέχουμε ικανές και αναγκαίες συνθήκες, που αφορούν στη συντακτική μορφή ενός περιοριστή ακεραιότητας, έτσι ώστε το πεδίο που περιγράφει να δέχεται έναν μη-δικτατορικό συμψηφιστή. Ονομάζουμε αυτό το είδος τύπων δυνητικούς περιοριστές ακεραιότητας (possibility integrity constraints). Δείχνουμε ότι οι δυνητικοί περιοριστές ακεραιότητας είναι εύκολα αναγνωρίσιμοι και παρέχουμε αλγόριθμους οι οποίοι, δοθέντος ενός πεδίου D \subseteq {0,1}^m, ελέγχουν σε χρόνο πολυωνυμικό στο μέγεθός του εάν δέχεται έναν μη-δικτατορικό συμψηφιστή, και παράγουν έναν δυνητικό περιοριστή ακεραιότητας που το περιγράφει, σε περίπτωση που αυτό συμβαίνει. Μελετάμε επίσης διάφορες υποκατηγορίες μη-δικτατορικών συμψηφιστών, συγκεκριμένα τοπικά μη-δικτατορικούς συμψηφιστές (locally non-dictatorial aggregators), συμψηφιστές που δεν είναι γενικευμένες δικτατορίες (not generalized dictatorships), ανωνυμικούς (anonymous), μονοτονικούς (monotone), ισχυρά δημοκρατικούς (StrongDem) και συστηματικούς συμψηφιστές (systematic aggregators). Χαρακτηρίζουμε συντακτικώς τους αντίστοιχους περιοριστές ακεραιότητας και αποδεικνύουμε ότι κάθε ένα από αυτά τα είδη περιοριστών ακεραιότητας μπορεί να αναγνωριστεί αποτελεσματικά. Τέλος, δείχνουμε ότι δοθέντος ενός πεδίου D, μπορούμε αμφότερα να ελέγξουμε αποτελεσματικά αν περιγράφεται από έναν τέτοιο τύπο και, σε περίπτωση που αυτό συμβαίνει, να τον κατασκευάσουμε.
(EL)
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.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
