  In {\em 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 {\em 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 {\em 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 {\em 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.
