Computer Science/Discrete Mathematics Seminar I

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.