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 S-1, S-2, ..., S-m, each having a cost c(S-i) 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'), where OPT' is the best cover disjoint from the optimum cover OPT. The VCG mechanism requires finding an optimum cover. For k >= 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'). The same approximation algorithms have payment bounded by 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.k(2) times the total payment of the VCG mechanism. (C) 2014 Elsevier B.V. All rights reserved.
展开▼
