Truthful and Near-Optimal Mechanism Design via Linear Programming
We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for "packing domains", any alpha-approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem by alpha can be used to construct an alpha-approximation mechanism that is truthful in expectation. This immediately gives a unified way of obtaining truthful mechanisms with good approximation guarantees, and yields a variety of new and significantly improved results. In particular, we obtain the first truthful mechanisms with tight approximation guarantees for a variety of multi-parameter domains: a $O(\sqrt m)$-approximation for combinatorial auctions (CAs), a $(1+\e)$-approximation for multi-unit CAs with $\Omega(\log m)$ copies of each item, and a 2-approximation for multi-parameter knapsack problems (multi-unit auctions).
Our construction is based on considering an LP relaxation of the problem and using the classic Vickrey-Clarke-Groves mechanism to obtain a truthful mechanism in this fractional domain. We show that the (fractional) optimal solution scaled down by alpha, where alpha 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 viewed as a way of exploiting VCG in a computationally tractable way even when the underlying social-welfare maximization problem is NP-hard.
This is joint work with Chaitanya Swamy.
An extended abstract can be downloaded from: http://www.cs.huji.ac.il/~tron/papers/mechdeslp.ps
The talk will be completely self-contained.