Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts

David Kempe, Mahyar Salek, Cristopher Moore

We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. For Vertex Cover auctions, the v…