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 therefore the loss in attainable welfare suffered by the rest bidders given the winner b_i got the item t_j. In other words it is the social cost incurred by the rest as predicted. This quantity depends on the offers of the rest agents and is unknown to agent b_i. According Vickrey-Clarke-Groves recipe which is an improvement of Vickrey' s auction recipe it is the payment for t_j paid by the winning bidder b_i.

The highest bidder is the winning, but he pays for the auctioned object the social cost incurred by the rest of the agents.

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_i wins t_i upon submitting his true valuations.

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

U_i - U_j = v_i - \left(V^{M}_{N \setminus \{b_i\}} - V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right) - v_j + \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right) = \left[v_i + V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\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_i - U_j \geq 0.

The following is an alternative and simpler proof of Vickrey-Clark-Groves auction theorem.[6]

If our bidder offers anything, he may sometimes win, sometimes don' t get the item, that is zero balance, and sometimes lose. It depends on the incurred social loss of the rest agents. We shall prove that if he offers his true valuation he has the greatest probability to gain something and at the same time zero probability to lose. Let v_i be the actual bid of our bidder for item t_i and A his honest value for the same item and let u_i be the social cost suffered by the rest agents. If v_i < A he can hope to get the object at a gain A-u_i if v_i > u_i. The relative probability of this to happen is v_i \div A. This is maximized to 1 for v_i = A. If v_i > A he runs the risk to lose u_i - A if v_i > u_i > A and the relative probability of this to happen is (v_i-A)\div v_i. This is zeroed again for v_i = A.

The theorem thus proven has as conclusion that the utility value obtained by honest bidding is maximized. In other words the private interest of the highest bidder is optimally served. But as we see from the foregoing mathematical transformations also the total social value achieved is maximum. This is the magic of Vickrey-Clarke-Groves recipe: It coordinates the private interest with the public!

More general setting[edit]

We can consider a more general setting[7] 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. doi:10.1007/bf01726210. 
  4. ^ Groves, T. (1973). "Incentives in Teams". Econometrica 41 (4): 617–631. doi:10.2307/1914085. 
  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. ^ Morton, Davis (2001), The Math of Money
  7. ^ Nisan, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007