Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
We study truthful mechanisms for hiring a team of agents in three
classes of set systems: Vertex Cover auctions, k-flow auctions, and
For Vertex Cover auctions, the vertices are owned by selfish and
rational agents, and the auctioneer wants to purchase a vertex cover
For k-flow auctions, the edges are owned by the agents, and
the auctioneer wants to purchase k edge-disjoint s-t paths, for
given s and t.
In the same setting, for cut auctions, the auctioneer wants to
purchase an s-t cut.
Only the agents know their costs, and the auctioneer needs to select a
feasible set and payments based on bids made by the agents.
We present constant-competitive truthful mechanisms for all three set systems.
That is, the maximum overpayment of the mechanism is within a constant
factor of the maximum overpayment of any truthful mechanism, for
every set system in the class.
The mechanism for Vertex Cover is based on scaling each bid
by a multiplier derived from the dominant eigenvector of a certain
matrix. The mechanism for k-flows prunes the graph to be minimally
(k+1)-connected, and then applies the Vertex Cover mechanism.
Similarly, the mechanism for cuts contracts the graph until all s-t
paths have length exactly 2, and then applies the Vertex Cover