Optimal Multi-dimensional Mechanism Design

PhD Qualifying Examination


Title: "Optimal Multi-dimensional Mechanism Design"

by

Mr. Bo QIN


Abstract:

Optimal mechanism design problem, which addresses how a seller can auction 
off items to interested bidders to maximize her profit, are extremely 
important in mathematical economics and are becoming more so in computer 
science. In a seminal result, Myerson solved the single-item Bayesian 
mechanism design problem. Even though some progress was made in certain 
restricted settings, the extension of this problem to multi-dimensional 
mechanism design, which may incorporate more general settings with 
multiple heterogeneous items, asymmetric bidders' preferences as well as 
complicated feasibility constraints, remains open. Despite its importance 
in economics, this multi-dimensional mechanism design problem has been 
notorious in algorithmic game theory due to the hardness of developing a 
polynomial-time optimal mechanism, even for simple cases.

This survey concentrates on describing progress on the optimal 
multi-dimensional mechanism design problem. Our main purpose is to present 
an overview of the development of solutions for this problem, with 
emphasis on some recent typical ideas and techniques. In particular, some 
important results in designing polynomial-time optimal mechanisms for some 
specific multi-dimensional settings are discussed and compared, including 
recently obtained constant-factor and nearly-optimal approximations, as 
well as as lower bounds on this problem in the general setting. We end 
this survey by discussing some open questions.


Date:			Wednesday, 12 March 2014

Time:                   2:00pm - 4:00pm

Venue:                  Room 3402
                         lifts 17/18

Committee Members:	Prof. Mordecai Golin (Supervisor)
 			Dr. Sunil Arya (Chairperson)
 			Prof. Siu-Wing Cheng
 			Dr. Ke Yi


**** ALL are Welcome ****