Computer Science – Computational Complexity
Scientific paper
2009-12-17
Computer Science
Computational Complexity
Scientific paper
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 vertices are owned by selfish and rational agents, and the auctioneer wants to purchase a vertex cover from them. 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 mechanism.
Kempe David
Moore Cristopher
Salek Mahyar
No associations
LandOfFree
Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-684921