Algorithmische Grundlagen der Social-Choice-Theorie

• Antragsteller: Professor Dr. Felix Brandt; Professor Dr. Jörg-Matthias Rothe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 209922626

• Erstellungsjahr: 2018

Zusammenfassung der Projektergebnisse

Inhaltlich sind die wichtigsten Ergebnisse („highlights“) dieses Projekts die folgenden: Wir initiierten eine systematische Untersuchung zur Komplexität von Problemen in Wahlen mit top-, bottom- und doubly-truncated ballots sowie von Possible-Winner-Varianten. - Wir zeigten, dass unter allen bisher untersuchten natürlichen Wahlsystemen mit effizienter Gewinnerbestimmung fallback voting die umfassendste Kontrollresistenz aufweist. Auch die Komplexität von Manipulation, Bestechung und Kontrolle in Bucklin-Wahlen wurde sehr umfassend geklärt. - Wir charakterisierten Strategiesicherheit in scoring allocation correspondences durch eine einfache Bedingung und initiierten eine umfassende Untersuchung weiterer ihrer Eigenschaften. - Wir führten den Begriff der Online-Manipulation und der Online-Kontrolle für sequenzielle Wahlen ein und zeigten die PSPACE-Vollständigkeit der entsprechenden Probleme im allgemeinen Fall sowie weitere Komplexitätsresultate für spezifische natürliche Wahlsysteme. - Wir bestimmten die Komplexität von Manipulation, Bestechung und Kontrolle für die Klasse der uniform premise-based quota rules in der judgment aggregation für verschiedene Präferenztypen. - Wir vervollständigten die Resultate zur Kontrollkomplexität für Borda- und Veto-Wahlen. - Wir schlugen statistische Methoden zur Kalibrierung von review scores vor, um subjektive Bewertungen wissenschaftlicher Arbeiten fairer und besser vergleichbar zu machen.

Projektbezogene Publikationen (Auswahl)

• Campaigns for Lazy Voters: Truncated Ballots, Tagungsband 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’12), IFAAMAS, pp. 577–584. Valencia, Spain, Juni 2012
  D. Baumeister, P. Faliszewski, J. Lang und J. Rothe
  
• Journal of Computer and System Sciences, vol. 80, no. 4, pp. 697–710, Juni 2014
  E. Hemaspaandra, L. Hemaspaandra und J. Rothe
  (Siehe online unter https://doi.org/10.1016/j.jcss.2013.10.001)
• Theory of Computing Systems, vol. 53, no. 3, pp. 467–502, Oktober 2013
  D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann und J. Rothe
  (Siehe online unter https://doi.org/10.1007/s00224-012-9437-9)
• Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 3, pp. 628–655, Mai 2017
  D. Baumeister, S. Bouveret, J. Lang, N. Nguyen, T. Nguyen, J. Rothe und A. Saffidine
  (Siehe online unter https://doi.org/10.1007/s10458-016-9340-x)
• Complexity of Manipulation and Bribery in Judgment Aggregation for Uniform Premise-Based Quota Rules, Mathematical Social Sciences, vol. 76, pp. 19–30, Juli 2015
  D. Baumeister, G. Erdélyi, O. Erdélyi und J. Rothe
  (Siehe online unter https://doi.org/10.1016/j.mathsocsci.2015.03.006)
• Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting, Journal of Autonomous Agents and Multi-Agent Systems, vol. 29, no. 6, pp. 1091–1124, November 2015
  P. Faliszewski, Y. Reisch, J. Rothe und L. Schend
  (Siehe online unter https://doi.org/10.1007/s10458-014-9277-x)
• Control Complexity in Bucklin and Fallback Voting: A Theoretical Analysis, Journal of Computer and System Sciences, vol. 81, no. 4, pp. 632–660, Juni 2015
  G. Erdélyi, M. Fellows, J. Rothe und L. Schend
  (Siehe online unter https://doi.org/10.1016/j.jcss.2014.11.002)
• Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer Texts in Business and Economics, Springer-Verlag, Berlin, Heidelberg, 2015, xiv+612 Seiten
  J. Rothe (ed.)
  (Siehe online unter https://doi.org/10.1007/978-3-662-47904-9)
• A Statistical Approach to Calibrating the Scores of Biased Reviewers of Scientific Papers, Metrika, vol. 79, no. 1, pp. 37–57, Januar 2016
  W. Kuhlisch, M. Roos, J. Rothe, J. Rudolph, B. Scheuermann und D. Stoyan
  (Siehe online unter https://doi.org/10.1007/s00184-015-0542-z)
• Solving Seven Open Problems of Offline and Online Control in Borda Elections, Tagungsband 31st AAAI Conference on Artificial Intelligence (AAAI’17), AAAI Press, pp. 3029–3035. San Francisco, USA, Februar 2017
  N. Neveling und J. Rothe
  
• The Complexity of Online Voter Control in Sequential Elections, Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 5, pp. 1055–1076, September 2017
  E. Hemaspaandra, L. Hemaspaandra und J. Rothe
  (Siehe online unter https://doi.org/10.1007/s10458-016-9349-1)
• Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods, Social Choice and Welfare, vol. 50, no. 1, pp. 101–122, Januar 2018
  N. Nguyen, D. Baumeister und J. Rothe
  (Siehe online unter https://doi.org/10.1007/s00355-017-1075-3)