In set-system auctions , there are several overlapping teams of agents, and a task that can be completed by any of these teams. The buyer's goal is to hire a team and pay as little as possible. Recently, Karlin, Kempe and Tamir introduced a new definition of frugality ratio for this setting. Informally, the frugality ratio is the ratio of the total payment of a mechanism to perceived fair cost. In this paper, we study this together with alternative notions of fair cost, and how the resulting frugality ratios relate to each other for various kinds of set systems. We propose a new truthful polynomial-time auction for the vertex cover problem (where the feasible sets correspond to the vertex covers of a given graph), based on the local ratio algorithm of Bar-Yehuda and Even. The mechanism guarantees to find a winning set whose cost is at most twice the optimal. In this situation, even though it is NP-hard to find a lowest-cost feasible set, we show that local optimality of a solution can be used to derive frugality bounds that are within a constant factor of best possible. To prove this result, we use our alternative notions of frugality via a bootstrapping technique, which may be of independent interest.
Vertex-cover auctions have been studied in the past by Talwar @cite_9 and Calinescu @cite_3 . Both of these papers are based on the definition of frugality ratio used in @cite_5 ; as mentioned before, this means that their results only apply to bipartite graphs. Talwar @cite_9 shows that the frugality ratio of VCG is at most @math . However, since finding the cheapest vertex cover is an NP-hard problem, the VCG mechanism is computationally infeasible. The first (and, to the best of our knowledge, only) paper to investigate polynomial-time truthful mechanisms for vertex cover is @cite_3 . That paper studies an auction that is based on the greedy allocation algorithm, which has an approximation ratio of @math . While the main focus of @cite_3 is the more general set cover problem, the results of @cite_3 imply a frugality ratio of @math for vertex cover. Our results improve on those of @cite_9 as our mechanism is polynomial-time computable, as well as on those of @cite_3 , as our mechanism has a better approximation ratio, and we prove a stronger bound on the frugality ratio; moreover, this bound also applies to the mechanism of @cite_3 .
@cite_5 @cite_9 @cite_3
2061256213 1537430179 2046744707
We consider the problem of selecting a low-cost s - t path in a graph where the edge costs are a secret, known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges so as to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays Θ(n) times the actual cost of the path, even if there is an alternate path available that costs only (1 p e) times as much. This inspires the frugal path problem, which is to design a mechanism that selects a path and induces truthful cost revelation, without paying such a high premium. This article contributes negative results on the frugal path problem. On two large classes of graphs, including those having three node-disjoint s - t paths, we prove that no reasonable mechanism can always avoid paying a high premium to induce truthtelling. In particular, we introduce a general class of min function mechanisms, and show that all min function mechanisms can be forced to overpay just as badly as VCG. Meanwhile, we prove that every truthful mechanism satisfying some reasonable properties is a min function mechanism. Our results generalize to the problem of hiring a team to complete a task, where the analog of a path in the graph is a subset of the agents constituting a team capable of completing the task. The celebrated Vickrey-Clarke-Grove(VCG) mechanism induces selfish agents to behave truthfully by paying them a premium. In the process, it may end up paying more than the actual cost to the agents. For the minimum spanning tree problem, if the market is "competitive", one can show that VCG never pays too much. On the other hand, for the shortest s-t path problem, Archer and Tardos [5] showed that VCG can overpay by a factor of ?(n). A natural question that arises then is: For what problems does VCG overpay by a lot? We quantify this notion of overpayment, and show that the class of instances for which VCG never overpays is a natural generalization of matroids, that we call frugoids. We then give some sufficient conditions to upper bound and lower bound the overpayment in other cases, and apply these to several important combinatorial problems. We also relate the overpayment in an suitable model to the locality ratio of a natural local search procedure. 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.