Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες
Στην εργασία αυτή ασχολούμαστε με θέματα κοινωνικής επιλογής και πιο συγκεκριμένα με συμβιβαστικές ψηφοφορίες στις οποίες κάθε ψηφοφόρος ψηφίζει ένα (πιθανόν κενό) σύνολο υποψηφίων και το αποτέλεσμα είναι ένα σύνολο υποψηφίων πλήθους k, για δεδομένο k (π.χ. εκλογή επιτροπής). Εξετάζουμε τον κανόν...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2011
|
| Θέματα: | |
| Διαθέσιμο Online: | http://nemertes.lis.upatras.gr/jspui/handle/10889/4063 |
| id |
nemertes-10889-4063 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Συμβιβαστικές ψηφοφορίες Προσεγγιστικοί αλγόριθμοι Ανθεκτικότητα σε χειραγώγηση Κανόνες ψηφοφορίας Approval voting Approximation algorithms Strategy proofness Voting rules 324.650 285 |
| spellingShingle |
Συμβιβαστικές ψηφοφορίες Προσεγγιστικοί αλγόριθμοι Ανθεκτικότητα σε χειραγώγηση Κανόνες ψηφοφορίας Approval voting Approximation algorithms Strategy proofness Voting rules 324.650 285 Καλαϊτζής, Δημήτριος Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| description |
Στην εργασία αυτή ασχολούμαστε με θέματα κοινωνικής επιλογής και πιο συγκεκριμένα με συμβιβαστικές ψηφοφορίες στις οποίες κάθε ψηφοφόρος ψηφίζει ένα (πιθανόν κενό) σύνολο υποψηφίων και το αποτέλεσμα είναι ένα σύνολο υποψηφίων πλήθους k, για δεδομένο k (π.χ. εκλογή επιτροπής). Εξετάζουμε τον κανόνα minimax σε συμβιβαστικές ψηφοφορίες, στις οποίες το αποτέλεσμα αντιπροσωπεύει ένα συμβιβασμό μεταξύ των προτιμήσεων των ψηφοφόρων, με την έννοια ότι η μέγιστη απόσταση μεταξύ των προτιμήσεων οποιουδήποτε ψηφοφόρου και του αποτελέσματος είναι όσο το δυνατό μικρότερη. Αυτός ο κανόνας έχει δύο μειονεκτήματα. Πρώτον, ο υπολογισμός του αποτελέσματος που ελαχιστοποιεί τη μέγιστη απόσταση από κάθε ψηφοφόρο είναι ένα υπολογιστικά δύσκολο πρόβλημα και δεύτερον, οποιοσδήποτε αλγόριθμος που πάντα επιστρέφει ένα τέτοιο αποτέλεσμα, δίνει στους ψηφοφόρους κίνητρο να πουν ψέματα για την πραγματική τους προτίμηση, με σκοπό να βελτιώσουν την απόσταση τους από το τελικό αποτέλεσμα.
Για να ξεπεράσουμε αυτά τα μειονεκτήματα χρησιμοποιούμε προσεγγιστικούς αλγορίθμους, δηλαδή αλγορίθμους που παράγουν αποτέλεσμα που αποδεδειγμένα προσεγγίζει την minimax απόσταση για κάθε δοσμένο στιγμιότυπο. Τέτοιοι αλγόριθμοι μπορούν να χρησιμοποιηθούν σαν εναλλακτικοί κανόνες ψηφοφορίας. Παρουσιάζουμε ένα 2-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, ο οποίος υπολογίζει το αποτέλεσμα στρογγυλοποιώντας ντετερμινιστικά τη λύση του χαλαρωμένου γραμμικού προγράμματος μέσω του οποίου εκφράζουμε το πρόβλημά μας. Ο καλύτερος προηγούμενος προσεγγιστικός αλγόριθμος επιτύγχανε λόγο απόδοσης 3 και συνεπώς το παραπάνω αποτέλεσμα αποτελεί σημαντική βελτίωση. Επιπλέον ασχολούμαστε με προσεγγιστικούς αλγορίθμους που είναι ανθεκτικοί σε χειραγώγηση είτε από μεμονωμένους ψηφοφόρους είτε από ομάδες ψηφοφόρων. Τέτοιοι αλγόριθμοι δεν προσφέρουν κίνητρο στους ψηφοφόρους να δηλώσουν ψευδώς τις προτιμήσεις τους με σκοπό να βελτιώσουν την απόστασή τους από το τελικό αποτέλεσμα. Μια τέτοια μελέτη εντάσσεται στα πλαίσια της έρευνας που γίνεται τα τελευταία χρόνια πάνω στο σχεδιασμό προσεγγιστικών αλγοριθμικών μηχανισμών χωρίς χρήματα. Συμπληρώνουμε προηγούμενα αποτελέσματα με νέα πάνω και κάτω φράγματα για strategyproof και group-strategyproof αλγορίθμους. |
| author2 |
Κακλαμάνης, Χρήστος |
| author_facet |
Κακλαμάνης, Χρήστος Καλαϊτζής, Δημήτριος |
| format |
Thesis |
| author |
Καλαϊτζής, Δημήτριος |
| author_sort |
Καλαϊτζής, Δημήτριος |
| title |
Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| title_short |
Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| title_full |
Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| title_fullStr |
Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| title_full_unstemmed |
Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| title_sort |
υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες |
| publishDate |
2011 |
| url |
http://nemertes.lis.upatras.gr/jspui/handle/10889/4063 |
| work_keys_str_mv |
AT kalaïtzēsdēmētrios ypologistikazētēmatasesymbibastikespsēphophories AT kalaïtzēsdēmētrios approximationalgorithmsandmechanismdesignforminimaxapprovalvoting |
| _version_ |
1771297238452011008 |
| spelling |
nemertes-10889-40632022-09-05T14:07:07Z Υπολογιστικά ζητήματα σε συμβιβαστικές ψηφοφορίες Approximation algorithms and mechanism design for minimax approval voting Καλαϊτζής, Δημήτριος Κακλαμάνης, Χρήστος Χρήστος, Κακλαμάνης Σπυράκης, Παύλος Καραγιάννης, Ιωάννης Kalaitzis, Dimitrios Συμβιβαστικές ψηφοφορίες Προσεγγιστικοί αλγόριθμοι Ανθεκτικότητα σε χειραγώγηση Κανόνες ψηφοφορίας Approval voting Approximation algorithms Strategy proofness Voting rules 324.650 285 Στην εργασία αυτή ασχολούμαστε με θέματα κοινωνικής επιλογής και πιο συγκεκριμένα με συμβιβαστικές ψηφοφορίες στις οποίες κάθε ψηφοφόρος ψηφίζει ένα (πιθανόν κενό) σύνολο υποψηφίων και το αποτέλεσμα είναι ένα σύνολο υποψηφίων πλήθους 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. 2011-01-11T07:34:40Z 2011-01-11T07:34:40Z 2010-10-12 2011-01-11T07:34:40Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/4063 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
