Truthful and Near-Optimal Mechanism Design via Linear Programming

Abstract

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any α -approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem by α can be used to construct an α -approximation mechanism that is truthful in expectation. This immediately yields a variety of new and significantly improved results for various problem domains and furthermore, yields truthful (in expectation) mechanisms with guarantees that match the best-known approximation guarantees when truthfulness is not required. In particular, we obtain the first truthful mechanisms with approximation guarantees for a variety of multiparameter domains. We obtain truthful (in expectation) mechanisms achieving approximation guarantees of O (√ m ) for combinatorial auctions (CAs), (1 + ϵ ) for multiunit CAs with B = Ω (log m ) copies of each item, and 2 for multiparameter knapsack problems (multi-unit auctions). Our construction is based on considering an LP relaxation of the problem and using the classic VCG mechanism to obtain a truthful mechanism in this fractional domain. We argue that the (fractional) optimal solution scaled down by α , where α is the integrality gap of the problem, can be represented as a convex combination of integer solutions, and by viewing this convex combination as specifying a probability distribution over integer solutions, we get a randomized, truthful in expectation mechanism. Our construction can be seen as a way of exploiting VCG in a computational tractable way even when the underlying social-welfare maximization problem is NP -hard.