4 citations · 10 across the 26 of their papers we have counts for
29 papers
Nearly Group-Separable Elections
Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski +3
We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several…
Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals
Šimon Schierreich, Ildikó Schlotter
We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented…
Algorithms for Candidate Control in Greedy 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 welfare-based rules---GreedyAV and GreedyCost---which are w…
Network Allocation Games with Anonymous Preferences
Argyrios Deligkas, Eduard Eiben, Šimon Schierreich +1
We study network allocation games in which a set of agents must be allocated to (a subset of) the vertices of a graph topology. The agents are anonymous and strategic: Each of them…
An Entropy Potential for Type-Composition Games
Morteza Alimi, Merlin de la Haye, Pascal Lenzner +3
Potential functions are a key tool in theoretical computer science with applications ranging from the runtime analysis of algorithms and data structures, through the analysis of th…
What Makes Majority Illusion Easy to Detect?
Šimon Schierreich, Ildikó Schlotter
Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior…
Navigating the Complexity Landscape of Nominee Selection in Schulze Voting
Katarína Cechlárová, Jörg Rothe, Šimon Schierreich +1
We study the Possible President problem and the Necessary President problem for Schulze voting, a rule that, due to its many desirable axiomatic properties, is popular in practice.…
Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences
Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos +1
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 nat…
Optimal Path Planning in Hostile Environments
Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya +1
Coordinating agents through hazardous environments, such as aid-delivering drones navigating conflict zones or field robots traversing deployment areas filled with obstacles, poses…
Stability in Distance Preservation Games on Graphs
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith +2
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 b…
Participatory Budgeting Project Strength via Candidate Control
Piotr Faliszewski, Łukasz Janeczko, Dušan Knop +4
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 add…
Tight Asymptotic Bounds for Fair Division With Externalities
Frank Connor, Max Dupré la Tour, Vishnu V. Narayan +1
We study the problem of allocating a set of indivisible items among agents whose preferences include externalities. Unlike the standard fair division model, agents may derive posit…
Dividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
Argyris Deligkas, Eduard Eiben, Tiger-Lily Goldsmith +2
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. T…
The Algorithmic Landscape of Fair and Efficient Distribution of Delivery Orders in the Gig Economy
Hadi Hosseini, Šimon Schierreich
Distributing services, goods, and tasks in the gig economy heavily relies upon on-demand workers (aka agents), leading to new challenges varying from logistics optimization to the…
Balanced and Fair Partitioning of Friends
Argyrios Deligkas, Eduard Eiben, Stavros D. Ioannidis +2
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…
Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
Václav Blažej, Dušan Knop, Jan Pokorný +1
We study the Equitable Connected Partition (ECP for short) problem, where we are given a graph G=(V,E) together with an integer p, and our goal is to find a partition of V into p p…
Individual Rationality in Topological Distance Games is Surprisingly Hard
Argyrios Deligkas, Eduard Eiben, Dušan Knop +1
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 depend…
Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough?
Šimon Schierreich
The election, a cornerstone of democracy, is one of the best-recognizable symbols of democratic governance. Voters' confidence in elections is essential, and these days, we can wat…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function that t…
Evaluation of Project Performance in Participatory Budgeting
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko +5
We study ways of evaluating the performance of losing projects in participatory budgeting (PB) elections by seeking actions that would have led to their victory. We focus on loweri…
Towards More Realistic Models for Refugee Integration: Anonymous Refugee Housing with Upper-Bounds
Šimon Schierreich
[Knop and Schierreich; AAMAS~'23] recently introduced a novel model for refugee housing, where we are given a city's topology represented as a graph, a set of inhabitants who occup…
The Complexity of Fair Division of Indivisible Items with Externalities
Argyrios Deligkas, Eduard Eiben, Viktoriia Korchemna +1
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 g…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that too…
On the Complexity of Target Set Selection in Simple Geometric Networks
Michal Dvořák, Dušan Knop, Šimon Schierreich
We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the n…