Author name cluster

Argyrios Deligkas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

41 papers

2 author rows

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.

PDF Details DOI

AAAI Conference 2026 Short Paper

Network Restoration Games with Quotas (Student Abstract)

Philip Bogaars
Argyrios Deligkas
Eduard Eiben
Michail Fasoulakis

In a game of Network Restoration Games With Quotas, there is an underlying graph where a subset of its edges have to be restored by a set of agents. Each agent has a creation cost for each such edge, a traversal cost for every edge of the graph, and in addition they have a quota on the number of edges they have to restore. Then, given a set of edges that fulfill the quota, the cost of an agent is the cost of creating these edges, plus the cost of reaching them, i.e., the traversal cost. We prove that any cost-minimizing allocation is swap-stable, i.e., there is no profitable exchange of edges between any pair of agents, but computing one is hard even on trees. We complement this by designing an algorithm that finds a swap-stable allocation on trees in polynomial time and we quantify its cost against the optimal one.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Public Goods Games in Directed Networks with Constraints on Sharing

Argyrios Deligkas
Gregory Gutin
Mark Jones
Philip R. Neary
Anders Yeo

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, neighboring players are out-neighbors in a directed graph, and there is a capacity constraint on their number, k, that can benefit from the good. This means that each player makes a two-pronged decision: decide whether or not to buy and, conditional on buying, choose which k out-neighbors to share access. We examine both pure and mixed Nash equilibria in the model from the perspective of existence, computation, and efficiency. We perform a comprehensive study for these three dimensions with respect to both sharing capacity (k) and the network structure (the underlying directed graph), and establish sharp complexity dichotomies for each.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Balanced and Fair Partitioning of Friends

Argyrios Deligkas
Eduard Eiben
Stavros D. Ioannidis
Dušan Knop
Šimon Schierreich

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 agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold: (a) we adapt several fairness notions that have been developed in the fair division literature to our setting; (b) we give several existence guarantees supported by polynomial-time algorithms; (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.

PDF Details DOI

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.

PDF Details DOI

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.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Parameterized Algorithms for Multiagent Pathfinding on Trees

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Iyad Kanj
M. S. Ramanujan

The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes 𝑘 agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by 𝑘: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of 𝑘, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i. e. , trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.

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.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Individual Rationality in Topological Distance Games Is Surprisingly Hard

Argyrios Deligkas
Eduard Eiben
Dušan Knop
Šimon Schierreich

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 depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative. We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.

PDF Details DOI

AAAI Conference 2024 Conference Paper

The Complexity of Fair Division of Indivisible Items with Externalities

Argyrios Deligkas
Eduard Eiben
Viktoriia Korchemna
Šimon Schierreich

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 gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

PDF Details DOI

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

Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph and prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions which 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 k = 2 with r red agents and b blue agents. We show that all solution-notions we consider are intractable even when b = 1 and that they do not admit any FPT algorithm when parameterized by r and b, 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 r, b and the maximum degree of the graph. For the general case with k ≥ 2 types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by k for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by k and the treewidth of the graph.

JAAMAS Journal 2024 Journal Article

Truthful interval covering

Argyrios Deligkas
Aris Filos-Ratsikas
Alexandros A. Voudouris

Abstract We initiate the study of a novel problem in mechanism design without money, which we term Truthful Interval Covering (TIC). An instance of TIC consists of a set of agents each associated with an individual interval on a line, and the objective is to decide where to place a covering interval to minimize the total social or egalitarian cost of the agents, which is determined by the intersection of this interval with their individual ones. This fundamental problem can model situations of provisioning a public good, such as the use of power generators to prevent or mitigate load shedding in developing countries. In the strategic version of the problem, the agents wish to minimize their individual costs, and might misreport the position and/or length of their intervals to achieve that. Our goal is to design truthful mechanisms to prevent such strategic misreports and achieve good approximations to the best possible social or egalitarian cost. We consider the fundamental setting of known intervals with equal lengths and provide tight bounds on the approximation ratios achieved by truthful deterministic mechanisms. For the social cost, we also design a randomized truthful mechanism that outperforms all possible deterministic ones. Finally, we highlight a plethora of natural extensions of our model for future work, as well as some natural limitations of those settings.

IJCAI Conference 2024 Conference Paper

Truthful Interval Covering

Argyrios Deligkas
Aris Filos-Ratsikas
Alexandros A. Voudouris

We initiate the study of a novel problem in mechanism design without money, which we term Truthful Interval Covering (TIC). An instance of TIC consists of a set of agents each associated with an individual interval on a line, and the objective is to decide where to place a covering interval to minimize the total social or egalitarian cost of the agents, which is determined by the intersection of this interval with their individual ones. This fundamental problem can model situations of provisioning a public good, such as the use of power generators to prevent or mitigate load shedding in developing countries. In the strategic version of the problem, the agents wish to minimize their individual costs, and might misreport the position and/or length of their intervals to achieve that. Our goal is to design truthful mechanisms to prevent such strategic misreports and achieve good approximations to the best possible social or egalitarian cost. We consider the fundamental setting of known intervals with equal lengths and provide tight bounds on the approximation ratios achieved by truthful deterministic mechanisms. For the social cost, we also design a randomized truthful mechanism that outperforms all possible deterministic ones. Finally, we highlight a plethora of natural extensions of our model for future work, as well as some natural limitations of those settings.

PDF Details DOI

SODA Conference 2023 Conference Paper

A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games

Argyrios Deligkas
Michail Fasoulakis
Evangelos Markakis 0001

Since the seminal PPAD-completeness result for computing a Nash equilibrium even in two-player games, an important line of research has focused on relaxations achievable in polynomial time. In this paper, we consider the notion of ε-well-supported Nash equilibrium, where ε ∈ [0, 1] corresponds to the approximation guarantee. Put simply, in an ε-well-supported equilibrium, every player chooses with positive probability actions that are within ε of the maximum achievable payoff, against the other player's strategy. Ever since the initial approximation guarantee of 2/3 for well-supported equilibria, which was established more than a decade ago, the progress on this problem has been extremely slow and incremental. Notably, the small improvements to 0. 6608, and finally to 0. 6528, were achieved by algorithms of growing complexity. Our main result is a simple and intuitive algorithm, that improves the approximation guarantee to 1/2. Our algorithm is based on linear programming and in particular on exploiting suitably defined zero-sum games that arise from the payoff matrices of the two players. As a byproduct, we show how to achieve the same approximation guarantee in a query-efficient way. * The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07007

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.

IJCAI Conference 2023 Conference Paper

Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems

Argyrios Deligkas
Eduard Eiben
Gregory Gutin
Philip Neary
Anders Yeo

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed MWDP, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games.

PDF Details DOI

TCS Journal 2023 Journal Article

Learning approximately optimal contracts

Alon Cohen
Argyrios Deligkas
Moran Koren

In principal-agent models, a principal offers a contract to an agent to preform a certain task. The agent exerts a level of effort that maximizes her utility. The principal is oblivious to the agent's chosen level of effort, and conditions her wage only on possible outcomes. In this work, we consider a model in which the principal is unaware of the agent's utility and action space: she sequentially offers contracts to identical agents, and observes the resulting outcomes. We present an algorithm for learning the optimal contract under mild assumptions. We bound the number of samples needed for the principal obtain a contract that is within ϵ of her optimal net profit for every ϵ > 0. Our results are robust even when considering risk averse agents. Furthermore, we show that when there only two possible outcomes, or the agent is risk neutral, the algorithm's outcome approximates the optimal contract described in the classical theory.

IJCAI Conference 2023 Conference Paper

Minimizing Reachability Times on Temporal Graphs via Shifting Labels

Argyrios Deligkas
Eduard Eiben
George Skretas

We study how we can accelerate the spreading of information in temporal graphs via shifting operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, shifting some connections, i. e. , advancing or delaying them, can decrease the time required to reach from some vertex (source) to another vertex. We study how we can minimize the maximum time a set of sources needs to reach every vertex, when we are allowed to shift some of the connections. If we restrict the allowed number of changes, we prove that, already for a single source, the problem is NP-hard, and W[2]-hard when parameterized by the number of changes. Then we focus on unconstrained number of changes. We derive a polynomial-time algorithm when there is one source. When there are two sources, we show that the problem becomes NP-hard; on the other hand, we design an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution, that works for any number of sources. Finally, we provide polynomial-time algorithms for several graph classes.

PDF Details DOI

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.

AAAI Conference 2023 Conference Paper

Tight Inapproximability for Graphical Games

Argyrios Deligkas
John Fearnley
Alexandros Hollender
Themistoklis Melissourgos

We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: ε-Nash equilibria (ε-NE) and ε-well-supported Nash equilibria (ε-WSNE), where ε is in [0,1]. We prove that computing an ε-NE is PPAD-complete for any constant ε smaller than 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε smaller than 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.

PDF Details DOI

STOC Conference 2022 Conference Paper

Constant inapproximability for PPA

Argyrios Deligkas
John Fearnley
Alexandros Hollender
Themistoklis Melissourgos

In the ε-Consensus-Halving problem, we are given n probability measures v 1 , …, v n on the interval R = [0,1], and the goal is to partition R into two parts R + and R − using at most n cuts, so that | v i ( R + ) − v i ( R − )| ≤ ε for all i . This fundamental fair division problem was the first natural problem shown to be complete for the class PPA, and all subsequent PPA-completeness results for other natural problems have been obtained by reducing from it. We show that ε-Consensus-Halving is PPA-complete even when the parameter ε is a constant. In fact, we prove that this holds for any constant ε < 1/5. As a result, we obtain constant inapproximability results for all known natural PPA-complete problems, including Necklace-Splitting, the Discrete-Ham-Sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.

AAAI Conference 2022 Conference Paper

Heterogeneous Facility Location with Limited Resources

Argyrios Deligkas
Aris Filos-Ratsikas
Alexandros A. Voudouris

We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0, 1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

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.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Pizza Sharing Is PPA-Hard

Argyrios Deligkas
John Fearnley
Themistoklis Melissourgos

We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPAhard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPAhardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also prove that decision variants of the square-cut problem are hard: the approximate problem is NP-complete, and the exact problem is ETR-complete.

FOCS Conference 2022 Conference Paper

Pure-Circuit: Strong Inapproximability for PPAD

Argyrios Deligkas
John Fearnley
Alexandros Hollender
Themistoklis Melissourgos

The current state-of-the-art methods for showing inapproximability in PPAD arise from the $\varepsilon$-Generalized-Circuit ($\varepsilon$-GCIRCUIT) problem. Rubinstein (2018) showed that there exists a small unknown constant $\varepsilon$ for which $\varepsilon$-GCIRCUIT is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using $\varepsilon$-GCIRCUIT as an intermediate problem. We introduce PURE-CIRCUIT, a new intermediate problem for PPAD, which can be thought of as $\varepsilon$-GCIRCUIT pushed to the limit as $\varepsilon\rightarrow 1$, and we show that the problem is PPAD-complete. We then prove that $\varepsilon$-GCIRCUIT is PPAD-hard for all $\varepsilon \lt 0. 1$ by a reduction from PURE-CIRCUIT, and thus strengthen all prior work that has used GCIRCUIT as an intermediate problem from the existential-constant regime to the large-constant regime. We show that stronger inapproximability results can be derived by a direct reduction from PURE-CIRCUIT. In particular, we prove that finding an $\varepsilon$-well-supported Nash equilibrium in a polymatrix game is PPAD-hard for all $\varepsilon \lt 1/3$, and that this result is tight for two-action games.

IJCAI Conference 2022 Conference Paper

The Complexity of Envy-Free Graph Cutting

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

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 correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.

PDF Details DOI

MFCS Conference 2022 Conference Paper

The Complexity of Periodic Energy Minimisation

Duncan Adamson
Argyrios Deligkas
Vladimir V. Gusev
Igor Potapov

The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

AIJ Journal 2022 Journal Article

Two's company, three's a crowd: Consensus-halving for a constant number of agents

Argyrios Deligkas
Aris Filos-Ratsikas
Alexandros Hollender

We consider the ε-Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions that all of them simultaneously consider to be of approximately the same value (up to ε). This problem was recently shown to be PPA-complete, for n agents and n cuts, even for very simple valuation functions. In a quest to understand the root of the complexity of the problem, we consider the setting where there is only a constant number of agents, and we consider both the computational complexity and the query complexity of the problem. For agents with monotone valuation functions, we show a dichotomy: for two agents the problem is polynomial-time solvable, whereas for three or more agents it becomes PPA-complete. Similarly, we show that for two monotone agents the problem can be solved with polynomially-many queries, whereas for three or more agents, we provide exponential query complexity lower bounds. These results are enabled via an interesting connection to a monotone Borsuk-Ulam problem, which may be of independent interest. For agents with general valuations, we show that the problem is PPA-complete and admits exponential query complexity lower bounds, even for two agents.

IJCAI Conference 2021 Conference Paper

The Parameterized Complexity of Connected Fair Division

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Walrasian Equilibria in Markets with Small Demands

Argyrios Deligkas
Themistoklis Melissourgos
Paul G. Spirakis

We study the complexity of finding a Walrasian equilibrium in markets where the agents have 𝑘-demand valuations. These valuations are an extension of unit-demand valuations where a bundle’s value is the maximum of its 𝑘-subsets’ values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For 𝑘 = 2, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for 𝑘 = 3 the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.

MFCS Conference 2020 Conference Paper

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Argyrios Deligkas
George B. Mertzios
Paul G. Spirakis
Viktor Zamaraev

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0. 299862744n) = O(1. 23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0. 3n) = O(1. 2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0. 2971925n) = O(1. 22876ⁿ). Our algorithm is based on a fundamental structural property of Thomason’s lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ, Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

AAAI Conference 2020 Conference Paper

Optimizing Reachability Sets in Temporal Graphs by Delaying

Argyrios Deligkas
Igor Potapov

A temporal graph is a dynamic graph where every edge is assigned a set of integer time labels that indicate at which discrete time step the edge is available. In this paper, we study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources. The questions about reachability sets are motivated by numerous applications of temporal graphs in network epidemiology and scheduling problems in supply networks in manufacturing. We introduce control mechanisms for reachability sets that are based on two natural operations of delaying time events. The ﬁrst operation, termed merging, is global and batches together consecutive time labels in the whole network simultaneously. This corresponds to postponing all events until a particular time. The second, imposes independent delays on the time labels of every edge of the graph. We provide a thorough investigation of the computational complexity of different objectives related to reachability sets when these operations are used. For the merging operation, we prove NP-hardness results for several minimization and maximization reachability objectives, even for very simple graph structures. For the second operation, we prove that the minimization problems are NP-hard when the number of allowed delays is bounded. We complement this with a polynomial-time algorithm for the case of unbounded delays.

MFCS Conference 2018 Conference Paper

Directed Graph Minors and Serial-Parallel Width

Argyrios Deligkas
Reshef Meir

Graph minors are a primary tool in understanding the structure of undirected graphs, with many conceptual and algorithmic implications. We propose new variants of directed graph minors and directed graph embeddings, by modifying familiar definitions. For the class of 2-terminal directed acyclic graphs (TDAGs) our two definitions coincide, and the class is closed under both operations. The usefulness of our directed minor operations is demonstrated by characterizing all TDAGs with serial-parallel width at most k; a class of networks known to guarantee bounded negative externality in nonatomic routing games. Our characterization implies that a TDAG has serial-parallel width of 1 if and only if it is a directed series-parallel graph. We also study the computational complexity of finding a directed minor and computing the serial-parallel width.

AAMAS Conference 2018 Conference Paper

Heterogeneous Facility Location Games

Eleftherios Anastasiadis
Argyrios Deligkas

We study heterogeneous k-facility location games on a real line segment. In this model there are k facilities to be placed on a line segment where each facility serves a different purpose. Thus, the preferences of the agents over the facilities can vary arbitrarily. Our goal is to design strategy proof mechanisms that locate the facilities in a way to maximize the minimum utility among the agents. For k = 1, if the agents’ locations are known, we prove that the mechanism that locates the facility on an optimal location is strategy proof. Fork ≥ 2, we prove that there is no optimal strategy proof mechanism, deterministic or randomized, even when k = 2 and there are only two agents with known locations. We derive inapproximability bounds for deterministic and randomized strategy proof mechanisms. Finally, we provide strategy proof mechanisms that achieve constant approximation. All of our mechanisms are simple and communication efficient. As a byproduct we show that some of our mechanisms can be used to achieve constant factor approximations for other objectives as the social welfare and the happiness.

IJCAI Conference 2018 Conference Paper

Traffic Light Scheduling, Value of Time, and Incentives

Argyrios Deligkas
Erez Karpas
Ron Lavi
Rann Smorodinsky

We study the intersection signalling control problem for cars with heterogeneous valuations of time (VoT). We are interested in a control algorithm that has some desirable properties: (1) it induces cars to report their VoT truthfully, (2) it minimizes the value of time lost for cars waiting at the intersection, and (3) it is computationally efficient. We obtain three main results: (1) We describe a computationally efficient heuristic forward search approach to solve the static problem. Simulation results show that this method is significantly faster than the dynamic-programming approach to solve the static problem (which is by itself polynomial time). We therefore believe that our algorithm can be commercially implemented. (2) We extend the solution of the static problem to the dynamic case. We couple our algorithm with a carefully designed payment scheme which yields an incentive compatible mechanism. In other words, it is the best interest of each car to truthfully report its VoT. (3) We describe simulation results that compare the social welfare obtained by our scheduling algorithm, as measured by the total value of waiting time, to the social welfare obtained by other intersection signalling control methods.

MFCS Conference 2017 Conference Paper

Binary Search in Graphs Revisited

Argyrios Deligkas
George B. Mertzios
Paul G. Spirakis

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al. , STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex– the "median"–which minimises a potential \Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al. , namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential \Gamma that allows querying approximate medians.

AAAI Conference 2017 Conference Paper

The Computational Complexity of Weighted Greedy Matching

Argyrios Deligkas
George Mertzios
Paul Spirakis

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDY- MATCHING. In wide contrast to the maximum weight matching problem, for which many efﬁcient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bush graphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is ρ, then for every > 0 the randomized MRG algorithm of (Aronson et al. 1995) gives a (ρ − )-approximation for the maximum cardinality matching. We conjecture that a tight bound for ρ is 2 3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.

AAMAS Conference 2016 Conference Paper

An Empirical Study on Computing Equilibria in Polymatrix Games

Argyrios Deligkas
John Fearnley
Tobenna Peter Igwe
Rahul Savani

The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents. Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players. The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications. In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke’s algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium. Our study covers games arising from a number of interesting applications. We find that Lemke’s algorithm can compute exact equilibria in relatively large games in a reasonable amount of time. If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method. We also report on which games are most challenging for each of the algorithms. General Terms Algorithms, Economics

AAAI Conference 2014 Conference Paper

Increasing VCG Revenue by Decreasing the Quality of Items

Mingyu Guo
Argyrios Deligkas
Rahul Savani

The VCG mechanism is the standard method to incentivize bidders in combinatorial auctions to bid truthfully. Under the VCG mechanism, the auctioneer can sometimes increase revenue by “burning” items. We study this phenomenon in a setting where items are described by a number of attributes. The value of an attribute corresponds to a quality level, and bidders’ valuations are non-decreasing in the quality levels. In addition to burning items, we allow the auctioneer to present some of the attributes as lower quality than they actually are. We consider the following two revenue maximization problems under VCG: finding an optimal way to mark down items by reducing their quality levels, and finding an optimal set of items to burn. We study the effect of the following parameters on the computational complexity of these two problems: the number of attributes, the number of quality levels per attribute, and the complexity of the bidders’ valuation functions. Bidders have unit demand, so VCG’s outcome can be computed in polynomial time, and the valuation functions we consider are step functions that are non-decreasing with the quality levels. We prove that both problems are NP-hard even in the following three simple settings: a) four attributes, arbitrarily many quality levels per attribute, and single-step valuation functions, b) arbitrarily many attributes, two quality levels per attribute, and single-step valuation functions, and c) one attribute, arbitrarily many quality-levels, and multi-step valuation functions. For the case where items have only one attribute, and every bidder has a single-step valuation (zero below some quality threshold), we show that both problems can be solved in polynomial-time using a dynamic programming approach. For this case, we also quantify how much better marking down is than item burning, and we compare the revenue of both approaches with computational experiments.

IJCAI Conference 2013 Conference Paper

Revenue Maximization via Hiding Item Attributes

Mingyu Guo
Argyrios Deligkas

We study probabilistic single-item second-price auctions where the item is characterized by a set of attributes. The auctioneer knows the actual instantiation of all the attributes, but he may choose to reveal only a subset of these attributes to the bidders. Our model is an abstraction of the following Ad auction scenario. The website (auctioneer) knows the demographic information of its impressions, and this information is in terms of a list of attributes (e. g. , age, gender, country of location). The website may hide certain attributes from its advertisers (bidders) in order to create thicker market, which may lead to higher revenue. We study how to hide attributes in an optimal way. We show that it is NP-hard to compute the optimal attribute hiding scheme. We then derive a polynomial-time solvable upper bound on the optimal revenue. Finally, we propose two heuristicbased attribute hiding schemes. Experiments show that revenue achieved by these schemes is close to the upper bound.

PDF Details DOI