Notation

For any set of auctioned items ${\displaystyle M=\{t_{1},\ldots ,t_{m}\}}$ and any set of bidders ${\displaystyle N=\{b_{1},\ldots ,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).}$

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^{*}}$, a maximum weight bipartite matching with respect to the bids, and compute

${\displaystyle 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 ${\displaystyle a^{*}}$.