The 29th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 17th to 24th, 2017. Participants can arrive either on February 17th or the 18th. Lectures will start February 19th and end on the 23rd. The subject of this year's workshop will be Complexity in Economics and Game Theory.
Tim Roughgarden
Stanford University
Complexity in Economics and Game Theory
The goal of this workshop is twofold: (i) to explain how complexity theory has helped illuminate several barriers in economics and game theory; and (ii) to illustrate how game-theoretic questions have led to new and interesting complexity theory (including several breakthroughs in the past few months!). There will be two five-lecture sequences: the "Solar Lectures," focusing on the communication and computational complexity of computing equilibria, and the "Lunar Lectures," focusing on applications of complexity theory in game theory and economics. Detailed schedule:
Solar Lecture 1: Introduction and wish list. Polynomial-time algorithms and rapidly converging dynamics for Nash equilibria in zero-sum games.
Solar Lectures 2 and 3: Lower bound on the communication complexity of computing a Nash equilibrium (even approximately) in bimatrix games. We will focus on the hot-off-the-press paper by Babichenko and Rubinstein, and will also discuss the relevant tools from communication complexity (such as Raz-McKenzie-type simulation theorems). [These lectures include a guest appearance by Omri Weinstein.]
Solar Lecture 4: Computational complexity background relevant for equilibrium computation. TFNP, PPAD, and all that. Evidence of hardness of TFNP and its subclasses.
Solar Lecture 5: The high-order bits of Rubinstein's proof (Best Paper, FOCS '16) that the Exponential Time Hypothesis for PPAD implies quasi-polynomial-time hardness for computing an approximate Nash equilibrium of a bimatrix game.
Lunar Lecture 1: How computer science has influenced real-world auction design. Case study: the 2016-2017 FCC Incentive Auction.
Lunar Lecture 2: Complexity-theoretic barriers to near-optimal equilibria: nondeterministic communication complexity lower bounds translate to lower bounds on the "price of anarchy" (i.e., the approximation ratio achieved by Nash equilibria). [Based on the speaker's FOCS '14 paper.]
Lunar Lecture 3: Complexity-theoretic barriers in markets: computational complexity separations imply non-existence of competitive equilibria in markets with indivisible goods. [Based on joint work with Inbal Talgam-Cohen, EC '15.]
Lunar Lecture 4: The borders of Border's theorem: why a famous result from auction theory cannot be generalized, unless the polynomial hierarchy collapses. [Based on joint work with Parikshit Gopalan and Noam Nisan, EC '15.]
Lunar Lecture 5: Epilogue: positive results for relaxations of the Nash equilibrium concept, such as correlated equilibria.