The main objective of computational social choice is to improve the understanding of social choice mechanisms and of algorithmic decision making. A large part of the literature analyses scenarios where a group of voters has clear opinions on a group of candidates that are used by every voter to rank all candidates in a linear order. Typical questions then concern the control of voters, the mutual influence of voters and the bribing of voters under various voting protocols, with the goal of making some preferred candidate win the election or with the goal of making some unwanted candidate lose the election. Popular voting protocols are e.g., approval voting, Borda count, plurality voting, and run-off voting. The computational social choice community has developed a number of general techniques to approach such questions.

The aim of this dissertation project is to investigate these classical questions of voter control under uncertain preferences, where the decision maker only has partial information on the voter’s preferences. For example, a voter can only order the candidates partially (as he/she did not spend much time on comparing and ranking his/her less preferred candidates). A natural case is formed by so-called linear orders with ties, where the voter only ranks subsets of tied candidates and is indifferent between any pair of candidates in the same subset. Another example arises if the decision maker knows that the voter’s preferences come from a small (voter-dependent) set of linear orders. This project aims to systematically study the algorithmic problems with voting under uncertain preferences. Its goals are to determine their computational complexity, analyse their approximate behavior, and investigate their parametrised complexity under appropriate parametrisations of the underlying instance space.

Another class of challenging research questions arises from probabilistic information on the uncertain preferences of a voter. For instance, the decision maker might know the probability distribution over some small (voter-dependent) set of linear orders. Or: all linear extensions of some given partial order could be equally likely. Or: the probabilistic information on various voters could be dependent on each other. In such situations, even very simple questions (like: Who is the most likely candidate to win the election under a given voting protocol? Who is the least likely candidate to win? What is the probability that candidate x will win the election? What is the probability that candidate x will beat candidate y?) become quite nontrivial from a computational point of view. This dissertation project aims to understand which of the resulting algorithmic problems are #P-hard, and to find approximation algorithms and fully polynomial randomised approximation schemes for the hard variants.