On the Expected VCG Overpayment in Large Networks

Motivated by the increasing need to price networks, we study the prices resulting from of a variant of the VCG mechanism, specifically defined for networks by J. Feigenbaum, et al (2002). This VCG mechanism is the unique efficient and strategyproof mechanism, however it is not budget-balanced and in fact it is known to result in arbitrarily bad overpayments for some graphs by A. Archer and E. Tardos (2002), In contrast, we study more common types of graphs and show that the VCG overpayment is not too high, so it is still an attractive pricing candidate. We prove that the average overpayment in Erdos-Renyi random graphs with unit costs is p/(2 - p) for any n, when the average degree is higher than a given threshold. Our simulations show that the overpayment is greater than p/(2 - p) below this threshold, hence, together with the constant upper bound from Mihail et al. (2003), the overpayment is constant regardless of graph size. We then present simulation results which show that power-law graphs with unit costs has overpayments that decrease with graph size and finally, power-law graphs with uniformly random costs has a small constant overpayment