Vickrey Auction - Use in Network Routing

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 d_k 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 − e_k indicates graph G without the link e_k. 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