"algo-ad-gsp"

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 payment: CPC_i = AdRank_{i+1} / QualityScore_i (price to maintain position)
5. Last slot winner pays the minimum bid threshold

Phase 3: Verification

Check: all payments ≤ bids, positions ordered by Ad Rank, no advertiser pays more than their bid. Gate: Payment ≤ bid for all winners, positions consistent.

Phase 4: Output

Return slot assignments with positions, CPCs, and estimated clicks.

Output Format

{
  "slots": [{"advertiser": "A", "position": 1, "ad_rank": 8.5, "cpc": 2.10, "est_clicks": 100}],
  "metadata": {"total_bidders": 15, "slots_available": 4, "auction_type": "gsp"}
}