Šimon Schierreich

AAMAS Conference 2026 Conference Paper

Algorithms for Candidate Control in Sequential Participatory Budgeting Rules

• Šimon Schierreich
• Krzysztof Sornat

We study the problem of candidate control in participatory budgeting elections. Our focus is on two prominent sequential welfarebased rules—GreedyAV and GreedyCost—which are widely used in practice. Candidate control asks whether we can strategically modify the set of available candidates so as to either ensure that a preferred candidate 𝑝 is selected (constructive control) or prevent 𝑝 from being selected (destructive control). Sinceallvariantsofcandidatecontrolunderthetworulesweconsider are known to be NP-hard, we analyze the problems through the lens of parameterized complexity and approximability. Under thefirstlens, weprovideacomprehensiveclassificationwithrespect to natural parameters such as the number of voters, the number of controlled candidates, and the number of distinct costs, as well as their combinations. Within the second perspective, we establish a tight approximability bound.

AAMAS Conference 2026 Conference Paper

Detecting Approximate Clones under Approval Voting

• Théo Delemazure
• Piotr Faliszewski
• Łukasz Janeczko
• Dušan Knop
• Kristýna Pekárková
• Jan Pokorný
• Šimon Schierreich
• Ildikó Schlotter

In approval elections, two candidates are called perfect clones if they are approved by exactly the same set of voters. We propose a general framework for studying approximations of this notion, and demonstrate its power using two natural approximation measures with various appealing axiomatic properties. For both of these measures, we consider two fundamental tasks: deciding whether a large approximate clone set exists in a given election, and computing a partition of the candidate set into approximate clone sets. We show that both tasks are, in general, computationally intractable. To have a better understanding of the boundary between tractable and intractable instances, we analyze the parameterized complexity of these problems with respect to several parameters, including the number of voters and candidates, the approximation threshold, the number and size of partition parts, and structural properties of the instances, such as the number of approvals per voter or per candidate. Finally, we explore how our approximation measures behave in real-world approval elections.

AAAI Conference 2026 Conference Paper

Dividing Indivisible Items for the Benefit of All: It Is Hard to Be Fair Without Social Awareness

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• Dušan Knop
• Šimon Schierreich

In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if for every agent valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.

AAMAS Conference 2026 Conference Paper

Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences

• Foivos Fioravantes
• Harmender Gahlawat
• Nikolaos Melissinos
• Šimon Schierreich

Hedonic games are an archetypal problem in coalition formation, where a set of selfish agents want to partition themselves into stable coalitions. In this work, we focus on two natural constraints on the possible outcomes. First, we require that exactly 𝑘 coalitions are created. Then, looselyfollowingthemodelofBilòetal. (AAAI2022), we assume that each of the 𝑘 coalitions is additionally associated with a lower and upper bound on its size. The notion of stability that we study is that of individual rationality (IR), which requires that no agent strictly prefers to be alone compared to being in his or her coalition. Although IR is trivially satisfiable even in the most general modelsofhedonicgames, thecomplexitypictureofdecidingwhetheran IR allocation exists, considering the above constraints, is unexpectedly rich. We reveal that tractable fragments of this computational problem require surprisingly nontrivial arguments, even if we restrict ourselves to additively separable and fractional hedonic games. Our tractability results, achieved by exploiting the structure of the underlying preference graph, are also complemented by their intractability counterparts, painting a fairly complete picture of the tractability landscape of this problem.

AAMAS Conference 2026 Conference Paper

Stability in Distance Preservation Games on Graphs

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• Dušan Knop
• Šimon Schierreich

We introduce a new class of network allocation games called graphical distance preservation games. Here, we are given a graph, called a topology, and a set of agents that need to be allocated to its vertices. Moreover, every agent has an ideal (and possibly different) distance in which to be from some of the other agents. Given an allocation of agents, each one of them suffers a cost that is the sum of the differences from the ideal distance for each agent in their subset. The goal is to decide whether there is a stable allocation of the agents, i. e. , no agent would like to deviate from their location. Specifically, we consider three different stability notions: envy-freeness, swap stability, and jump stability. We perform a comprehensive study of the (parameterized) complexity of the problem in three different dimensions: the topology of the graph, the number of agents, and the structure of preferences of the agents.

AAAI Conference 2025 Conference Paper

Balanced and Fair Partitioning of Friends

• Argyrios Deligkas
• Eduard Eiben
• Stavros D. Ioannidis
• Dušan Knop
• Šimon Schierreich

In the recently introduced model of fair partitioning of friends, there is a set of agents located on the vertices of an underlying graph that indicates the friendships between the agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold: (a) we adapt several fairness notions that have been developed in the fair division literature to our setting; (b) we give several existence guarantees supported by polynomial-time algorithms; (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.

EUMAS Conference 2025 Conference Paper

Controlling the Spread of Two Secrets in Diverse Social Networks

• Václav Blažej
• Dušan Knop
• Šimon Schierreich

IJCAI Conference 2025 Conference Paper

Participatory Budgeting Project Strength via Candidate Control

• Piotr Faliszewski
• Łukasz Janeczko
• Dušan Knop
• Jan Pokorný
• Šimon Schierreich
• Mateusz Słuszniak
• Krzysztof Sornat

We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Equal-Shares, but there are natural cases with polynomial-time algorithms. We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments on real-life PB instances.

AAMAS Conference 2025 Conference Paper

Participatory Budgeting Project Strength via Candidate Control

• Piotr Faliszewski
• Lukasz Janeczko
• Dušan Knop
• Jan Pokorný
• Šimon Schierreich
• Mateusz Sluszniak
• Krzysztof Sornat

We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Eqal-Shares, but there are natural cases with polynomial-time algorithms (e. g. , for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects.

EUMAS Conference 2025 Conference Paper

Stability in Newcomers' Housing: A Story about Anonymous Preferences and Beyond

• Grzegorz Lisowski
• Šimon Schierreich

IJCAI Conference 2024 Conference Paper

Evaluation of Project Performance in Participatory Budgeting

• Niclas Boehmer
• Piotr Faliszewski
• Łukasz Janeczko
• Dominik Peters
• Grzegorz Pierczyński
• Šimon Schierreich
• Piotr Skowron
• Stanisław Szufa

We study ways of evaluating the performance of losing projects in participatory budgeting (PB) elections by seeking actions that would make them win. We focus on lowering their costs, obtaining additional approvals, and removing approvals for competing projects: The larger a change is needed, the less successful is the given project. We seek efficient algorithms for computing our measures and we analyze them experimentally, focusing on GreedyAV, Phragmen, and Equal-Shares PB rules.

IJCAI Conference 2024 Conference Paper

Individual Rationality in Topological Distance Games Is Surprisingly Hard

• Argyrios Deligkas
• Eduard Eiben
• Dušan Knop
• Šimon Schierreich

In the recently introduced topological distance games, strategic agents need to be assigned to a subset of vertices of a topology. In the assignment, the utility of an agent depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative. We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.

IJCAI Conference 2024 Conference Paper

Multivariate Analysis and Structural Restrictions in Computational Social Choice

• Šimon Schierreich

In my research, I focus on computationally hard problems in the area of computational social choice. I am interested in the study of input restrictions that guarantee the existence of efficient and scalable algorithms that can be of practical interest.

AAAI Conference 2024 Conference Paper

The Complexity of Fair Division of Indivisible Items with Externalities

• Argyrios Deligkas
• Eduard Eiben
• Viktoriia Korchemna
• Šimon Schierreich

We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

AIJ Journal 2023 Journal Article

Hedonic diversity games: A complexity picture with more than two colors

• Robert Ganian
• Thekla Hamm
• Dušan Knop
• Šimon Schierreich
• Ondřej Suchý

Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work (Boehmer and Elkind, AAAI 2020).

AAAI Conference 2023 Short Paper

Maximizing Influence Spread through a Dynamic Social Network (Student Abstract)

• Šimon Schierreich

Modern social networks are dynamic in their nature; a new connections are appearing and old connections are disappearing all the time. However, in our algorithmic and complexity studies, we usually model social networks as static graphs. In this paper, we propose a new paradigm for the study of the well-known Target Set Selection problem, which is a fundamental problem in viral marketing and the spread of opinion through social networks. In particular, we use temporal graphs to capture the dynamic nature of social networks. We show that the temporal interpretation is, unsurprisingly, NP-complete in general. Then, we study computational complexity of this problem for multiple restrictions of both the threshold function and the underlying graph structure and provide multiple hardness lower-bounds.

AAAI Conference 2023 Conference Paper

The Parameterized Complexity of Network Microaggregation

• Václav Blažej
• Robert Ganian
• Dušan Knop
• Jan Pokorný
• Šimon Schierreich
• Kirill Simonov

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.

AAAI Conference 2022 Short Paper

Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

• Dušan Knop
• Šimon Schierreich
• Ondřej Suchý

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous TARGET SET SELECTION problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion arriving. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parametrized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in FPT if we parametrize by the vertex cover number of the underlying graph.

AAAI Conference 2022 Short Paper

Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)

• Václav Blažej
• Dušan Knop
• Šimon Schierreich

Information diffusion in social networks is a well-studied concept in social choice theory. We propose the study of the diffusion of two secrets in a heterogeneous environment from the complexity perspective, that is, there are two different networks with the same set of agents (e. g. , the structure of the set of followers might be different in two distinct social networks). Formally, our model combines two group identification processes for which we do have independent desiderata—either constructive, where we would like a given group of agents to be exposed to a secret, or destructive, where a given group of agents should not be exposed to a secret. To be able to reach these targets, we can either delete an agent or introduce a previously latent agent. Our results are mostly negative—all of the problems are NP-hard. Therefore, we propose a parameterized study with respect to the natural parameters, the number of influenced agents, the size of the required/protected agent sets, and the duration of the diffusion process. Most of the studied problems remain W[1]-hard even for a combination of these parameters. We complement these results with nearly optimal XP algorithms.

AAAI Conference 2022 Conference Paper

Hedonic Diversity Games: A Complexity Picture with More than Two Colors

• Robert Ganian
• Thekla Hamm
• Dušan Knop
• Šimon Schierreich
• Ondřej Suchý

Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexitytheoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a complete parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question posed in previous work.