Publications
Below is the publication list with links to copies of the papers. The links labelled "pdf" are to files that are made available here for personal, non-commercial use only; those labelled "arXiv" link to full versions avialable on arXiv.org; and those labelled "doi"/"url" link to publishers' official web pages.
Key for publication type
- Refereed journal paper
- Refereed conference paper
- Preprint
- Other (book chapter, tech report, thesis etc.)
2023
The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani.
[ bibtex | arXiv ]Biased Recommender Systems And Supplier Competition
Amelia Fletcher, Peter L. Ormosi, Rahul Savani, and Jacopo Castellini.
Available on SSRN.
[ bibtex | doi/url ]First Order Methods for Geometric Optimization of Crystal Structures
Antonia Tsili, Matthew Dyer, Vladimir Gusev, Piotr Krysta, and Rahul Savani.
[ bibtex | arXiv ]Ordinal Potential-based Player Rating
Nelson Vadori and Rahul Savani.
[ bibtex | arXiv ]Conditional Generators for Limit Order Book Environments: Explainability, Challenges, and Robustness
Andrea Coletta, Joseph Jerome, Rahul Savani, and Svitlana Vytrenko.
ICAIF 2023
[ bibtex | arXiv | doi/url ]Mbt-gym: Reinforcement learning for model-based limit order book trading
Joseph Jerome, Leandro Sánchez-Betancourt, Rahul Savani, and Martin Herdegen.
ICAIF 2023
[ bibtex | arXiv | doi/url ]The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani.
Journal of the ACM
Preliminary conference version appeared at STOC 2021
[ bibtex | arXiv | doi/url ]Recommender systems and supplier competition on platforms
Amelia Fletcher, Peter L. Ormosi, and Rahul Savani.
Journal of Competition Law & Economics
Also available on SSRN
[ bibtex | doi/url ]Reinforcement Learning in Crystal Structure Prediction
Elena Zamaraeva, Christopher M. Collins, Dmytro Antypov, Vladimir V. Gusev, Rahul Savani, Matthew S. Dyer, George R. Darling, Igor Potapov, Matthew J. Rosseinsky, and Paul G. Spirakis.
Digital Discovery
[ bibtex | arXiv | doi/url ]
2022
Generative Models over Neural Controllers for Transfer Learning
James Butterworth, Rahul Savani, and Karl Tuyls.
PPSN 2022
[ bibtex | doi/url ]Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent
Ian Gemp, Rahul Savani, Marc Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, Andrea Tacchetti, Tom Eccles, and János Kramár.
AAMAS 2022
[ bibtex | arXiv | doi/url ]Market Making with Scaled Beta Policies
Joseph Jerome, Gregory Palmer, and Rahul Savani.
ICAIF 2022
[ bibtex | arXiv | doi/url ]Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
Nelson Vadori, Rahul Savani, Thomas Spooner, and Sumitra Ganesh.
ICML 2022
[ bibtex | arXiv | pdf | doi/url ]Difference Rewards Policy Gradients
Jacopo Castellini, Sam Devlin, Frans Oliehoek, and Rahul Savani.
Neural Computing and Applications
Preliminary version appeared at ALA 2021
[ bibtex | arXiv | doi/url ]A faster algorithm for finding Tarski fixed points
John Fearnley, Dömötör Pálvölgyi, and Rahul Savani.
ACM Transactions on Algorithms
Preliminary conference version appeared at STACS 2021
[ bibtex | arXiv | doi/url ]
2021
Difference Rewards Policy Gradients
Jacopo Castellini, Sam Devlin, Frans Oliehoek, and Rahul Savani.
ALA 2021 (Best Paper Award)
(extended abstract at AAMAS 2021)
[ bibtex | arXiv ]Trading via Selective Classification
Nestoras Chalkidis and Rahul Savani.
ICAIF 2021
[ bibtex | arXiv | doi/url ]The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani.
STOC 2021 (Best Paper Award)
[ bibtex | arXiv | pdf | doi/url ]A faster algorithm for finding Tarski fixed points
John Fearnley, Dömötör Pálvölgyi, and Rahul Savani.
STACS 2021
Journal version in ACM Transactions on Algorithms; the second author joined after the STACS version was published.
[ bibtex | arXiv | doi/url ]Analysing Factorizations of Action-Value Networks for Cooperative Multi-Agent Reinforcement Learning
Jacopo Castellini, Frans Oliehoek, Rahul Savani, and Shimon Whiteson.
Autonomous Agents and Multi-Agent Systems 35:25:53 pages
Preliminary version appeared as an extended abstract at AAMAS 2019
[ bibtex | arXiv | doi/url ]Reachability Switching Games
John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani.
Logical Methods in Computer Science
Preliminary conference version appeared at ICALP 2018
[ bibtex | arXiv | doi/url ]A Deep Learning Approach to Identify Unhealthy Advertisements in Street View Images
Gregory Palmer, Mark Green, Emma Boyland, Yales Stefano Rios Vasconcelos, Rahul Savani, and Alex Singleton.
Scientific Reports 11:4884:12 pages
[ bibtex | arXiv | doi/url ]
2020
A Natural Actor-Critic Algorithm with Downside Risk Constraints
Thomas Spooner and Rahul Savani.
[ bibtex | arXiv ]Tree Polymatrix Games are PPAD-hard
Argyrios Deligkas, John Fearnley, and and Rahul Savani.
ICALP 2020
[ bibtex | arXiv | doi/url ]One-Clock Priced Timed Games are PSPACE-hard
John Fearnley, Rasmus Ibsen-Jensen, and Rahul Savani.
LICS 2020
[ bibtex | arXiv | doi/url ]The Automated Inspection of Opaque Liquid Vaccines
Gregory Palmer, Benjamin Schnieders, Rahul Savani, Karl Tuyls, Joscha-David Fossel, and Harry Flore.
ECAI 2020
[ bibtex | arXiv | doi/url ]Robust Market Making via Adversarial Reinforcement Learning
Thomas Spooner and Rahul Savani.
IJCAI 2020
(extended abstract at AAMAS 2020)
[ bibtex | arXiv | doi/url ]Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.
Journal of Computer and System Sciences 114:1–35
Preliminary conference version appeared at ICALP 2019; this paper substantially revises and extends the work described in our previous preprint “End of Potential Line” (arXiv:1804.03450)
[ bibtex | arXiv | doi/url ]Mapping the Geodemographics of Digital Inequality in Great Britain
Alex Singleton, Alexandros Alexiou, and Rahul Savani.
Computers, Environment and Urban Systems 82:20 pages
[ bibtex | doi/url ]Bayesian optimisation of restriction zones for bluetongue control
Thomas Spooner, Anne E Jones, John Fearnley, Rahul Savani, Joanne Turner, and Matthew Baylis.
Scientific Reports 10:15139:18 pages
[ bibtex | doi/url ]
2019
Evolving Indoor Navigational Strategies Using Gated Recurrent Units In NEAT
James Butterworth, Rahul Savani, and Karl Tuyls.
GECCO 2019
(extended abstract)
[ bibtex | arXiv ]The Representational Capacity of Action-Value Networks for Multi-Agent Reinforcement Learning
Jacopo Castellini, Frans Oliehoek, Rahul Savani, and Shimon Whiteson.
AAMAS 2019
(extended abstract)
[ bibtex | arXiv | pdf ]Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.
ICALP 2019
Journal version in the Journal of Computer and System Sciences (2020); this paper substantially revises and extends the work described in our previous preprint “End of Potential Line” (arXiv:1804.03450)
[ bibtex | arXiv | doi/url ]Negative Update Intervals in Deep Multi-Agent Reinforcement Learning
Gregory Palmer, Rahul Savani, and Karl Tuyls.
AAMAS 2019
[ bibtex | arXiv | pdf ]Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzínski, and Rahul Savani.
Algorithmica 81:1205-1231
Preliminary conference version appeared at WINE 2016
[ bibtex | arXiv | doi/url ]Computing Stable Outcomes in Symmetric Additively-Separable Hedonic Games
Martin Gairing and Rahul Savani.
Mathematics of Operations Research 44:1101–1121
Combines preliminary conference versions from SAGT 2010 and AAMAS 2011
[ bibtex | arXiv | doi/url ]Preface to the Special Issue on Algorithmic Game Theory
Martin Gairing and Rahul Savani.
Theory of Computing Systems 63:2-3
Special issue for SAGT 2016
[ bibtex | doi/url ]
2018
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.
This paper has been subsumed by our follow-up work “Unique End of Potential Line” (ICALP 2019)
[ bibtex | arXiv ]Reachability Switching Games
John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani.
ICALP 2018
[ bibtex | arXiv | pdf | doi/url ]Beyond Local Nash Equilibria for Adversarial Networks
Frans A. Oliehoek, Rahul Savani, Jose Gallego-Posada, Elise van der Pol, and Roderich Gross.
BNAIC 2018
[ bibtex | arXiv | doi/url ]Lenient Multi-Agent Deep Reinforcement Learning
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani.
AAMAS 2018
[ bibtex | arXiv | pdf ]Market Making via Reinforcement Learning
Thomas Spooner, John Fearnley, Rahul Savani, and Andreas Koukorinis.
AAMAS 2018
[ bibtex | arXiv | pdf ]Inapproximability Results for Constrained Approximate Nash Equilibria
Argyrios Deligkas, John Fearnley, and and Rahul Savani.
Information and Computation 262, Part 1:40–56
Preliminary conference version appeared at WINE 2016
[ bibtex | arXiv | doi/url ]The Complexity of All-switches Strategy Improvement
John Fearnley and Rahul Savani.
Logical Methods in Computer Science 14:57 pages
Preliminary conference version appeared at SODA 2016
[ bibtex | arXiv | doi/url ]Space Debris Removal: Learning to Cooperate and the Price of Anarchy
Richard Klima, Daan Bloembergen, Rahul Savani, Karl Tuyls, Alexander Wittig, Andrei Sapera, and Dario Izzo.
Frontiers in Robotics and AI 5:22 pages
[ bibtex | doi/url ]Symmetric Decomposition of Asymmetric Games
Karl Tuyls, Julien Perolat, Marc Lanctot, Georg Ostrovski, Rahul Savani, Joel Leibo, Toby Ord, Thore Graepel, and Shane Legg.
Scientific Reports 8:Article number: 1015 (20 pages)
[ bibtex | arXiv | doi/url ]
2017
CLS: New Problems and Completeness
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.
[ bibtex | arXiv ]GANGs: Generative Adversarial Network Games
Frans A. Oliehoek, Rahul Savani, Jose Gallego-Posada, Elise van der Pol, Edwin D. de Jong, and Roderich Gross.
[ bibtex | arXiv ]Computing Constrained Approximate Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, and Rahul Savani.
SAGT 2017
[ bibtex | arXiv | doi/url ]LiftUpp: Support to develop learner performance
Frans A. Oliehoek, Rahul Savani, Elliot Adderton, Xia Cui, David Jackson, Phil Jimmieson, John Christopher Jones, Keith Kennedy, Ben Mason, Adam Plumbley, and Luke Dawson.
AIED 2017
[ bibtex | arXiv | doi/url ]Computing Approximate Nash Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis.
Algorithmica 77:487–514
Preliminary conference version appeared at WINE 2014
[ bibtex | arXiv | doi/url ]
2016
Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT) .
Martin Gairing and Rahul Savani, editors.
volume 9928 of Lecture Notes in Computer Science Springer, 2016.
[ bibtex | doi/url ]Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzínski, and Rahul Savani.
WINE 2016
Journal version in Algorithmica (2019)
[ bibtex | arXiv | doi/url ]Inapproximability Results for Approximate Nash Equilibria
Argyrios Deligkas, John Fearnley, and and Rahul Savani.
WINE 2016
Journal version in Information and Computation (2018)
[ bibtex | arXiv | doi/url ]An Empirical Study on Computing Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, and Rahul Savani.
AAMAS 2016
[ bibtex | arXiv | pdf | doi/url ]The Complexity of All-switches Strategy Improvement
John Fearnley and Rahul Savani.
SODA 2016
[ bibtex | arXiv | doi/url ]Hedonic Games
Haris Aziz and Rahul Savani.
Chapter 15, Handbook of Computational Social Choice.
Cambridge University Press.
An official copy of the whole book can be found under the resources tab at the official publisher's site: http://www.cambridge.org/9781107060432. It requires the password: cam1CSC.
[ bibtex | pdf | doi/url ]Approximate Well-Supported Nash Equilibria Below Two-Thirds
John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen.
Algorithmica 76:297-319
Preliminary conference version appeared at SAGT 2012
[ bibtex | arXiv | doi/url ]Finding approximate Nash equilibria of bimatrix games via payoff queries
John Fearnley and Rahul Savani.
ACM Transactions on Economics and Computation 4:Article 25, 19 pages
Invited to special issue for EC 2014
[ bibtex | arXiv | doi/url ]Space Debris Removal: A Game Theoretic Analysis
Richard Klima, Daan Bloembergen, Rahul Savani, Karl Tuyls, Daniel Hennes, and Dario Izzo.
Games 7:Issue 3, Article 20
Short version appeared in: Proc. of the European Conference on Artificial Intelligence (ECAI)
[ bibtex | pdf | doi/url ]Unit Vector Games
Rahul Savani and Bernhard von Stengel.
International Journal of Economic Theory 12:7-27
By invitation
[ bibtex | arXiv | doi/url ]
2015
An empirical study of finding approximate equilibria in bimatrix games
John Fearnley, Tobenna Peter Igwe, and Rahul Savani.
SEA 2015
[ bibtex | arXiv | doi/url ]The Complexity of the Simplex Method
John Fearnley and Rahul Savani.
STOC 2015
[ bibtex | arXiv | doi/url ]Learning equilibria of games via payoff queries
John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
Journal of Machine Learning Research 16:1305-1344
Preliminary conference version appeared at EC 2013
[ bibtex | arXiv | doi/url ]Game Theory Explorer: software for the applied game theorist
Rahul Savani and Bernhard von Stengel.
Computational Management Science 12(1):5–13
[ bibtex | arXiv | doi/url ]
2014
Equilibrium Computation (Dagstuhl Seminar 14342)
Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, and Vijay V. Vazirani.
Dagstuhl Report.
[ bibtex | pdf | doi/url ]Cooperative max games and agent failures
Yoram Bachrach, Rahul Savani, and Nisarg Shah.
AAMAS 2014
[ bibtex | pdf | doi/url ]Computing Approximate Nash Equilibria in Polymatrix Games
Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis.
WINE 2014
Journal version in Algorithmica (2017)
[ bibtex | arXiv | doi/url ]A Data Rich Money Market Model
Paul Devine and Rahul Savani.
SIMULTECH 2014
[ bibtex ]Finding approximate Nash equilibria of bimatrix games via payoff queries
John Fearnley and Rahul Savani.
EC 2014
Journal version in TEAC (2016)
[ bibtex | arXiv | doi/url ]Increasing VCG Revenue by Decreasing the Quality of Items
Mingyu Guo, Argyrios Deligkas, and Rahul Savani.
AAAI 2014
[ bibtex | pdf | doi/url ]
2013
Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3
Yogesh Anbalagan, Sergey Norin, Rahul Savani, and Adrian Vetta.
WINE 2013
[ bibtex | arXiv | doi/url ]Learning equilibria of games via payoff queries
John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
EC 2013
Journal version in JMLR (2015)
[ bibtex | arXiv | doi/url ]The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani.
ACM Transactions on Economics and Computation 1(2):Article 9, 25 pages
Preliminary conference version appeared at FOCS 2011
[ bibtex | arXiv | doi/url ]On the approximation performance of fictitious play in finite games
Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, and Carmine Ventre.
International Journal of Game Theory 42(4):1059–1083
Preliminary conference version appeared at ESA 2011
[ bibtex | arXiv | doi/url ]
2012
Approximate Well-Supported Nash Equilibria Below Two-Thirds
John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen.
SAGT 2012
Journal version in Algorithmica (2016)
[ bibtex | arXiv | doi/url ]High-Frequency Trading: The Faster, the Better?
Rahul Savani.
IEEE Intelligent Systems 27(4):70–73
[ bibtex | pdf | doi/url ]
2011
Computing stable outcomes in hedonic games with voting-based deviations
Martin Gairing and Rahul Savani.
AAMAS 2011
Journal version in Mathematics of Operations Research (2019)
[ bibtex | pdf | doi/url ]The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani.
FOCS 2011
Journal version in TEAC (2013)
[ bibtex | arXiv | doi/url ]On the Approximation Performance of Fictitious Play in Finite Games
Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, and Carmine Ventre.
ESA 2011
Journal version in IJGT (2013)
[ bibtex | arXiv | doi/url ]
2010
Linear Complementarity Algorithms for Infinite Games
John Fearnley, Marcin Jurdziński, and Rahul Savani.
SOFSEM 2010
[ bibtex | arXiv | pdf | doi/url ]Computing Stable Outcomes in Hedonic Games
Martin Gairing and Rahul Savani.
SAGT 2010
Journal version in Mathematics of Operations Research (2019)
[ bibtex | pdf | doi/url ]
2009
Multi-strategy trading utilizing market regimes
Hynek Mlnařík, Subramaniam Ramamoorthy, and Rahul Savani.
Advances in Machine Learning for Computational Finance Workshop.
[ bibtex ]Power Indices in Spanning Connectivity Games
Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani.
AAIM 2009
[ bibtex | arXiv | pdf | doi/url ]Wiretapping a Hidden Network
Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani.
WINE 2009
[ bibtex | arXiv | pdf | doi/url ]Enumeration of Nash equilibria for two-player games
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel.
Economic Theory 42(1):9–37
[ bibtex | pdf | doi/url ]
2008
A Simple P-Matrix Linear Complementarity Problem for Discounted Games
Marcin Jurdziński and Rahul Savani.
CiE 2008
[ bibtex | pdf | doi/url ]Good neighbors are hard to find: computational complexity of network formation
Richard Baron, Jacques Durieu, Hans Haller, Rahul Savani, and Philippe Solal.
Review of Economic Design 12(1):1–19
[ bibtex | pdf | doi/url ]
2006
Finding Nash equilibria of bimatrix games
Rahul Savani.
PhD thesis, London School of Economics, 2006.
[ bibtex | pdf | doi/url ]Hard-to-Solve Bimatrix Games
Rahul Savani and Bernhard von Stengel.
Econometrica 74(2):397–429
Preliminary conference version appeared at FOCS 2004
[ bibtex | pdf | doi/url ]
2005
A Novel Strategy for the Penn-Lehman Automated Trading Competition
Rahul Savani and Ben Veal.
Technical Report: CDAM Research Report LSE-CDAM-2005-12.
[ bibtex | doi/url ]Mixed-species aggregations in birds: zenaida doves, Zenaida aurita, respond to the alarm calls of carib grackles, Quiscalus lugubris
Andrea S. Griffin, Rahul Savani, Kristina Hausmanis, and Louis Lefebvre.
Animal Behaviour 70(3):507–515
[ bibtex | pdf | doi/url ]
2004
Challenge Instances for NASH
Rahul Savani.
Technical Report: CDAM Research Report LSE-CDAM-2004-14.
[ bibtex | doi/url ]Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game
R. Savani and B. von Stengel.
FOCS 2004
Journal version in Econometrica (2006)
[ bibtex | pdf | doi/url ]