27 citations · 187 across the 36 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…
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…
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…
One-Clock Priced Timed Games are PSPACE-hard
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponen…
An Improved Envy-Free Cake Cutting Protocol for Four Agents
Georgios Amanatidis, George Christodoulou, John Fearnley +3
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents,…
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…
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
John Fearnley, Tobenna Peter Igwe, Rahul Savani
While there have been a number of studies about the efficacy of methods to find exact Nash equilibria in bimatrix games, there has been little empirical work on finding approximate…
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…
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
John Fearnley, Rahul Savani
We study the deterministic and randomized query complexity of finding approximate equilibria in bimatrix games. We show that the deterministic query complexity of finding an -Na…
Learning Equilibria of Games via Payoff Queries
John Fearnley, Martin Gairing, Paul Goldberg +1
A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of th…
Approximate Well-supported Nash Equilibria below Two-thirds
John Fearnley, Paul W. Goldberg, Rahul Savani +1
In an epsilon-Nash equilibrium, a player can gain at most epsilon by changing his behaviour. Recent work has addressed the question of how best to compute epsilon-Nash equilibria,…
Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width
John Fearnley, Sven Schewe
Parity games are a much researched class of games in NP intersect CoNP that are not known to be in P. Consequently, researchers have considered specialised algorithms for the case…
Efficient Approximation of Optimal Control for Markov Games
John Fearnley, Markus Rabe, Sven Schewe +1
We study the time-bounded reachability problem for continuous-time Markov decision processes (CTMDPs) and games (CTMGs). Existing techniques for this problem use discretisation tec…
Playing Muller Games in a Hurry
John Fearnley, Martin Zimmermann
This work studies the following question: can plays in a Muller game be stopped after a finite number of moves and a winner be declared. A criterion to do this is sound if Player 0…
Non-oblivious Strategy Improvement
John Fearnley
We study strategy improvement algorithms for mean-payoff and parity games. We describe a structural property of these games, and we show that these structures can affect the behavi…
Linear Complementarity Algorithms for Infinite Games
John Fearnley, Marcin Jurdziński, Rahul Savani
The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity…