Multidimensional Mechanism Design: Finite-Dimensional Approximations and Efficient Computation

Alexandre Belloni (), Giuseppe Lopomo () and Shouqiang Wang ()
Additional contact information
Alexandre Belloni: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Giuseppe Lopomo: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Shouqiang Wang: Fuqua School of Business, Duke University, Durham, North Carolina 27708

Operations Research, 2010, vol. 58, issue 4-part-2, 1079-1089

Abstract: Multidimensional mechanism design problems have proven difficult to solve by extending techniques from the one-dimensional 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.

Keywords: linear programming; large-scale systems; algorithms; infinite dimensional; bidding; auctions (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0824 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-2:p:1079-1089

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().