Στοιχεία επιβλεπόντων καθηγητών:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Phokion G. Kolaitis, Distinguished Professor, Department of Computer Science and Engineering, UC Santa Cruz
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Περίληψη:
Παρουσιάζουμε διάφορες επίσημες προσεγγίσεις στη θεωρία συμψηφισμού απόψεων, όπου οι όχι/ναι θέσεις μιας ομάδας ατόμων πάνω σε μια σειρά από 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, μπορούμε αμφότερα να ελέγξουμε αποτελεσματικά αν περιγράφεται από έναν τέτοιο τύπο και, σε περίπτωση που αυτό συμβαίνει, να τον κατασκευάσουμε.
