Traditionally, an election consists of a candidate set and a voter set, and each voter completely ranks all candidates from first to last. Depending on the voters’ rankings, a voting rule determines the winner or the winners of the election. Apart from winner determination, there are further problems related to voting which are usually formulated as decision problems. For instance, in bribery we ask whether an external agent can make a candidate a winner of the given election by changing at most a certain number of voters’ votes.
In this thesis, we generalize the assumption of complete information and regard nine different partial information models in total (some of them are already known). We study the complexity of the problems necessary winner, possible winner, necessary bribery, and possible bribery in the voting rules k-Approval and k-Veto.
Moreover, we consider another model of incomplete information. In contrast to the models previously mentioned, lottery-based voting is based on the assumption that the votes are given as complete rankings, but a lottery draws at random a voter subset of fixed and predetermined size to which a voting rule is applied afterward. Once more, we investigate the complexity for variants of necessary and possible winner as well as necessary and possible bribery. Besides, we consider a counting problem asking how many subelections of a certain size exist such that a designated candidate wins the election.
We further regard two voting rules frequently used in practice — Plurality with Runoff and Veto with Runoff. We explore the complexity of bribery and several control problems such as control by adding, deleting, and replacing candidates and/or voters. For several problems, we assume that there is full information.
Last but not least, we attend to group identification. On the one hand, we determine the complexity for group bribery as well as three different destructive group control variants in group identification. On the other hand, we consider partial information in group identification and, in particular, we study the problems possibly qualified individuals and necessarily qualified individuals as well as variations of these problems where each individual must qualify exactly k individuals.