Multidimensional Mechanism Design: Finite-Dimensional Approximations and Efficient Computation

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.