Complexity of Strategic Behavior in Collective Decision Making

• Applicant: Professor Dr. Jörg-Matthias Rothe
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 438204498

This research project (renewal proposal) falls into the area of computational social choice (COMSOC) where classical social choice theory and economics meet theoretical computer science (in particular, computational complexity and algorithmics) and artifical intelligence (in particular, multiagent systems). The main objective of this project proposal is to study the computational complexity of strategic behavior in central areas of collective decision making. While some goals of the original project could be realized pretty comprehensively already (e.g., regarding control and bribery problems in an online and offline context in voting), the main focus in this renewal project is on especially promising topics we started to explore in the original project and that open up new opportunities. We will keep studying strategic behavior in collective decision making by voting and will, in particular, employ voting rules in network analysis; we’ll also study strategic behavior in cooperative games (such as in weighted voting games and hedonic games); and strategic behavior, Pareto efficiency, optimization of social welfare, and fairness properties in the allocation of indivisible goods. In these areas, we have set challenging but very concrete and specific goals. In a fourth work package we plan to mix the areas of fair division of indivisible goods and argumentation theory: We seek to formulate and investigate fairness properties in argumentation frameworks. Since this is quite a novel approach, it offers a huge innovation potential and might establish an entirely new line of research that is highly relevant both from a theoretical and a practical point of view. To accomplish our goals, we will apply methods of classical and parameterized complexity theory and of approximation theory, make use of probabilistic approaches, will study the axiomatic properties of the underlying voting and allocation mechanisms, and we will perform empirical studies.

• DFG Programme: Research Grants