Back to Details

algo-ad-vcg

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

VCG Mechanism (Vickrey-Clarke-Groves)

VCG机制（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.
VCG机制将广告位分配给能最大化总社会福利的竞标者，并向每个中标者收取其对其他竞标者造成的外部性成本。真实出价是占优策略。算法时间复杂度为O(N log N + K × N)，其中N为竞标者数量，K为广告位数量。

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)
触发条件：
  • 设计激励兼容（真实）的多广告位拍卖机制
  • 计算基于外部性定价的福利最大化分配方案
  • 开展VCG与GSP拍卖对比的学术分析
不适用场景：
  • 当收益最大化比真实性更重要时（GSP通常能产生更高收益）
  • 单物品拍卖场景（标准Vickrey拍卖即可满足需求）

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

阶段1：输入验证

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.
收集每个广告主每次点击的真实估值，以及每个广告位的CTR（点击率）。估值必须非负。 **校验规则：**所有估值非负，广告位CTR随位置顺序递减。

Phase 2: Core Algorithm

阶段2：核心算法

  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 = (welfare of others without i) - (welfare of others with i present)
  4. This equals: Σ over lower positions j of (value_{j+1} × (CTR_j - CTR_{j+1}))
  1. 计算福利最大化分配方案：将广告主分配到广告位，以最大化Σ(价值_i × 广告位CTR_i)
  2. 对于每个中标者i（位于广告位s）：计算移除竞标者i后的总福利（重新优化剩余竞标者的分配）
  3. VCG支付金额_i = （无竞标者i时其他竞标者的福利） - （有竞标者i时其他竞标者的福利）
  4. 等价于：对所有更低位置j求和 (价值_{j+1} × (CTR_j - CTR_{j+1}))

Phase 3: Verification

阶段3：验证

Check: all payments ≤ valuations (individual rationality), truthful bidding is dominant strategy, allocation maximizes welfare. Gate: IR satisfied, welfare is optimal.
检查：所有支付金额≤估值（个体理性）、真实出价为占优策略、分配方案实现福利最大化。 **校验规则：**满足个体理性，福利达到最优。

Phase 4: Output

阶段4：输出

Return allocation with VCG payments and welfare metrics.
返回包含VCG支付金额和福利指标的分配结果。

Output Format

输出格式

json
{
  "allocation": [{"advertiser": "A", "slot": 1, "vcg_payment_per_click": 1.80, "total_welfare_contribution": 500}],
  "metadata": {"total_welfare": 1500, "total_revenue": 420, "mechanism": "vcg"}
}
json
{
  "allocation": [{"advertiser": "A", "slot": 1, "vcg_payment_per_click": 1.80, "total_welfare_contribution": 500}],
  "metadata": {"total_welfare": 1500, "total_revenue": 420, "mechanism": "vcg"}
}

Examples

示例

Sample I/O

输入输出样例

Input: 3 bidders values [10, 8, 2], 2 slots CTRs [0.5, 0.3] Expected: Allocation: Bidder1→Slot1, Bidder2→Slot2. VCG payments: Bidder1 = 8×(0.5-0.3)+2×0.3 = 2.20, Bidder2 = 2×0.3 = 0.60.
**输入：**3个竞标者的估值为[10, 8, 2]，2个广告位的CTR为[0.5, 0.3] **预期结果：**分配方案：竞标者1→广告位1，竞标者2→广告位2。VCG支付金额：竞标者1 = 8×(0.5-0.3)+2×0.3 = 2.20，竞标者2 = 2×0.3 = 0.60。

Edge Cases

边缘情况

InputExpectedWhy
All same valuationAll pay 0No externality imposed — no marginal harm
One bidder, one slotPays 0No other bidder harmed
Bidders < slotsAll win, all pay 0No competition = no externality
输入预期结果原因
所有估值相同所有竞标者支付0未产生外部性——无边际损害
1个竞标者，1个广告位支付0无其他竞标者受到损害
竞标者数量＜广告位数量所有竞标者中标，均支付0无竞争=无外部性

Gotchas

注意事项

  • Revenue deficit: VCG often generates less revenue than GSP. In some cases, winners pay nothing (zero externality).
  • Computational complexity: For general combinatorial auctions, VCG requires solving NP-hard welfare maximization. For position auctions, it's polynomial.
  • Collusion vulnerability: VCG can be manipulated by colluding bidders who coordinate to reduce each other's externalities.
  • Non-monotonicity: Adding a slot can sometimes DECREASE revenue (known as the "lonely bidder" pathology).
  • Practical rarity: Almost no major ad platform uses pure VCG. It's theoretically elegant but commercially suboptimal.
  • 收益缺口：VCG通常比GSP产生更少的收益。在某些情况下，中标者无需支付任何费用（零外部性）。
  • 计算复杂度：对于一般组合拍卖，VCG需要解决NP-hard的福利最大化问题。对于位置拍卖，复杂度为多项式级。
  • 串通漏洞：VCG可能被串通的竞标者操纵，他们通过协调来降低彼此的外部性成本。
  • 非单调性：增加广告位有时可能会降低收益（即“孤独竞标者”病态现象）。
  • 实际应用罕见：几乎没有主流广告平台使用纯VCG机制。它在理论上很优雅，但在商业上并非最优选择。

References

参考资料

  • For VCG vs GSP revenue comparison, see 
    references/revenue-comparison.md
  • For combinatorial VCG extensions, see 
    references/combinatorial-vcg.md
  • 有关VCG与GSP收益对比，详见
    references/revenue-comparison.md
  • 有关组合VCG扩展，详见
    references/combinatorial-vcg.md