Multidimensional Mechanism Design: Finite-Dimensional Approximations and Efficient Computation

• 成果类型: Article
• 署名作者: Belloni, Alexandre; Lopomo, Giuseppe; Wang, Shouqiang
• 署名单位: Duke University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0824
• 发表日期: 2010
• 页码: 1079-1089
• 关键词: Monopoly; auctions

摘要

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.