VCG Mechanism (Vickrey-Clarke-Groves)

Overview

VCG allocates slots to maximize total social welfare and charges each winner the externality they impose on others. Truthful bidding is a dominant strategy. Runs in O(N log N + K × N) where N=bidders, K=slots.

When to Use

Trigger conditions:

• Designing an incentive-compatible (truthful) multi-slot auction
• Computing welfare-maximizing allocations with externality pricing
• Academic analysis comparing VCG to GSP auctions

When NOT to use:

• When revenue maximization matters more than truthfulness (GSP often generates more revenue)
• For single-item auctions (standard Vickrey suffices)

Algorithm