Characterizing Incentive Compatibility for Convex Valuations

We study implementability in dominant strategies of social choice functions when sets of types are multi-dimensional and convex, sets of outcomes are arbitrary, valuations for outcomes are convex functions in the type, and utilities over outcomes and payments are quasi-linear. Archer and Kleinberg [1] have proven that in case of valuation functions that are linear in the type monotonicity in combination with a local integrability condition are equivalent with implementability. We show that in the case of convex valuation functions one has to require in addition a property called decomposition monotonicity in order to conclude implementability from monotonicity and the integrability condition. Decomposition monotonicity is automatically satisfied in the linear case.

Saks and Yu [9] have shown that for the same setting as in Archer and Kleinberg [1], but finite set of outcomes, monotonicity alone is sufficient for implementability. Later Archer and Kleinberg [1], Monderer [6] and Vohra [10] have given alternative proofs for the same theorem. Using our characterization, we show that the Saks and Yu theorem generalizes to convex valuations. Again, decomposition monotonicity has to be added as a condition.