Abstract
Approximation guarantees for game-theoretic equilibria (a.k.a. "price of anarchy" (POA) bounds) have long been an important subject within algorithmic game theory. Over the past five years, a coherent and user-friendly theory of such bounds has emerged. The first lecture discusses games and mechanisms that are "smooth", and how this translates to approximation guarantees both for no-regret learners and in games of incomplete information. The second lecture discusses "composition theorems", which reduce bounding the POA of complex mechanisms to that of simpler mechanisms, and techniques for translating lower bounds from computational and communication complexity to POA lower bounds.
The first session of this talk will take place on Monday, August 24 from 3:30 pm to 4:30 pm.