VCG Auction

thm. VCG Mechanism Auction. The following mechanism is DSIC and Welfare Maximizing. Compute the optimum allocation $S=(S_1^{\ast },\dots ,S_n^{\ast })$. Then for an agent $i$, let

• $V^{\ast }:={\sum }_{j\ne i}^n{v}_j(S_j^{\ast })$ Optimal Social Welfare
• $V_{-i}^{\ast }:={\text{max}}_{i\ne j}{\sum }_{j=1}^n{v}_j(S_{j,-i})$
  • where $s_j^{-1}$ is the optimal allocation to $j$ when $i$ is simply removed from auction
  • Thus $v_{-i}^{\ast }$ is the optimal social welfare without $i$
• Thus $V^{\ast }\ge V_{-i}^{\ast }$
  • because adding more bidders can only increase social welfare

thm. The following allocation rule is DSIC and welfare-maximizing: Allocate by $\text{max}{\sum }_{j=1}^n{v}_j(S_j)$ Charge price to $i$:

$$p_i=\underset{\text{ re-run auction without i }}{\underbrace{V_{-i}^{\ast }}}-\underset{\text{auction’s welfare }-i\text{’s welfare}}{\underbrace{(V^{\ast }-v_i(S_i^{\ast }))}}$$

Intuition. This is similar to charging $i$ the externality of joining the auction;

Proof. First, $0\le p_i<v_i(S_i)$, i.e. we don’t charge negative prices, or a price higher than the bid:

• $\underset{\text{ without i }}{\underbrace{V_{-i}^{\ast }}}>\underset{\text{ excluding i }}{\underbrace{V^{\ast }-v_i(S_i^{\ast })}}$ because, thus $0\le p_i$
• $p_i=v_i(S_i^{\ast })+\underset{<0}{\underbrace{V_{-i}^{\ast }-V^{\ast }}}$ because $V^{\ast }>V_{-i}^{\ast }$, i.e. adding more bidders cannot decrease welfare.

Second, fixing other’s bids ${\vec{b}}_{-i}$, $i$ will be incentivized to tell the truth of $b_i$. Consider the situation where the auctioneer took these bids and allocated $\hat{S}=(\widehat{S_1},\dots ,\widehat{S_n}).$

$$\begin{array}{rl}{p}_i& =V_{-i}^{\ast }-(V^{\ast }-v_i(S_i^{\ast }))\\ & :={\text{max}}_S\sum _{j\ne i}{b}_j(\widehat{S_j})-\sum _{j\ne i}{b}_j(S_j^{\ast })\end{array}$$

Now, the goal of bidder $i$ is to maximize their utility:

$$\begin{array}{rl}{\mu }_i(\vec{b})& =v_i(\widehat{S_i})-p_i(\vec{b})\\ & =v_i(\widehat{S_i})-\left({\text{max}}_S\sum _{j\ne i}{b}_j(\widehat{S_j})-\sum _{j\ne i}{b}_j(S_j^{\ast })\right)\\ & =\underset{\text{ i can maximize }}{\underbrace{v_i(\widehat{S_i})+\sum _{j\ne i}{b}_j(S_j^{\ast })}}-\underset{\text{ i cannot control }}{\underbrace{{\text{max}}_S\sum _{j\ne i}{b}_j(\widehat{S_j})}}\end{array}$$

Thus, the problem of $i$ maximizing their utility ${\mu }_i$ is equivalent, by design of the pricing mechanism, as maximizing $v_i(\widehat{S_i})+{\sum }_{j\ne i}{b}_j(S_j^{\ast })$, and this is equivalent to social welfare of the original auction.

$${\text{max}}_{b_i}{\mu }_i(b_i,\overrightarrow{b_{-i}})⟺{\text{max}}_S\sum _{i=0}^n{b}_j(S_j)$$

Thus $i$ is incentivized to tell the truth. ■