This research project 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 two central areas of collective decision making: voting and the allocation of indivisible goods.
While these are separate topics, there are various connecting links and joint features. We will focus on our recently introduced online voting and scoring allocation models in the following four packages:
(1) online bribery in sequential elections;
(2) online manipulation, online control, and online bribery over single-peaked electorates;
(3) strategy-proofness and other properties in scoring-based allocation of indivisible goods; and
(4) fairness properties and social welfare optimization in the allocation of indivisible goods.
In each of these work packages, we will consider natural, important problems modeling a certain kind of strategic behavior or some other (e.g., fairness) property. In particular, we seek to explore in which way and to what extent computational complexity can be used as protection against undesired behavior such as manipulation attacks. Our complexity analysis will employ tools from classical complexity, parameterized complexity, and the theory of approximations, and in addition we will perform empirical studies, make use of probabilistic approaches, and will study the axiomatic properties of the underlying voting and allocation mechanisms.
The project is funded by the German Research Foundation (DFG) for 3 years with 546.900 €.
Prof. Dr. Jörg Rothe
Prof. Dr. Jörg Rothe leitet seit 2000 die Arbeitsgruppe für Komplexitätstheorie und Kryptologie am Insituts für Informatik an der Heinrich-Heine-Universität Düsseldorf.
Seine Forschungsinteressen liegen in der Computational Social Choice, der Algorithmischen Spieltheorie und Fair Division, wobei der Fokus jeweils auf der algorithmischen und komplexitätstheoretischen Behandlung der relevanten Probleme liegt. Im Rahmen des DIID gilt sein Interesse formalen Modellen der theoretischen Informatik für die Beschreibung und Bewertung von Nutzer-Interaktionen in Online-Partizipationsprozessen.