Complexity of strategic influences in elections and group identification with a main focus on incomplete information

Abstract

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.

Gewöhnlich besteht eine Wahl aus einer Kandidatenmenge sowie einer Wählermenge, wobei jeder Wähler alle Kandidaten vom ersten bis zum letzten Rang einreiht. Abhängig von den Rankings der Wähler bestimmt eine Wahlregel den oder die Gewinner der Wahl. Neben der Gewinnerbestimmung gibt es weitere Probleme bezüglich Wahlen, welche traditionell als Entscheidungsprobleme formuliert werden. Im Bestechungsproblem stellt sich beispielsweise die Frage, ob ein externer Agent einen Kandidaten zum Gewinner der Wahl machen kann, wenn höchstens eine gewisse Anzahl an Wählerstimmen geändert wird.

In dieser Arbeit verallgemeinern wir die Annahme vollständiger Information und betrachten insgesamt neun verschiedene Modelle partieller Information (manche dieser Modelle sind schon bekannt). Wir untersuchen die Komplexität für die Probleme Necessary Winner, Possible Winner, Necessary Bribery und Possible Bribery für die Wahlregeln k-Approval und k-Veto.

Wir betrachten außerdem ein weiteres Modell unvollständiger Information. Im Gegensatz zu den vorher genannten Modellen basiert lotteriebasiertes Wählen auf der Annahme, dass die Wählerstimmen zwar als vollständige Rankings gegeben sind, aber ein Lotterie eine Wählerteilmenge fester vorgegebener Größe zufällig auslost, auf welche anschließend eine Wahlregel angewandt wird. Erneut untersuchen wir unter anderem die Komplexität für Varianten der Probleme Necessary und Possible Winner sowie Necessary und Possible Bribery. Überdies betrachten wir ein Zählproblem, bei dem sich die Frage stellt, auf wie viele verschiedene Möglichkeiten die Lotterie eine feste Anzahl an Wählern auslosen kann, so dass ein designierter Kandidat ein Wahlgewinner ist.

Ferner betrachten wir zwei häufig in der Praxis verwendete Wahlregeln, Pluralität und Veto jeweils mit Stichwahl. Wir erforschen die Komplexität von Bestechung sowie mehrerer Kontrollprobleme wie Kontrolle durch Hinzufügen, Löschen und Ersetzen von Kandidaten und/oder Wählern. Für sämtliche Probleme nehmen wir an, dass volle Information vorliegt.

Schließlich widmen wir uns der Gruppenidentifikation. Wir bestimmen einerseits die Komplexität für Gruppenbestechung sowie drei verschiedene Arten destruktiver Gruppenkontrolle. Andererseits betrachten wir Gruppenidentifikation unter partieller Information und untersuchen insbesondere die Probleme Possibly Qualified Individuals und Necessarily Qualified Individuals sowie Varianten dieser Probleme, bei denen jedes Individuum genau k Individuen qualifizieren muss.