Caltech Home > Home > Events > Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar
open search form
Thursday, April 30, 2015
12:00 PM - 1:00 PM
Annenberg 213

Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

Reverse Mechanism Design
Nima Haghpanah, Postdoctoral Scholar, Computer Science and Artificial Intelligence Laboratory, MIT,
Myerson's 1981 characterization of revenue-optimal auctions for single-dimensional agents follows from the design of virtual values that satisfy two properties. 1) The pointwise optimization of virtual surplus gives an allocation rule that is incentive compatible; and 2) The virtual values are an "amortization" of the revenue.  That is, the expected the virtual surplus of any incentive compatible mechanism is equal to the expected revenue of that mechanism.  A challenge of generalizing the approach to multi-dimensional agents is that a mechanism that pointwise optimizes "virtual values" resulting from a general application of integration by parts is not incentive compatible.
 
We give a framework for reverse mechanism design.  Instead of solving for the optimal mechanism in general, we hypothesize a (natural) specific form of the optimal mechanism and identify conditions for existence of virtual values that prove the mechanism is optimal.  As an example, we derive conditions in the form of positive correlation between values, for the optimality of mechanisms that sell each agent her favorite item or nothing for unit demand agents.  As another example, we derive conditions for the optimality of posting a single price for the grand bundle for additive agents.
 
Joint work with Jason Hartline.  To appear on the Conference on Economics and Computation (EC 15).
For more information, please contact Sydney Garstang by email at sydney@caltech.edu.