John Fearnley

STOC Conference 2025 Conference Paper

Monotone Contractions

• Eleni Batziou
• John Fearnley
• Spencer Gordon
• Ruta Mehta
• Rahul Savani

STOC Conference 2024 Conference Paper

The Complexity of Computing KKT Solutions of Quadratic Programs

• John Fearnley
• Paul W. Goldberg
• Alexandros Hollender
• Rahul Savani

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.

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

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.

STOC Conference 2021 Conference Paper

The complexity of gradient descent: CLS = PPAD ∩ PLS

• John Fearnley
• Paul W. Goldberg
• Alexandros Hollender
• Rahul Savani

We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1] 2 is PPAD ∩ PLS-complete. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more “natural” counterpart to PPAD ∩ PLS and contains many interesting problems - is itself equal to PPAD ∩ PLS.

I&C Journal 2018 Journal Article

Inapproximability results for constrained 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 δ-SW: find an ϵ-approximate Nash equilibrium (ϵ-NE) that is within δ of the best social welfare achievable by an ϵ-NE. Our main result is that, if the exponential-time hypothesis (ETH) is true, then solving ( 1 8 − O ( δ ) ) -NE O ( δ ) -SW for an n × n bimatrix game requires n Ω ˜ ( log ⁡ n ) time. Building on this result, we show similar conditional running time lower bounds for a number of other decision problems for ϵ-NE, where, for example, the payoffs or supports of players are constrained. We show quasi-polynomial lower bounds for these problems assuming ETH, where these lower bounds apply to ϵ-Nash equilibria for all ϵ < 1 8. The hardness of these other decision problems has so far only been studied in the context of exact equilibria.

AAMAS Conference 2018 Conference Paper

Market Making via Reinforcement Learning

• Thomas Spooner
• John Fearnley
• Rahul Savani
• Andreas Koukorinis

Market making is a fundamental trading problem in which an agent provides liquidity by continually offering to buy and sell a security. The problem is challenging due to inventory risk, the risk of accumulating an unfavourable position and ultimately losing money. In this paper, we develop a high-fidelity simulation of limit order book markets, and use it to design a market making agent using temporal-difference reinforcement learning. We use a linear combination of tile codings as a value function approximator, and design a custom reward function that controls inventory risk. We demonstrate the effectiveness of our approach by showing that our agent outperforms both simple benchmark strategies and a recent online learning approach from the literature.

Highlights Conference 2017 Conference Abstract

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space

• John Fearnley
• Sanjay Jain
• Sven Schewe
• Frank Stephan
• Dominik Wojtczak

Abstract available in PDF.

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

I&C Journal 2016 Journal Article

Efficient approximation of optimal control for continuous-time Markov games

• John Fearnley
• Markus N. Rabe
• Sven Schewe
• Lijun Zhang

We study the time-bounded reachability problem for continuous-time Markov decision processes (CTMDPs) and games (CTMGs). Existing techniques for this problem use discretisation techniques to partition time into discrete intervals of size ε, and optimal control is approximated for each interval separately. Current techniques provide an accuracy of O ( ε 2 ) on each interval, which leads to an infeasibly large number of intervals. We propose a sequence of approximations that achieve accuracies of O ( ε 3 ), O ( ε 4 ), and O ( ε 5 ), that allow us to drastically reduce the number of intervals that are considered. For CTMDPs, the performance of the resulting algorithms is comparable to the heuristic approach given by Buchholz and Schulz, while also being theoretically justified. All of our results generalise to CTMGs, where our results yield the first practically implementable algorithms for this problem. We also provide memoryless strategies for both players that achieve similar error bounds.

SODA Conference 2016 Conference Paper

The Complexity of All-switches Strategy Improvement

• John Fearnley
• Rahul Savani

Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parametrized by a switching rule, and one of the most natural rules is “all switches” which switches as many edges as possible in each iteration. Continuing a recent line of work, we study all-switches strategy improvement from the perspective of computational complexity. We consider two natural decision problems, both of which have as input a game G, a starting strategy s, and an edge e. The problems are: 1. The edge switch problem, namely, is the edge e ever switched by all-switches strategy improvement when it is started from s on game G? 2. The optimal strategy problem, namely, is the edge e used in the final strategy that is found by strategy improvement when it is started from s on game G? We show PSPACE-completeness of the edge switch problem and optimal strategy problem for the following settings: Parity games with the discrete strategy improvement algorithm of Vöge and Jurdziński; mean-payoff games with the gain-bias algorithm [11, 33]; and discounted-payoff games and simple stochastic games with their standard strategy improvement algorithms. We also show PSPACE-completeness of an analogous problem to edge switch for the bottom-antipodal algorithm for Acyclic Unique Sink Orientations on Cubes.

JMLR Journal 2015 Journal Article

Learning Equilibria of Games via Payoff Queries

• John Fearnley
• Martin Gairing
• Paul W. Goldberg
• Rahul Savani

A recent body of experimental literature has studied {\em empirical game-theoretical analysis}, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for exact equilibria of bimatrix and graphical games. We then study the query complexity of approximate equilibria in bimatrix games. Finally, we study the query complexity of exact equilibria in symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

I&C Journal 2015 Journal Article

Reachability in two-clock timed automata is PSPACE-complete

• John Fearnley
• Marcin Jurdziński

Recently, Haase, Ouaknine, and Worrell have shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.

STOC Conference 2015 Conference Paper

The Complexity of the Simplex Method

• John Fearnley
• Rahul Savani

The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE-complete to find the solution that is computed by the simplex method using Dantzig's pivot rule. Secondly, we prove that deciding whether Dantzig's rule ever chooses a specific variable to enter the basis is PSPACE-complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig's pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and then show PSPACE-completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.

CSL Conference 2012 Conference Paper

Bounded Satisfiability for PCTL

• Nathalie Bertrand 0001
• John Fearnley
• Sven Schewe

While model checking PCTL for Markov chains is decidable in polynomial-time, the decidability of PCTL satisfiability is a long standing open problem. While general satisfiability is an intriguing challenge from a purely theoretical point of view, we argue that general solutions would not be of interest to practitioners: such solutions could be too big to be implementable or even infinite. Inspired by bounded synthesis techniques, we turn to the more applied problem of seeking models of a bounded size: we restrict our search to implementable - and therefore reasonably simple - models. We propose a procedure to decide whether or not a given PCTL formula has an implementable model by reducing it to an SMT problem. We have implemented our techniques and found that they can be applied to the practical problem of sanity checking - a procedure that allows a system designer to check whether their formula has an unexpectedly small model.

MFCS Conference 2011 Conference Paper

Parity Games on Graphs with Medium Tree-Width

• John Fearnley
• Oded Lachish

Abstract This paper studies the problem of solving parity games on graphs with bounded tree-width. Previous work by Obdržálek has produced an algorithm that uses \(n^{O(k^2)}\) time and \(n^{O(k^2)}\) space, where k is the tree-width of the graph that the game is played on. This paper presents an algorithm that uses n O ( k log n ) time and O ( n + k log n ) space. This is the fastest known algorithm for parity games whose tree-width k satisfies (in standard asymptotic notation) k ∈ ω (log n ) and \(k \in o(\sqrt{n}/\log n)\).

GandALF Workshop 2010 Workshop Paper

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 wins an infinite-duration Muller game if and only if she wins the finite-duration version. A sound criterion is presented that stops a play after at most 3^n moves, where n is the size of the arena. This improves the bound (n! +1)^n obtained by McNaughton and the bound n! +1 derived from a reduction to parity games.