The VCG Auction
A VCG mechanism consists of $n$ strategic players and a finite set $\Omega$ of possible auction outcomes. Each player $i$ has a private valuation $v_i(\omega)$ for each outcome $\omega \in \Omega $. If assumed truthful bids, the allocation rule is to select an outcome $\omega^*=X(bid)$ that maximizes the sum of bids. \begin{equation} X(bid) = \arg\max_{\omega\in\Omega}{\sum_{i=1}^n{bid_i(\omega)}}. \end{equation} Then, the payment function is designed as \begin{equation} p_i(bid) = \max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)} - \sum_{j \neq i }{bid_j(\omega^{*})}, \end{equation} where $\omega^*=X(bid)$, in order to charge bidder (player) $i$ for its externality. This would make bidders tend to bid the true valuations as their dominant strategy. As a result, the utility (u_i(\omega)) for each bidder $i$ in outcome $\omega$ will be their private value minus their VCG payment as \begin{equation} u_i(\omega) = v_i(\omega) - p_i(bid). \end{equation}
Properties for VCG
Recall that the VCG mechanism is to (1) assume truthful bidding, pick the welfare-maximizing outcome due to the demand for welfare maximization, and (2) define a payment rule that leads to a DSIC mechanism. Besides, it also guaranteed us individual rationality (utilities of players are not negative) and weakly budget balance (total payment to central(auctioneer) is not negative).
Social Surplus Maximization
We can get social surplus maximized since we define our allocation rule as directly pick the welfare-maximizing outcome.
Truthful bidding (DSIC)
If we fix bidder $i$ and the bids of other bidders $bid_{-i}$, when the outcome $X(bid)$ chosen by the allocation rule is $\omega^*$, bidder $i$’s utility would be
\begin{equation*} \label{eq1}
\begin{split}
u_i(\omega^*) & = v_i(\omega^*) - p_i(bid) \
& = \Big[v_i(\omega^*)\Big] - \Big[\max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)} - \sum_{j \neq i }{bid_j(\omega^{*})}\Big] \
& = \Big[v_i(\omega^*) + \sum_{j \neq i }{bid_j(\omega^{*})}\Big] - \Big[\max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)}\Big].
\end{split}
\end{equation*}
Note that the term in the second bracket is independent of what bidder $i$ bids, so the utility-maximizing problem reduces to maximizing the terms in the first bracket. If bidder $i$ bids $bid_i = v_i$, then the terms in the first bracket will be identical to what the mechanism wants to maximize in eq.(1). Hence, we know that bidding truthfully would result in the VCG mechanism choosing an outcome that not only maximizes welfare but also maximizes bidder $i$’s utility.
Individual Rationality
Individual rationality is also a property that the VCG mechanism guaranteed. Followed by the terms above and if bidder $i$ bids $bid_i = v_i$ ,
\begin{equation*}
\begin{split}
u_i(\omega^*) & = v_i(\omega^*) - p_i(bid) \
& = \sum_{j}{bid_j(\omega^{*})} - \max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)}.
\end{split}
\end{equation*}
Then, since $\omega^*$ is the outcome that maximizes social welfare, $$\sum_{j}{bid_j(\omega^{*})} \geq \sum_{j}{bid_j(\omega)}, \forall \omega \in \Omega, \omega \neq \omega^{*}.$$
And from *no negative externalities*, which means that the utility of any choice that each player can make without the player’s participation is zero or positive, $bid_i(\omega) \geq 0$, we can get $$\sum_{j}{bid_j(\omega^{*})} \geq \max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)},$$ thus $u_i(\omega^*)$ is non-negative.
Weakly Budget Balance
VCG mechanism also provides weakly budget balance property when the no single-agent effect holds. If bidder $i$ bids $bid_i = v_i$, \begin{equation*} \begin{split} \sum_{i}{p_i(bid)} & = \sum_{i}{\Big[\max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)} - \sum_{j \neq i }{bid_j(\omega^{*})}\Big] }. \end{split} \end{equation*} By no single-agent effect property, that is, the sum of welfares of agents without $i$ is weakly increased by dropping $i$ from the auction, $$\max_{\omega \in \Omega}\sum_{j \neq i }{bid_j(\omega)} \geq \sum_{j \neq i }{bid_j(\omega^{*})} \ , \forall i .$$ We prove that the sum of transfers (payments) from bidders to the center is non-negative.
Concerns
- Complexity