Back to Details

algo-ad-gsp

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

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.
GSP将K个广告位分配给N个竞价者，出价最高者获得顶部广告位，次高者获得第二位，以此类推。每个中标者需支付其下一位竞价者的出价（按广告位的第二价格结算）。Google Ads和Bing Ads均采用该机制。排序出价的时间复杂度为O(N log N)。

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)
触发条件：
  • 了解搜索引擎广告竞价机制
  • 根据出价与质量数据计算广告排名与单次点击成本（CPC）
  • 分析搜索广告中的竞价策略
不适用场景：
  • 需要激励相容的真实竞价时（使用VCG机制）
  • 分析展示/程序化广告竞价时（通常采用第一价格机制）

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).
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

阶段1：输入验证

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

阶段2：核心算法

  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
  1. 计算每个广告主的广告排名：AdRank_i = Bid_i × QualityScore_i
  2. 按广告排名降序排列广告主
  3. 将前K位广告主分配至1至K号广告位
  4. 计算支付费用：CPC_i = AdRank_{i+1} / QualityScore_i（维持当前排名所需的价格）
  5. 最后一位中标者支付最低出价阈值

Phase 3: Verification

阶段3：验证

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

阶段4：输出

Return slot assignments with positions, CPCs, and estimated clicks.
返回包含广告位、CPC和预估点击量的分配结果。

Output Format

输出格式

json
{
  "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"}
}
json
{
  "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"}
}

Examples

示例

Sample I/O

输入输出示例

Input: Bidders: A(bid=3, QS=8), B(bid=4, QS=5), C(bid=2, QS=9). Slots: 2. Expected: Ranks: A=24, C=18, B=20. Order: A(1st), B(2nd). CPC_A = 20/8 = 2.50, CPC_B = 18/5 = 3.60.
输入： 竞价者：A(出价=3，质量得分QS=8)、B(出价=4，QS=5)、C(出价=2，QS=9)。广告位数量：2。 预期结果： 排名：A=24，C=18，B=20。排序：A(第1位)，B(第2位)。CPC_A = 20/8 = 2.50，CPC_B = 18/5 = 3.60。

Edge Cases

边缘情况

InputExpectedWhy
Tie in Ad RankPlatform tiebreaker (historical CTR, etc.)GSP needs strict ordering
One bidderWins slot 1, pays minimum CPCNo competition → floor price
Bid below thresholdNot eligibleMinimum bid requirement enforced
输入预期结果原因
广告排名相同平台使用决胜规则（如历史点击率等）GSP需要严格的排序
仅一位竞价者获得第1位广告位，支付最低CPC无竞争→执行底价
出价低于阈值无资格参与强制执行最低出价要求

Gotchas

注意事项

  • Quality Score is opaque: Google's QS includes expected CTR, ad relevance, and landing page experience. The exact formula is proprietary.
  • Strategic bid shading: Since GSP isn't truthful, sophisticated advertisers shade bids. This means observed bids don't reflect true willingness to pay.
  • Position ≠ value: Higher position gets more clicks but at higher CPC. The most profitable position may be #2 or #3, not #1.
  • Budget constraints: GSP doesn't account for daily budgets. Budget-constrained advertisers must pace bids throughout the day.
  • Broad match expansion: The auction includes query-expanded matches, which may have different conversion rates than exact matches.
  • 质量得分不透明：Google的质量得分包含预期点击率、广告相关性和着陆页体验。具体公式为专有内容。
  • 战略性出价压低：由于GSP不具备激励相容性，成熟的竞价者会战略性压低出价。这意味着观察到的出价并不反映其真实支付意愿。
  • 排名≠价值：排名越高获得的点击量越多，但CPC也越高。最盈利的位置可能是第2位或第3位，而非第1位。
  • 预算限制：GSP不考虑每日预算。受预算限制的广告主需在全天内调整出价节奏。
  • 广泛匹配扩展：竞价会包含查询扩展匹配，其转化率可能与精确匹配不同。

References

参考资料

  • For Nash equilibrium analysis of GSP, see 
    references/gsp-equilibrium.md
  • For comparison with VCG mechanism, see 
    references/gsp-vs-vcg.md
  • 有关GSP的纳什均衡分析，请参阅
    references/gsp-equilibrium.md
  • 有关与VCG机制的对比，请参阅
    references/gsp-vs-vcg.md