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 overbids with v_{i}(t_{j}) for an item t_j wins it, but 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, as predicted, given the winner b_i got the item t_j. This quantity depends on the offers of the rest agents and is unknown to agent b_i.

The winning bidder whose bid is his true value A for the item t_j, v_{i}(t_{j})=A, derives maximum 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. Then the net utility U_i attained by b_i is given by U_i = v_i-\left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right)=\sum_{i}v_i-\sum_{j\neq i}v_j+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}}=\sum_i v_i-V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}}=\sum_i v_i-V^M_{N\setminus\{b_i\}}. As V^M_{N\setminus\{b_i\}} is independent of v_i, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility \sum_i v_i for the declared bid v_i.

Let us form the difference U_i - U_j = \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] between net utility U_i of b_i under truthful bidding v_i gotten item t_i, and net utility U_j of bidder b_i under non-truthful bidding v'_i for item t_i gotten item t_j on utility v_j.

\left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right] is the maximum corporate gross utility obtained with the non-truthful bidding. But the allocation assigning t_j to b_i is different from the allocation of t_i to b_i which gets maximum true gross corporate utility. Hence \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]\geq 0 and U_i\geq U_j q.e.d.

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 Clark 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. ^ http://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf
  6. ^ Nisan, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007