Near-Optimal Equilibria

Lecture 1: Near-Optimal Equilibria I
Lecture 2: Near-Optimal Equilibria II
 

This series of talks was part of the Economics and Computation Boot Camp. Videos for each talk area available through the links above.

Speaker: Tim Roughgarden, Stanford University

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.