Vickrey–Clarke–Groves auction

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.

Formal description

Notation

For any set of auctioned items $M = \{t_1,\ldots,t_m\}$ and any 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. For a bidder $b_i$ and item $t_j$, let the bidder's bid for the item be $v_{i}(t_{j})$. The notation $A \setminus B$ means the set of elements of A which are not elements of B.

Assignment

A bidder $b_i$ whose bid for an item $t_j$, namely $v_{i}(t_{j})$, is an "overbid" wins the item, 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.

Explanation

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

Winner's utility

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

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

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

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

To make it clearer, 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 true utility $v_j$.

$\left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]$ is the corporate gross utility obtained with the non-truthful bidding. But the allocation assigning $t_j$ to $b_i$ is different from the allocation assigning $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.

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

1. von Ahn, Luis (2011-10-13). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. Retrieved 2015-04-13.
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