Dokument: Algorithms and Complexity for Fair Division, Voting, and Peer Reviewing

Titel:	Algorithms and Complexity for Fair Division, Voting, and Peer Reviewing
Weiterer Titel:	Algorithmen und Komplexitätsanalysen für faires Aufteilen, Wahlen und Peer-Review Prozesse
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=28146
URN (NBN):	urn:nbn:de:hbz:061-20140122-153047-8
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Dr. Roos, Magnus [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 712,3 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 22.01.2014 / geändert 22.01.2014
Beitragende:	Prof. Dr. Rothe, Jörg [Betreuer/Doktorvater] Prof. Dr. Mauve, Martin [Gutachter] Prof. Dr. Maudet, Nicolas [Gutachter]
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibungen:	Computational Social Choice ist ein aufstrebendes Gebiet in der Schnittmenge zwischen der Social Choice Theorie und der Informatik und deckt verschiedene Themenbereiche ab. Drei davon werden in dieser Arbeit betrachtet. In Multiagent Resource Allocation ist die Aufgabe, verschiedene unteilbare Güter auf eine Menge von Agenten aufzuteilen, wobei das Ziel ist, einige Fairness- und Social Welfare-Kriterien zu erfüllen. Die allgemeinen Entscheidungsprobleme, die den Problemen, eine Allokation mit maximaler sozialer Wohlfahrt zu finden, zugrunde liegen, sind entweder als NP-vollständig bekannt oder die NP-Vollständigkeit wird in dieser Arbeit bewiesen. Weiterhin wird gezeigt, dass einige exakte Versionen dieser Probleme DP-vollständig sind. Eine Forschungsfrage im Bereich der Wahlsysteme ist das Possible-Winner-Problem. Dieses Problem wird in dieser Arbeit mit gewichteten Wählern und unter drei Arten der Unsicherheit behandelt. Beim Possible-Winner-Problem mit Hinblick auf das Hinzufügen von neuen Kandidaten ist die Frage, ob es möglich ist, einen ausgezeichneten Kandidaten zum Gewinner einer Wahl zu machen, wenn neue Kandidaten nach der Stimmabgabe hinzugefügt werden. Verschiedene NP-Vollständigkeitsbeweise werden für diverse Wahlsysteme gezeigt. Dabei wird sowohl der Fall von uneindeutigen Gewinnern als auch der Fall von eindeutigen Gewinnern betrachtet. Weiterhin wird die Zugehörigkeit zur Klasse P für beide Fälle bewiesen. Eine weitere Variante vom Possible-Winner-Problem ist das Possible-Winner-Problem mit ungewissem Wahlsystem. Bei diesem Problem wird eine Klasse von Wahlsystemen vorgegeben und der Wahlvorstand sucht nach der Stimmabgabe ein bestimmtes Wahlsystem aus dieser Klasse aus. Die Frage ist wieder, ob ein ausgezeichneter Kandidate zum Gewinner der Wahl gemacht werden kann. Dieses Problem wird für die Klasse der Scoring-Protokolle und für Copeland^(alpha)-Wahlen betrachtet. Das dritte Problem, das betrachtet wird, ist die Frage nach den Gewichten der Wähler. Beim Possible-Winner-Problem mit unsicheren Gewichten ist die Frage, ob ein ausgezeichneter Kandidat zum Gewinner der Wahl werden kann, wenn die Gewichte einiger Wähler erst nach der Stimmabgabe festgelegt werden. Diese Frage wird mit Hinblick auf verschiedene Wahlsysteme untersucht. Für einige Wahlsysteme wird die NP-Vollständigkeit dieses Problems bewiesen, während für einige andere die Zugehörigkeit zur Komplexitätsklasse P gezeigt wird. Der dritte behandelte Themenbereich ist verwandt mit dem Bereich Preference Aggregation. Diese Arbeit behandelt das Rating-Problem, das beim Peer-Review-Prozess auftritt und schlägt zwei neue Verfahren vor, um die Punkte, die die Gutachter für die Paper vergeben, zu kalibrieren. Außerdem wird neben diesen kalibrierten Punkten noch die Härte der Gutachter geschätzt. Natürlich sind die kalibrierten Punkte realistischer als eine einfache Mittelwertbildung, wenn die Härte der Gutachter mit berücksichtigt wird, wobei die Mittelwertbildung heutzutage typischerweise bei Konferenzen und Workshops angewendet wird. Die vorgeschlagenen Ansätze werden sowohl anhand konstruierter Beispiele als auch mit echten Daten eines Workshops, der 2010 in Düsseldorf stattfand, evaluiert. Computational social choice is an emerging field at the intersection between social choice theory and computer science and covers several topics. Three of them are investigated in this thesis. In multiagent resource allocation the task is to distribute indivisible and nonshareable items among a set of agents, where the goal is to fulfill some criteria of fairness or social welfare. In this thesis different notions of social welfare optimization are studied. The general decision problems underlying the problems of finding allocations with maximal social welfare are either known to be NP-complete or proved to be NP-complete in this thesis. Furthermore, some of the exact versions of these problems are shown to be DP-complete. One research question in the field of voting is the possible winner problem. This problem is studied with weighted voters and under three types of uncertainty in this thesis. The possible winner problem with respect to the addition of new candidates asks whether it is possible to make a distinguished candidate a winner of a given election if new candidates are added after all votes have been cast. Several NP-completeness results are shown for several voting systems in both the co-winner case and the unique-winner case. Furthermore, membership in P is proved for veto voting in both cases. Another variant of the possible winner problem is possible winner with uncertain voting system. Here, only a class of voting systems is given and after all votes have been cast, the chair chooses a specific voting system from this class. Again, the question is whether a specific candidate can be made a winner of the election by choosing the appropriate voting system. This problem is studied for scoring rules and for Copeland^(alpha) elections, again with weighted voters. In the third possible winner problem considered, uncertainty concerns the weights themselves. In the possible winner problem with uncertain weights, the question is whether a distinguished candidate can be made a winner of the election if the weights of some voters can be adjusted after all votes have been cast. This question is explored for several voting systems in this thesis, for some of them NP-completeness is proved, whereas for some of them membership in P is shown. The third topic studied is related to preference aggregation. In this context, this thesis studies the rating problem in the peer reviewing process and proposes two new approaches for aggregating the scores that reviewers give for the examined papers. Besides aggregating these scores, also the rigor of the reviewers is estimated by statistical analysis. Of course, when taking the degree of rigor into account, aggregating the scores is more realistic than simply computing the average, which is typically done for conferences and workshops nowadays. The proposed methods are evaluated by small toy examples as well as by real-world data from a workshop which took place in Düsseldorf in 2010.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology
Dokument erstellt am:	22.01.2014
Dateien geändert am:	22.01.2014
Promotionsantrag am:	18.07.2013
Datum der Promotion:	20.11.2013