Paper Info
Title
Frugality in path auctions
Abstract
We consider the problem of picking (buying) an inexpensive s -- t path in a graph where edges are owned by independent (selfish) agents, and the cost of an edge is known to its owner only. We study the problem of finding frugal mechanisms for this task, i.e. we investigate the payments the buyer must make in order to buy a path.First, we show that any mechanism with (weakly) dominant strategies (or, equivalently, any truthful mechanism) for the agents can force the buyer to make very large payments. Namely, for every such mechanism, the buyer can be forced to pay c(P) + 1/2k(c(Q) -- c(P)), where c(P) is the cost of the shortest path, c(Q) is the cost of the second-shortest path, and k is the number of edges in P. This extends the previous work of Archer and Tardos [1], who showed a similar lower bound for a subclass of truthful mechanisms called min-function mechanisms. Our lower bounds have no such limitations on the mechanism.Motivated by this lower bound, we study mechanisms for this problem providing Bayes-Nash equilibrium strategies for the agents. In this class, we identify the optimal mechanism with regard to total payment. We then demonstrate a separation in terms of average overpayments between the classical VCG mechanism and the optimal mechanism showing that under various natural distributions of edge costs, the optimal mechanism pays at most logarithmic factor more than the actual cost, whereas VCG pays √k times the actual cost. On the other hand, we also show that the optimal mechanism does incur at least a constant factor overpayment in natural distributions of edge costs. Since our mechanism is optimal, this gives a lower bound on all mechanisms with Bayes--Nash equilibria.
Year
DOI
Venue
2004
10.1145/982792.982900
Symposium on Discrete Algorithms
Keywords
Field
DocType
optimal mechanism,min-function mechanism,shortest path,truthful mechanism,frugal mechanism,edge cost,second-shortest path,actual cost,path auction,classical vcg mechanism,lower bound,nash equilibria,linear programming relaxation,complexity,matching,crossing number,nash equilibrium,triangulation,spanning tree
Combinatorics,Mathematical optimization,Crossing number (graph theory),Shortest path problem,Optimal mechanism,Upper and lower bounds,Vickrey–Clarke–Groves auction,Common value auction,Spanning tree,Linear programming relaxation,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89871-558-X
72
7.23
References 
Authors
7
3
Name
Order
Citations
PageRank
Edith Elkind11340120.81
Amit Sahai213566545.52
Kenneth Steiglitz31128660.13