21 citations · 65 across the 25 of their papers we have counts for
21 papers · 1 filter
Constant Inapproximability for Fisher Markets
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was…
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, m…
Distributed Agent-Constrained Truthful Facility Location
Argyrios Deligkas, Panagiotis Kanellopoulos, Alexandros A. Voudouris
We study a distributed facility location problem in which a set of agents, each with a private position on the real line, is partitioned into a collection of fixed, disjoint groups…
Agent-Constrained Truthful Facility Location Games
Argyrios Deligkas, Mohammad Lotfi, Alexandros A. Voudouris
We consider a truthful facility location problem in which there is a set of agents with private locations on the line of real numbers, and the goal is to place a number of faciliti…
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 asso…
Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
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 appro…
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
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 polynom…
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute -ap…
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 lin…
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…
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…
Heterogeneous Facility Location Games
Eleftherios Anastasiadis, Argyrios Deligkas
We study heterogeneous -facility location games. In this model there are facilities where each facility serves a different purpose. Thus, the preferences of the agents over…
Path Polymatrix Games are PPAD-hard
Argyrios Deligkas, John Fearnley, Rahul Savani
We prove that it is PPAD-hard to compute a Nash equilibrium in a tree polymatrix game with at most twenty actions per player, and path polymatrix game with at most four hundred act…
Connected Subgraph Defense Games
Eleni C. Akrida, Argyrios Deligkas, Themistoklis Melissourgos +1
We study a security game over a network played between a and . Every attacker chooses, probabilistically, a node of the network to damage. The defender ch…
Learning Approximately Optimal Contracts
Alon Cohen, Moran Koren, Argyrios Deligkas
In principal-agent models, a principal offers a contract to an agent to perform a certain task. The agent exerts a level of effort that maximizes her utility. The principal is obli…
Computing Constrained Approximate Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Rahul Savani
This paper is about computing constrained approximate Nash equilibria in polymatrix games, which are succinctly represented many-player games defined by an interaction graph betwee…
Inapproximability Results for Approximate Nash Equilibria
Argyrios Deligkas, John Fearnley, Rahul Savani
We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem -NE -S…
An Empirical Study on Computing Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe +1
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…
Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis +3
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same t…
Lipschitz Continuity and Approximate Equilibria
Argyrios Deligkas, John Fearnley, Paul Spirakis
In this paper, we study games with continuous action spaces and non-linear payoff functions. Our key insight is that Lipschitz continuity of the payoff function allows us to provid…
Computing Approximate Nash Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Rahul Savani +1
In an -Nash equilibrium, a player can gain at most by unilaterally changing his behaviour. For two-player (bimatrix) games with payoffs in , the best-known achieva…