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 €.
