Bounding the payment of approximate truthful mechanisms

In a STACS 2003 paper, Talwar analyzes the overpayment the VCG mechanism incurs for ensuring truthfulness in auctions. Among other results, he studies k-Set Cover (given a universe U   and a collection of sets S1,S2,…,SmS1,S2,…,Sm, each having a cost c(Si)c(Si) and at most k elements of U, find a minimum cost subcollection – a cover – whose union equals U) and shows that the payment of the VCG   mechanism is at most k⋅c(OPT′)k⋅c(OPT′), where OPT′OPT′ is the best cover disjoint from the optimum cover OPTOPT. The VCG   mechanism requires finding an optimum cover. For k≥3k≥3, k  -Set Cover is known to be NP-hard, and thus truthful mechanisms based on approximation algorithms are desirable. We show that the payment incurred by two mechanisms based on approximation algorithms (including the Greedy algorithm) is bounded by (k−1)c(OPT)+k⋅c(OPT′)(k−1)c(OPT)+k⋅c(OPT′). The same approximation algorithms have payment bounded by k(c(OPT)+c(OPT′))k(c(OPT)+c(OPT′)) when applied to more general set systems, which include k-Polymatroid Cover, a problem related to Steiner Tree computations. If q is such that an element in a k-Set Cover instance appears in at most q   sets, we show that the total payment based on our algorithms is bounded by q⋅k2q⋅k2 times the total payment of the VCG mechanism.