algo-ad-vcg

# 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 ``` IRON LAW: VCG Guarantees Truthful Bidding BUT May Not Maximize Revenue VCG payments are based on externality (harm to others), not competition. This makes VCG payments often LOWER than GSP payments. Platforms choose GSP because it typically generates higher revenue despite strategic bidding. Truthfulness has a revenue cost. ``` ### Phase 1: Input Validation Collect true valuations per click for each advertiser and CTR for each slot position. Valuations must be non-negative. **Gate:** All valuations non-negative, slot CTRs decreasing by position. ### Phase 2: Core Algorithm 1. Compute welfare-maximizing allocation: assign advertisers to slots to maximize Σ(value_i × CTR_slot_i) 2. For each winner i in slot s: compute total welfare WITHOUT advertiser i (re-optimize remaining bidders) 3. VCG payment_i = (welfar...