Tiger-Lily Goldsmith

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.

IJCAI Conference 2025 Conference Paper

EF1 and EFX Orientations

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• Viktoriia Korchemna

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 set. For EF1, we show that EF1 orientations always exist when agents have monotone valuations, via a pseudopolynomial-time algorithm. This surprisingly positive result is the main contribution of our paper. We complement this result with a comprehensive set of scenarios where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time. For EFX, we focus on the recently proposed graph instances, where every agent corresponds to a vertex on a graph and their allowed set of items consists of the edges incident to their vertex. It was shown that finding an EFX orientation is NP-complete in general. We prove that it remains intractable even when the graph has a vertex cover of size 8, or when we have a multigraph with only 10 vertices. We essentially match these strong negative results with a fixed-parameter tractable algorithm that is virtually the best someone could hope for.

AAAI Conference 2025 Conference Paper

How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs

• Argyrios Deligkas
• Michelle Döring
• Eduard Eiben
• Tiger-Lily Goldsmith
• George Skretas
• Georg Tennigkeit

Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.

AAAI Conference 2025 Conference Paper

The Complexity of Extending Fair Allocations of Indivisible Goods

• Argyrios Deligkas
• Eduard Eiben
• Robert Ganian
• Tiger-Lily Goldsmith
• Stavros D. Ioannidis

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 the remaining items. In view of the NP-hardness of the problem, we investigate whether - and under which conditions - one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that - unlike when computing allocations from scratch - the non-algorithmic question of whether more relaxed EF1 or EFX allocations exist can be completely resolved in the extension setting.

AAMAS Conference 2024 Conference Paper

The Parameterized Complexity of Welfare Guarantees in Schelling Segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

Schelling’s model considers 𝑘 types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and PO. Firstly, we focus on the fundamental case where 𝑘 = 2 and there are 𝑟 red agents and 𝑏 blue agents. We show that all solution-notions we consider are intractable even when 𝑏 = 1 and that they do not admit an FPT algorithm when parameterized by 𝑟 and 𝑏, unless FPT = W[1]. In addition, we show that WO and GWO remain intractable even on cubic graphs. We complement these negative results with an FPT algorithm parameterized by 𝑟, 𝑏 and the maximum degree of the graph. For the general case with 𝑘 types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by 𝑘 for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by 𝑘 and the treewidth of the graph.

TCS Journal 2024 Journal Article

The parameterized complexity of welfare guarantees in Schelling segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

AAMAS Conference 2023 Conference Paper

Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• George Skretas

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 goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions. In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.

AAMAS Conference 2023 Conference Paper

The Parameterized Complexity of Welfare Guarantees in Schelling Segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

Schelling’s model considers 𝑘 types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighbor agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare and Pareto optimality, alongside the recently proposed notions of group-welfare optimality and utility-vector optimality.

IJCAI Conference 2022 Conference Paper

Parameterized Complexity of Hotelling-Downs with Party Nominees

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

We study a generalization of the Hotelling-Downs model through the lens of parameterized complexity. In this model, there is a set of voters on a line and a set of parties that compete over them. Each party has to choose a nominee from a set of candidates with predetermined positions on the line, where each candidate comes at a different cost. The goal of every party is to choose the most profitable nominee, given the nominees chosen by the rest of the parties; the profit of a party is the number of voters closer to their nominee minus its cost. We examine the complexity of deciding whether a pure Nash equilibrium exists for this model under several natural parameters: the number of different positions of the candidates, the discrepancy and the span of the nominees, and the overlap of the parties. We provide FPT and XP algorithms and we complement them with a W[1]-hardness result.