Brief announcement: on the expected overpayment of VCG mechanisms in large networks
The VCG mechanism for buying a path from s to t in a network with selfish edges, selects the lowest-cost path (LCP) and pays each edge e on the path the edge’s cost plus a bonus equal to the increase in cost of the lowest-cost path from s to t if edge e were omitted from the graph G, that is payment(e, s, t) = cost(e)+LCP (G− e, s, t)− LCP (G, s, t). These payments are unacceptably high in some graphs containing two node-disjoint paths, and there are few positive results which prove small upper bounds on the expected payments in large and more realistic networks [4, 1]. In this paper, we give an improvement on the VCG overpayment bound of Mihail, Papadimitriou and Saberi [4] for random graphs. As a corollary, we show that the overpayment is not necessarily correlated with the competitiveness of a graph (measured, for example, by the number of node-disjoint paths between a source-destination pair [1]), and it is not necessarily correlated with the size of the graph, contrary to the conjecture in Mihail et al. [4] that the overpayment in random graphs Gn,p is Θ(1/np). Our results show that the overpayment is low when there are two almost equally short paths between the source and destination; the presence of more edges or more competition does not necessarily reduce it and may even hurt it.