|
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).
|
|
