Structural and Algorithmic Aspects of Preference-based Problems in Social Choice

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 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 hardness 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 can be exploited to design more efficient algorithms. The primary goal of this project 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. A core concept in PA is fixed-parameter tractability (FPT) which captures problems solvable in f (k) n^O(1) time, where n denotes the input size and f is some computable function (usually exponential) of the parameter k. Roughly speaking, FPT generalizes the classical polynomial time solvability P to also admit a factor f (k), which is typically super-polynomial in k. If the value of k is small, then an FPT algorithm can still be considered to be efficient. We will base our approach on well-established parameterized techniques such as (1) kernelization, which is a polynomial-time preprocessing procedure with guaranteed performance, and (2) distance to tractability, which measures the distance to some polynomial-time solvable special case of an NP-hard problem. We will also exploit some of the latest trends in parameterized research such as (3) "FPT in P", which applies PA to problems that are solvable in polynomial time (P), and (4) parameterized approximation, which is an c-approximation algorithm running in time f (k, c). We choose these techniques to start our investigation as not only they have proven to be successful and practical, but they have also been rarely applied to COMSOC problems so far. We focus on prominent COMSOC problems that have been extensively studied, e.g. voting, as well as problems that are more application-oriented, e.g. those with time-evolving preferences. (I) voting problems, e.g. determining the winner of an election or voting manipulation; (II) problems with preferences that may be non-linear orders, e.g. allowing ties; (III) preference-based matching problems such as STABLE MARRIAGE and STABLE ROOMMATES; (IV) problems where the preferences evolve over time, requiring traditional solution concepts tobe extended. Summarizing, we will systematically study the parameterized complexity of the COMSOC problems addressed; see the left part of Table 1 in the Work Plan for an overview. We foresee active collaboration with Prof. Szeider and his research division as he and his division members have done high impact work on PA for various problems that arise, e.g. from AI. Moreover, we will explore the implementability of SAT solving, utilizing the expertise of many researchers at TU Wien. We will also conduct algorithm engineering for different kinds of real-world data from, for instance, the freely available PreLib library (www.preflib.org) to further tailor our algorithms to practical needs. Alongside the design and analysis of practical algorithms, the research project also aims at o providing more refined models for real-world problems, and o establishing interaction between COMSOC theorist and people who could potentially benefit from using COMSOC methods.