Vickrey auction

A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. 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.

This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction.

Vickrey's original paper mainly considered auctions where only a single, indivisible good is being sold. The terms Vickrey auction and second-price sealed-bid auction are, in this case only, equivalent and used interchangeably. In the case of multiple identical goods, the bidders submit inverse demand curves and pay the opportunity cost.

Vickrey auctions are much studied in economic literature but uncommon in practice. Generalized variants of the Vickrey auction for multiunit auctions exist, such as the generalized second-price auction used in Google's and Yahoo!'s online advertisement programs (not incentive compatible) and the Vickrey–Clarke–Groves auction (incentive compatible). e(v)=\tfrac{1}{2}v. We now argue that in the sealed first price auction the equilibrium bid of a buyer with valuation v is B(v)=e(v)=\tfrac{1}{2}v. That is, the payment of the winner in the sealed first-price auction is equal to the expected revenue in the sealed second-price auction.

Proof of revenue equivalence Suppose that buyer 2 bids according to the strategy B(v) = v/2 , where B(v) is the buyer's bid for a valuation v . We need to show that buyer 1's best response is to use the same strategy. Note first that if buyer 2 uses the strategy B(v) = v/2 , then buyer 2's maximum bid is B(1) = 1/2 and so buyer 1 wins with probability 1 with any bid of 1/2 or more.

Consider then a bid b on the interval [0,1/2] . Let buyer 2's value be x . Then buyer 1 wins if B(x) = x/2 , that is, if x . Under Vickrey's assumption of uniformly distributed values, the win probability is w(b) = 2b . Buyer 1's expected payoff is therefore U(b)=w(b)(v-b)=2b(v-b)=\tfrac{1}{2}[v^2-(v-2b)^2] Note that U(b) takes on its maximum at b = v/2 = B(v) . p_k = d_k + \operatorname{MCF}(G - e_k) - \operatorname{MCF}(G), 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–Rényi random graph with n nodes and edge probability p, \scriptstyle G \in G(n, p) approaches \frac{p}{2-p} as n, approaches \scriptstyle \infty , for n p = \omega(\sqrt{n \log n}) .

Prior to this result, it was known that VCG overpayment in G(n, p) is \Omega\left(\frac{1}{np}\right) and O(1)\, with high probability given np=\omega(\log n).\,

Text derived from https://en.wikipedia.org/w/index.php?oldid=1338833083 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.