Exploiting structure in computationally hard voting problems

This thesis explores and exploits structure inherent in voting problems. Some of these structures are found in the preferences of the voters, such as the domain restrictions which have been widely studied in social choice theory [ASS02, ASS10]. Others can be expressed as quantifiable measures (or parameters) of the input, which make them accessible to a parameterized complexity analysis [Cyg+15, DF13, FG06, Nie06]. Accordingly, the thesis deals with two major topics. The first topic revolves around preference structures, e.g. single-crossing or one-dimensional Euclidean structures. It is covered in Chapters 3 to 5. The second topic includes the parameterized complexity analysis of two computationally hard voting problems, making use of some of the structural properties studied in the first part of the thesis. It also investigates questions on the computational complexity, both classical and parameterized, of several voting problems for two widely used parliamentary voting rules. It is covered in Chapters 6 to 8. In Chapter 3, we study the single-crossing property which describes a natural order of the voters such that for each pair of alternatives, there are at most two consecutive voters along this order which differ in their relative ordering of the two alternatives. We find finitely many forbidden subprofiles whose absence from a profile is necessary and sufficient for the existence of single-crossingness. Using this result, we can detect single-crossingness without probing every possible order of the voters. We also present an algorithm for the detection of single-crossingness in O(nm2) time via PQ trees [BL76], where n denotes the number of voters and m the number of alternatives. In Chapter 4, we study the one-dimensional Euclidean property which describes an embedding of the alternatives and voters into the real numbers such that every voter prefers alternatives that are embedded closer to him to those which are embedded farther away. We show that, contrary to our results for the single-crossing property, finitely many forbidden subprofiles are not sufficient to characterize the one-dimensional Euclidean property. In Chapter 5, we study the computational question of achieving a certain property, as for instance single-crossingness, by deleting the fewest number of either alternatives or voters. We show that while achieving single-crossingness by deleting the fewest number of voters can be done in polynomial time, it is NP-hard to achieve this if we delete alternatives instead. Both problem variants are NP-hard for the remaining popular properties, such as single-crossingness or value-restriction. All these problems are trivially fixed-parameter tractable for the parameter "number of alternatives to delete" (resp. "number of voters to delete") because for each studied property there are finitely many forbidden subprofiles whose removal makes a profile possess this property. In Chapter 6, we introduce a combinatorial variant of CONTROL BY ADDING VOTERS. In CONTROL BY ADDING VOTERS as introduced by Bartholdi III, Tovey, and Trick [BTT92], there is a set of unregistered voters (with known preference orders), and the goal is to add the fewest number of unregistered voters to a given profile such that a specific alternative wins. In our new model, we additionally assume that adding a voter means also adding a bundle (that is, a subset) of other voters for free. We focus on two prominent voting rules, the plurality rule and the Condorcet rule. Our problem turns out to be extremely hard; it is NP-hard for even two alternatives. We identify different parameters arising from the combinatorial model and obtain an almost complete picture of the parameterized complexity landscape. For the case where the bundles of voters have a certain structure, our problem remains hard for single-peaked preferences, while it is polynomial-time solvable for single-crossing preferences. In Chapter 7, we investigate how different natural parameters and price function families influence the computational complexity of SHIFT BRIBERY [EFS09], which asks whether it is possible to make a specific alternative win by shifting it higher in the preference orders of some voters. Each shift has a price, and the goal is not to exceed the budget. We obtain both fixed-parameter tractability and parameterized intractability results. We also study the optimization variant of SHIFT BRIBERY which seeks to minimize the budget spent, and present an approximation algorithm which approximates the budget within a factor of (1 + epsilon) and has a running time whose super-polynomial part depends only on the approximation parameter epsilon and the parameter "number of voters". In Chapter 8, we turn our focus to two prominent parliamentary voting rules, the successive rule and the amendment rule. Both rules proceed according to a linear order of the alternatives, called the agenda. We investigate MANIPULATION (which asks to add the fewest number of voters with arbitrary preference orders to make a specific alternative win), AGENDA CONTROL (which asks to design an appropriate agenda for a specific alternative to win), and POSSIBLE/NECESSARY WINNER (which asks whether a specific alternative wins in a/every completion of the profile and the agenda). We show that while MANIPULATION and AGENDA CONTROL are polynomial-time solvable for both rules, our real-world experimental results indicate that most profiles cannot be manipulated by only few voters, and that a successful agenda control is typically impossible. POSSIBLE WINNER is NP-hard for both rules. While NECESSARY WINNER is coNP-hard for the amendment rule, it is polynomial-time solvable for the successive rule. All considered computationally hard voting problems are fixed-parameter tractable for the parameter "number of alternatives".
 
Die vorliegende Arbeit beschäftigt sich mit Wahlproblemen und den darin auftretenden Strukturen. Einige dieser Strukturen finden sich in den Wählerpräferenzen,wie zum Beispiel die in der Sozialwahltheorie (engl. social choice theory) intensiv erforschten domain restrictions [ASS02, ASS10], wo die Wählerpräferenzen eine bestimmte eingeschränkte Struktur haben. Andere Strukturen lassen sich wiederum mittels Problemparametern quantitativ ausdrücken, was sie einer parametrisierten Komplexitätsanalyse zugänglich macht [Cyg+15, DF13, FG06, Nie06]. Dieser Zweiteilung folgend ist die Arbeit in zwei Themengebiete untergliedert. Das erste Gebiet beinhaltet Betrachtungen zu Strukturen in Wählerpräferenzen, wie z. B. Single-Crossing-Strukturen oder eindimensionale euklidische Strukturen. Es wird in den Kapiteln 3 bis 5 abgehandelt. Das zweite Themengebiet umfasst die parametrisierte Komplexitätsanalyse zweier NP-schwerer Wahlprobleme, wobei die neu gewonnenen Erkenntnisse zu den im ersten Teil der Arbeit untersuchten Strukturen verwendet werden. Es beschäftigt sich außerdem mit Fragen sowohl zur klassischen als auch zur parametrisierten Komplexität mehrerer Wahlprobleme für zwei in der Praxis weit verbreitete parlamentarische Wahlverfahren. Dieser Teil der Arbeit erstreckt sich über die Kapitel 6 bis 8. Kapitel 3 untersucht die Single-Crossing-Eigenschaft. Diese beschreibt eine Anordnung der Wähler, bei der es für jedes Paar von Alternativen höchstens zwei aufeinanderfolgende Wähler gibt, die unterschiedlicher Meinung über die Reihenfolge dieser beiden Alternativen sind. Wie sich herausstellt, lässt sich diese Eigenschaft durch eine endliche Anzahl von verbotenen Strukturen charakterisieren. Ein Wählerprofil ist genau dann single-crossing, wenn es keine dieser Strukturen beinhaltet. Es wird außerdem ein Algorithmus vorgestellt, der die Single-Crossing-Eigenschaft unter Verwendung von PQ trees [BL76] in O(nm2) Schritten erkennt, wobei n die Anzahl der Wähler und m die Anzahl der Alternativen ist. Kapitel 4 behandelt Wählerprofile, die eindimensional-euklidisch sind, d.h. für die sich die Alternativen und Wähler so auf die reelle Achse abbilden lassen, dass für jeden Wähler und je zwei Alternativen diejenige näher zum Wähler abgebildet wird, die er der anderen vorzieht. Es stellt sich heraus, dass es im Gegensatz zur Single-Crossing-Eigenschaft nicht möglich ist, eindimensionale euklidische Profile durch endlich viele verbotene Strukturen zu charakterisieren. Kapitel 5 beschäftigt sich mit der Frage, wie berechnungsschwer es ist, eine bestimmte strukturelle Eigenschaft wie z.B. die Single-Crossing-Eigenschaft zu erreichen, indem man eine möglichst kleine Anzahl von Wählern oder Kandidaten aus einem Profil entfernt. Es zeigt sich, dass dieses Problem für die Single-Crossing-Eigenschaft durch das Löschen von Wählern zwar in polynomieller Zeit gelöst werden kann, es durch das Löschen von Kandidaten jedoch NP-schwer ist. Für alle anderen Eigenschaften sind beide Löschensvarianten ebenfalls NP-schwer. Allerdings lässt sich für jedes der Probleme auf triviale Weise mittels des Parameters "Anzahl der zu löschenden Wähler bzw. Alternativen" fixed-parameter tractability zeigen. Das bedeutet, dass sie effizient lösbar sind, wenn der Parameter klein ist. Der Grund dafür ist, dass sich alle hier betrachteten Eigenschaften durch eine endliche Anzahl verbotener Strukturen charakterisieren lassen, deren Zerstörung die gewünschte Eigenschaft herstellt. Kapitel 6 führt die kombinatorische Variante des bekannten Problems CONTROL BY ADDING VOTERS ein, das erstmals durch Bartholdi III, Tovey und Trick [BTT92] beschrieben wurde. In der klassischen Problemstellung gibt es eine Menge von nichtregistrierten Wählern mit bekannten Präferenzen, und es wird eine kleinste Teilmenge von nichtregistrierten Wählern gesucht, sodass deren Hinzufügen zu einem gegebenen Profil einen bestimmten Kandidaten zum Gewinner macht. In der hier beschriebenen Variante wird zusätzlich angenommen, dass für jeden hinzugefügten Wähler auch eine Menge von weiteren Wählern "kostenlos" hinzugefügt werden kann. Dieses Problem wird für die beiden bekannten Wahlregeln Condorcet-Wahl und Mehrheitswahl untersucht. Wie sich herausstellt, ist die Problemstellung schon für zwei Alternativen NP-schwer. Desweiteren werden Parameter identifiziert, die sich aus den kombinatorischen Eigenschaften dieses Problems ergeben. Für diese lässt sich eine beinahe erschöpfende Beschreibung der parametrisierten Komplexität des Problems erstellen. In einem Fall, bleibt unser Problem für sogenannte Single-Peaked-Präferenzen berechnungsschwer, während es für Single-Crossing-Präferenzen in polynomieller Zeit lösbar ist. Kapitel 7 untersucht, wie verschiedene natürliche Parameter und Preisfunktionen die Berechnungskomplexität des SHIFT BRIBERY-Problems [EFS09] beeiniv flussen. Darin fragt man, ob eine gegebene Alternative zum Gewinner gemacht werden kann, indem sie in den Präferenzen einiger Wähler nach vorne verschoben wird. Jede Verschiebung hat einen Preis, und das Ziel ist es, ein gegegebenes Budget nicht zu überschreiten. Die Ergebnisse sind gemischt: einige Parameter erlauben effiziente Algorithmen, während für andere das Problem schwer bleibt, z.B. für den Parameter "Anzahl der beeinflussten Wähler" ist das Problem sogar W[2]-schwer. Für die Optimierungsvariante von SHIFT BRIBERY, bei der das verwendete Budget minimiert wird, erzielen wir einen Approximationsalgorithmus mit einem Approximationsfaktor von (1 + epsilon), dessen Laufzeit in ihrem nicht-polynomiellen Anteil nur von epsilon und der Anzahl der Wähler abhängt. Kapitel 8 konzentriert sich auf zwei weitverbreitete parlamentarische Wahlregeln: die successive rule und die amendment rule. Beide Regeln verwenden eine lineare Ordnung der Alternativen, auch Agenda genannt. Es werden drei Probleme untersucht: MANIPULATION fragt nach der kleinstmöglichen Anzahl von Wählern mit beliebigen Präferenzen, deren Hinzufügung einen bestimmten Kandidaten zum Gewinner macht; AGENDA CONTROL fragt, ob es möglich ist, eine Agenda derart festzulegen, dass ein bestimmter Kandidat gewinnt; POSSIBLE/NECESSARY WINNER fragt für unvollständige Wählerpräferenzen und/oder eine nur teilweise festgelegte Agenda, ob eine bestimmte Alternative überhaupt bzw. sicher zum Sieger machen kann. Es stellt sich heraus, dass sowohl MANIPULATION als auch AGENDA CONTROL für beide Wahlregeln in polynomieller Zeit lösbar sind. Allerdings deuten die Ergebnisse einer auf realem Wählerverhalten basierenden, experimentellen Studie darauf hin, dass die meisten Profile nicht durch einige wenige Wähler manipuliert werden können, und dass eine erfolgreiche Kontrolle mittels Agenda typischerweise nicht möglich ist. POSSIBLE WINNER ist für beide Regeln NP-schwer, während NECESSARY WINNER für die amendment rule coNP-schwer und für die successive rule in polynomieller Zeit lösbar ist. Alle betrachtete NP-schwere oder coNP-schwere Wahlprobleme sind "fixed-parameter tractable" für den Parameter "Anzahl der Alternativen".