Vickrey–Clarke–Groves auction

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"VCG" redirects here. For the heartbeat recording method see Vectorcardiography.

In auction theory, a Vickrey–Clarke–Groves (VCG) auction of multiple goods is a sealed-bid auction wherein bidders report their valuations for the items. The auction system assigns the items in a socially optimal manner. This system charges each individual the harm they cause to other bidders,[1] and ensures that the optimal strategy for a bidder is to bid the true valuations of the objects. 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.

Formal description[edit]

For any set of auctioned items M = \{t_1,\ldots,t_m\} and a set of bidders N = \{b_1,\ldots,b_n\}, let V^M_N be the social value of the VCG auction for a given bid-combination. A bidder b_i who wins an item t_j pays V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}, which is the social cost of his winning that is incurred by the rest of the agents

Indeed, the set of bidders other than b_i is N \setminus \{b_i\}. When item t_j is available, they could attain welfare V^{M}_{N \setminus \{b_i\}}. The winning of the item by b_i reduces the set of available items to M \setminus \{t_j\}, however, so that the attainable welfare is now V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}. The difference between the two levels of welfare is the payment for t_j paid by the winning bidder b_i.

The winning bidder who has value A for the item t_j derives therefore utility A - \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right).

Examples[edit]

Example #1[edit]

See the example with apples in the Generalization section of Vickrey Auction.

Example #2[edit]

Assume that there are two bidders, b_1 and b_2, two items, t_1 and t_2, and each bidder is allowed to obtain one item. We let v_{i,j} be bidder b_i's valuation for item t_j. Assume v_{1,1} = 10, v_{1,2} = 5, v_{2,1} = 5, and v_{2,2} = 3. We see that both b_1 and b_2 would prefer to receive item t_1; however, the socially optimal assignment gives item t_1 to bidder b_1 (so his achieved value is 10) and item t_2 to bidder b_2 (so his achieved value is 3). Hence, the total achieved value is 13, which is optimal.

If person b_2 were not in the auction, person b_1 would still be assigned to t_1, and hence person b_1 can gain nothing. The current outcome is 10 hence b_2 is charged 10-10=0.

If person b_1 were not in the auction, t_1 would be assigned to b_2, and would have valuation 5. The current outcome is 3 hence b_1 is charged 5-3=2.

Example #3[edit]

Here we will look at a multiple item auction. Consider the situation when there are n bidders, n houses, and values \tilde v_{ij}, representing the value player i has for house j. 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 \tilde b_{ij}, asking each player i how much he would wish to bid for house j. Define b_i(a) = \tilde b_{ik} if bidder i receives house k in the matching a. Now compute a^*, a maximum weight bipartite matching with respect to the bids, and compute

p_i = \left[ \max_{a \in A} \sum_{j \neq i} b_j(a) \right] - \sum_{j \neq i} b_j(a^*) .

The first term is another max weight bipartite matching, and the second term can be computed easily from a^*.

Optimality of Truthful Bidding[edit]

The following is a proof that bidding one's true valuations for the auctioned items is optimal[5]

For each bidder b_i, let v_i be his true valuation of an item t_i, and suppose (without loss of generality) that b_1 wins t_1 upon submitting his true valuations.

Note that the size bid of b_1 has no effect on his utility as long as he wins the item (see the utility function above). Hence, we assume that b_1 does not bid truthfully, and receives item t_j because of his non-truthful bidding. In the truthful bidding case, b_1 has total utility U_1 = v_1-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right). In the untruthful bidding case, b_1 has total utility U_2 = v_j-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right). Hence, we must prove that U_1 - U_2 \geq 0, which shows that the utility received from truthful bidding is always at least that received from untruthful bidding.

U_1 - U_2 = v_1 - \left(V^{M}_{N \setminus \{b_1\}} - V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right) - v_j + \left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right) = \left[v_1 + V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right]

However, the first term there is the maximum total social value achieved when b_1 received t_1, and the second term there is the maximum total social value achieved when b_1 received t_j. However, we assumed that the VCG auction gave b_1 item t_1; hence, the first term must be greater, and U_1 - U_2 \geq 0.

More general setting[edit]

We can consider a more general setting[6] of the VCG mechanism. Consider a set A of possible outcomes and n bidders which have different valuations for each outcome. This can be expressed as, function

v_i : A \longrightarrow R_+

for each bidder i which expresses the value it has for each alternative. In this auction, each bidder will submit his valuation and the VCG mechanism will choose the alternative a \in A that maximizes  \sum_i v_i(a) and charge prices p_i given by:

p_i = h_i(v_{-i}) - \sum_{j \neq i} v_j(a)

where v_{-i} = (v_1, \dots, v_{i-1}, v_{i+1}, \dots, v_n), that is, h_i is a function that only depends on the valuation of the other players. This alone gives a truthful mechanism, that is, a mechanism where bidding the true valuation is a dominant strategy.

We could take, for example, h_i(v_{-i}) = 0, but we would have all prices negative, which might not be desirable. We would rather prefer that players give money to the mechanism than the other way around. The function:

h_i(v_{-i}) = \max_{b \in A} \sum_{j \neq i} v_j(b)

is called Clarke pivot rule.

On the other hand, if we do not know the values v_i, we can solicit bids b_i : A \longrightarrow R_+. The mechanism then chooses a^* maximizing the revenue \sum_i b_i(a^*), treating the bids like the values. We then set

p_i = \left[ \max_{a \in A} \sum_{j \neq i} b_j(a) \right] - \sum_{j \neq i} b_j(a^*).

Intuitively, the mechanism charges player i his externality, or the decrease in optimal social welfare when he is included in the auction.

The Clark pivot rule has some very good properties as:

  • it is individually rational, i.e., v_i (a) - p_i \geq 0. It means that all the players are getting positive utility by participating in the auction. No one is forced to bid.
  • it has no positive transfers, i.e., p_i \geq 0. The mechanism does not need to pay anything to the bidders.

See also[edit]

References[edit]

  1. ^ von Ahn, Luis (2008-10-07). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. Retrieved 2008-11-05. 
  2. ^ 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. 
  3. ^ Clarke, E. (1971). "Multipart Pricing of Public Goods". Public Choice 11 (1): 17–33. 
  4. ^ Groves, T. (1973). "Incentives in Teams". Econometrica 41 (4): 617–631. 
  5. ^ von Ahn, Luis (2008-10-07). "Assignment 5 Solutions" (PDF). 15–396: Science of the Web Published Solutions. Carnegie Mellon University. Retrieved 2008-11-05. 
  6. ^ Nisan, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007