Frugality ratios and improved truthful mechanisms for vertex cover

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg

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 l…