Multidimensional mechanism design: Finite-dimensional approximations and efficient computation

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Belloni, A; Lopomo, G; Wang, S

Published Date

  • July 1, 2010

Published In

Volume / Issue

  • 58 / 4 PART 2

Start / End Page

  • 1079 - 1089

Electronic International Standard Serial Number (EISSN)

  • 1526-5463

International Standard Serial Number (ISSN)

  • 0030-364X

Digital Object Identifier (DOI)

  • 10.1287/opre.1100.0824

Citation Source

  • Scopus