Η ψηφοφορία είναι ένας δημοφιλής τρόπος για κατανεμημένη λήψη αποφάσεων και παραδοσιακά είναι το αντικείμενο της θεωρίας κοινωνικής επιλογής έχοντας ως κεντρικό πρόβλημα το πως θα φτάσουμε ομόφωνα σε μια κοινωνικά καλή απόφαση έχοντας ως δεδομένο τις προτιμήσεις των ψηφοφόρων πάνω σε ένα σύνολο από υποψηφίους. Πολλά συστήματα ψηφοφορίας έχουν εμφανιστεί στη σχετική βιβλιογραφία από τότε που οι Borda και Marquis de Condorcet πρότειναν στα τέλη του 18ου αιώνα τα πρώτα συστήματα. Ενώ οι περισσότερες από τις σχετικές έρευνες εστιάζουν στις ιδιότητες των συστημάτων ψηφοφορίας για κυβερνητικές εκλογές ή λήψη αποφάσεων σε επιτροπές, η εμφάνιση εφαρμογών μεγάλης κλίμακας για εξόρυξη πληροφορίας, κατάταξη, και ανάκτηση έχει βάλει την ψηφοφορία στην ημερήσια διάταξη της έρευνας της επιστήμης των υπολογιστών. Όντως, προβλήματα σαν την κατάταξη συνόλων μπορούν να θεωρηθούν ως προβλήματα εκλογών. Στα προβλήματα κατάταξης συνόλων, δίδεται ένα σύνολο από διαφορετικές κατατάξεις (π.χ. τα αποτελέσματα από διαφορετικές μηχανές αναζήτησης ιστοσελίδων σε ένα συγκεκριμένο ερώτημα) για το ίδιο σύνολο δεδομένων (π.χ. ιστοσελίδες σχετικές με το ερώτημα), και ο σκοπός είναι να επιλεγεί μια μοναδική κατάταξη που είναι κοντά σε όλες τις κατατάξεις σύμφωνα με ένα καλώς ορισμένο κριτήριο. Σε αυτό το παράδειγμα, οι διαφορετικές μηχανές αναζήτησης είναι οι ψηφοφόροι και κάθε σελίδα αντιστοιχεί σε ένα υποψήφιο, και ο σκοπός σύμφωνα με το οποίον υπολογίζεται η μοναδική κατάταξη είναι ο κανόνας ψηφοφορίας. Είναι φανερό ότι σε τέτοιες εφαρμογές η απόφαση για το ποιος είναι ο νικητής των εκλογών δεν είναι το μόνο πρόβλημα, συνήθως απαιτείται η πλήρης κατάταξη των υποψηφίων. Στην εργασία αυτή γίνεται αρχικά μια προσπάθεια καταγραφής των κυριότερων συστημάτων κοινωνικής επιλογής. Κατά κύριο λόγο εστιάζουμε στη μέθοδο που πρότεινε ο Dodgson και ακολούθως στην μέθοδο του Young. Αυτοί οι κανόνες ψηφοφορίας έχουν σχεδιαστεί για να βρίσκουν τον υποψήφιο που είναι πιο κοντά στο νικητή κατά Condorcet. Το σκορ ενός δεδομένου υποψηφίου είναι γνωστό ότι είναι δύσκολο να υπολογιστεί και για τους δυο κανόνες. Σε αυτήν την εργασία, προτείνουμε για την μέθοδο του Dodgson δυο προσεγγιστικούς αλγόριθμους. Πιο συγκεκριμένα παρουσιάστηκαν και αναλύθηκαν δυο προσεγγιστικοί αλγόριθμοι υπολογισμού του Dodgson σκορ ενός υποψηφίου σε μία εκλογή Dodgson με N υποψηφίους, ένας άπληστος ντετερμινιστικός και ένας πιθανοτικός. Και οι δυο αλγόριθμοι έχουν λόγο προσέγγισης Ο (log N). Επίσης αποδεικνύουμε ότι ο άπληστος αλγόριθμος είναι βέλτιστος μέχρι ένα παράγοντα της τάξης του 2 εκτός αν όλα τα προβλήματα που ανήκουν στο ΝΡ έχουν υπο-εκθετικού (quasi-polynomial) χρόνου αλγορίθμους. Παρόλο που ο άπληστος αλγόριθμος είναι υπολογιστικά ισχυρότερος, ο πιθανοτικός μας αλγόριθμος έχει πλεονέκτημα υπό την οπτική της θεωρίας κοινωνικής επιλογής. Ακόμη, δείχνουμε ότι ο υπολογισμός οποιασδήποτε ικανοποιητικής προσέγγισης που παράγεται από τον κανόνα του Dodgson είναι υπολογιστικά δύσκολη. Αυτό παρέχει μια θεωρητική εξήγηση από σκοπιά υπολογιστικής πολυπλοκότητας για τις μεγάλες διαφορές που έχουν παρατηρηθεί στην θεωρία κοινωνικής επιλογής όταν συγκρίνονται οι εκλογές Dodgson με απλούστερους κανόνες ψηφοφορίας. Τέλος δείχνουμε ότι το πρόβλημα υπολογισμού του Young σκορ είναι ΝΡ-δύσκολο να προσεγγιστεί υπό οποιονδήποτε παράγοντα. Τα κυριότερα αποτελέσματα που εκπονήθηκαν σε αυτήν την εργασία παρουσιάστηκαν στο συνέδριο ACM-SIAM Symposium on Discrete Algorithms (SODA09). / Voting is a popular way for distributed decision making and has traditionally been the subject of Social Choice Theory with the central issue being how to reach consensus on a socially good decision given the preferences of voters on a set of alternatives (or candidates). Several voting systems have appeared in the related literature since the first voting systems were proposed by Borda and Marquis de Condorcet at the end of the 18th century. While most of the related studies have focused on properties of voting systems for government elections or decision making in committees, the emergence of large-scale applications for data mining, classification, and retrieval has put voting in the research agenda of Computer Science. Indeed, problems like rank aggregation can be thought of as elections. In rank aggregation, we are given a set of different rankings (e.g., the results from different web search engines on a particular query) over the same set of data (e.g., web pages related to the query), and the objective is to select a single ranking which is close to all rankings according to a well-defined criterion. In this example, the different web search engines are the voters, each web page corresponds to a candidate, and the objective according to which the single ranking is computed is the voting rule. Clearly, in such applications, deciding the winner of the election is not the only issue; usually, the ranking of the candidates is required as a complete answer. In this thesis firstly we familiarize the reader with the main different methods of social choice theory. We focus on two methods, the Dodgson method and the Young one. These two voting rules have been designed in order to find the candidate which is closer to the Condorcet winner, under two different significances of approach. The score of a given candidate is known that is NP-hard to compute for the two voting rules. So we suggest two approximation algorithms for the Dodgson's method. These two approximation algorithms compute the Dodgson score of a given candidate in an election of N candidates. The first one is a greedy deterministic algorithm while the second one is randomized. Both algorithms have approximation ratio of O(logN). While the greedy algorithm is computationally superior in every way, we show that the randomized has the advantage of being monotonic, which is a desirable property from a social choice point of view. We further observe that it follows from the work of McCabe-Dansted that the Dodgson score cannot be approximated within sublogarithmic factors by polynomial-time deterministic algorithms unless P = NP, and by polynomial-time randomized algorithms unless RP = NP. We prove a more explicit inapproximability result of (1-ε) lnm, under the assumption that problems in NP do not have algorithms running in quasi-polynomial time; this implies that the approximation ratio achieved by our greedy algorithm is optimal up to a factor of 2. Some of the results mentioned above establish that there are sharp discrepancies between the Dodgson ranking and the rankings produced by other rank aggregation rules. Some of these rules (e.g., Borda and Copeland) are polynomial-time computable, so the corresponing results can be viewed as negative results regarding the approximability of the Dodgson ranking by polynomial-time algorithms. We show that the problem of distinguishing between whether a given alternative is the unique Dodgson winner or in the last O(√m) positions in any Dodgson ranking is NP-hard. Finally, we found the following result : it is NP-hard to approximate the Young score within any factor. Speciφιcally, we show that it is NP-hard to distinguish between the case where the Young score of a given alternative is 0, and the case where the score is greater than 0. As a corollary we obtain an inapproximability result for the Young ranking. The results of this thesis were presented in ACM-SIAM Symposium on Discrete Algorithms (SODA09).

Στην εργασία αυτή ασχολούμαστε με θέματα κοινωνικής επιλογής και πιο συγκεκριμένα με συμβιβαστικές ψηφοφορίες στις οποίες κάθε ψηφοφόρος ψηφίζει ένα (πιθανόν κενό) σύνολο υποψηφίων και το αποτέλεσμα είναι ένα σύνολο υποψηφίων πλήθους k, για δεδομένο k (π.χ. εκλογή επιτροπής). Εξετάζουμε τον κανόνα minimax σε συμβιβαστικές ψηφοφορίες, στις οποίες το αποτέλεσμα αντιπροσωπεύει ένα συμβιβασμό μεταξύ των προτιμήσεων των ψηφοφόρων, με την έννοια ότι η μέγιστη απόσταση μεταξύ των προτιμήσεων οποιουδήποτε ψηφοφόρου και του αποτελέσματος είναι όσο το δυνατό μικρότερη. Αυτός ο κανόνας έχει δύο μειονεκτήματα. Πρώτον, ο υπολογισμός του αποτελέσματος που ελαχιστοποιεί τη μέγιστη απόσταση από κάθε ψηφοφόρο είναι ένα υπολογιστικά δύσκολο πρόβλημα και δεύτερον, οποιοσδήποτε αλγόριθμος που πάντα επιστρέφει ένα τέτοιο αποτέλεσμα, δίνει στους ψηφοφόρους κίνητρο να πουν ψέματα για την πραγματική τους προτίμηση, με σκοπό να βελτιώσουν την απόσταση τους από το τελικό αποτέλεσμα. Για να ξεπεράσουμε αυτά τα μειονεκτήματα χρησιμοποιούμε προσεγγιστικούς αλγορίθμους, δηλαδή αλγορίθμους που παράγουν αποτέλεσμα που αποδεδειγμένα προσεγγίζει την minimax απόσταση για κάθε δοσμένο στιγμιότυπο. Τέτοιοι αλγόριθμοι μπορούν να χρησιμοποιηθούν σαν εναλλακτικοί κανόνες ψηφοφορίας. Παρουσιάζουμε ένα 2-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, ο οποίος υπολογίζει το αποτέλεσμα στρογγυλοποιώντας ντετερμινιστικά τη λύση του χαλαρωμένου γραμμικού προγράμματος μέσω του οποίου εκφράζουμε το πρόβλημά μας. Ο καλύτερος προηγούμενος προσεγγιστικός αλγόριθμος επιτύγχανε λόγο απόδοσης 3 και συνεπώς το παραπάνω αποτέλεσμα αποτελεί σημαντική βελτίωση. Επιπλέον ασχολούμαστε με προσεγγιστικούς αλγορίθμους που είναι ανθεκτικοί σε χειραγώγηση είτε από μεμονωμένους ψηφοφόρους είτε από ομάδες ψηφοφόρων. Τέτοιοι αλγόριθμοι δεν προσφέρουν κίνητρο στους ψηφοφόρους να δηλώσουν ψευδώς τις προτιμήσεις τους με σκοπό να βελτιώσουν την απόστασή τους από το τελικό αποτέλεσμα. Μια τέτοια μελέτη εντάσσεται στα πλαίσια της έρευνας που γίνεται τα τελευταία χρόνια πάνω στο σχεδιασμό προσεγγιστικών αλγοριθμικών μηχανισμών χωρίς χρήματα. Συμπληρώνουμε προηγούμενα αποτελέσματα με νέα πάνω και κάτω φράγματα για strategyproof και group-strategyproof αλγορίθμους. / We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some fixed k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the preferences of the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. This study falls within the recently initiated line of research on approximate mechanism design without money. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.