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.)

2021

• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
  Nelson Vadoori, Rahul Savani, Thomas Spooner, and Sumitra Ganesh
  [ bibtex | arXiv  ]

  ---

• 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
  [ 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  ]

  ---

• 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  ]

  ---