Computational Foundations of Social Choice

• Applicants: Professor Dr. Felix Brandt; Professor Dr. Jörg-Matthias Rothe
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 209922626

• Final Report Year: 2018

Final Report Abstract

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.

Publications

• 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
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at 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.)
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at https://doi.org/10.1007/s00355-017-1075-3)