Abstract: We survey three recent applications of complexity theory to algorithmic game theory. First, we explain when and how communication and computational lower bounds for algorithms for an optimization problem translate to lower bounds on the price of anarchy (POA) in games derived from the problem. This is a new approach to POA lower bounds, based on reductions in lieu of explicit constructions. These lower bounds are particularly significant for problems of designing games that have only near-optimal equilibria, ranging from the design of simple combinatorial auctions to the existence of effective tolls for routing networks. Second, we study "the borders of Border's theorem", a fundamental result in auction design that gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment. We explain a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. Finally, we explain "why prices need algorithms," in the sense that the guaranteed existence of pricing equilibria (like Walrasian equilibria) is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This connection implies a host of impossibility results, and suggests a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept. Includes joint work with Parikshit Gopalan, Noam Nisan, and Inbal Talgam-Cohen.

Abstract: We consider the landscape of popular matchings in a bipartite graph where every vertex has strict preferences over its neighbors. Algorithmically speaking, this landscape seems to have only a few bright spots. However relaxing popular matchings to popular mixed matchings makes several hard problems tractable.

Abstract: One of the most extensively studied problems within algorithmic game theory is the computability of Nash equilibrium, especially in two-player games. Given that the general case succumbs to PPAD-completeness, even for inverse polynomial approximation, there has been extensive work on finding efficient algorithms for subclasses of games as well as obtaining conditional lower bound. In this talk, I will discuss a (non-enumerative) algorithmic tool to solve a class of rank-1 games (rank-2 and beyond is PPAD-hard), and unconditional lower bounds under the sum-of-squares algorithmic framework. This framework is powerful enough to capture most known approximation algorithms in combinatorial optimization including the celebrated semidefinite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning.

Based on joint works with B. Adsul, J. Garg, P. Kothari, and M. Sohoni)