# 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 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 the payment for $t_j$ paid by the winning bidder $b_i$.

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

### 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_1$ wins $t_1$ upon submitting his true valuations.

Note that the size bid of $b_1$ has no effect on his utility as long as he wins the item (see the utility function above). 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$.

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