Šimon Schierreich

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.

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ý

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.