Dokument: The Control Complexity of Sincere-Strategy Preference-Based Approval Voting and of Fallback Voting, and a Study of Optimal Lobbying and Junta Distributions for SAT
| Titel: | The Control Complexity of Sincere-Strategy Preference-Based Approval Voting and of Fallback Voting, and a Study of Optimal Lobbying and Junta Distributions for SAT | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=10720 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20090325-110236-6 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Erdelyi, Gabor [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Rothe, Jörg [Betreuer/Doktorvater] Prof. Dr. Wanke, Egon [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibungen: | Wahlverfahren werden nicht nur in der Politik, sondern auch in
vielen Gebieten der Informatik eingesetzt (z.B. bei Multi-Agenten-Systemen in der K\"unstlichen Intelligenz). Brams und Sanver führten zwei Wahlsysteme ein, die das bekannte Approval Voting modifizieren: Sincere-strategy Preference-based Approval Voting (SP-AV) und Fallback Voting (FV). Diese beiden Wahlsysteme werden in der vorliegenden Arbeit im Hinblick auf Wahlkontrolle untersucht. In solchen Kontrollszenarien versucht ein externer Agent, das Wahlergebnis durch Hinzufügen/Entfernen/Partitionieren von entweder Kandidaten oder Wählern zu beeinflussen. Es wird gezeigt, dass SP-AV gegen 19 der üblichen 22 Typen von Wahlkontrolle resistent ist, d.h., die entsprechenden Kontrollprobleme sind NP-hart). Unter allen natürlichen Wahlsystemen, deren Sieger in Polynomialzeit bestimmt werden können, besitzt SP-AV somit die meisten Resistenzen gegen Wahlkontrolle. Insbesondere ist SP-AV (nach Copeland Voting) das zweite solche Wahlsystem, das gegen alle Typen der konstruktiven Wahlkontrolle resistent ist. Anders als Copeland Voting ist SP-AV jedoch auch weitgehend resistent gegen die destruktiven Kontrolltypen. Außerdem wird gezeigt, dass FV -- ebenso wie SP-AV -- vollständig resistent gegen alle Typen von Kandidatenkontrolle ist. Christian et al. zeigten, dass das Problem Optimal Lobbying im Sinne der parametrisierten Komplexität schwer zu lösen ist. In der vorliegenden Arbeit wird ein effizienter Algorithmus entworfen und analysiert, der sogar die verallgemeinerte Variante Optimal Weighted Lobbying dieses Problems in einem logarithmischen Faktor approximiert, und es wird gezeigt, dass dieser Approximationsfaktor für diesen Algorithmus nicht verbessert werden kann. Weiterhin wird das Gewinnerproblem für Dodgson-Wahlen untersucht. Hemaspaandra, Hemaspaandra und Rothe zeigten, dass dieses Problem vollständig für parallelen Zugriff auf NP ist. Homan und Hemaspaandra stellten eine effiziente Heuristik vor, die unter geeigneten Voraussetzungen Dodgson-Gewinner mit einer garantierten Häufigkeit findet, d.h., diese Heuristik ist ein so genannter ``frequently self-knowingly correct algorithm''. In der vorliegenden Arbeit wird dieser Algorithmus-Typ in Bezug zur Klasse Average-Case Polynomial Time (AvgP) gesetzt. Es wird gezeigt, dass jedes Verteilungsproblem in AvgP bezüglich der Gleichverteilung einen solchen "frequently self-knowingly correct algorithm" hat, der in Polynomialzeit läuft. Außerdem werden einige Eigenschaften des verwandten Begriffs "probability weight of correctness" hinsichtlich der von Procaccia and Rosenschein eingeführten so genannten Junta-Verteilungen untersucht.While voting systems were originally used in political science, they are now also of central importance in various areas of computer science, such as artificial intelligence (in particular within multiagent systems). Brams and Sanver introduced sincere-strategy preference-based approval voting (SP-AV) and fallback voting (FV), two election systems which combine the preference rankings of voters with their approvals of candidates. We study these two systems with respect to procedural control - settings in which an agent seeks to influence the outcome of elections via control actions such as adding/deleting/partitioning either candidates or voters. We prove that SP-AV is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, for the 22 control types studied here, SP-AV has more resistances to control, by three, than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al.) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control. We show that FV has full resistance to candidate control. We also investigate two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former problem, Christian et al. showed that optimal lobbying is intractable in the sense of parameterized complexity. We propose an efficient greedy algorithm that nonetheless approximates a generalized variant of this problem, optimal weighted lobbying, and thus the original optimal lobbying problem as well. We also show that the approximation ratio of this algorithm is tight. The problem of determining Dodgson winners is known to be complete for parallel access to NP. Homan and Hemaspaandra proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is indeed a ``frequently self-knowingly correct algorithm.'' We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenschein's junta distributions. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Computational Complexity Theory/Cryptology | |||||||
| Dokument erstellt am: | 25.03.2009 | |||||||
| Dateien geändert am: | 19.03.2009 | |||||||
| Promotionsantrag am: | 16.01.2009 | |||||||
| Datum der Promotion: | 16.03.2009 |
