Vickrey auction
Encyclopedia
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, and in which 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. However, when either a divisible good or multiple identical goods are sold in a single auction, these terms are used differently.
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 didn't bid, minus the total bids of all the other actual winning bidders.
For example, suppose two apples are being auctioned among three bidders.
First, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B. Next, the formula for deciding payments gives:
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. NYU Law School uses an iterated version of the Vickrey auction model for its course registration lottery.
with independent private values (IPV) each bidder maximizes his or her expected utility by bidding (revealing) his or her true valuation.
The Vickrey–Clarke–Groves (VCG) mechanism has the additional shortcomings:
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.
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.
Let
be bidder i's value for the item. Let 
be bidder i's bid for the item.
The payoff for bidder i is
The strategy of overbidding is dominated by bidding truthfully. Assume that bidder i bids
.
If
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
then the bidder would lose the item either way so the strategies have equal payoffs in this case.
If
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
.
If
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
then the bidder would win the item either way so the strategies have equal payoffs in this case.
If
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.
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)
in the MCF is paid
,
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,
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
Auction
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder...
, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was created by William Vickrey
William Vickrey
William Spencer Vickrey was a Canadian professor of economics and Nobel Laureate. Vickrey was awarded the Nobel Memorial Prize in Economics with James Mirrlees for their research into the economic theory of incentives under asymmetric information...
. This type of auction is strategically similar to an English auction
English auction
An English auction is a type of auction, whose most typical form 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 accepts increasingly higher bids from the floor consisting of buyers with...
, and gives bidders an incentive to bid their true value
Incentive compatibility
In mechanism design, a process is said to be incentive-compatible if all of the participants fare best when they truthfully reveal any private information asked for by the mechanism. As an illustration, voting systems which create incentives to vote dishonestly lack the property of incentive...
.
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. However, when either a divisible good or multiple identical goods are sold in a single auction, these terms are used differently.
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
Uniform price auction
A uniform price auction is a multiunit auction in which a fixed number of identical units of a commodity are sold for the same price. Each bidder in the auction bids a price and a quantity. The price bid is considered the maximum price they are willing to pay per item, and the quantity is the...
. 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 didn't bid, minus the total bids of all the other actual winning bidders.
For example, suppose two apples are being auctioned among 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, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B. Next, the formula for deciding payments gives:
- A: B and C have total utility $2 (the amount they pay together: $2 + $0) - if A were removed, the optimal allocation would give B and C total utility $6 ($0 + $6). So A pays $4 (6$ − $2).
- B: A and C have total utility $5 ($5 + $0) - if B were removed, the optimal allocation would give A and C total utility $(0 + 6). So B pays $1 ($6 − $5).
- similarly, C pays $0 (5 + 2) − (5 + 2) = $0.
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
Stamp collecting
Stamp collecting is the collecting of postage stamps and related objects. It is one of the world's most popular hobbies, with the number of collectors in the United States alone estimated to be over 20 million.- Collecting :...
. eBay
EBay
eBay Inc. is an American internet consumer-to-consumer corporation that manages eBay.com, an online auction and shopping website in which people and businesses buy and sell a broad variety of goods and services worldwide...
's system of proxy bidding
Proxy bid
Proxy bidding is an implementation of an English second-price auction used on eBay, in which the winning bidder pays the price of the second-highest bid plus a defined increment. It differs from a Vickrey auction in that bids are not sealed; the "current highest bid" is always displayed...
is similar, but not identical, to a Vickrey auction. A slight generalized variant of a Vickrey auction, named generalized second-price auction
Generalized second-price auction
The generalized second-price auction is a non-truthful auction mechanism for multiple items. First thought of as a natural extension of the Vickrey auction, it actually doesn't conserve some good properties of the Vickrey auction . It is used mainly in the context of keyword auctions, where...
, which is different from the VCG mechanism, is known to be used in Google's and Yahoo!'s online advertisement programmes. NYU Law School uses an iterated version of the Vickrey auction model for its course registration lottery.
Self-revelation/incentive compatibility
In a Vickrey auctionAuction
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder...
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 decision 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. 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
Despite the Vickrey auction's strengths, it has shortcomings:- It does not allow for price discoveryPrice discoveryThe price discovery process is the process of determining the price of an asset in the marketplace through the interactions of buyers and sellers ....
, that is, discovery of the market price if the buyers are unsure of their own valuations, without sequential auctions. - Sellers may use shillShillA shill, plant or stooge is a person who helps a person or organization without disclosing that he or she has a close relationship with that person or organization...
bids to increase profit.
The Vickrey–Clarke–Groves (VCG) mechanism has the additional shortcomings:
- It is vulnerable to bidder collusionCollusionCollusion is an agreement between two or more persons, sometimes illegal and therefore secretive, to limit open competition by deceiving, misleading, or defrauding others of their legal rights, or to obtain an objective forbidden by law typically by defrauding or gaining an unfair advantage...
. 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. http://www.maxi-pedia.com/vickrey+auction - 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.
Proof of dominance of truthful bidding
The dominant strategy in a Vickrey auction with a single, indivisible item is for each bidder to bid their true value of the item.Let
be bidder i's value for the item. Let be bidder i's bid for the item.The payoff for bidder i is
The strategy of overbidding is dominated by bidding truthfully. Assume that bidder i bids
.If
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
then the bidder would lose the item either way so the strategies have equal payoffs in this case.If
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
.If
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
then the bidder would win the item either way so the strategies have equal payoffs in this case.If
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.
Use in network routing
In network routing, VCG mechanisms are a family of paymentPayment
A payment is the transfer of wealth from one party to another. A payment is usually made in exchange for the provision of goods, services or both, or to fulfill a legal obligation....
schemes based on the added value
Added value
Added value in financial analysis of shares is to be distinguished from value added. Used as a measure of shareholder value, calculated using the formula:...
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
Strategyproof
In game theory, an asymmetric game where players have private information is said to be strategyproof if there is no incentive for any of the players to lie about or hide their private information from the other players....
, but also the minimum among all strategyproof mechanisms.
In the case of network flows, Unicast
Unicast
right|200pxIn computer networking, unicast transmission is the sending of messages to a single network destination identified by a unique address.-Addressing methodologies:...
or Multicast
Multicast
In computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
, 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)
in the MCF is paid,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
Erdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
with n nodes and edge probability p,
approachesas n, approaches
, for . Prior to this result, it was known thatVCG overpayment in G(n, p) is
and
with high probability given