Στο πλαίσιο της παρούσας διδακτορικής διατριβής μελετώνται υπολογιστικά ζητήματα που προκύπτουν από τη θεωρία της κοινωνικής επιλογής. Ένα από τα κύρια θέματα της θεωρίας αυτής είναι οι εκλογές. Τα προβλήματα που σχετίζονται με τις εκλογές ανήκουν στη θεωρία ψηφοφοριών όπου βασικό πρόβλημα είναι η εύρεση του νικητή των εκλογών όταν έχουμε ως δεδομένες τις προτιμήσεις των ψηφοφόρων. Στη βιβλιογραφία υπάρχουν αρκετοί κανόνες ψηφοφορίας βάσει των οποίων γίνεται ο υπολογισμός της κατάταξης μιας ψηφοφορίας και της ανάδειξης του νικητή. Η θεωρία των ψηφοφοριών αποτελεί ένα σημαντικό κλάδο της θεωρίας της κοινωνικής επιλογής με άμεσες εφαρμογές στην κοινωνία, καθώς οι κανόνες αυτοί εφαρμόζονται στην πράξη σε βουλευτικές, δημοτικές ή τοπικές εκλογές, καθώς επίσης και σε αρκετές επιτροπές σχετικές με την λήψη συλλογικών αποφάσεων. Στη συγκεκριμένη διατριβή μελετούμε πρώτα τους κανόνες ψηφοφορίας που πρότειναν ο Dodgson και ο Young, οι οποίοι είναι σχεδιασμένοι έτσι ώστε να εντοπίζουν τον υποψήφιο που είναι διαισθητικά πιο κοντά στο να είναι ο νικητής σύμφωνα με το κριτήριο του Condorcet. Σύμφωνα με το κριτήριο αυτό, νικητής θα πρέπει να είναι ο υποψήφιος που έχει την προτίμηση της πλειοψηφίας έναντι των άλλων υποψήφιων. Ωστόσο κάτι τέτοιο δεν μπορεί να υπολογιστεί πάντα, καθώς οι προτιμήσεις της πλειοψηφίας μπορεί να είναι κυκλικές. Για παράδειγμα σε μια εκλογή με 3 υποψηφίους, ο υποψήφιος a να προτιμάται σε σχέση με τον b, ο b να προτιμάται σε σχέση με τον c, αλλά ο c να προτιμάται σε σχέση με τον a. Στην περίπτωση αυτή δεν μπορεί να καθοριστεί ο νικητής των εκλογών σύμφωνα με το κριτήριο του Condorcet. Για το λόγο αυτό χρησιμοποιούμε τους κανόνες ψηφοφορίας που προτάθηκαν από τους Dodgson και Young, οι οποίοι παρέχουν μια διαφορετική έννοια εγγύτητας ενός υποψήφιου στο να αναδειχθεί νικητής κατά Condorcet. Οι συγκεκριμένοι κανόνες αποτελούν ένα σημαντικό κομμάτι της βιβλιογραφίας της θεωρίας της Κοινωνικής Επιλογής διότι διαισθητικά παρουσιάζουν υψηλή εγγύτητα με τον κανόνα του Condorcet. Πιο συγκεκριμένα και σύμφωνα με τον κανόνα του Dodgson ισχύουν τα εξής: δεδομένου ενός συνόλου προτιμήσεων των ψηφοφόρων, ο βαθμός ενός υποψηφίου ορίζεται ως ο ελάχιστος αριθμός των ανταλλαγών που πρέπει να γίνουν μεταξύ γειτονικών υποψηφίων στην κατάταξη των ψηφοφόρων έτσι ώστε ο συγκεκριμένος υποψήφιος να αναδειχθεί νικητής κατά Condorcet. Ο υποψήφιος που έχει τον ελάχιστο βαθμό Dodgson είναι νικητής κατά Dodgson. Αντίστοιχα, σύμφωνα με τον κανόνα του Young ο βαθμός ενός υποψηφίου είναι το μέγεθος του μεγαλύτερου υποσυνόλου ψηφοφόρων έτσι ώστε, αν ληφθούν υπόψη μόνο αυτά τα ψηφοδέλτια, ο συγκεκριμένος υποψήφιος να γίνεται νικητής κατά Condorcet. Ο υποψήφιος με το μέγιστο βαθμό Young είναι νικητής κατά Young.
Δυστυχώς, ο υπολογισμός του βαθμού ενός δεδομένου υποψηφίου είναι δύσκολος είτε με τον κανόνα του Dodgson είτε με τον κανόνα του Young. Για αυτό το λόγο τα υπολογιστικά ζητήματα που προκύπτουν και μελετώνται στην παρούσα διατριβή αφορούν στην προσέγγιση των δυο αυτών κανόνων ψηφοφορίας. Πιο συγκεκριμένα παρουσιάζονται δύο αλγόριθμοι που προσεγγίζουν το βαθμό ενός υποψηφίου σύμφωνα με τον κανόνα του Dodgson: ένας άπληστος αλγόριθμος και ένας αλγόριθμος βασισμένος σε γραμμικό πρόγραμμα. Οι δυο αυτοί αλγόριθμοι έχουν λόγο προσέγγισης H_{m-1}, όπου m είναι ο αριθμός των υποψηφίων και H_{m-1} είναι ο (m-1)-ος αρμονικός αριθμός. Επίσης, αποδεικνύεται ότι δεν υπάρχει αλγόριθμος πολυωνυμικού χρόνου που να προσεγγίζει το βαθμό Dodgson κατά λογαριθμικό παράγοντα, εκτός εάν υπάρχουν για τα προβλήματα της κλάσης NP αλγόριθμοι ψευδο-πολυωνυμικού χρόνου. Παρότι διαισθητικά υπερέχει ο άπληστος αλγόριθμος, στη συγκεκριμένη διατριβή υποστηρίζουμε ότι ο αλγόριθμος που είναι βασισμένος σε γραμμικό πρόγραμμα έχει πλεονέκτημα από την οπτική της θεωρίας της κοινωνικής επιλογής. Επιπλέον, αποδεικνύεται ότι ο υπολογισμός κάθε λογικής προσέγγισης της κατάταξης που παράγεται από τον κανόνα Dodgson είναι ένα υπολογιστικά δύσκολο πρόβλημα, γεγονός που εξηγεί, από την πλευρά της θεωρίας της πολυπλοκότητας, το ότι έχουν παρατηρηθεί μεγάλες διαφορές κατά τη σύγκριση εκλογών Dodgson με απλούστερους κανόνες ψηφοφορίας που εμπεριέχονται στη βιβλιογραφία της θεωρίας της κοινωνικής επιλογής. Τέλος, αποδεικνύεται ότι το πρόβλημα υπολογισμού του βαθμού ενός υποψηφίου σύμφωνα με τον κανόνα του Young είναι επίσης υπολογιστικά δύσκολο. Αυτό οδηγεί σε ένα αποτέλεσμα μη προσεγγισιμότητας για την κατάταξη υποψηφίων σε μια εκλογή σύμφωνα με τον κανόνα του Young.
Αν και ο κανόνας του Dodgson είναι ένας από τους πιο καλά μελετημένους κανόνες ψηφοφορίας, παρουσιάζει σοβαρές ελλείψεις, τόσο από υπολογιστικής άποψης --- είναι υπολογιστικά δύσκολο ακόμη και να προσεγγιστεί ο βαθμός Dodgson ενός υποψηφίου --- όσο και από την πλευρά της κοινωνικής επιλογής, καθώς αποτυγχάνει σε βασικές επιθυμητές ιδιότητές της, όπως είναι η μονοτονία και η ομοιογένεια. Ωστόσο, αυτό δεν αποκλείει την ύπαρξη προσεγγιστικών αλγορίθμων για τον κανόνα του Dodgson που είναι μονότονοι ή ομοιογενείς, οπότε τίθεται το ερώτημα ύπαρξης τέτοιων αλγόριθμων. Στη διατριβή αυτή δίνονται οριστικές απαντήσεις στα ερωτήματα αυτά. Παρουσιάζεται ένας μονότονος αλγόριθμος εκθετικού χρόνου που πετυχαίνει λόγο προσέγγισης του βαθμού Dodgson ίσο με 2 και το αποτέλεσμα συμπληρώνεται με ένα αυστηρό αντίστοιχο κάτω φράγμα. Παρουσιάζεται επίσης ένας μονότονος προσεγγιστικός αλγόριθμος πολυωνυμικού χρόνου με λόγο O(logm) (όπου m είναι ο αριθμός των υποψηφίων): και στην περίπτωση αυτή το αποτέλεσμα είναι βέλτιστο, λόγω ύπαρξης αντίστοιχου κάτω φράγματος. Επιπλέον, αποδεικνύεται ότι μια μικρή παραλλαγή σε ένα γνωστό κανόνα ψηφοφορίας δίνει ένα μονότονο, ομοιογενή, O(m logm)-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, με τον καλύτερο δυνατό λόγο προσέγγισης, ακόμη και αν αυτό που μας ενδιαφέρει είναι μόνο η ομοιογένεια. Τέλος, μελετώνται διάφορες πρόσθετες ιδιότητες κοινωνικής επιλογής, για τις οποίες δεν υπάρχει αλγόριθμος με λόγο προσέγγισης που να εξαρτάται μόνο από το m . Αυτά τα αποτελέσματα της προσεγγισιμότητας του κανόνα αυτού αποτελούν σημαντική προσφορά της διατριβής καθώς μπορούν να θεωρηθούν ως κανόνες που υπολογίζονται σε πολυωνυμικό χρόνο και πληρούν μάλιστα επιθυμητές κοινωνικές ιδιότητες, ενώ ταυτόχρονα διέπονται και από την φιλοσοφία του κανόνα που θέσπισε ο Dodgson.
Ένα άλλο σημαντικό υπολογιστικό πρόβλημα με το οποίο ασχολείται η παρούσα διατριβή είναι αυτό της δωροδοκίας των εκλογών. Στο πρόβλημα της δωροδοκίας μπορεί κάποιος με δεδομένο ένα χρηματικό προϋπολογισμό να αλλάξει τις προτιμήσεις των ψηφοφόρων ώστε να αναδειχθεί νικητής των εκλογών ο υποψήφιος της αρεσκείας του. Στη συγκεκριμένη διατριβή μελετώνται κανόνες ψηφοφορίας που βασίζονται στη βαθμολόγηση των υποψηφίων. Πιο συγκεκριμένα μελετάται η τάξη των κανόνων ψηφοφορίας όπου κάθε ψηφοφόρος εκχωρεί κ βαθμούς στον υποψήφιο που προτιμά ως πρώτο, λ βαθμούς στον υποψήφιο που προτιμά ως δεύτερο και 0 βαθμούς σε όλους τους υπόλοιπους υποψηφίους. Αποδεικνύεται ότι για αυτήν την τάξη των κανόνων βαθμολόγησης η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Στους κανόνες που βασίζονται στην βαθμολόγηση των υποψηφίων περιλαμβάνονται αυτοί της πλειοψηφίας και της 2-έγκρισης όπου μια βέλτιστη στρατηγική δωροδοκίας μπορεί εύκολα να υπολογιστεί, καθώς επίσης και ο κανόνας της 3-έγκρισης όπου η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Λαμβάνοντας υπόψιν την πολυπλοκότητα αυτών των κανόνων εξάγεται το συμπέρασμα ότι οι κανόνες που μελετήθηκαν είναι εκ των πιο απλών που δεν είναι ευάλωτοι στη δωροδοκία. / In this PhD thesis we study computational problems arising from the theory of social choice. One main aspect of Computational Social Choice is voting theory. The most important problem of voting theory is the computation of the winner of the elections when we have as input the preferences of the voters. In the literature there are many voting rules according to which the computation of the winner of the elections is done. Voting theory is a seminal subject in the Computational Social Choice theory with applications in the society. Voting rules are widely used in government and municipal or local elections and also in committees for taking decisions. In this thesis we start by considering voting rules proposed by Dodgson and Young. These rules are both designed to find an alternative closest to being a Condorcet winner. According to the Condorcet criterion, the winner of the elections should be the one that the majority of the voters prefer in relation to every other candidate. Unfortunately, the preferences of the majority may be circular. For example, in an election with 3 candidates, candidate a is preferred to b by the majority and b is preferred in relation to c, but c is preferred to a. Then a Condorcet winner does not exist. Each of these voting rules provide a different notion of proximity of how close they are to Condorcet rule. In the Dodgson rule the score of a candidate, given a set of preferences, is the minimum number of exchanges between adjacent candidates in order for the specific candidate to become a Condorcet winner. The Dodgson winner is the candidate with the minimum Dodgson score. In the Young rule the score of a candidate is the size of the largest subset of voters, when taking in account only these votes, the specific candidate becomes a Condorcet winner. The Young winner is the candidate with the maximum Young score.
The score of a given alternative is known to be hard to compute under either rule and so the computational problems that arise and we consider are related to the approximation of the voting rules proposed by Dodgson and Young. We put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of H_{m-1}, where m is the number of alternatives and H_{m-1} is the (m-1)st harmonic number. We also prove that there is no polynomial time algorithm that approximates the Dodgson score by (1/2-ε)lnm, unless problems in NP have quasi-polynomial time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Also, we show that the problem of calculating the Young score is NP-hard to approximate by any factor. This leads to an inapproximability result for the Young ranking.
Although Dodgson's rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view --- it is NP-hard even to approximate the Dodgson score within sublogarithmic factors --- and from the social choice point of view --- it fails basic social choice desiderata such as monotonicity and homogeneity. However, this does not preclude the existence of approximation algorithms for Dodgson that are monotonic or homogeneous, and indeed it is natural to ask whether such algorithms exist. In this thesis we give definitive answers to these questions. We design a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(logm)-approximation algorithm (where m is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation on a known voting rule yields a monotonic, homogeneous, polynomial-time O(m logm)-approximation algorithm, and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity.
We complete the picture by studying several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist.
In this thesis we consider also the important computational problem of bribery in elections, where the winning candidate is computed using a scoring voting rule. In the bribery problem we have an external agent who wants to change the preferences of some voters to make his favorite candidate win the election given a budget. In this thesis we consider scoring voting rules where the voter gives to the first candidate κ points, λ points to his second most preferred candidate and zero points to all other candidates. We prove that for this class of rules bribery is a computationally hard problem. The class of scoring voting rules includes plurality and 2-approval for which an optimal bribing strategy can be computed efficiently as well as 3-approval which is hard to bribe. Concluding we derive that the class of rules we consider is one of the most simple scoring voting rules that are resistant to bribery.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/7999 |
| Date | 15 September 2014 |
| Creators | Καρανικόλας, Νικόλαος |
| Contributors | Κακλαμάνης, Χρήστος, Karanikolas, Nikolaos, Σπυράκης, Παύλος, Καραγιάννης, Ιωάννης, Βαρβαρίγος, Εμμανουήλ, Γαλλόπουλος, Ευστράτιος, Κοσμαδάκης, Σταύρος, Νικολετσέας, Σωτήρης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0044 seconds