thm. VCG Mechanism Auction. The following mechanism is DSIC and Welfare Maximizing. Compute the optimum allocation . Then for an agent , let

  • Optimal Social Welfare
    • where is the optimal allocation to when is simply removed from auction
    • Thus is the optimal social welfare without
  • Thus
    • because adding more bidders can only increase social welfare

thm. The following allocation rule is DSIC and welfare-maximizing: Allocate by Charge price to :

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

Proof. First, , i.e. we don’t charge negative prices, or a price higher than the bid:

  • because, thus
  • because , i.e. adding more bidders cannot decrease welfare.

Second, fixing other’s bids , will be incentivized to tell the truth of . Consider the situation where the auctioneer took these bids and allocated

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

Thus, the problem of maximizing their utility is equivalent, by design of the pricing mechanism, as maximizing , and this is equivalent to social welfare of the original auction.

Thus is incentivized to tell the truth.