Intractability in Algorithmic Game Theory

Computer Science/Discrete Mathematics Seminar I
Topic:Intractability in Algorithmic Game Theory
Speaker:Tim Roughgarden
Affiliation:Stanford University
Date:Monday, March 11
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/1213/0311-TimRoughgarden

We discuss three areas of algorithmic game theory that have grappled with intractability. The first is the complexity of computing game-theoretic equilibria, like Nash equilibria. There is an urgent need for new ideas on this topic, to enable meaningful research in the face of computational hardness results. The other domains concern the design and analysis of mechanisms (such as auctions). Here, we discuss a novel analysis framework that interpolates between worst- and average-case analysis and permits strong and informative positive results; and how joint game-theoretic and computational constraints exacerbate intractability in algorithmic mechanism design.