ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

03 Dec 2004:
VCG Overpayment in Random Graphs
Authors: D. Karger, E. Nikolova
Speaker: Gwendoline Chien

From: DIMACS Workshop on Computational Issues in Auction Design

The authors addressed the problem of selecting the cheapest possible route between a source and a destination in a graph in which edges are owned by self agents. The VCG mechanism is the unique efficient mechanism, however the payments made by VCG can be unacceptably high in some graphs. In this paper, they study the VCG overpayment in different types of graphs with unit and uniformly random edge costs. The results suggests that for common real-world networks, the VCG payments will not e too much higher than the true costs.