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:
“How have I been able to live so long outside Nature without identifying myself with it? Everything lives, moves, everything corresponds; the magnetic rays, emanating either from myself or from others, cross the limitless chain of created things unimpeded; it is a transparent network that covers the world, and its slender threads communicate themselves by degrees to the planets and stars. Captive now upon earth, I commune with the chorus of the stars who share in my joys and sorrows.”
—Gérard De Nerval (1808–1855)