https://en.wikipedia.org/wiki/Vickrey_auction

Jump to content
[ ] Main menu
Main menu
move to sidebar hide
Navigation

  * Main page
  * Contents
  * Current events
  * Random article
  * About Wikipedia
  * Contact us
  * Donate

Contribute

  * Help
  * Learn to edit
  * Community portal
  * Recent changes
  * Upload file

Languages
Language links are at the top of the page across from the title.
[wikipe] Wikipedia The Free Encyclopedia
Search
[                    ]
Search
  * Create account
  * Log in

[ ] Personal tools

  * Create account
  * Log in

Pages for logged out editors learn more

  * Contributions
  * Talk

[ ]

Contents

move to sidebar hide

  *  
    (Top)
  *  
    1Properties
    Toggle Properties subsection
      +  
        1.1Self-revelation and incentive compatibility
      +  
        1.2Ex-post efficiency
      +  
        1.3Weaknesses
  *  
    2Proof of dominance of truthful bidding
  *  
    3Revenue equivalence of the Vickrey auction and sealed first
    price auction
  *  
    4Use in network routing
  *  
    5Generalizations
  *  
    6See also
  *  
    7References
  *  
    8Notes

Toggle the table of contents
[ ] Toggle the table of contents

Vickrey auction

[ ] 13 languages

  * Cestina
  * Deutsch
  * Espanol
  * frsy
  * Francais
  * Italiano
  * `bryt
  * Nederlands
  * Ri Ben Yu 
  * Polski
  * Russkii
  * Svenska
  * Zhong Wen 

Edit links

  * Article
  * Talk

[ ] English

  * Read
  * Edit
  * View history

[ ] Tools
Tools
move to sidebar hide
Actions

  * Read
  * Edit
  * View history

General

  * What links here
  * Related changes
  * Upload file
  * Special pages
  * Permanent link
  * Page information
  * Cite this page
  * Wikidata item

Print/export

  * Download as PDF
  * Printable version

From Wikipedia, the free encyclopedia
Auction priced by second-highest sealed bid

Part of a series on
              Auctions
Auction Room, Christie's, circa 1808.
                Types
  * All-pay
  * Amsterdam
  * Anglo-Dutch
  * Barter double
  * Best/not best
  * Brazilian
  * Calcutta
  * Candle
  * Chinese
  * Click-box bidding
  * Combinatorial
  * Common value
  * Deferred-acceptance
  * Discriminatory price
  * Double
  * Dutch
  * English
  * Forward
  * French
  * Generalized first-price
  * Generalized second-price
  * Japanese
  * Multi-attribute
  * Multiunit
  * No-reserve
  * Rank
  * Reverse
  * Scottish
  * Sealed first-price
  * Simultaneous ascending
  * Single-price
  * Traffic light
  * Uniform price
  * Unique bid
  * Value of revenues
  * Vickrey
  * Vickrey-Clarke-Groves
  * Walrasian
  * Yankee

               Bidding
  * Shading
  * Calor licitantis
  * Cancellation hunt
  * Jump
  * Rigging
  * Sniping
  * Suicide
  * Tacit collusion

              Contexts
  * Algorithms
  * Autos
  * Art
  * Charity
  * Children
  * Cricket players
  * Domain names
  * Flowers
  * Loans
  * Scam
  * Slaves
  * Spectrum
  * Stamps
  * Virginity
  * Wine
  * Wives

               Theory
  * Digital goods
  * Price of anarchy
  * Revenue equivalence
  * Winner's curse

               Online
  * Ebidding
  * Private electronic market
  * Software

  * v
  * t
  * e

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^[1] though it had been used by stamp collectors since
1893.^[2] In 1797 Johann Wolfgang von Goethe sold a manuscript using
a sealed-bid, second-price auction.^[3]

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.^[4]

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 programmes
^[5]^[6] (not incentive compatible) and the Vickrey-Clarke-Groves
auction (incentive compatible).

Properties[edit]

Self-revelation and incentive compatibility[edit]

In a Vickrey auction with private values each bidder maximizes their
expected utility by bidding (revealing) their valuation of the item
for sale. These type of auctions are sometimes used for specified
pool trading in the agency mortgage-backed securities (MBS) market.

Ex-post efficiency[edit]

A Vickrey auction is decision efficient (the winner is the bidder
with the highest valuation) under the most general circumstances;^[
citation needed] it thus provides a baseline model against which the
efficiency properties of other types of auctions can be posited. It
is only ex-post efficient (sum of transfers equal to zero) if the
seller is included as "player zero," whose transfer equals the
negative of the sum of the other players' transfers (i.e. the bids).

Weaknesses[edit]

  * 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.

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

  * It is vulnerable to bidder collusion. If all bidders in Vickrey
    auction reveal their valuations to each other, they can lower
    some or all of their valuations, while preserving who wins the
    auction.^[7]
  * It is vulnerable to a version of shill bidding in which a buyer
    uses multiple identities in the auction in order to maximize its
    profit.^[8]
  * 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
(without introducing the VCG opportunity-cost mechanism described at
the bottom of this article) can be shown by the following example.
Consider three 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 go up when bids are either increased or decreased, the
seller's revenues are non-monotonic with respect to bids.

Proof of dominance of truthful bidding[edit]

The dominant strategy in a Vickrey auction with a single, indivisible
item is for each bidder to bid their true value of the item.^[9]

Let v i {\displaystyle v_{i}} v_{i} be bidder i's value for the item.
Let b i {\displaystyle b_{i}} b_{i} be bidder i's bid for the item.
The payoff for bidder i is { v i - max j [?] i b j if  b i > max j [?] i
b j 0 otherwise {\displaystyle {\begin{cases}v_{i}-\max _{j\neq i}b_
{j}&{\text{if }}b_{i}>\max _{j\neq i}b_{j}\\0&{\text{otherwise}}\end
{cases}}} {\begin{cases}v_{i}-\max _{{j\neq i}}b_{j}&{\text{if }}b_
{i}>\max _{{j\neq i}}b_{j}\\0&{\text{otherwise}}\end{cases}}

The strategy of overbidding is dominated by bidding truthfully.
Assume that bidder i bids b i > v i {\displaystyle b_{i}>v_{i}} b_
{i}>v_{i}.

If max j [?] i b j < v i {\displaystyle \max _{j\neq i}b_{j}<v_{i}} \
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 max j [?] i b j > b i {\displaystyle \max _{j\neq i}b_{j}>b_{i}} \
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 < max j [?] i b j < b i {\displaystyle v_{i}<\max _{j\neq i}b_
{j}<b_{i}} v_{i}<\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 b i < v i {\displaystyle b_{i}<v_{i}} b_{i}
<v_{i}.

If max j [?] i b j > v i {\displaystyle \max _{j\neq i}b_{j}>v_{i}} \
max _{{j\neq i}}b_{j}>v_{i} then the bidder would lose the item with
a truthful bid as well as an underbid, so the strategies have equal
payoffs for this case.

If max j [?] i b j < b i {\displaystyle \max _{j\neq i}b_{j}<b_{i}} \
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 < max j [?] i b j < v i {\displaystyle b_{i}<\max _{j\neq i}b_
{j}<v_{i}} b_{i}<\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 positive 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.

Revenue equivalence of the Vickrey auction and sealed first price
auction[edit]

The two most common auctions are the sealed first price (or high-bid)
auction and the open ascending price (or English) auction. In the
former each buyer submits a sealed bid. The high bidder is awarded
the item and pays his or her bid. In the latter, the auctioneer
announces successively higher asking prices and continues until no
one is willing to accept a higher price. Suppose that a buyer's
valuation is v {\displaystyle v} v and the current asking price is b
{\displaystyle b} b. If v < b {\displaystyle v<b} {\displaystyle v<b}
, then the buyer loses by raising his hand. If v > b {\displaystyle
v>b} {\displaystyle v>b} and the buyer is not the current high
bidder, it is more profitable to bid than to let someone else be the
winner. Thus it is a dominant strategy for a buyer to drop out of the
bidding when the asking price reaches his or her valuation. Thus,
just as in the Vickrey sealed second price auction, the price paid by
the buyer with the highest valuation is equal to the second highest
value.

Consider then the expected payment in the sealed second-price
auction. Vickrey considered the case of two buyers and assumed that
each buyer's value was an independent draw from a uniform
distribution with support [ 0 , 1 ] {\displaystyle [0,1]} [0,1]. With
buyers bidding according to their dominant strategies, a buyer with
valuation v {\displaystyle v} v wins if his opponent's value x < v {\
displaystyle x<v} {\displaystyle x<v}. Suppose that v {\displaystyle
v} v is the high value. Then the winning payment is uniformly
distributed on the interval [ 0 , v ] {\displaystyle [0,v]} {\
displaystyle [0,v]} and so the expected payment of the winner is

    e ( v ) = 1 2 v {\displaystyle e(v)={\tfrac {1}{2}}v} 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 {\displaystyle v} v is

    B ( v ) = e ( v ) = 1 2 v {\displaystyle B(v)=e(v)={\tfrac {1}
    {2}}v} 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
{\displaystyle B(v)=v/2} {\displaystyle B(v)=v/2}, where B ( v ) {\
displaystyle B(v)} B(v) is the buyer's bid for a valuation v {\
displaystyle v} 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 {\
displaystyle B(v)=v/2} {\displaystyle B(v)=v/2}, then buyer 2's
maximum bid is B ( 1 ) = 1 / 2 {\displaystyle B(1)=1/2} {\
displaystyle 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 {\displaystyle b} b on
the interval [ 0 , 1 / 2 ] {\displaystyle [0,1/2]} {\displaystyle
[0,1/2]}. Let buyer 2's value be x {\displaystyle x} x. Then buyer 1
wins if B ( x ) = x / 2 < b {\displaystyle B(x)=x/2<b} {\displaystyle
B(x)=x/2<b}, that is, if x < 2 b {\displaystyle x<2b} {\displaystyle
x<2b}. Under Vickrey's assumption of uniformly distributed values,
the win probability is w ( b ) = 2 b {\displaystyle w(b)=2b} {\
displaystyle w(b)=2b}. Buyer 1's expected payoff is therefore

    U ( b ) = w ( b ) ( v - b ) = 2 b ( v - b ) = 1 2 [ v 2 - ( v - 2
    b ) 2 ] {\displaystyle U(b)=w(b)(v-b)=2b(v-b)={\tfrac {1}{2}}
    [{{v}^{2}}-{{(v-2b)}^{2}}]} U(b)=w(b)(v-b)=2b(v-b)={\tfrac {1}
    {2}}[{{v}^{{2}}}-{{(v-2b)}^{{2}}}]

Note that U ( b ) {\displaystyle U(b)} {\displaystyle U(b)} takes on
its maximum at b = v / 2 = B ( v ) {\displaystyle b=v/2=B(v)} {\
displaystyle b=v/2=B(v)}.

Use in network routing[edit]

         This section needs additional citations for verification.
         Please help improve this article by adding citations to
[50px-Q] reliable sources in this section. Unsourced material may be
         challenged and removed. (May 2009) (Learn how and when to
         remove this template message)

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) e k {\displaystyle \scriptstyle e_{k}} \
scriptstyle e_{k} in the MCF is paid

    p k = d k + M C F ( G - e k ) - M C F ( G ) {\displaystyle p_{k}=
    d_{k}+MCF(G-e_{k})-MCF(G)} 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 - 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
Erdos-Renyi random graph with n nodes and edge probability p, G [?] G (
n , p ) {\displaystyle \scriptstyle G\in G(n,p)} \scriptstyle G\in G
(n,p) approaches

    p 2 - p {\displaystyle {\frac {p}{2-p}}} {\frac {p}{2-p}}

as n, approaches [?] {\displaystyle \scriptstyle \infty } \scriptstyle
\infty , for n p = o ( n log [?] n ) {\displaystyle np=\omega ({\sqrt
{n\log n}})} np=\omega ({\sqrt {n\log n}}). Prior to this result, it
was known that VCG overpayment in G(n, p) is

    O ( 1 n p ) {\displaystyle \Omega \left({\frac {1}{np}}\right)} \
    Omega \left({\frac {1}{np}}\right)

and

    O ( 1 ) {\displaystyle O(1)\,} O(1)\,

with high probability given

    n p = o ( log [?] n ) . {\displaystyle np=\omega (\log n).\,} np=\
    omega (\log n).\,

Generalizations[edit]

The most obvious generalization to multiple or divisible goods 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
items are assigned to maximize the sum of utilities; then each bidder
pays the "opportunity cost" that their presence introduces to all the
other players. This opportunity cost for a bidder is defined as the
total bids of all the other bidders that would have won if the first
bidder had not bid, minus the total bids of all the other actual
winning bidders.

A different kind of generalization is to set a reservation price--a
minimum price below which the item is not sold at all. In some cases,
setting a reservation price can substantially increase the revenue of
the auctioneer. This is an example of Bayesian-optimal mechanism
design.

In mechanism design, the revelation principle can be viewed as a
generalization of the Vickrey auction.

See also[edit]

  * Auction theory
  * First-price sealed-bid auction
  * VCG auction

References[edit]

  * Vijay Krishna, Auction Theory, Academic Press, 2002.
  * Peter Cramton, Yoav Shoham, Richard Steinberg (Eds),
    Combinatorial Auctions, MIT Press, 2006, Chapter 1. ISBN 
    0-262-03342-9.
  * Paul Milgrom, Putting Auction Theory to Work, Cambridge
    University Press, 2004.
  * Teck Ho, "Consumption and Production" UC Berkeley, Haas Class of
    2010.

Notes[edit]

 1. ^ Vickrey, William (1961). "Counterspeculation, Auctions, and
    Competitive Sealed Tenders". The Journal of Finance. 16 (1):
    8-37. doi:10.1111/j.1540-6261.1961.tb02789.x.
 2. ^ Lucking-Reiley, David (2000). "Vickrey Auctions in Practice:
    From Nineteenth-Century Philately to Twenty-First-Century
    E-Commerce". Journal of Economic Perspectives. 14 (3): 183-192.
    doi:10.1257/jep.14.3.183.
 3. ^ Benny Moldovanu and Manfred Tietzel (1998). "Goethe's
    Second-Price Auction". The Journal of Political Economy. 106 (4):
    854-859. CiteSeerX 10.1.1.560.8278. doi:10.1086/250032. JSTOR 
    2990730.
 4. ^ Jones, Derek (2003). "Auction Theory for the New Economy". New
    Economy Handbook. Emerald Publishing Ltd. ISBN 978-0123891723.
 5. ^ 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.
 6. ^ Hal R. Varian: "Position Auctions". International Journal of
    Industrial Organization, 2006, doi:10.1016/j.ijindorg.2006.10.002
    .
 7. ^ "Vickrey Auction". maxi-pedia.com.
 8. ^ Lawrence M. Ausubel, and Paul Milgrom . The Lovely but Lonely
    Vickrey Auction. Combinatorial Auctions, MIT Press, 2006, Chapter
    1, p. 12, .
 9. ^ von Ahn, Luis (30 September 2008). "Auctions" (PDF). 15-396:
    Science of the Web Course Notes. Carnegie Mellon University.
    Archived from the original (PDF) on 8 October 2008. Retrieved 6
    November 2008.

Authority control: National Edit this at Wikidata   * Germany

*
Retrieved from "https://en.wikipedia.org/w/index.php?title=
Vickrey_auction&oldid=1138519757"
Category:

  * Types of auction

Hidden categories:

  * Articles with short description
  * Short description matches Wikidata
  * All articles with unsourced statements
  * Articles with unsourced statements from November 2012
  * Articles needing additional references from May 2009
  * All articles needing additional references
  * Articles with GND identifiers

  * This page was last edited on 10 February 2023, at 03:31 (UTC).
  * Text is available under the Creative Commons
    Attribution-ShareAlike License 4.0 ; additional terms may apply.
    By using this site, you agree to the Terms of Use and Privacy
    Policy. Wikipedia(r) is a registered trademark of the Wikimedia
    Foundation, Inc., a non-profit organization.

  * Privacy policy
  * About Wikipedia
  * Disclaimers
  * Contact Wikipedia
  * Code of Conduct
  * Mobile view
  * Developers
  * Statistics
  * Cookie statement

  * Wikimedia Foundation
  * Powered by MediaWiki

Toggle limited content width