JavaScript is disabled for your browser. Some features of this site may not work without it.
Simple And Approximately Optimal Mechanisms Design

Author
Fu, Hu
Abstract
Mechanism design studies optimization problems with inputs from selfishly behaving agents. To a class of relatively simple questions, classical auction theory gives optimal solution which are often too complicated for practical use. This dissertation presents techniques and results on the design and analysis of simple and practical auctions that have provably approximately optimal performances. For single-parameter revenue optimization, we present the k-lookahead auction, which works for coorelated valuation distributions, and we discuss its consequences, which encompass a family of reserveprice-based auctions with approximately optimal revenue. For more general settings, we present the marginal revenue mechanisms as a framework for designing simple mechanisms in very general settings. Both frameworks are motivated with clear economic intuitions. For social welfare maximization in combinatorial auctions, we present an equilibrium analysis for simultaneous item auctions. In particular, we show that when valuations exhibit no complements, the welfare loss in these auctions at Bayesian Nash equilibria is bounded by small constants.
Date Issued
2013-08-19Subject
mechanism design; approximation algorithms; equilibrium analysis
Committee Chair
Kleinberg, Robert David
Committee Member
Joachims, Thorsten; Brown, Kenneth Stephen; Kleinberg, Jon M
Degree Discipline
Computer Science
Degree Name
Ph. D., Computer Science
Degree Level
Doctor of Philosophy
Type
dissertation or thesis