Vickrey auction

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.

A generalization of the Vickrey auction that maintains the incentive to bid truthfully is known as the Vickrey-Clarke-Groves (VCG) mechanism. The idea in VCG is that each player in the auction pays the opportunity cost that their presence introduces to all the other players. For example, suppose that we want to auction two apples, and we have three bidders. Bidder A wants one apple and bids $5 for that apple. Bidder B wants one apple and is willing to pay $2 for it. Bidder C wants two apples and is willing to pay $6 to have both of them, but is uninterested in buying only one without the other. First, we decide the outcome of the auction by maximizing bids: the apples go to bidder A and bidder B. Next, to decide payments, we consider the opportunity cost that each bidder imposed on the rest of the bidders. Currently, B has a utility of $2. If bidder A had not been present, C would have won, and had a utility of $6, so A pays $6-$2 = $4. For the payment of bidder B: currently A has a utility of $5 and C has a utility of 0. If bidder B had been absent, C would have won and had a utility of $6, so B pays $6-$5 = $1. The outcome is identical whether or not bidder C participates, so C does not need to pay anything.

Vickrey auctions are much studied in economic literature, but are not particularly common in practice. One market in which they have been used is stamp collecting. eBay's system of proxy bidding is similar, but not identical, to a Vickrey auction. A slight generalized variant of a Vickrey auction, named generalized second-price auction, which is different from the VCG mechanism, is known to be used in Google's and Yahoo!'s online advertisement programmes. [Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz: "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords". American Economic Review 97(1), 2007 pp 242-259.] [Hal R. Varian: "Position Auctions". International Journal of Industrial Organization, 2006,doi:10.1016/j.ijindorg.2006.10.002 .]

Properties

elf-revelation/Incentive compatibility

In a Vickrey auction with independent private values (IPV) each bidder maximizes his or her expected utility by bidding (revealing) his or her true valuation.

Ex-post efficiency

A Vickrey auction is ex post efficient (the winner is the bidder with the highest valuation) under the most general circumstances; it thus provides a baseline model against which the efficiency properties of other types of auctions can be posited.

Weaknesses

Despite the Vickrey auction's strengths, it has shortcomings:

*It does not allow for Price discovery, that is, discovery of the market price if the buyers are unsure of their own valuations, without sequential auctions.

*Sellers may use shill bids to increase profit.

*In iterated Vickrey auctions, the strategy of revealing true valuations is no longer dominant.

The Vickrey-Clarke-Groves (VCG) mechanism has the additional shortcomings:

*It is vulnerable to collusion by losing bidders.

*It is vulnerable to shill bidding with respect to the buyers.

*It does not necessarily maximize seller revenues; seller revenues may even be zero in VCG auctions. If the purpose of holding the auction is to maximize profit for the seller rather than just allocate resources among buyers, then VCG may be a poor choice.

*The seller's revenues are non-monotonic with regard to the sets of bidders and offers.

The non-monotonicity of seller's revenues with respect to bids can be shown by the following example. Consider 3 bidders A, B, and C, and two homogeneous items bid upon, Y and Z. A wants both items and bids $2 for the package of Y and Z. B and C both bid $2 each for a single item (bid $2 for Y or Z), as they really want one item but don't care if they have the second. Now, Y and Z are allocated to B and C, but the price is $0, as can be found by removing either B or C respectively. If C bid $0 instead of $2, then the seller would make $2 instead of $0. Because the seller's revenue can also go up when bids are increased, the seller's revenues are non-monotonic with respect to bids.

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 "d""k" of each of the links and payment is calculated as follows:

Each link (or node) scriptstyle e_k in the MCF is paid

:p_{k} = d_{k} + MCF(G - e_{k}) - 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", 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

:Omegaleft(frac{1}{np} ight)

and

:O(1),

with high probability given

:np=omega(log n).,

External links

* [http://www.u.arizona.edu/~dreiley/papers/VickreyHistory.pdf Paper on the history of Vickrey auctions in stamp collecting]

References

*Vijay Krishna, "Auction Theory"
*Peter Cramton, Yoav Shoham, Richard Steinberg (Eds), Combinatorial Auctions (2006), Chapter 1. ISBN 0-262-03342-9.
*Paul Milgrom, "Putting Auction Theory to Work"

Notes


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Vickrey auction — noun A type of sealed bid auction, where bidders submit written bids without knowing the bids of others, in which the highest bidder wins but the price paid is the second highest bid …   Wiktionary

  • Vickrey-Clarke-Groves mechanism — Vickrey Clarke Groves Mechanisms (VCG Mechanisms) are a generalization of the Vickrey auction.VCG Mechanism for the provision of public goodsThe price of the public good is divided by the number of players, and evenly distributed among them. The… …   Wikipedia

  • Auction — Auctioneer redirects here. For the DC Comics supervillain, see Auctioneer (comics). An auctioneer and her assistants scan the crowd for bidders. An auction is a process of buying and selling goods or services by offering them up for bid, taking… …   Wikipedia

  • Vickrey, William — ▪ American economist in full  William Spencer Vickrey   born June 21, 1914, Victoria, British Columbia, Canada died October 11, 1996, Harrison, New York, U.S.       Canadian born American economist who brought innovative analysis to the problems… …   Universalium

  • Auction theory — is an applied branch of game theory which deals with how people act in auction markets and researches the game theoretic properties of auction markets. There are many possible designs (or sets of rules) for an auction and typical issues studied… …   Wikipedia

  • Vickrey-Clarke-Groves-Mechanismus — Vickrey Clarke Groves Mechanismen (VCG Mechanismen) sind eine Verallgemeinerung der Vickreyauktion. Mit diesem Begriff wird eine Klasse von Mechanismen bezeichnet, deren Mitglieder die Eigenschaft haben, dass wahrheitsgemäßes Bieten eine… …   Deutsch Wikipedia

  • Vickrey-Clarke-Groves — Enchère de Vickrey Une enchère de Vickrey ou enchère au second prix est un type d enchère à plis fermés où le lot est attribué au plus offrant mais au prix donné par le deuxième plus offrant. Elles portent le nom de William Vickrey, qui a… …   Wikipédia en Français

  • Vickrey-Auktion — Die Vickreyauktion ist eine Auktionsform. Sie ist auch unter der Bezeichnung Zweitpreisauktion (Second Price Sealed Bid Auction) bekannt. Die Vickreyauktion ist nach ihrem Erfinder, dem Nobelpreisträger William Vickrey, benannt und zeigt ihre… …   Deutsch Wikipedia

  • William Vickrey — Infobox Scientist name = William Vickrey image size = 180px birth date = birth date|1914|6|21|mf=y birth place = Victoria, British Columbia, Canada death date = death date and age|1996|10|11|1914|6|21|mf=y death place = Harrison, New York, USA… …   Wikipedia

  • English auction — An English auction is a type of auction, whose most typical form[clarification needed] is the open outcry auction. The auctioneer opens the auction by announcing a Suggested Opening Bid, a starting price or reserve for the item on sale and then… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”