Mechanism design studies problems where the preferences of self-interested participants --- such as a value of a good or a cost of performing a task --- are a priori unknown to the decision-maker. The high-level goal is to design a protocol, or "mechanism," that interacts with participants so that self-interested behavior yields a desirable outcome.
Computer science has brought new ideas and techniques to the classical economic theory of mechanism design. A primary signature of the computer science approach is approximation --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. Approximation guarantees are a fundamental tool for measuring suboptimality, which can arise in mechanism design because of computational tractability constraints, the inefficiency of game-theoretic equilibria, or information-theoretic barriers to obtaining full optimality. The goals of the proposed research are: to further the theory of prior-independent and prior-free auctions for revenue maximization; to apply the concept of approximation to auctions with interdependent values; to pursue equilibrium performance guarantees for auctions with low-dimensional bid spaces; and to seek new results on tractable combinatorial auctions.
The broader significance and importance of the project are as follows. First, mechanism design has several applications highly relevant to the computing industry, such as combinatorial auctions for wireless spectrum, search keyword auctions, and the real-time allocation of both online and more traditional advertising. The proposed research applies concepts and techniques from theoretical computer science to obtain new insights about fundamental models in mechanism design, and to produce new models and results that may be more germane for computer science applications. Second, the project funding will enable the mentoring of PhD students, innovation in graduate teaching, the dissemination of technical surveys and educational materials, and the recruitment of undergraduates into research.
