Textbooks

• Algorithms Illuminated: This is a book series inspired by my online courses currently running on the Coursera and EdX (Part 1/Part 2) platforms.
  • Omnibus (Parts 1-4 combined)
  • Part 1: The Basics
  • Part 2: Graph Algorithms and Data Structures
  • Part 3: Greedy Algorithms and Dynamic Programming
  • Part 4: Algorithms for NP-Hard Problems
• Twenty Lectures: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016. See also the Amazon page and Lanchester Prize citation.

• The BWCA Book: Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 2022. (Amazon page) (introductory chapter)
• The AGT Book: Algorithmic Game Theory, co-edited with Noam Nisan, Eva Tardos, and Vijay Vazirani, Cambridge University Press, 2007.
  • Read the entire book online by clicking here (look under the "Resources" tab). Here's errata from the first two printings.

• Complexity Theory, Game Theory, and Economics (The Barbados Lectures), Foundations and Trends in Theoretical Computer Science, 2020. (Preprint)
• Communication Complexity (for Algorithm Designers), Foundations and Trends in Theoretical Computer Science, 2016. (Preprint)
• Selfish Routing and the Price of Anarchy, MIT Press, 2005. (Sample chapter)

Surveys

• Distribution-Free Models of Social Networks, Chapter 28 in Beyond the Worst-Case Analysis of Algorithms, 2020. (with C. Seshadhri)
• Distributional Analysis, Chapter 8 in Beyond the Worst-Case Analysis of Algorithms, 2020.
• Resource Augmentation, Chapter 4 in Beyond the Worst-Case Analysis of Algorithms, 2020.
• Introduction (to Beyond Worst-Case Analysis), Chapter 1 in Beyond the Worst-Case Analysis of Algorithms, 2020.
• Approximately Optimal Mechanism Design, Annual Reviews of Economics, 2019. (with Inbal Talgam-Cohen)
• Beyond Worst-Case Analysis, Communications of the ACM, 2019.
• The Price of Anarchy in Auctions (survey), Journal of Artificial Intelligence Research, 2017. (with Vasilis Syrgkanis and Éva Tardos)
• Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned, SIGEcom Exchanges, 2014.
• Approximation in Algorithmic Game Theory, notes from a lecture at the Princeton Workshop on Approximation Algorithms, 2011. (with Qiqi Yan)
• Algorithmic Game Theory, Communications of the ACM, July 2010. Preprint
• Computing Equilibria: A Computational Complexity Perspective, invited survey for Economic Theory, 2010.
• Routing Games, Chapter 18 in Algorithmic Game Theory, 2007.
• Introduction to the Inefficiency of Equilibria, Chapter 17 in Algorithmic Game Theory, 2007. (with Éva Tardos)
• Selfish Routing and the Price of Anarchy (Survey), OPTIMA #74, 2007.
• Potential Functions and the Inefficiency of Equilibria (Survey), International Congress of Mathematicians, 2006.

Home