6 papers
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…
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…
Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair o…
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…