Vickrey–Clarke–Groves auction
<templatestyles src="Module:Hatnote/styles.css"></templatestyles>
In auction theory, a Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other people in the auction. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders.[1] It also gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items. It is a generalization of a Vickrey auction for multiple items.
The auction is named after William Vickrey,[2] Edward H. Clarke,[3] and Theodore Groves[4] for their papers that successively generalized the idea.
Contents
Intuitive description
We consider an auction where a set of identical products are being sold. Bidders can take part in the auction by announcing the maximum price they are willing to pay to receive N products. Each buyer is allowed to declare more than one bid, since its willingness-to-pay per unit might be different depending on the total number of units it receives. Bidders cannot see other people's bids at any moment since they are sealed (only visible to the auction system). Once all the bids are made, the auction is closed.
All the possible combinations of bids are then considered by the auction system, and the one maximizing the total sum of bids is kept, with the condition that it does not exceed the total amount of products available and that at most one bid from each bidder can be used. Bidders who have made a successful bid then receive the product quantity specified in their bid. The price they pay in exchange, however, is not the amount they had bid initially but only the marginal harm their bid has caused to other bidders (which is at most as high as their original bid).
This marginal harm caused to other participants (i.e. the final price paid by each individual with a successful bid) can be calculated as: (sum of bids of the auction from the second best combination of bids) - (what other bidders have bidden in the current (best) combination of bids). If the sum of bids of the second best combination of bids is the same as that of the best combination, then the price paid by the buyers will be the same as their initial bid. In all other cases, the price paid by the buyers will be lower.
At the end of the auction, the total utility has been maximized since all the goods have been attributed to the people with the highest combined willingness-to-pay. If agents are fully rational and in the absence of collusion, we can assume that the willingness to pay have been reported truthfully since only the marginal harm to other bidders will be charged to each participant, making it a dominant strategy. The type of auction, however, will not maximize the seller's revenue unless the sum of bids of the second best combination of bids is equal to the sum of bids of the best combination of bids.
Formal description
- Notation
For any set of auctioned items and any set of bidders
, let
be the social value[clarification needed] of the VCG auction for a given bid-combination. For a bidder
and item
, let the bidder's bid for the item be
. The notation
means the set of elements of A which are not elements of B.
- Assignment
A bidder whose bid for an item
, namely
, is an "overbid" wins the item, but pays
, which is the social cost of his winning that is incurred by the rest of the agents.
- Explanation
Indeed, the set of bidders other than is
. When item
is available, they could attain welfare
The winning of the item by
reduces the set of available items to
, however, so that the attainable welfare is now
. The difference between the two levels of welfare is therefore the loss in attainable welfare suffered by the rest bidders, as predicted, given the winner
got the item
. This quantity depends on the offers of the rest agents and is unknown to agent
.
- Winner's utility
The winning bidder whose bid is his true value for the item
,
derives maximum utility
Examples
Example #1
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 $6 ($0 + $6). So B pays $1 ($6 − $5).
- Similarly, C pays $0 (($5 + $2) − ($5 + $2)).
Example #2
Assume that there are two bidders, and
, two items,
and
, and each bidder is allowed to obtain one item. We let
be bidder
's valuation for item
. Assume
,
,
, and
. We see that both
and
would prefer to receive item
; however, the socially optimal assignment gives item
to bidder
(so his achieved value is
) and item
to bidder
(so his achieved value is
). Hence, the total achieved value is
, which is optimal.
If person were not in the auction, person
would still be assigned to
, and hence person
can gain nothing. The current outcome is
hence
is charged
.
If person were not in the auction,
would be assigned to
, and would have valuation
. The current outcome is 3 hence
is charged
.
Example #3
Here we will look at a multiple item auction. Consider the situation when there are bidders,
houses, and values
, representing the value player
has for house
. Possible outcomes in this auction are characterized by bipartite matchings, pairing houses with people. If we know the values, then maximizing social welfare reduces to computing a maximum weight bipartite matching.
If we do not know the values, then we instead solicit bids , asking each player
how much he would wish to bid for house
. Define
if bidder
receives house
in the matching
. Now compute
, a maximum weight bipartite matching with respect to the bids, and compute
.
The first term is another max weight bipartite matching, and the second term can be computed easily from .
Optimality of Truthful Bidding
The following is a proof that bidding one's true valuations for the auctioned items is optimal.[5]
For each bidder , let
be his true valuation of an item
, and suppose (without loss of generality) that
wins
upon submitting his true valuations. Then the net utility
attained by
is given by
. As
is independent of
, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility
for the declared bid
.
To make it clearer, let us form the difference between net utility
of
under truthful bidding
gotten item
, and net utility
of bidder
under non-truthful bidding
for item
gotten item
on true utility
.
is the corporate gross utility obtained with the non-truthful bidding. But the allocation assigning
to
is different from the allocation assigning
to
which gets maximum (true) gross corporate utility. Hence
and
q.e.d.
See also
- Vickrey–Clarke–Groves mechanism: a generalization of VCG auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.
- Preference revelation
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ http://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf