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.)
2022
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
to appear
[ bibtex | arXiv ]
2021
Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
Nelson Vadori, Rahul Savani, Thomas Spooner, and Sumitra Ganesh
[ bibtex | arXiv ]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 ]Trading via Selective Classification
Nestoras Chalkidis and Rahul Savani
ICAIF 2021
to appear
[ bibtex | arXiv ]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
The second author joined after the STACS version was published.
[ bibtex | arXiv | doi/url ]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 | doi/url ]
2020
A Natural Actor-Critic Algorithm with Downside Risk Constraints
Thomas Spooner and Rahul Savani
[ bibtex | arXiv ]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 ]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 ]Tree Polymatrix Games are PPAD-hard
Argyrios Deligkas, John Fearnley, 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 ]Robust Market Making via Adversarial Reinforcement Learning
Thomas Spooner and Rahul Savani
IJCAI 2020
(extended abstract at AAMAS 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 ]
2019
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 ]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 ]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 ]Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani
ICALP 2019
Journal version to appear in the Journal of Computer and System Sciences; this paper substantially revises and extends the work described in our previous preprint “End of Potential Line” (arXiv:1804.03450)
[ bibtex | arXiv | doi/url ]Evolving Indoor Navigational Strategies Using Gated Recurrent Units In NEAT
James Butterworth, Rahul Savani, and Karl Tuyls
GECCO 2019
(extended abstract)
[ bibtex | arXiv ]Negative Update Intervals in Deep Multi-Agent Reinforcement Learning
Gregory Palmer, Rahul Savani, and Karl Tuyls
AAMAS 2019
[ bibtex | arXiv | pdf ]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 ]
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 ]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 ]Inapproximability Results for Constrained Approximate Nash Equilibria
Argyrios Deligkas, John Fearnley, and Rahul Savani
Information and Computation 262, Part 1:40–56
Preliminary conference version appeared at WINE 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 ]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 ]Reachability Switching Games
John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani
ICALP 2018
[ bibtex | arXiv | pdf | doi/url ]Market Making via Reinforcement Learning
Thomas Spooner, John Fearnley, Rahul Savani, and Andreas Koukorinis
AAMAS 2018
[ bibtex | arXiv | pdf ]Lenient Multi-Agent Deep Reinforcement Learning
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani
AAMAS 2018
[ bibtex | arXiv | pdf ]
2017
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 ]CLS: New Problems and Completeness
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani
[ bibtex | arXiv ]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 ]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 ]
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 ]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 ]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 ]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 ]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 ]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 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 ]
2015
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 ]The Complexity of the Simplex Method
John Fearnley and Rahul Savani
STOC 2015
[ bibtex | arXiv | doi/url ]An empirical study of finding approximate equilibria in bimatrix games
John Fearnley, Tobenna Peter Igwe, and Rahul Savani
SEA 2015
[ bibtex | arXiv | doi/url ]
2014
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 ]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 ]Cooperative max games and agent failures
Yoram Bachrach, Rahul Savani, and Nisarg Shah
AAMAS 2014
[ bibtex | pdf | doi/url ]A Data Rich Money Market Model
Paul Devine and Rahul Savani
SIMULTECH 2014
[ bibtex ]Equilibrium Computation (Dagstuhl Seminar 14342)
Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, and Vijay V. Vazirani.
Dagstuhl Report.
[ bibtex | pdf | doi/url ]
2013
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 ]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 ]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 ]
2012
High-Frequency Trading: The Faster, the Better?
Rahul Savani
IEEE Intelligent Systems 27(4):70–73
[ bibtex | pdf | doi/url ]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 ]
2011
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 ]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 ]
2010
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 ]Linear Complementarity Algorithms for Infinite Games
John Fearnley, Marcin Jurdziński, and Rahul Savani
SOFSEM 2010
[ bibtex | arXiv | pdf | doi/url ]
2009
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 ]Wiretapping a Hidden Network
Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani
WINE 2009
[ bibtex | arXiv | pdf | doi/url ]Power Indices in Spanning Connectivity Games
Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani
AAIM 2009
[ bibtex | arXiv | pdf | doi/url ]Multi-strategy trading utilizing market regimes
Hynek Mlnařík, Subramaniam Ramamoorthy, and Rahul Savani.
Advances in Machine Learning for Computational Finance Workshop.
[ bibtex ]
2008
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 ]A Simple P-Matrix Linear Complementarity Problem for Discounted Games
Marcin Jurdziński and Rahul Savani
CiE 2008
[ 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
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 ]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 ]
2004
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 ]Challenge Instances for NASH
Rahul Savani.
Technical Report: CDAM Research Report LSE-CDAM-2004-14.
[ bibtex | doi/url ]