Optimal Mechanism Design for Multi-dimensional Agents


Nima Haghpana

Monday, January 28, 2013
4:00 PM, 5130 Upson Hall


We study optimal auctions for single-good settings with multi-dimensional and non-linear agents. Our setting includes environments where agents have private budgets, risk preferences, or preferences over several possible configurations of the good. These are the main challenge areas for auction theory.

We show that multi-agent auction problems can be decomposed into a collection of single-agent problems, the solutions to which can be reassembled as a mechanism.  We give two such decompositions.  The first is to a more complex single-agent problem and the resulting reduction is computationally tractable by tools from convex optimization.  The mechanism it gives is optimal.  The second is to a simpler single-agent problem from which Myerson-like virtual values can be derived.  The resulting mechanism awards the item to the agent with the highest positive virtual value.  This mechanism is optimal when the single-agent problems satisfy a natural linearity condition, and approximately optimal more generally.

The talk is based on joint work with Saeed Alaei, Hu Fu, Jason Hartline, and Azarakhsh Malekian.