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?
Faculty Host: Ariel Procaccia
sawako [atsymbol] cs.cmu.edu