Use in Network Routing
In network routing, VCG mechanisms are a family of payment schemes based on the added value concept. The basic idea of a VCG mechanism in network routing is to pay the owner of each link or node (depending on the network model) that is part of the solution, its declared cost plus its added value. In many routing problems, this mechanism is not only strategyproof, but also the minimum among all strategyproof mechanisms.
In the case of network flows, Unicast or Multicast, a minimum cost flow (MCF) in graph G is calculated based on the declared costs dk of each of the links and payment is calculated as follows:
Each link (or node) in the MCF is paid
- ,
where MCF(G) indicates the cost of the minimum cost flow in graph G and G − ek indicates graph G without the link ek. Links not in the MCF are 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 n nodes and edge probability p, approaches
as n, approaches, for . Prior to this result, it was known that VCG overpayment in G(n, p) is
and
with high probability given
Read more about this topic: Vickrey Auction
Famous quotes containing the word network:
“A culture may be conceived as a network of beliefs and purposes in which any string in the net pulls and is pulled by the others, thus perpetually changing the configuration of the whole. If the cultural element called morals takes on a new shape, we must ask what other strings have pulled it out of line. It cannot be one solitary string, nor even the strings nearby, for the network is three-dimensional at least.”
—Jacques Barzun (b. 1907)