Vickrey–Clarke–Groves auction

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, while ensuring each bidder receives at most one item. This system charges each individual the harm they cause to other bidders, 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, Edward H. Clarke, and Theodore Groves.

A 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$ 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 introduction of Vickrey Auction.

Example #2

Assume that there are two bidders, b₁ and b₂, two items, t₁ and t₂, 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₁ and b₂ would prefer to receive item t₁; however, the socially optimal assignment gives item t₁ to bidder b₁ (so his achieved value is 10) and item t₂ to bidder b₂ (so his achieved value is 3). Hence, the total achieved value is 13, which is optimal.

If person b₂ were not in the auction, person b₁ would still be assigned to t₁, and hence no harm was done for that bidder. Hence, b₂ is charged nothing.

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

Optimality of Truthful Bidding

The following is a proof that bidding one's true valuations for the auctioned items is optimal

For each bidder b_i, let v_i be her true valuation of an item t_i, and suppose (without loss of generality) that b₁ wins t₁ upon submitting his true valuations.

Note that the size bid of b₁ has no effect on her utility as long as she wins the item (see the utility function above). Hence, we assume that b₁ does not bid truthfully, and receives item t_j because of his non-truthful bidding. In the truthful bidding case, b₁ 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₁ 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₁ received t₁, and the second term there is the maximum total social value achieved when b₁ received t_j. However, we assumed that the VCG auction gave b₁ item t₁; hence, the first term must be greater, and $U_1 - U_2 \geq 0$.

More general setting

We can consider a more general setting 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

∑	vi(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.