Komplexität von Wahlproblemen: Gewinner-Bestimmung, Manipulation und Wahlkontrolle
Final Report Abstract
Inhalt dieses Projekts ist eine umfassende algorithmische und komplexitätstheoretische Untersuchung von Wahlproblemen (z.B. Kontrolle, Manipulation und Bestechung). Die Komplexitätsanalyse von Wahlsystemen fällt in das interdisziplinäre Gebiet „Computational Social Choice". Wahlsysteme sind Vorschriften, mit denen aus einer Gruppe von Kandidaten (oder Alternativen) der oder die Sieger einer Abstimmung ausgewählt werden können. Seit langem werden Wahlsysteme in den Politik- und Wirtschaftswissenschaften (speziell in der Social-Choice- Theorie) untersucht. Da sich jedoch auch in der Informatik viele Anwendungen aus der Theorie des Wählens und der Präferenzaggregation ergeben - speziell in automatisierten Verfahren (z. B. bei elektronischen Wahlen, Multi-Agenten-Systemen, Page-Ranking-Algorithmen für Suchmaschinen und Recommender-Systeme im Internet, bei E-Kommerz und elektronischen Auktionen) -, ist die algorithmische Analyse von Wahlproblemen (wie z. B. dem Manipulationsproblem) eine zentrale Aufgabe. Auch wenn nach dem gefeierten Gibbard-Satterthwaite-Resultat im Prinzip kein natürliches Wahlsystem vor Manipulation durch strategische Wähler gefeit ist, so kann Berechnungshärte im Sinne der Komplexitätstheorie doch einen Schutz gegen Manipulation, strategisches Wählen und andere Arten der Wahlbeeinflussung bieten. Bei den Szenarien der Wahlkontrolle versucht ein Wahlleiter, den Ausgang der Wahl durch strukturelle Veränderungen der Wahl wie dem Hinzufügen, Entfernen oder Partitionieren der Kandidaten oder Wähler zu beeinfiussen. Man unterscheidet dabei konstruktive und destruktive Szenarien sowie verschiedene Regeln zum Umgang mit „Unentschieden" in den Partitionierungsfällen. Dies führt zu den 22 in der Literatur betrachteten Standard-Kontrolltypen. Das Ziel besteht darin, möglichst natürliche Wahlsysteme zu finden, die einen möglichst umfassenden Schutz gegen diese 22 Kontrolltypen bieten. Es ist uns gelungen, mit dem Copeland-Wahlsystem das erste natürliche Wahlsystem (dessen Gewinner in Polynomialzeit bestimmt werden können) zu identifizieren, das vollständig resistent gegen konstruktive Wahlkontrolle ist, d.h., die entsprechenden Kontrollprobleme sind NP-hart. Ein mittels Hybridisierung von uns konstruiertes Wahlsystem ist zwar resistent gegen alle Typen der Wahlkontrolle, aber relativ künstlich. Wir zeigten, dass (unter den natürlichen Wahlsystemen mit einem effizient lösbaren Gewinnerproblem) SP-AV - eine Variante des hybriden Systems "sincere-strategy preference-based approval voting" von Brams und Sanver (2006) - mit 19 Resistenzen den bisher umfangreichsten Schutz gegen Wahlkontrolle bietet. Nicht weniger Kontrollresistenzen hat, wie wir zeigten, das Fallback-System von Brams und Sanver, dass das Bucklin- mit dem Approval-Wahl system kombiniert und in gewissem Sinn noch natürlicher als SP-AV ist. Manipulation modelliert Wahlbeeinflussung durch strategische Wähler. Für eine Reihe von Wahlsystemen (z. B. Scoring-Protokolle, zu denen Systeme wie Borda, Veto oder k-Approval gehören) zeigten wir die algorithmische Härte oder effiziente Lösbarkeit der entsprechenden Probleme im Worst-Case-Modell. Auch untersuchten wir Ansätze zur effizienten (heuristischen) Lösbarkeit von Manipulationsproblemen im Average-Case- oder Typical-Case-Modell und zeigten ihre Grenzen auf. Außerdem studierten wir Manipulation und Kontrolle für Wähler mit dem in der Politikwissenschaft kanonischen Modell der single-peaked preferences und fanden Fälle, bei denen die Komplexität des Problems durch diese Einschränkung verringert, beibehalten oder sogar erhöht wird. Weiterhin untersuchten wir Bestechungsprobleme für Copeland-Wahlen und das Probabilistic Lobbying Problem in einer Vielzahl von Szenarien. Viele unserer Resultate zur klassischen Komplexität von Problemen werden durch Fest-Parameter-Algorithmen bzw. parametrisierte Komplexitätsresultate (z. B. W[2]-Härte) sowie durch Approximierbarkeitsresultate komplementiert. Wir erzielten auch einige Dicholomieresultate, die einfach zu testende Bedingungen angeben, mit denen man die einfachen Instanzen eines Problems (oder einer Familie von Problemen) von den schweren unterscheiden kann, so z. B. für das Possible Winner Problem (das das Manipulationsproblem verallgemeinert) In der Klasse der Scoring-Protokolle. Schließlich erzielten wir Komplexitätsergebnisse zu • gewichteten Wahlspielen, insbesondere zu dem neu eingeführten Begriff cost of stability und zum Merging Problem und Splitting Problem im Zusammenhang mit dem Shapley-Shubik- und dem (probabilistischen) Banzhaf-Power-lndex; • (inklusions-)minimalen upward covering sets und downward covering sets für unvollständige Dominanzrelationen.
Publications
- Frequency of Correctness versus Average Polynomial Time. Information Processing Letters, vol. 109, no. 16, pp. 946-949, Juli 2009
G. Erdelyi, L. Hemaspaandra, J. Rothe und H. Spakowski
- Generalized Juntas and NP-Hard Sets. Theoretical Computer Science, vol. 410, no. 38^0, pp. 3995-4000, September 2009
G. Erdelyi, L. Hemaspaandra, J. Rothe und H. Spakowski.
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control. Journal of Artificial Intelligence Research, vol. 35. pp. 275-341. 2009
P. Faliszewski. E. Hemaspaandra, L. Hemaspaandra und J. Rothe
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control. Mathematical Logic Quarterly, vol. 55, no. 4, pp. 425-443, August 2009
G. Erdelyi, M. Nowak und J. Rothe
- The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control. Information and Computation, vol. 209, no. 2, pp. 89-107, 2011
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra und J. Rothe
- Control Complexity in Fallback Voting. Tagungsband Computing: the J6th Australasian Theory Symposium (CATS'10), Australian Computer Society Conferences in Research and Practice in Information Technology Series, vol. 32, no. 8. pp. 39-48. Brisbane, Australia, Januar 201
G. Erdelyi und J. Rothe
