Characterizing implementable allocation rules in multi-dimensional environments

We study characterizations of implementable allocation rules when types are multi-dimensional, monetary transfers are allowed, and agents have quasi-linear preferences over outcomes and transfers. Every outcome is associated with a continuous valuation function that maps an agent's type to his value for this outcome. Sets of types are assumed to be convex. Our main characterization theorem implies that allocation rules are implementable if and only if they are implementable on any two-dimensional convex subset of the type set. For finite sets of outcomes, they are implementable if and only if they are implementable on every one-dimensional subset of the type set. Our results complement and extend significantly a characterization result by Saks and Yu, as well as follow-up results thereof. Contrary to our model, this stream of literature identifies types with valuation vectors. In such models, convexity of the set of valuation vectors allows for a similar characterization as ours. Furthermore, implementability on one-dimensional subsets of valuation vectors is equivalent to monotonicity. We show by example that the latter does not hold anymore in our more general setting. Our proofs demonstrate that the linear programming approach to mechanism design, pioneered in Gui et al. and Vohra, can be extended from models with linear valuation functions to arbitrary continuous valuation functions. This provides a deeper understanding of the role of monotonicity and local implementation. In particular, we provide a new, simple proof of the Saks and Yu theorem, and generalizations thereof. Modeling multi-dimensional mechanism design the way we propose it here is of relevance whenever types are given by few parameters, while the set of possible outcomes is large, and when values for outcomes are non-linear functions in types.