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.


This talk represents joint work with Anna Karlin and Tami Tamir.