APPROACHES TO THE THEORY OF AGGREGATION

Διπλωματική Εργασία uoadl:2898139 56 Αναγνώσεις

Μονάδα:
Κατεύθυνση Θεωρητικά Μαθηματικά
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2020-02-25
Έτος εκπόνησης:
2020
Συγγραφέας:
Κοκονέζη Σοφία
Στοιχεία επιβλεπόντων καθηγητών:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Phokion G. Kolaitis, Distinguished Professor, Department of Computer Science and Engineering, UC Santa Cruz
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Πρωτότυπος Τίτλος:
APPROACHES TO THE THEORY OF AGGREGATION
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Προσεγγίσεις στη θεωρία συμψηφισμού
Περίληψη:
Παρουσιάζουμε διάφορες επίσημες προσεγγίσεις στη θεωρία συμψηφισμού απόψεων, όπου οι όχι/ναι θέσεις μιας ομάδας ατόμων πάνω σε μια σειρά από 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, μπορούμε αμφότερα να ελέγξουμε αποτελεσματικά αν περιγράφεται από έναν τέτοιο τύπο και, σε περίπτωση που αυτό συμβαίνει, να τον κατασκευάσουμε.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Θεωρία συμψηφισμού, λήψη συλλογικών αποφάσεων, υπολογιστική θεωρία κοινωνικών προτιμήσεων
Ευρετήριο:
Όχι
Αρ. σελίδων ευρετηρίου:
0
Εικονογραφημένη:
Όχι
Αρ. βιβλιογραφικών αναφορών:
36
Αριθμός σελίδων:
88
master_s_thesis_Kokonezi_FINAL.pdf (961 KB) Άνοιγμα σε νέο παράθυρο