9 papers · 1 filter
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…