Multidimensional mechanism design: Finite-dimensional approximations and efficient computation
Repository Usage Stats
Multidimensional mechanism design problems have proven difficult to solve by extending techniques from the onedimensional case. This paper considers mechanism design problems with multidimensional types when the seller's cost function is not separable across buyers. By adapting results obtained by Border [Border, K. 1991. Implementation of reduced form auctions: A geometric approach. Econometrica 59 1175-1187], we transform the seller's problem into a representation that only involves "interim" variables and eliminates the dimensionality dependence on the number of buyers. We show that the associated infinite-dimensional optimization problem posed by the theoretical model can be approximated arbitrarily well by a sequence of finite-dimensional linear programming problems. We provide an efficient-i.e., terminating in polynomial time in the problem size-method to compute the separation oracle associated with the Border constraints and incentive compatibility constraints. This implies that our finite-dimensional approximation is solvable in polynomial time. Finally, we illustrate how the numerical solutions of the finite-dimensional approximations can provide insights into the nature of optimal solutions to the infinite-dimensional problem in particular cases. ©2010 INFORMS.
Published Version (Please cite this version)10.1287/opre.1100.0824
Publication InfoBelloni, A; Lopomo, G; & Wang, S (2010). Multidimensional mechanism design: Finite-dimensional approximations and efficient computation. Operations Research, 58(4 PART 2). pp. 1079-1089. 10.1287/opre.1100.0824. Retrieved from http://hdl.handle.net/10161/4439.
This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.
More InfoShow full item record
John D. Forsyth Professor of Business Administration
Alexandre Belloni is a Professor of Decision Sciences at the Fuqua School of Business at Duke University. He received his Ph.D. in Operations Research from the Massachusetts Institute of Technology (2006) and a M.Sc. in Mathematical Economics from IMPA (2002). He deferred the offer to join the faculty at Duke University to accept the IBM Herman Goldstein Postdoctoral Fellowship (2006-2007). Professor Belloni’s research interests are on statistics and optimization and on their a
Professor of Business Administration
Giuseppe (Pino) Lopomo is Professor of Economics at the Fuqua School of Business, Duke University. He also has a courtesy appointment at the Economics Department of Duke University. He has a Laurea Magna cum laude from Bocconi University in Milan, Italy, and a Ph.D. in Business Administration from the Stanford Graduate School of Business. Before joining the faculty at Duke, he was Assistant Professor of Economics at the Stern School of Business of New York University, and
Alphabetical list of authors with Scholars@Duke profiles.