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