1 citations · 3 across the 21 of their papers we have counts for
22 papers
Delegated Fair Division
Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis +2
Motivated by recently introduced problems on delegated resource allocation, we study a model of fair division, where a set of indivisible goods is to be allocated to some agents, e…
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…
Maximizing Reachability via Shifting of Temporal Paths
Argyrios Deligkas, Michelle Döring, Eduard Eiben +2
We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of k temporal paths, i.e., every given path is a sequence of…
Coordinated Motion Planning is FPT on Discretized Simple Polygons
Argyrios Deligkas, Eduard Eiben, Robert Ganian +1
In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of robots. At each time step, any subset of robots may move…
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…
Public Goods Games in Directed Networks with Constraints on Sharing
Argyrios Deligkas, Gregory Gutin, Mark Jones +2
In a public goods game, every player chooses whether or not to buy a good that all neighboring players will have access to. We consider a setting in which the good is indivisible,…
Parameterized Complexity of Temporal Connected Components
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, that is, graphs whose edges are available only at specific points in time.…
Mechanism Design with Outliers and Predictions
Argyrios Deligkas, Eduard Eiben, Sophie Klumper +2
We initiate the study of mechanism design with outliers, where the designer can discard agents from the social cost objective. This setting is particularly relevant when some a…
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…
The Complexity of Extending Fair Allocations of Indivisible Goods
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate…
EF1 and EFX Orientations
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith +1
We study the problem of finding fair allocations -- EF1 and EFX -- of indivisible goods with orientations. In an orientation, every agent gets items from their own predetermined se…
How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
Logistics and transportation networks require a large amount of resources to realize necessary connections between locations and minimizing these resources is a vital aspect of pla…
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…
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of …
The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspon…
Some coordination problems are harder than others
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kin…
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…
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrar…
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordinati…
Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source
Argyrios Deligkas, Michelle Döring, Eduard Eiben +2
We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the…
Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
In the -Consensus-Halving problem, we are given probability measures on the interval , and the goal is to partition into two parts…
Combinatorial Algorithms for Multidimensional Necklaces
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev +1
A necklace is an equivalence class of words of length over an alphabet under the cyclic shift (rotation) operation. As a classical object, there have been many algorithmic resu…