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 second session of this talk will take place on Tuesday, August 25 from 2:00 pm to 3:00 pm.