Vickrey-Clarke-Groves

From Free net encyclopedia

In network routing, Vickrey-Clark-Groves (VCG) mechanisms are a family of payment schemes developed by W. Vickrey, E. H. Clarke, and T. Groves based on the added value concept. The basic idea of a VCG mechanism is to pay the owner of each link or node (depending on the network model) it declared cost plus its added value. In many routing problems, this mechanism is not only strategyproof, but minimum among all strategyproof mechanisms.

In the simplest, unicast case, a least cost path in graph G is calculated based on the declared costs <math>d_{k}</math> of each of the links, and payment is calculated as follows:

Each link <math>e_{k}</math> on the LCP is paid

<math>p_{k} = d_{k} + LCP(G - e_{k}) - LCP(G)</math>

and each link not on the LCP is paid nothing. This routing problem is one of the cases for which VCG is strategyproof and minimum.

In 2004, it was shown that the expected VCG overpayment of an Erdös-Renyi random graph with <math>n</math> nodes and edge probability <math>p</math> <math>G \in G(n, p)</math> approaches

<math> \frac{p}{2-p} </math>

as <math>n</math>, approaches <math> \infty </math>. Prior to this result, it was known that VCG overpayment in <math> G(n, p)</math> is

<math>\Omega(\frac{1}{np})</math>

and

<math>O(1)</math>

with high probability given

<math>np=\omega(\log n)</math>.