# Vickrey–Clarke–Groves auction

"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

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

### Example #1

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

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

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

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.