CSAIL Publications and Digital Archive header
bullet Research Abstracts Home bullet CSAIL Digital Archive bullet Research Activities bullet CSAIL Home bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

 

Research Abstracts - 2007
horizontal line

horizontal line

vertical line
vertical line

On the Expected VCG Overpayment in Large Networks

David Karger & Evdokia Nikolova

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. 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. 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 Erd\H{o}s-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, Papadimitriou and Saberi, 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.

References:

[1] David Karger and Evdokia Nikolova. ``On the Expected VCG Overpayment in Large Networks." In Proceedings of 45th IEEE Conference on Decision and Control (CDC 2006) (Invited).

 

vertical line
vertical line
 
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu