Last year I gave a series of lectures covering the latest connections between complexity theory and economics. Morning lectures focused on the most recent breakthroughs on the complexity of computing equilibria, including Rubinstein’s quasi-polynomial-time hardness for computing an approximate Nash equilibrium of a bimatrix game from FOCS ’16, the Babichenko-Rubinstein communication complexity lower bounds for the same problem (from STOC ’17), and the Hubacek-Naor-Yogev average-case hardness of TFNP (from ITCS ’17). Evening lectures focused on complexity-theoretic barriers in economics (including joint work with Parikshit Gopalan, Noam Nisan, and Inbal Talgam-Cohen).
I’m happy to report that lectures notes are finally available (from arXiv or ECCC).
Turing's Invisible Hand 
Leave a Reply