algo-ad-gsplisted

# Generalized Second Price Auction ## Overview GSP allocates K ad slots to N bidders, assigning the highest bidder the top slot, second-highest the second slot, etc. Each winner pays the bid of the advertiser ONE POSITION BELOW them (per-slot second price). Used by Google Ads and Bing Ads. Runs in O(N log N) for sorting bids. ## When to Use **Trigger conditions:** - Understanding search engine ad auction mechanics - Computing ad position and cost-per-click from bid and quality data - Analyzing bidding strategy in sponsored search **When NOT to use:** - When you need incentive-compatible truthful bidding (use VCG mechanism) - When analyzing display/programmatic ad auctions (typically use first-price) ## Algorithm ``` IRON LAW: GSP Is NOT Incentive-Compatible Unlike Vickrey (single-item second-price) auctions, truthful bidding is NOT a dominant strategy in GSP. Bidders may strategically shade bids below their true value. The equilibrium depends on competitor bids. Ad Rank = Bid × Quality Score (Google's variant adds format/extensions). ``` ### Phase 1: Input Validation Collect: bids, quality scores (or ad rank scores) for all competing advertisers. Define available slot positions and their click-through rate multipliers. **Gate:** All bids positive, quality scores in valid range. ### Phase 2: Core Algorithm 1. Compute Ad Rank for each advertiser: AdRank_i = Bid_i × QualityScore_i 2. Sort advertisers by Ad Rank descending 3. Assign top-K to slots 1 through K 4. Compute