CS 789 THEORY SEMINAR [home]

Speaker:   Edith Elkind
Affiliation:  Princeton Uniniversity
Date:  Wednesday, December 1, 2004        
Time:  3-4pm          
Place: 310 Rhodes Hall
Title:    Reducing overpayment in shortest path auctions.

Abstract: 
We discuss the problem of purchasing an inexpensive s--t path
in a network where edges are owned by independent (selfish) agents, and the cost of an edge is known to its owner only.

We show that any mechanism with (weakly) dominant strategies (or, equivalently, any truthful mechanism) can force the buyer to make very large payments. Namely, for every such mechanism,
the buyer can be forced to pay c(P) + n/2*(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 n is the number of edges in P.

The worst-case lower bounds motivate us to approach this problem from average-case viewpoint, where edge cost distributions are assumed to be known to the mechanism designer. In this framework, we identify the optimal mechanism with regard to total payment,
and demonstrate that for certain distributions, there is an exponential separation in terms of average overpayments between the classical VCG mechanism and the optimal mechanism.

The computational burden imposed by an optimal mechanism may be
unacceptably high. In some cases, one can achieve a significant improvement over VCG simply by deleting some edges from the graph and running VCG on the modified graph. In the last part of the talk
we analyze the strengths and limitations of this approach.