Vickrey–Clarke–Groves auction

Formal description

Notation

For any set of auctioned items ${\displaystyle M=\{t_1,\dots ,t_m\}}$ and any set of bidders ${\displaystyle N=\{b_1,\dots ,b_n\}}$, let ${\displaystyle V_N^M}$ be the social value of the VCG auction for a given bid-combination. That is, how much each person values the items they've just won, added up across everyone. The value of the item is zero if they do not win. For a bidder ${\displaystyle b_i}$ and item ${\displaystyle t_j}$, let the bidder's bid for the item be ${\displaystyle v_i(t_j)}$. The notation ${\displaystyle A\setminus B}$ means the set of elements of A which are not elements of B.

Assignment

A bidder ${\displaystyle b_i}$ whose bid for an item ${\displaystyle t_j}$ is an "overbid", namely ${\displaystyle v_i(t_j)}$, wins the item, but pays ${\displaystyle V_{N\setminus \{b_i\}}^M-V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}}$, which is the social cost of their winning that is incurred by the rest of the agents.

Explanation

Indeed, the set of bidders other than ${\displaystyle b_i}$ is ${\displaystyle N\setminus \{b_i\}}$. When item ${\displaystyle t_j}$ is available, they could attain welfare ${\displaystyle V_{N\setminus \{b_i\}}^M.}$ The winning of the item by ${\displaystyle b_i}$ reduces the set of available items to ${\displaystyle M\setminus \{t_j\}}$, so the attainable welfare is now ${\displaystyle V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}}$. The difference between the two levels of welfare is therefore the loss in attainable welfare suffered by the rest of the bidders, as predicted, given the winner ${\displaystyle b_i}$ got the item ${\displaystyle t_j}$. This quantity depends on the offers of the rest of the agents and is unknown to agent ${\displaystyle b_i}$.

Winner's utility

The winning bidder whose bid is the true value ${\displaystyle A}$ for the item ${\displaystyle t_j}$, ${\displaystyle v_i(t_j)=A,}$ derives maximum utility ${\displaystyle A-\left(V_{N\setminus \{b_i\}}^M-V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}\right).}$

Examples

Two items, three bidders

Suppose two apples are being auctioned among three bidders.

• Bidder A wants one apple and is willing to pay $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, since their combined bid of $5 + $2 = $7 is greater than the bid for two apples by bidder C who is willing to pay only $6. Thus, after the auction, the value achieved by bidder A is $5, by bidder B is $2, and by bidder C is $0 (since bidder C gets nothing). Note that the determination of winners is essentially a knapsack problem.

Next, the formula for deciding payments gives:

• For bidder A: The payment for winning required of A is determined as follows: First, in an auction that excludes bidder A, the social-welfare maximizing outcome would assign both apples to bidder C for a total social value of $6. Next, the total social value of the original auction excluding A's value is computed as $7 − $5 = $2. Finally, subtract the second value from the first value. Thus, the payment required of A is $6 − $2 = $4.
• For bidder B: Similar to the above, the best outcome for an auction that excludes bidder B assigns both apples to bidder C for $6. The total social value of the original auction minus B's portion is $5. Thus, the payment required of B is $6 − $5 = $1.
• Finally, the payment for bidder C is (($5 + $2) − ($5 + $2)) = $0.

After the auction, A is $1 better off than before (paying $4 to gain $5 of utility), B is $1 better off than before (paying $1 to gain $2 of utility), and C is neutral (having not won anything).

Two bidders

Assume that there are two bidders, ${\displaystyle b_1}$ and ${\displaystyle b_2}$, two items, ${\displaystyle t_1}$ and ${\displaystyle t_2}$, and each bidder is allowed to obtain one item. We let ${\displaystyle v_{i,j}}$ be bidder ${\displaystyle b_i}$'s valuation for item ${\displaystyle t_j}$. Assume ${\displaystyle v_{1,1}=10}$, ${\displaystyle v_{1,2}=5}$, ${\displaystyle v_{2,1}=5}$, and ${\displaystyle v_{2,2}=3}$. We see that both ${\displaystyle b_1}$ and ${\displaystyle b_2}$ would prefer to receive item ${\displaystyle t_1}$; however, the socially optimal assignment gives item ${\displaystyle t_1}$ to bidder ${\displaystyle b_1}$ (so their achieved value is ${\displaystyle 10}$) and item ${\displaystyle t_2}$ to bidder ${\displaystyle b_2}$ (so their achieved value is ${\displaystyle 3}$). Hence, the total achieved value is ${\displaystyle 13}$, which is optimal.

If person ${\displaystyle b_2}$ were not in the auction, person ${\displaystyle b_1}$ would still be assigned to ${\displaystyle t_1}$, and hence person ${\displaystyle b_1}$ can gain nothing more. The current outcome is ${\displaystyle 10}$; hence ${\displaystyle b_2}$ is charged ${\displaystyle 10-10=0}$.

If person ${\displaystyle b_1}$ were not in the auction, ${\displaystyle t_1}$ would be assigned to ${\displaystyle b_2}$, and would have valuation ${\displaystyle 5}$. The current outcome is 3; hence ${\displaystyle b_1}$ is charged ${\displaystyle 5-3=2}$.

Example #3

Consider an auction of ${\displaystyle n}$ houses to ${\displaystyle n}$ bidders, who are to each receive a house. ${\displaystyle {\tilde{v}}_{ij}}$, represents the value player ${\displaystyle i}$ has for house ${\displaystyle j}$. Possible outcomes 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 ${\displaystyle {\tilde{b}}_{ij}}$, asking each player ${\displaystyle i}$ how much they would wish to bid for house ${\displaystyle j}$. Define ${\displaystyle b_i(a)={\tilde{b}}_{ik}}$ if bidder ${\displaystyle i}$ receives house ${\displaystyle k}$ in the matching ${\displaystyle a}$. Now compute ${\displaystyle a^{\ast }}$, a maximum weight bipartite matching with respect to the bids, and compute

${\displaystyle p_i=\left[\underset{a\in A}{max}\sum _{j\ne i}{b}_j(a)\right]-\sum _{j\ne i}{b}_j(a^{\ast })}$.

The first term is another max weight bipartite matching, and the second term can be computed easily from ${\displaystyle a^{\ast }}$.

Optimality of truthful bidding

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

For each bidder ${\displaystyle b_i}$, let ${\displaystyle v_i}$ be their true valuation of an item ${\displaystyle t_i}$, and suppose (without loss of generality) that ${\displaystyle b_i}$ wins ${\displaystyle t_i}$ upon submitting their true valuations. Then the net utility ${\displaystyle U_i}$ attained by ${\displaystyle b_i}$ is given by their own valuation of the item they've won, minus the price they've paid:

${\displaystyle \begin{array}{cc}{U}_i& =v_i-\left(V_{N\setminus \{b_i\}}^M-V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}\right)\\ & =\sum _j{v}_j-\sum _{j\ne i}{v}_j+V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}-V_{N\setminus \{b_i\}}^M\\ & =\sum _j{v}_j-V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}+V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}-V_{N\setminus \{b_i\}}^M\\ & =\sum _j{v}_j-V_{N\setminus \{b_i\}.}^M\end{array}}$

As ${\displaystyle V_{N\setminus \{b_i\}}^M}$ is independent of ${\displaystyle v_i}$, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility ${\displaystyle \sum _j{v}_j}$ for the declared bid ${\displaystyle v_i}$.

To make it clearer, let us form the difference ${\displaystyle U_i-U_j=\left[v_i+V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}\right]-\left[v_j+V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}\right]}$ between net utility ${\displaystyle U_i}$ of ${\displaystyle b_i}$ under truthful bidding ${\displaystyle v_i}$ gotten item ${\displaystyle t_i}$, and net utility ${\displaystyle U_j}$ of bidder ${\displaystyle b_i}$ under non-truthful bidding ${\displaystyle v_i^{\prime }}$ for item ${\displaystyle t_i}$ gotten item ${\displaystyle t_j}$ on true utility ${\displaystyle v_j}$.

${\displaystyle \left[v_j+V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}\right]}$ is the corporate gross utility obtained with the non-truthful bidding. But the allocation assigning ${\displaystyle t_j}$ to ${\displaystyle b_i}$ is different from the allocation assigning ${\displaystyle t_i}$ to ${\displaystyle b_i}$ which gets maximum (true) gross corporate utility. Hence ${\displaystyle \left[v_i+V_{N\setminus \{b_i\}}^{M\setminus \{t_i\}}\right]-\left[v_j+V_{N\setminus \{b_i\}}^{M\setminus \{t_j\}}\right]\ge 0}$ and ${\displaystyle U_i\ge U_j}$ q.e.d.