We study truthful mechanisms for auctions in which the auctioneer is
trying to hire a team of agents to perform a complex task, and paying
them for their work. As common in the field of mechanism design, we
assume that the agents are selfish and will act in such a way as to
maximize their profit, which in particular may include misrepresenting
their true incurred cost.
Our first contribution is a new and natural definition of the
frugality ratio of a mechanism, measuring the amount by which a
mechanism ``overpays'', and extending previous definitions to all
monopoly-free set systems.

After reexamining several known results in light of this new
definition, we proceed to study in detail shortest path auctions and
``$r$-out-of-$k$ sets'' auctions. We show that when individual set
systems (e.g., graphs) are considered instead of worst cases over all
instances, these problems exhibit a rich structure, and the
performance of mechanisms may be vastly different. In particular, we
show that the well-known VCG mechanism may be far from optimal in
these settings, and we propose and analyze a mechanism that is always
within a constant factor of optimal.