AI Lab logo
menu MENU

Theory Seminar

Price of Anarchy for Auction Revenue

Jason HartlineNorthwestern University

For the most part, the first step of a classical microeconomic analysis is to understand equilibrium. Unfortunately, the settings in which such an analysis is analytically tractable are often disappointingly idealistic. As a motivating example for the talk:
Even the Bayes-Nash equilibrium of the first-price auction with bidders with independent but non-identically distributed private values is outside the reach of this classical approach. Our contributions are two part (a) to develop methodology for understanding complex equilibria, and specifically (b) to quantify the Bayes-Nash revenue of auctions.

Our method of analysis isolate the equilibrium argument from complexity of environment as follows: (a) study general properties of single-player best response, (b) study general properties of game outcomes for distributions over players' actions (ignoring equilibrium), and (c) combine. We apply this method to analyze the revenue of auctions in equilibrium. For example, we show that the first-price auction with appropriate reserves obtains significant fraction of the revenue of the optimal auction. Moreover, as an example of the power of our analysis method, the same analysis that implies that equilibria in first-price auctions have good revenue, implies that simultaneous first-price auctions have good revenue.

Joint work with Darrell Hoy and Samuel Taggart.

Prof. Hartline's research introduces design and analysis methodologies from computer science to understand and improve outcomes of economic systems. This approach is applied to auction theory in his graduate textbook Mechanism Design and Approximation ( which is under preparation. Prof. Hartline received his Ph.D. in 2003 from the University of Washington under the supervision of Anna Karlin. He was a postdoctoral fellow at Carnegie Mellon University under the supervision of Avrim Blum; and subsequently a researcher at Microsoft Research in Silicon Valley. He joined Northwestern University in 2008 where he is an associate professor of computer science. He is currently on sabbatical visiting Harvard University's Economics Department.

Sponsored by