Theory seminar: Reverse Mechanism Design

Monday, January 26, 2015 -
1:00pm to 2:00pm
CS 4310

Speaker Name: 

Nima Haghpanah

Speaker Institution: 




Cookies Location: 

CS 4310


Myerson's 1981 characterization of revenue-optimal auctions for single-dimensional agents follows from an amortized analysis of the incentives of a single agent. To optimize revenue in expectation, he maps values to virtual values which account for expected revenue gain but can be optimized pointwise. For single-dimensional agents the appropriate virtual values are unique and their closed form can be easily derived from integration by parts. A main challenge of generalizing the Myersonian approach to multi-dimensional agents is that the right amortization is not pinned down by integration by parts. For multi-dimensional agents, the optimal mechanism may be very complex. Complex mechanisms are impractical and rarely employed. We give a framework for reverse mechanism design. Instead of solving for the optimal mechanism in general, we assume a (natural) specific form of the mechanism. As an example of the framework, for agents with unit-demand preferences, we restrict attention to mechanisms that sell each agent her favorite item or nothing. From this restricted form, we will derive multi-dimensional virtual values. These virtual values prove this form of mechanism is optimal for a large class of item-symmetric distributions over types. As another example of our framework, for bidders with additive preferences, we derive conditions for the optimality of posting a single price for the grand bundle.