Complexity in Algorithmic Game Theory

At the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Venue: Indian Institute of Technology Bombay

Date: 10th December 2019

Since its inception, complexity has played a central role in algorithmic game theory. One of the most foundational results in this field is the PPAD-hardness of computing a Nash equilibrium. The complexity of vote manipulation is another classic, negative result in this context. Indeed, the study of complexity of game-theoretic solution concepts has led to renewed interest in complexity classes, such as PPAD and PLS, as well as the introduction of new classes, e.g., CLS. Besides computational complexity, a rich literature has also emerged that studies other notions such as communication complexity, query complexity, and menu-size complexity.‚Äč

The objective of this workshop is to bring together interested researchers to learn and discuss results on complexity in game theory. Towards this end, the workshop will combine presentations on recent research and tutorial-style talks, along with discussions on interesting, open problems. The encompassing theme of this workshop is aimed at bringing together a diverse audience.



Details to be updated soon...


  • Siddharth Barman, Indian Institute of Science,
  • Umang Bhaskar, Tata Institute of Fundamental Research,