|
On the Expected Overpayment
of Truthful Mechanisms 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 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, Papadimitriou and Saberi (2003), the overpayment
is constant regardless of graph size. We then find empirically that the
complete graph with random edge costs has worse overpayments, higher than
Theta((log n)1.5). Again from simulations, we see that
the power-law graph with unit costs has overpayments that decrease with
graph size and finally, the power-law graph with uniformly random costs
has a small constant overpayment.
References:
[1] David Karger and
Evdokia Nikolova.
``On
the Expected Overpayment of Truthful Mechanisms in Large Networks."
PODC 2005.
|
|
