Computer Science Colloquium: Borda Count in Collective Decision Making: A Summary of Recent Results
Speaker: Jörg Rothe | Heinrich-Heine-Universität Düsseldorf
Abstract: Borda Count is one of the earliest and most important voting rules. Going far beyond voting, we summarize recent advances related to Borda in computational social choice and, more generally, in collective decision-making. We first present a variety of well-known attacks modeling strategic behavior in voting—including manipulation, control, and bribery—and discuss how resistant Borda is to them in terms of computational complexity. We then describe how Borda can be used to maximize social welfare when indivisible goods are to be allocated to agents with ordinal preferences. Finally, we illustrate the use of Borda in forming coalitions of players in a certain type of hedonic game. All these approaches are central to applications in artificial intelligence.
About the Speaker: Jörg Rothe received his diploma in 1991, his PhD in 1995, and his habilitation degree in 1999, each from Friedrich-Schiller-Universität Jena, Germany. In 1993-1994 he was a visiting scholar and in 1997-1998 a visiting assistant professor at the CS department of University of Rochester, each with a DAAD research fellowship for working with Lane A. Hemaspaandra. Since 2000 he has been a professor of computer science at Heinrich-Heine-Universität Düsseldorf, Germany; in 2013 he was a visiting professor at the CS department of Stanford University, and since 2014 he has been the chair of the CS department at Heinrich-Heine-Universität Düsseldorf. After receiving a DFG Heisenberg Fellowship in 2000 he has been the principal investigator of six DFG projects, a principal investigator in a EUROCORES project of the European Science Foundation (ESF), and was involved in various other international collaborative research projects. His research interests are in computational social choice, algorithmic game theory, fair division, and argumentation theory, typically focusing on the algorithmic and complexity-theoretic properties of the related problems.
