Algorithmic Economics Seminar

Seminars
Associate Professor of Computer Science
Computer Science and Management Science and Engineering Departments
Stanford University
Approximation in Algorithmic Game Theory
Tuesday, March 11, 2014 - 12:00pm
6115 
Gates&Hillman Centers
Abstract:

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

For More Information, Please Contact:

sawako [atsymbol] cs ~replace-with-a-dot~ cmu ~replace-with-a-dot~ edu