Multivariate Analysis and Structural Restrictions in Computational Social Choice

1 Introduction

In an increasingly interconnected world, algorithmic decision-making systems have become integral to our daily lives, shaping outcomes in domains ranging from employment and lending to criminal justice and healthcare. However, these decisions do not always meet the desired criteria, such as fairness, equitability, inclusion, or diversity, which emerged as a pivotal concern in algorithmic decision-making. These principles are not mere ethical abstractions; they reflect the very essence of a just and harmonious society. The imperative to address these issues is underscored by the potential for biased algorithms to perpetuate existing inequalities, discriminate against marginalized groups, and erode trust in automated systems.

Simultaneously, designed systems not only need to uphold fairness, equality, and diversity, but also have to do so efficiently and on a scale. However, it turns out that the task of finding a decision that satisfies these requirements can often be computationally very hard. This computational complexity stems from the intricate trade-offs involved in optimizing multiple conflicting objectives, such as fairness and efficiency. It raises fundamental questions about the balance between the mathematical ideals of fairness and the real-world constraints of computational feasibility. Understanding these complexities is essential for the development of practical and socially responsible algorithmic systems.

Therefore, my PhD project aims to explore the intricate interplay between these core values and the computational challenges associated with computational problems that lie at the very heart of nowadays decision-making systems. More precisely, I am interested in computationally hard problems that arise in the area of computational social choice [Brandt et al., 2016] and use the framework of parameterized complexity [Cygan et al., 2015] that equips us with methods allowing for a formal study of structural restriction and conditions under which these problems become efficiently solvable.

2 Contribution

Prototypical problems in computational social choice possess a very similar structure. We are given a group of alternatives and a group of agents together with their preferences on the alternatives, and our goal is to find an "acceptable" alternative according to agents' preferences. The notion of an acceptable alternative and agents' preferences naturally vary between specific problems and applications; however, these notions are always mathematically well defined and try to describe different properties of the outcome, such as its fairness, proportionality, efficiency, or diversity.

The standard textbook in the area of computational social choice divides problems into four main sub-areas [Brandt et al., 2016]. Following this approach, I split the rest of this section into four subsections, and for each subarea, I give a brief overview of my contribution and introduce a few possible future directions.

2.1 Voting

In [Boehmer et al., 2024], we apply the foundational research on multiwinner votingto the area of participatory budgeting. In this real-life application, there is a set of projects, each associated with its cost, and a budget. The goal is to select a subset of projects whose overall costs do not exceed the budget to be funded and which are the best representatives of agents' preferences. More specifically, we introduce a robust framework that provides a more detailed explanation of the results, leading to a wider acceptance and satisfaction with the outcome of the election. As associated computational problems are intractable in many cases, we exploit various structural properties to design effective algorithms that are capable of computing our measures for real-life instances.

This framework is mainly focused on projects that were not successful in the given participatory budgeting instance. In our future work, we want to extend it to projects that were selected to be funded. This will allow us to give a more detailed description of the results.

2.2 Fair Allocation

Fair allocation is a prototypical decision-making problem at the intersection of computation and economics. The goal is to find a "fair" allocation of a set of items to a set of agents with respect to agents' preferences. In [Deligkas et al., 2024b], we follow a generalization of the standard model of fair division of indivisible items. Specifically, when determining whether an allocation is fair, the agents may additionally assume also which items not allocated to them were allocated to which agents. We provide a comprehensive study of the (parameterized) complexity of the problem of deciding whether there is a fair allocation with respect to a wide variety of different input restrictions.

Our work left unresolved the question of whether an efficient algorithm exists if the number of items is small. We want to resolve it to obtain the full complexity picture of the problem. Also, we focused solely on fairness notions based on envy between pairs of agents. Therefore, it is also natural to ask whether our techniques can be used in the case of other well-defined fairness notions, such as proportionality.

2.3 Coalition Formation

In the area of coalition formation, our goal is to partition a set of agents into subgroups, called coalitions, such that the agents are "satisfied" with the coalition they are allocated to.

In [Ganian et al., 2023b], we study the so-called hedonic diversity games, where the agents are additionally partitioned into several colors, and the agents' preferences are based on the ratio of agents of each color in their coalition. We study the problem of determining the existence of stable allocations under multiple input restrictions, including the number of colors or the number of coalitions. In another paper with a similar set of co-authors [Ganian et al., 2023a], we study similar restrictions in a different class of coalition formation games; namely, we investigate the class of social distance games.

In [Ganian et al., 2023b], we identified a natural restriction of agents' preferences and show that finding a stable outcome under this restriction can be significantly easier than in the original setting. Therefore, the natural future research direction is to extend the analysis of this restriction to other parameters. Moreover, hedonic diversity games are mostly unexplored from the perspective of other stability notions.

2.4 Additional Topics

In [Knop and Schierreich, 2023], we introduced a novel model of refugee housing that deals with a situation in which a community needs to house a group of refugees in empty houses, respecting the preferences of both the inhabitants and refugees. We show that, in general, finding an assignment of refugees that respects the preferences of all involved is computationally intractable. Therefore, we study which restrictions of the input guarantee the existence of efficient algorithms. Later, in [Schierreich, 2023], I provide a natural restriction of agents' preferences that is better motivated by practical instances and allows for more efficient algorithms. In [Lisowski and Schierreich, 2023], we study a variant of the problem in which agents can change their houses to improve their utility.

So far, research in the area of refugee housing has focused on different notions of stability. The two most promising directions for future work are the study of fair assignments and the study of approximation algorithms in this context.

Closely related to refugee housing are topological distance games, where we also want to allocate a set of agents to vertices of a graph. In [Deligkas et al., 2024a], we give an indepth study of structural restrictions that allow for fast computation of individually rational outcomes.

3 Conclusions

Many computationally hard problems arise naturally and need to be solved exactly in practice. This is particularly important for computational social choice, a research area that deals with many real-world problems. In my research, I focus on more fine-grained complexity analysis of important problems in this area and try to reveal conditions under which such problems become efficiently solvable in practice.

Acknowledgments

The work on this paper was supported by the Czech Science Foundation Grant No. 22-19557S, and by the Grant Agency of the CTU in Prague, grant No. SGS23/205/OHK3/3T/18.