Computer Science and Management Science and Engineering Departments
Approximation in Algorithmic Game Theory
Exact solutions are great when you can get them. When you can't, allowing approximation can extend the reach of a theory. We survey two genres of such results in algorithmic game theory: 1. Quantifying the inefficiency of equilibria. Equilibria are generally sub-optimal (think Prisoner's Dilemma). But are they ever guaranteed to be approximately optimal? The answer is "yes" for a remarkably wide range of applications and equilibrium concepts. 2. Reasoning about simple and practical auctions. Classical optimal auction theory assumes knowledge of a common prior, and can advocate unreasonably complex auctions. How much past data is required to justify rigorously a Bayesian approach? Can simple auctions, with little to no distributional dependence, perform approximately as well?