Equilibrium Computation in Games and Markets
Course outline
 Understanding the difficult in computing equilibria in strategic settings is one of the primary goals of algorithmic game theory. We know from Nash's theorem that an equilibrium typically exists, but how does one find an equilibrium? The pursuit of this goal has lead not only to interesting and surprising algorithmic techniques, but also to deep new results in computational complexity.

Our goal in this course is to survey, in some depth, the techniques that go into both the design of exact and approximation algorithms, as well as determining the hardness of equilibrium computation. In some sense, this is an advanced course in algorithms and complexity, though we will focus on the problem of equilibrium computation.

Please note that this is a reading course, and hence all participants in the course will be presenting the topics and papers we cover.

Prerequisites
 A good background in linear algebra as well as basic knowledge of computational complexity will be required.
Details
 Classes will be held Tue/Thu 9:30-11 am in D-405.

Classes begin on August 9th.

As this is a reading course, there will not be any formal evaluation.

Our primary reference materials will be the conference or (preferably) journal versions of papers, or the relevant chapters from the AGT book by Nisan et al. We may supplement these by surveys, course notes from other courses, etc.

Topics and Papers
 Here is a partial list of topics and papers we plan to cover:

  • Existence of equilibria
  • 2-player zero-sum games
  • Lemke-Howson for 2-player general-sum games
  • Richard J. Lipton, Evangelos Markakis, Aranyak Mehta. Playing large games using simple strategies. EC 2003.
  • Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni. Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. STOC 2011.
  • Ruta Mehta. Constant rank bimatrix games are PPAD-hard. STOC 2014.
  • Siddharth Barman. Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem. STOC 2015.
  • Mark Braverman, Young Kun-Ko, Omri Weinstein. Approximating the best Nash Equilibrium in n^o(log n)-time breaks the Exponential Time Hypothesis. SODA 2015
  • Market equilibria: Convex programming and tatonnement processes
  • Nikhil R. Devanur, Ravi Kannan. Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. FOCS 2008.
  • Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye. The complexity of equilibria: Hardness results for economies via a correspondence with games. Theor. Comput. Sci., 2008
  • Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar. The complexity of pure Nash equilibria. STOC 2004.
  • Igal Milchtaich. Representation of finite games as network congestion games. Int. J. Game Theory, 2013.
Classes
Aug 9
 Umang: Course details. Introduction to games, and a simple support enumeration algorithm for computing equilibria in bimatrix games.
Aug 11
 Umang: Equilibrium computation in two-player zero-sum games, and a proof of Nash's theorem.
Aug 25
 Umang: The Lemke-Howson algorithm for equilibrium computation in two-player symmetric games.
Aug 30
 Gunjan: Playing large games using simple strategies, EC 2003.
Sep 1, 6
 Phani: Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm, STOC 2011.
Sep 8
 Somnath: A proof of Brouwer's Fixed Point Theorem via Sperner's Lemma.
Sep 13, 15
 Umang: Constant rank bimatrix games are PPAD-hard, STOC 2014.
Sep 20
 Umang continues. Gunjan: Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem, STOC 2015.
Sep 22
 Gunjan continues.
Sep 29
 Phani: Nash and Correlated Equilibria: Some Complexity Considerations. Games and Econ. Behav, 1989
Oct 6
 Somnath: Membership in PPAD of 2-Nash and 2D-Sperner. Refs: Section 4 from A note on the Lemke-Howson algorithm, Math. Prog. Study 1974, and Theorem 3 from On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, JCSS 1994
Oct 11
 Umang: A polynomial-time algorithm for market equilibria in Fisher Markets with Linear Utilities, and a PTAS for Arrow-Debreu markets with linear utilities. Refs: Section 5.1, 5.2 from AGT book, and Auction Algorithms for Market Equilibrium, Math. Oper. Res. 2006.
Oct 25
 Umang: PTAS for Arrow-Debreu markets, continued.
Oct 27
 Umang: A discrete tatonnement-based algorithm for exchange markets satisfying weak gross substitutes. Ref: Market Equilibrium via the Excess Demand Function, STOC '05
Nov 3
 Umang: The Separation Lemma, and convex programming for market equilibria in Fisher Markets with concave utilities. Refs: Lemma 5 from On the Stability of the Competitive Equilibrium II, Econometrica 1959, and Sec. 1, 2, 4 from Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities, ICALP '04.
Nov 10, 14
 Phani: Market equilibria in polynomial time for a fixed number of goods or agents. Devanur and Kannan, FOCS '08
Nov 15
 Somnath: The complexity of equilibria: Hardness results for economies via a correspondence with games. Codenotti et al., Theor. Comput. Sci., 2008
List of papers for student presentations
The papers below are of varying levels of difficulty (which of course depends on your own background). Feel free to suggest papers outside of this list also.
  • Inner Product Spaces for MinSum Coordination Mechanisms. Cole et al., STOC '11
  • Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard. Barman and Ligett, EC '15.
  • Computing Shapley Value in Supermodular Coalitional Games. Liben-Nowell et al., COCOON '12.
  • On the Power of Randomization in Algorithmic Mechanism Design. Dobzinski and Dughmi, FOCS '09 and SIAM J. Comput., '13
  • Multiplicative Updates Outperform Generic No-Regret Learning in Congestion Games. Kleinberg, Piliouras, and Tardos, STOC '09
  • Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3. Anbalagan et al., WINE '13
  • Elections Can be Manipulated Often. Friedgut, Kalai, and Nisan, FOCS '08
  • Fair Enough: Guaranteeing Approximate Maximin Shares. Procaccia and Wang, EC '14
  • The computational difficulty of manipulating an election. Bartholdi, Tovey, and Trick. Social Choice and Welfare, 1989.
  • Approximate Nash equilibria in anonymous games. Daskalakis and Papadimitriou, J. Econ. Theory, 2015
  • How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. Singer, WSDM '12
  • Simpler Sybil-Proof Mechanisms for Multi-Level Marketing. Drucker and Fleischer, EC '12
Some tips on presentation
  • Don't present all the results in the paper; just focus on the main results.
  • Don't present all the technical details. You should always give the intuition, and cover enough detail that the audience is able to fill in missing details with a bit of work.
  • Don't go too quickly! Pretend as if you're teaching a class. Make sure to write down important stuff on the board, rather than just saying it and trusting the audience to remember.
  • Sometimes it's okay to cover a special case of a general proof, without getting into corner cases (unless these cases are what makes the paper interesting).
  • If possible, do try and simplify proofs and notation.
  • Give an idea of why the paper is interesting, what the main technical contribution is, and an outline of the results you will be presenting at the beginning.