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

2017

• John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.
  CLS: New Problems and Completeness.
  [ bibtex ] [ arXiv ]
• 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.
  LiftUpp: Support to develop learner performance.
  [ bibtex ] [ arXiv ]
• Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis.
  Computing Approximate Nash Equilibria in Polymatrix Games.
  Algorithmica, 77:487–514.
  Preliminary conference version appeared at WINE 2014.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Argyrios Deligkas, John Fearnley, and Rahul Savani.
  Computing Constrained Approximate Equilibria in Polymatrix Games.
  In Proc. of the Symposium on Algorithmic Game Theory (SAGT), To appear.
  [ bibtex ] [ arXiv ]

2016

• Martin Gairing and Rahul Savani, editors.
  Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT).
  volume 9928 of Lecture Notes in Computer Science Springer, 2016.
  [ bibtex ] [ doi/url ]
• Haris Aziz and Rahul Savani.
  Hedonic Games.
  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 ]
• Richard Klima, Daan Bloembergen, Rahul Savani, Karl Tuyls, Daniel Hennes, and Dario Izzo.
  Space Debris Removal: A Game Theoretic Analysis.
  Games, 7:Issue 3, Article 20.
  Short version appeared in: Proc. of the European Conference on Artificial Intelligence (ECAI).
  [ bibtex ] [ pdf ] [ doi/url ]
• Rahul Savani and Bernhard von Stengel.
  Unit Vector Games.
  International Journal of Economic Theory, 12:7-27.
  By invitation.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley and Rahul Savani.
  Finding approximate Nash equilibria of bimatrix games via payoff queries.
  ACM Transactions on Economics and Computation, 4:Article 25, 19 pages.
  Invited to special issue for EC 2014.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen.
  Approximate Well-Supported Nash Equilibria Below Two-Thirds.
  Algorithmica, 76:297-319.
  Preliminary conference version appeared at SAGT 2012.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzínski, and Rahul Savani.
  Distributed Methods for Computing Approximate Equilibria.
  In Proc. of the Conference on Web and Internet Economics (WINE), 15–28.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Argyrios Deligkas, John Fearnley, and Rahul Savani.
  Inapproximability Results for Approximate Nash Equilibria.
  In Proc. of the Conference on Web and Internet Economics (WINE), 29–43.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, and Rahul Savani.
  An Empirical Study on Computing Equilibria in Polymatrix Games.
  In Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 186–195.
  [ bibtex ] [ arXiv ] [ pdf ] [ doi/url ]
• John Fearnley and Rahul Savani.
  The Complexity of All-switches Strategy Improvement.
  In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 130–139.
  [ bibtex ] [ arXiv ] [ doi/url ]

2015

• John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
  Learning equilibria of games via payoff queries.
  Journal of Machine Learning Research, 16:1305-1344.
  Preliminary conference version appeared at EC 2013.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Rahul Savani and Bernhard von Stengel.
  Game Theory Explorer: software for the applied game theorist.
  Computational Management Science, 12(1):5–13.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley and Rahul Savani.
  The Complexity of the Simplex Method.
  In Proc. of the ACM Symposium on Theory of Computing (STOC), 201–208.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley, Tobenna Peter Igwe, and Rahul Savani.
  An empirical study of finding approximate equilibria in bimatrix games.
  In Proc. of the International Symposium on Experimental Algorithms (SEA), 339–351.
  [ bibtex ] [ arXiv ] [ doi/url ]

2014

• Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis.
  Computing Approximate Nash Equilibria in Polymatrix Games.
  In Proc. of the Conference on Web and Internet Economics (WINE), 58–71.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley and Rahul Savani.
  Finding approximate Nash equilibria of bimatrix games via payoff queries.
  In Proc. of the ACM conference on Economics and Computation (EC), 657–674.
  Journal version will appear in TEAC.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Mingyu Guo, Argyrios Deligkas, and Rahul Savani.
  Increasing VCG Revenue by Decreasing the Quality of Items.
  In Proc. of the AAAI Conference on Artificial Intelligence (AAAI), 705–711.
  [ bibtex ] [ pdf ] [ doi/url ]
• Yoram Bachrach, Rahul Savani, and Nisarg Shah.
  Cooperative max games and agent failures.
  In Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 29–36.
  [ bibtex ] [ pdf ] [ doi/url ]
• Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, and Vijay V. Vazirani.
  Equilibrium Computation (Dagstuhl Seminar 14342).
  Dagstuhl Report.
  [ bibtex ] [ pdf ] [ doi/url ]
• Paul Devine and Rahul Savani.
  A Data Rich Money Market Model.
  In Proc. of the International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), 231-236.
  [ bibtex ]

2013

• Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, and Carmine Ventre.
  On the approximation performance of fictitious play in finite games.
  International Journal of Game Theory, 42(4):1059–1083.
  Preliminary conference version appeared at ESA 2011.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani.
  The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
  ACM Transactions on Economics and Computation, 1(2):Article 9, 25 pages.
  Preliminary conference version appeared at FOCS 2011.
  [ bibtex ] [ arXiv ] [ doi/url ]
• Yogesh Anbalagan, Sergey Norin, Rahul Savani, and Adrian Vetta.
  Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3.
  In Proc. of the Conference on Web and Internet Economics (WINE), 15–23.
  [ bibtex ] [ arXiv ] [ doi/url ]
• John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
  Learning equilibria of games via payoff queries.
  In Proc. of the ACM conference on Electronic Commerce (EC), 397–414.
  Journal version will appear in JMLR.
  [ bibtex ] [ arXiv ] [ doi/url ]

2012

• Rahul Savani.
  High-Frequency Trading: The Faster, the Better?
  IEEE Intelligent Systems, 27(4):70–73.
  [ bibtex ] [ doi/url ]
• John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen.
  Approximate Well-Supported Nash Equilibria Below Two-Thirds.
  In Proc. of the Symposium on Algorithmic Game Theory (SAGT), 108–119.
  [ bibtex ] [ arXiv ] [ doi/url ]

2011

• Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani.
  The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
  In Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS), 67–76.
  Journal version appeared in TEAC (2013).
  [ bibtex ] [ arXiv ] [ doi/url ]
• Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, and Carmine Ventre.
  On the Approximation Performance of Fictitious Play in Finite Games.
  In Proc. of the European Symposium on Algorithms (ESA), 93–105.
  Journal version appeared in IJGT (2013).
  [ bibtex ] [ arXiv ] [ doi/url ]
• Martin Gairing and Rahul Savani.
  Computing stable outcomes in hedonic games with voting-based deviations.
  In Proc. of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 559–566.
  [ bibtex ] [ pdf ] [ doi/url ]

2010

• Martin Gairing and Rahul Savani.
  Computing Stable Outcomes in Hedonic Games.
  In Proc. of the Symposium on Algorithmic Game Theory (SAGT), 174–185.
  [ bibtex ] [ pdf ] [ doi/url ]
• John Fearnley, Marcin Jurdziński, and Rahul Savani.
  Linear Complementarity Algorithms for Infinite Games.
  In Proc. of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 382–393.
  [ bibtex ] [ arXiv ] [ pdf ] [ doi/url ]

2009

• David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel.
  Enumeration of Nash equilibria for two-player games.
  Economic Theory, 42(1):9–37.
  [ bibtex ] [ pdf ] [ doi/url ]
• Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani.
  Wiretapping a Hidden Network.
  In Proc. of the Workshop on Internet and Network Economics (WINE), 438–446.
  [ bibtex ] [ arXiv ] [ pdf ] [ doi/url ]
• Haris Aziz, Oded Lachish, Mike Paterson, and Rahul Savani.
  Power Indices in Spanning Connectivity Games.
  In Proc. of the International Conference on Algorithmic Aspects in Information and Management (AAIM), 55–67.
  [ bibtex ] [ arXiv ] [ pdf ] [ doi/url ]
• Hynek Mlnařík, Subramaniam Ramamoorthy, and Rahul Savani.
  Multi-strategy trading utilizing market regimes.
  Advances in Machine Learning for Computational Finance Workshop.
  [ bibtex ]

2008

• Richard Baron, Jacques Durieu, Hans Haller, Rahul Savani, and Philippe Solal.
  Good neighbors are hard to find: computational complexity of network formation.
  Review of Economic Design, 12(1):1–19.
  [ bibtex ] [ pdf ] [ doi/url ]
• Marcin Jurdziński and Rahul Savani.
  A Simple P-Matrix Linear Complementarity Problem for Discounted Games.
  In Proc. of Computability in Europe (CiE), 283–293.
  [ bibtex ] [ pdf ] [ doi/url ]

2006

• Rahul Savani.
  Finding Nash equilibria of bimatrix games.
  PhD thesis, London School of Economics, 2006.
  [ bibtex ] [ pdf ] [ doi/url ]
• Rahul Savani and Bernhard von Stengel.
  Hard-to-Solve Bimatrix Games.
  Econometrica, 74(2):397–429.
  Preliminary conference version appeared at FOCS 2004.
  [ bibtex ] [ pdf ] [ doi/url ]

2005

• Andrea S. Griffin, Rahul Savani, Kristina Hausmanis, and Louis Lefebvre.
  Mixed-species aggregations in birds: zenaida doves, Zenaida aurita, respond to the alarm calls of carib grackles, Quiscalus lugubris.
  Animal Behaviour, 70(3):507–515.
  [ bibtex ] [ pdf ] [ doi/url ]
• Rahul Savani and Ben Veal.
  A Novel Strategy for the Penn-Lehman Automated Trading Competition.
  Technical Report: CDAM Research Report LSE-CDAM-2005-12.
  [ bibtex ] [ doi/url ]

2004

• R. Savani and B. von Stengel.
  Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game.
  In Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS), 258–267.
  Journal version appeared in Econometrica (2006).
  [ bibtex ] [ pdf ] [ doi/url ]
• Rahul Savani.
  Challenge Instances for NASH.
  Technical Report: CDAM Research Report LSE-CDAM-2004-14.
  [ bibtex ] [ doi/url ]