5 citations · 12 across the 11 of their papers we have counts for
16 papers
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…
Online EFX Allocations with Predictions
Themistoklis Melissourgos, Nicos Protopapas
We study an online fair division problem where a fixed number of goods arrive sequentially and must be allocated to a given set of agents. Once a good arrives, its true value for e…
On the Smoothed Complexity of Combinatorial Local Search
Yiannis Giannakopoulos, Alexander Grosz, Themistoklis Melissourgos
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems, and show how a diverse selection of problems within the complexity class PLS can…
Multi-Agent Systems for Computational Economics and Finance
Michael Kampouridis, Panagiotis Kanellopoulos, Maria Kyropoulou +2
In this article we survey the main research topics of our group at the University of Essex. Our research interests lie at the intersection of theoretical computer science, artifici…
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…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
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…
Pizza Sharing is PPA-hard
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an -approximate solution…
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…
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…
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete, we sho…
Strategic Contention Resolution in Multiple Channels
George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis
We consider the problem of resolving contention in communication networks with selfish users. In a \textit{contention game} each of identical players has a single inform…
Approximating the Existential Theory of the Reals
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos +1
The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of variables in $\mathbb{R}…
An extension of the Moran process using type-specific connection graphs
Themistoklis Melissourgos, Sotiris Nikoletseas, Christoforos Raptopoulos +1
The Moran process, as studied by [Lieberman, E., Hauert, C. and Nowak, M. Evolutionary dynamics on graphs. Nature 433, pp. 312-316 (2005)], is a stochastic process modeling the spr…
Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values
Themistoklis Melissourgos, Paul Spirakis
The concept of an evolutionarily stable strategy (ESS), introduced by Smith and Price, is a refinement of Nash equilibrium in 2-player symmetric games in order to explain counter-i…