# Vickrey auction

A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins, but the price paid is the second-highest bid. The auction was created by William Vickrey. This type of auction is strategically similar to an English auction, and gives bidders an incentive to bid their true value.

Vickrey's original paper considered only auctions where a single, indivisible good is being sold. In this case, the terms Vickrey auction and second-price sealed-bid auction are equivalent, and are used interchangeably. When multiple identical units (or a divisible good) are being sold in a single auction, the most obvious generalization is to have all winning bidders pay the amount of the highest non-winning bid. This is known as a uniform price auction. The uniform-price auction does not, however, result in bidders bidding their true valuations as they do in a second-price auction unless each bidder has demand for only a single unit.

## Proof of Optimality of Truthful Bidding

The optimal strategy in a Vickrey auction with a single, indivisible item is for each bidder to bid their true value of the item.

Let vi be bidder i's value for the item. Let bi be bidder i's bid for the item.

The payoff for bidder i is $\begin{cases} v_i-\mbox{max}_{j\neq i} b_j & \mbox{if } b_i > \mbox{max}_{j\neq i} b_j \\ 0 & \mbox{otherwise} \end{cases}$

The strategy of overbidding is dominated by bidding truthfully. Assume that bidder i bids bi > vi.

If $\mbox{max}_{j\neq i} b_j < v_i$ then the bidder would win the item with a truthful bid as well as an overbid. The bid's amount does not change the payoff so the two strategies have equal payoffs in this case.

If $\mbox{max}_{j\neq i} b_j > b_i$ then the bidder would lose the item either way so the strategies have equal payoffs in this case.

If $v_i < \mbox{max}_{j\neq i} b_j < b_i$ then only the strategy of overbidding would win the auction. The payoff would be negative for the strategy of overbidding because they paid more than their value of the item, while the payoff for a truthful bid would be zero. Thus the strategy of bidding higher than one's true valuation is dominated by the strategy of truthfully bidding.

The strategy of underbidding is dominated by bidding truthfully. Assume that bidder i bids bi < vi.

If $\mbox{max}_{j\neq i} b_j > v_i$ then the bidder would lose the item with a truthful bid as well as an overbid, so the strategies have equal payoffs for this case.

If $\mbox{max}_{j\neq i} b_j < b_i$ then the bidder would win the item either way so the strategies have equal payoffs in this case.

If $b_i < \mbox{max}_{j\neq i} b_j < v_i$ then only the strategy of truthfully bidding would win the auction. The payoff for the truthful strategy would be payoff as they paid less than their value of the item, while the payoff for an underbid bid would be zero. Thus the strategy of underbidding is dominated by the strategy of truthfully bidding.

Truthful bidding dominates the other possible strategies (underbidding and overbidding) so it is an optimal strategy.

## Use in U.S. Treasury securities

U.S. Treasury securities are auctioned in competitive bidding under rules that are very similar to a Vickrey auction.

## 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) $e_k$ in the MCF is paid

pk = dk + MCF(Gek) − MCF(G),

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, $G \in G(n, p)$ approaches $\frac{p}{2-p}$

as n, approaches $\infty$, for $n p = \omega(\sqrt{n \log n})$. Prior to this result, it was known that VCG overpayment in G(np) is $\Omega\left(\frac{1}{np}\right)$

and $O(1)\,$

with high probability given $np=\omega(\log n).\,$