Στο πλαίσιο της παρούσας διδακτορικής διατριβής μελετώνται υπολογιστικά ζητήματα που προκύπτουν από τη θεωρία της κοινωνικής επιλογής. Ένα από τα κύρια θέματα της θεωρίας αυτής είναι οι εκλογές. Τα προβλήματα που σχετίζονται με τις εκλογές ανήκουν στη θεωρία ψηφοφοριών όπου βασικό πρόβλημα είναι η εύρεση του νικητή των εκλογών όταν έχουμε ως δεδομένες τις προτιμήσεις των ψηφοφόρων. Στη βιβλιογραφία υπάρχουν αρκετοί κανόνες ψηφοφορίας βάσει των οποίων γίνεται ο υπολογισμός της κατάταξης μιας ψηφοφορίας και της ανάδειξης του νικητή. Η θεωρία των ψηφοφοριών αποτελεί ένα σημαντικό κλάδο της θεωρίας της κοινωνικής επιλογής με άμεσες εφαρμογές στην κοινωνία, καθώς οι κανόνες αυτοί εφαρμόζονται στην πράξη σε βουλευτικές, δημοτικές ή τοπικές εκλογές, καθώς επίσης και σε αρκετές επιτροπές σχετικές με την λήψη συλλογικών αποφάσεων. Στη συγκεκριμένη διατριβή μελετούμε πρώτα τους κανόνες ψηφοφορίας που πρότειναν ο 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.

This Master of Arts thesis presents the results of research undertaken on two collections of Egyptian antiquities held at the University of Melbourne. The first collection belongs to Queen’s College and is known as the Dodgson Collection. The second collection, known as the Petrie Collection, forms a small part of the larger Classics and Archaeology Collection, belonging to the Centre for Classics and Archaeology and is housed at the Ian Potter Museum of Art. / Prior to undertaking the research for this thesis little was known of these collections and their origins. Through consultation and analysis of archival sources and published material it was possible reconstruct the genesis and history of these two collections of Egyptian antiquities. / The Dodgson Collection was bequeathed to Queen’s College in 1892 by the Reverend James Dodgson. This much was known, however it was unclear as to how James came to posses the material. My research has uncovered that the collection was created by Aquila Dodgson, brother of James, who lived in England. Aquila was greatly interested in ancient Egypt and became a friend of the English Egyptologist, Flinders Petrie. It was through this friendship that Aquila was able to acquire ancient Egyptian artefacts, some of which now reside in the Dodgson Collection at Queen’s College. / Equally under recognised, very little was known about the second collection, comprising thirty two Egyptian artefacts, commonly referred to as the Petrie Collection. It was assumed the collection had been acquired from Flinders Petrie as a result of a list and a number of handwritten notes found in the Classics and Archaeology Collection archive. My research into the collection and the archive material has discovered that the collection had been created by two brothers, Edward Eustace Miller and Everard Studley Miller. Some items had been acquired whilst on a trip to Egypt during the Australian summer of 1910–1911, although the bulk of the collection was given to Everard (living in Melbourne) by his brother Edward (living in London), who had acquired the material while working for Flinders Petrie in Egypt in 1920. The collection made its way to the University of Melbourne in 1957 after the death of Everard, who had bequeathed the material to the Classical Association of Victoria in 1956. The Association gave the collection to the then Classics Department in early 1957.

L’apport principal de cette thèse réside dans l’évaluation de la vulnérabilité d’un certain nombre de règles de voteà la violation de deux propriétés ; nous nous appuyons pour cela sur l’approche axiomatique de la théorie du choixsocial, qui permet d’étudier le comportement d’un mécanisme de choix social vis-à-vis d’un jugement de valeurémis par l’économiste. La symétrie inverse ("reversal symmetry") est la première propriété examinée. A la suite destravaux de Saari [150], nous évaluons deux catégories de règles de vote en prenant cette propriété comme critèrede décision : d’une part, les règles positionnelles simples et d’autre part les règles positionnelles à deux tours. Plusprécisément, nous calculons la probabilité d’occurrence de ce phénomène à la fois en domaine universel (c’est-à-direlorsque les individus peuvent exprimer n’importe quel ordre de préférence), et en domaine restreint (lorsque deshypothèses supplémentaires sont introduites sur la manière dont les votants classent les « candidats » à l’élection).Nous examinons le cas de trois candidats, de quatre candidats ainsi que le contexte d’élections à un très grandnombre de votants, en faisant tendre ce nombre vers l’infini.La seconde thématique est consacrée à l’examen du comportement de la règle de Dodgson face à la propriété d’homogénéité.Nous proposons une méthode de calcul simple et systématique du score de Dodgson. Nous distinguonsensuite différentes classes de profils pour lesquels cette règle est susceptible d’être vulnérable à cette propriété. Afinde compléter notre recherche, des fréquences de violation de cette propriété par la règle de Dodgson sont fournies. / The contribution of this thesis lies in the evaluation of the vulnerability of a number of voting rules to the violationof two properties of the theory of social choice. We rely on the axiomatic approach of social choice theory to examinethe behavior of a social choice procedure according to a value judgment (or axiom) emitted by the economist.Reversal symmetry is the first property studied. Following the works of Saari [150], we evaluate two families ofvoting by using this property as the decision criterion : the simple scoring rules on the one hand, and the scoringrules with runoff on the other hand. We do probability calculations to evaluate how frequent this phenomenon is,in the three-candidate case under universal domain as well as under a restricted domain, and we also tackle thefour-candidate case and the infinite number of voters case.The second topic is devoted to the study of the Dodgsonrule according to the homogeneity axiom. We introduce a simple and systematic method for the computation ofthe Dodgson score. We distinguish various classes of profiles at which that rule may be vulnerable to this property.Further, frequencies of violation of this property by the Dodgson rule are provided.

An introduction to Alice scholarship, including a brief biography of the author Charles Lutwidge Dodgson, under the pseudonym Lewis Carroll, as well as the subject matter. An examination of Alice's Adventures in Wonderland's genre, as well as an in-depth analysis of the text as a children's story.

This thesis has two aims. The first one is to elucidate how Alice’s Adventures in Wonderland (1865) functions as a Bildungsroman, and the other one is to demonstrate how the novel also has a coming of age aspect based on feminism. Whilst Alice matures in the traditional sense, she also in parallel does so as a stronger female fighting for gender rights with signs of feminism. The feminist angle as well as the surreal world of Wonderland makes the novel a not very obvious Bildungsroman in a genre dominated by male protagonists. For Alice to be a young female child who ends up in a fantasy world thus makes her a very fascinating character. The central hypothesis of this thesis is that what Alice is exposed to and reacts to in Wonderland generally reflects the genre of a Bildungsroman and also specifically a feminist Bildungsroman. Theoretical framework is based on the ideas of Franco Moretti, Mikhail Bakhtin, Thomas Jeffers, Carol Lazzaro-Weis, George Eliot and Elizabeth Drew Stoddard, as well as novels by Eliot and Stoddard. This includes dynamic protagonists, unpredictable development, symbols of modernity, the quest for universality, and minor characters who make sure that the protagonist develops, as well as feminist struggle by means of disregarding the ‘cult of true womanhood’ in a genre and society dominated by men.

No description available.