Parameterized Complexity Analysis for Judgment Aggregation

The field of computational social choice studies methods of collective decision making based on individual preferences or opinions, using tools and concepts from theoretical computer science. One setting studied in this area is that of judgment aggregation. In this setting, individuals provide their opinions on a set of logically related issues, and these individual opinions are to be combined into a single group opinion using a judgment aggregation procedure. An important matter in the investigation of such procedures is the computational complexity of various problems that arise, that is, the amount of time that is needed to solve these problems algorithmically. For example, one would like to design judgment aggregation procedures in such a way that collective opinions can be computed quickly. In the research project Parameterized Complexity Analysis of Judgment Aggregation, we will investigate the computational complexity of various problems that come up in the area of judgment aggregation. We will do so by means of the framework of parameterized complexity. This mathematical framework is capable of providing a detailed picture of the computational complexity of problems by taking into account multiple parameters of the input. The results that we will obtain will yield a more accurate view of the settings in which judgment aggregation problems can be solved efficiently, and the settings in which this is not possible. This project will initiate the first structured parameterized complexity analysis of problems arising in judgment aggregation. In order to adequately perform this complexity analysis, we will further develop the parameterized complexity tools that play a role in our investigation. The parameterized complexity tools that are most commonly used in the literature do not suffice to give a satisfactory analysis of many judgment aggregation problems. We will further develop recently devised parameterized complexity tools that help fill this gap to be able to provide a more successful analysis. These augmented parameterized complexity tools can also be used in future research to investigate problems in other areas of computer science.

The framework of Judgment Aggregation can be used to model and carry out complex voting scenarios. In general, this is computationally expensive to do, meaning that computing the winner of the voting scenario can take centuries or more. The main contributions of this project consist of the identification of particular settings where complex voting scenarios can be dealt with efficiently using the mathematical framework of Judgment Aggregation. One illustrative example of such a setting is that of participatory budgeting. In this setting, there is a budget to be spent on a combination of projects, and individuals can give their vote on how they think that the budget should be spent. This is a complex voting scenario: one cannot use a majority voting rule, because this could lead to an outcome that exceeds the budget. This is a realistic scenario that has been started to be used in cities around the world, including New York, Chicago, and many others. Judgment Aggregation offers various sophisticated voting rules that can be used in this setting. One example is the rule that selects the combination of projects that maximises the total satisfaction among the voters, while still remaining within budget. One of the key results of this project is an algorithm that enables efficient use of this voting rule in the setting of participatory budgeting. This algorithm is based on the smart use of various mathematical tools from the area of theoretical computer science. The outcomes of the project also include algorithms that enable the use of other sophisticated voting rules in the setting of participatory budgeting, as well as other complex voting scenarios. The research project also investigated the limits of such algorithms. The outcomes of the project also include complementary results, showing in which cases more restrictions are needed for efficient algorithms. Such results are indispensable in the development of efficient algorithms for complex voting scenarios. The results achieved in this project, on the one hand, constitute a useful further step in our quest for theoretical understanding of the computational properties of complex voting scenarios. Moreover, they point at useful and interesting directions for future theoretical research. On the other hand, the results give us concrete algorithms that can be used to develop software tools that can be used to carry out complex voting scenarios in an adequate way. Such software tools would embody the societal relevance of the theoretical research in this project.