Abstract: Algorithmic game theory is an active and impactful area of research that in recent years has found many applications in the study of large strategic environments, like online markets and auctions, as well as social and biological systems. A basic message that emerged from this area is in fact negative: determining game-theoretic solution concepts---e.g., Nash equilibria---is computationally hard in general. But, given that such solution concepts are widely used in the design and analysis of strategic environments, these complexity barriers need to be addressed.
Motivated by these considerations, in this talk I will present two complementary directions that address hardness results for Nash equilibria, which are one of the most well-studied solution concepts in game theory. First, I will show that for a relevant class of two-player games an approximate Nash equilibrium can be efficiently determined. A key technical component of this work is an approximate version of Caratheodory’s theorem; given the fundamental importance of Caratheodory’s theorem, this approximate version is interesting in its own right. Then, I will describe how an empirical perspective can be employed to address the complexity of Nash equilibria in a number of cases. I will conclude by presenting a number of related problems and future research directions.
