About
Social Choice or Societal Decision Making is concerned with how to combine individual opinions, preferences, or interests so as to reach a collective decision or social welfare. In Computational Social Choice (COMSOC), we explore the computational and algorithmic aspects of problems arising from social choice and decision making such as how to aggregate individual preferences or judgments to reach a consensus, how to fairly allocate a set of resources to some agents, how to optimally assign schools or colleges to students based on their preferences, or how to recommend potential interesting products such as movies to a user based on her and others' past and current preferences. One common point shared by these problems is that they involve preferences, be it from human beings or machines. Typically, such preference-based social choice problems are known to be computationally intractable. However, these intractability results are based on a worst-case analysis from classical complexity theory. Classical complexity analysis only explains how the computational cost of an algorithm depends on the size of the input, ignoring the fact that real-world instances usually have some structure which can be exploited to design more efficient algorithms. The primary goal of this project (started since October 2019) is to develop new efficient algorithms for practically relevant COMSOC problems and to gain new insights into how to "deconstruct" the hardness of these problems. To achieve our goal, we will investigate the computational complexity of COMSOC problems through the lens of Parameterized Algorithmics (PA), which has become an important research technique for designing exact and efficient algorithms primarily for graph problems. PA allows us to take into account the structural properties of a problem as expressed by a parameter, and to design more refined algorithms by viewing their computational cost as a function of both the input size and the parameter.
