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

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.

L'objet de cette thèse est l'étude des aspects algorithmiques du vote par approbation. Il s'agit principalement d'une étude théorique des enjeux computationnels soulevés par le vote par approbation dans des contextes de décisions variés. Cependant, j'étudie aussi des questions plus proches de la théorie classique du choix social et je conduis de brèves études expérimentales.Dans un premier temps, l'étude se porte sur une famille générale de règles de vote pour les élections de comités et les référendums multiples à l'aide du vote par approbation. Dans un second temps, je porte mon attention sur un contexte plus général, le vote par approbation sur domaines combinatoires en se basant sur des préférences conditionnelles. Finalement, je me place dans le cadre du vote avec préférences incomplètes pour étudier les problèmes de vainqueurs possibles et nécessaires dans le vote par approbation. / The subject of this thesis is the study of computational aspects of approval voting. Most of the works are theoretical results about computational issues raised by approval voting, in many different settings. However, I also study some questions that are more related to classical choice theory, and some problems are investigated through experimental analysis.Firstly, I study a general family of rules for approval voting in the context of committee elections and multiple referenda. Secondly, I focus on a more general setting, approval voting in combinatorial domains, based on conditional preferences. Finally, I consider approval voting in the context of incomplete preferences, to study the possible and necessary winner problems.