Dokument: Computational Complexity in Three Areas of Computational Social Choice: Possible Winners, Unidirectional Covering Sets, and Judgment Aggregation

Titel:Computational Complexity in Three Areas of Computational Social Choice: Possible Winners, Unidirectional Covering Sets, and Judgment Aggregation
URL für Lesezeichen:https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=22970
URN (NBN):urn:nbn:de:hbz:061-20121030-092538-0
Kollektion:Dissertationen
Sprache:Englisch
Dokumententyp:Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:Text
Autor: Baumeister, Dorothea [Autor]
Dateien:
[Dateien anzeigen]Adobe PDF
[Details]1,33 MB in einer Datei
[ZIP-Datei erzeugen]
Dateien vom 24.10.2012 / geändert 24.10.2012
Beitragende:Prof. Dr. Rothe, Jörg [Betreuer/Doktorvater]
Prof. Dr. Wanke, Egon [Gutachter]
Prof. Dr. Endriss, Ulle [Gutachter]
Dewey Dezimal-Klassifikation:000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:This thesis studies the computational complexity of different problems from three areas of computational social choice. The first one is voting, and especially the problem of determining whether a distinguished candidate can be a winner in an election with some kind of incomplete information. The second setting is in the broader sense related to the problem of determining winners. Here the computational complexity of problems related to minimal upward and downward covering sets is investigated. The last area is judgment aggregation. In contrast to the problems mentioned above we do not study the complexity of some kind of "winner" problem, but the complexity of three forms of influencing the outcome, namely manipulation, bribery, and control.

All studied problems come from computational social choice, which is a field at the interface between social choice theory and computer science, with a bidirectional transfer between these two disciplines. We focus on the study of the computational complexity of problems coming from social choice theory. One central problem in social choice is that of winner determination in elections. From a computational point of view it is desirable that the winner can be determined in polynomial time. Associated with this problem is the possible winner problem. Here, the question is whether an election, which is in some sense incompletely specified, can be completed such that a distinguished candidate wins the election. In contrast to the winner problem, it is not always desirable that possible winners can be computed in polynomial time, since this may give incentive to some kind of manipulation in the voting process. The first part of the thesis deals with the complexity of different possible winner problems, and establishes results for the classes P and NP.

Also related to the winner problem in voting are solution concepts for dominance graphs as they may result from a pairwise majority relation. A solution concept is a way of identifying the "most desirable" elements of such dominance graphs. In the second part of this thesis, we study the complexity of various problems related to so-called upward and downward covering sets. We show hardness and completeness not only for NP, but also for the complexity classes coNP and Theta_2^p, and we show membership in Sigma_2^p.

The last part of this thesis is concerned with judgment aggregation. Here the task is not to determine a winner, but to aggregate the individual judgment sets over possibly interconnected logical propositions. We study manipulation, bribery, and control in such processes. The manipulation problem asks whether a judge has an incentive to report an untruthful judgment set, in the bribery problem an external actor seeks to change the outcome by bribing some of the judges, and in the control problems the set of participating judges may be changed. Again, this may be undesirable, hence showing NP-hardness can be seen as providing some kind of protection against manipulation, bribery, and control. In addition to classical complexity results, we also study the parameterized complexity
and establish W[2]-hardness for various problems.

Diese Arbeit beschäftigt sich mit der Berechnungskomplexität von verschiedenen Problemen aus drei Bereichen der Computational Social Choice. Der erste Bereich beschäftigt sich mit Wahlen und speziell dem Problem, zu bestimmen, ob ein ausgewählter Kandidat in einer Wahl mit unvollständiger Information ein Gewinner sein kann. Im zweiten Bereich, der im weiteren Sinne mit dem Problem der Gewinnerbestimmung verwandt ist, wird die Berechnungskomplexität von Problemen bezüglich minimal upward und minimal downward covering sets untersucht. Das letzte Gebiet ist Judgment Aggregation. Hier wird nicht die Komplexität einer Art von "Gewinnerproblem" untersucht, sondern die dreier Formen von Beeinflussung, nämlich Manipulation, Bestechung und Kontrolle.

Alle untersuchten Probleme kommen aus der Computational Social Choice, einem Bereich an der Schnittstelle zwischen Social-Choice-Theorie und Informatik, mit einem bidirektionalen Transfer zwischen beiden Disziplinen. Hier liegt der Schwerpunkt auf der Untersuchung der Berechnungskomplexität von Problemen, die aus der Social-Choice-Theorie kommen. Das zentrale Problem der Gewinnerbestimmung in Wahlen ist in der Praxis wünschenswerterweise in Polynomialzeit zu lösen. Bei dem damit in engem Zusammenhang stehenden Possible Winner-Problem stellt sich die Frage, ob eine Wahl, die in einer bestimmten Weise unvollständig angegeben ist, so vervollständigt werden kann, dass ein gewünschter Kandidat gewinnt. Im Gegensatz zur Gewinnerbestimmung ist es meist jedoch nicht erwünscht, dass mögliche Gewinner in Polynomialzeit berechnet werden können, da dies einen Anreiz zur Manipulation des Wahlprozesses geben würde. Der erste Teil dieser Arbeit beschäftigt sich mit der Komplexität von verschiedenen Possible Winner-Problemen und liefert Resultate für die Klassen P und NP.

Ebenso verwandt mit dem Gewinnerproblem sind Lösungskonzepte für Dominanzgraphen, wie sie aus einer paarweisen Mehrheitsrelation resultieren können. Ein Lösungskonzept ist eine Möglichkeit, die "beliebtesten" Elemente eines solchen Dominanzgraphen zu bestimmen. Im zweiten Teil dieser Arbeit wird die Komplexität von verschiedenen Problemen bezüglich sogenannter upward und downward covering sets untersucht. Hierbei wird Härte und Vollständigkeit nicht nur für NP, sondern auch für die Komplexitätsklassen coNP und Theta_2^p, und Zugehörigkeit zu Sigma_2^p gezeigt.

Der letzte Teil dieser Arbeit beschäftigt sich mit Judgment Aggregation. Hier werden individuelle Urteile über möglicherweise miteinander verbundene logische Propositionen aggregiert. In dieser Arbeit werden Manipulation, Bestechung und Kontrolle in solchen Prozessen untersucht. Das Manipulationsproblem fragt, ob ein Richter einen Anreiz hat, ein unaufrichtiges Urteil abzugeben; im Bestechungsproblem versucht eine externe Person das Ergebnis durch Bestechung der Richter abzuändern, und in den Kontrollproblemen wird die Menge der teilnehmenden Richter verändert. Hier kann NP-Härte eine Art Schutz gegen diese unerwünschten Arten von Einflussnahme bieten. Zusätzlich zur klassischen Komplexitätstheorie untersuchen wir hier auch die parametrisierte Komplexität und zeigen W[2]-Härte für verschiedene Probleme.
Fachbereich / Einrichtung:Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology
Dokument erstellt am:30.10.2012
Dateien geändert am:30.10.2012
Promotionsantrag am:10.07.2012
Datum der Promotion:19.09.2012
english
Benutzer
Status: Gast
Aktionen