Frugality in path auctions

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) + \12k (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}, 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 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.