Vickrey–Clarke–Groves auction Information & Vickrey–Clarke–Groves auction Links at HealthHaven.com

A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction where multiple items are up for bid, and each bidder submits a different value for each item. The auction system assigns the items in a socially optimal manner, while ensuring each bidder receives at most one item. 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.

[edit] Formal notation

Let $M = \{t_1,\ldots,t_m\}$ be the set of items, $N = \{b_1,\ldots,b_n\}$ be the set of bidders. We also define $V^M_N$ to be the total social value achieved in a VCG auction run with items $M$ and bidders $N$ , with a given set of valuations submitted by the bidders.

Note that if bidder $b i$ is assigned item $t j$ , his cost in the VCG system is defined to be $V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}$ . The first term is the social value should person $b i$ be removed from the auction, the second term is the social value should person $b i$ and item $t j$ be removed from the auction. Hence, the second term is the social value received by all the other people when $b i$ participated in the auction, the first term is the social value received by all the other people when $b i$ did not participate in the auction, and hence their difference is the total harm caused by $b i$ .

Based on this, if the true valuation of item $t j$ by bidder $b i$ is $A$ , than the total utility achieved by bidder $b i$ in this auction is $A - \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right)$ (the value received by bidder $b i$ minus the cost assigned to him).

[edit] Example auctions

[edit] Example #1

Assume that there are two bidders $b 1$ and $b 2$ , and two items, $t 1$ and $t 2$ . 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 no harm was done for that bidder. Hence, $b 2$ is charged nothing.

If person $b 1$ were not in the auction, person $b 2$ would be assigned to $t 1$ , and would have valuation $5$ . $b 1$ thus caused $2$ harm to $b 2$ , and hence $b 1$ is charged $2$ .

[edit] Example #2

Suppose that we want to auction two apples, and we have 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, we decide the outcome of the auction by maximizing bids: the apples go to bidder A and bidder B. Next, to decide payments, we consider the opportunity cost that each bidder imposed on the rest of the bidders. Currently, B has a utility of $2. If bidder A had not been present, C would have won, and had a utility of $6, so A pays $6–$2 = $4. For the payment of bidder B: currently A has a utility of $5 and C has a utility of 0. If bidder B had been absent, C would have won and had a utility of $6, so B pays $6–$5 = $1. The outcome is identical whether or not bidder C participates, so C does not need to pay anything.

[edit] Proof of optimality of truthful bidding

The following is one proof that bidding the one's true valuations for the items is optimal:^[2]

We pick arbitrary bidder $b 1$ to focus on, and let $v i$ be his true valuation of item $t i$ . Assume without loss of generality that if $b 1$ submits his true values, the VCG auction assigns him item $t 1$ . We first note that what $b 1$ bids has no effect on his utility, assuming he receives the same item, since the value of $b 1$ 's utility is independent of the value of his bids.

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$ .

[edit] More general setting

We can consider a more general setting^[3] 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

∑	v_i(a)
i

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, what might not be desirable - we would rather prefer that players give money to the mechanism than the other way round. The function:

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

is called Clarke pivot rule. It 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 really being forced do bid.

it has no positive transfers, i.e., $p_i \geq 0$ . So the mechanism doesn't need to pay anything to the bidders.

[edit] References

^ von Ahn, Luis (2008-10-07). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. http://scienceoftheweb.org/15-396/lectures/lecture11.pdf. Retrieved 2008-11-05.
^ von Ahn, Luis (2008-10-07). "Assignment 5 Solutions" (PDF). 15–396: Science of the Web Published Solutions. Carnegie Mellon University. http://www.scienceoftheweb.org/15-396/assignments/assignment5_solutions.pdf. Retrieved 2008-11-05.
^ Nisam, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007

[0] von Ahn, Luis (2008-10-07). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. http://scienceoftheweb.org/15-396/lectures/lecture11.pdf. Retrieved 2008-11-05.

[1] von Ahn, Luis (2008-10-07). "Assignment 5 Solutions" (PDF). 15–396: Science of the Web Published Solutions. Carnegie Mellon University. http://www.scienceoftheweb.org/15-396/assignments/assignment5_solutions.pdf. Retrieved 2008-11-05.

[2] Nisam, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007

[1]

[2]

[3]

Contents