Approximation in Mechanism Design

This talk surveys three challenge areas for mechanism design and describes the role approximation plays in resolving them. Challenge 1: optimal mechanisms are parameterized by knowledge of the distribution of agent’s private types. Challenge 2: optimal mechanisms require precise distributional information. Challenge 3: in multi-dimensional settings economic analysis has failed to characterize optimal mechanisms. The theory of approximation is well suited to address these challenges. While the optimal mechanism may be parameterized by the distribution of agent’s private types, there
may be a single mechanism that approximates the optimal mechanism for any distribution. While the optimal mechanism may require precise distributional assumptions, there may be approximately optimal mechanism that depends only on natural characteristics of the distribution. While the multi- dimensional optimal mechanism may resist precise economic characterization, there may be simple description of approximately optimal mechanisms. Finally, these approximately optimal mechanisms, because of their simplicity and tractability, may be much more likely to arise in practice, thus making the theory of approximately optimal mechanism more descriptive than that of (precisely) optimal mechanisms. The talk will cover positive resolutions to these challenges with emphasis on basic techniques, relevance to practice, and future research directions.

Speaker Details

Dr. Hartline works in the topics in the intersection of computer science and economics with a focus on the design and analysis of economic systems (a.k.a., mechanism design). He has been an assistant professor in the EECS department at Northwestern University since January of 2008. He was a researcher at Microsoft Research, Silicon Valley from 2004 to 2007. He was was a founding organizer of the Bay Algorithmic Game Theory Symposium. In 2003, he held a postdoctoral research fellowship at the Aladdin Center at Carnegie Mellon University. He received his Ph.D. in Computer Science from the University of Washington in 2003 with advisor Anna Karlin and B.S.s in Computer Science and Electrical Engineering from Cornell University in 1997.

Date:
Speakers:
Jason Hartline
Affiliation:
Northwestern University
    • Portrait of Jeff Running

      Jeff Running