本文简单讨论oCPX中PID对效率的影响

本文的 oCPX 场景设定

  • 本文设定广告主出价点在 ROI 上 ，计费点在 CPC 上
  • 共 \(N\) 个广告主
  • 每个广告主有一个自己的ROI，且这个ROI是广告主私有价值的真实表达
  • 为简化讨论，假设每个广告主的预算无限
  • 假定预估值是准确的（比如PCOC是1.0，如果不准确可以优化预估模型，本文不讨论这个问题）

单次拍卖下oCPX的效率讨论

  • 假设在单次拍卖下，每个广告主的真实表达是ROI，此时社会福利为：
    $$ \sum_{i=1}^N CTR_i\cdot CVR_i \cdot Price_i \cdot \frac{1}{ROI_i} $$
    • 其中 \(i\) 表示广告主索引
  • 显然此时按照下面的公式排序是最优的：
    $$eCPM_i = CTR_i\cdot CVR_i \cdot Price_i \cdot \frac{1}{ROI_i}$$
  • PID会在出价上增加一个PID系数 \(k_i\)，即：
    $$Bid_{\text{cpc}} = CVR_i \cdot Price_i \cdot \frac{1}{ROI_i} \cdot \color{red}{k_i}$$
    • \(k_i\) 与广告主当前达成情况有关，与当前请求流量价值无关
    • 显然可以看出，不同广告主的 \(k_i\) 不同，此时按照 \(eCPM_i = CTR_i\cdot Bid_{\text{cpc}}\) 的排序无法保证社会福利最大化了
  • 实际上，可以证明，对于单次拍卖下，当广告主在这次请求上都表达出自己的真实ROI时，无论如何扰动出价（即任何调价策略），只要不是所有广告主的 \(k_i\) 完全相同，都无法保证社会福利最大化

多轮拍卖下oCPX的效率讨论

  • 多轮拍卖下的oCPX设定 ：广告主的ROI出价是一个投放周期内的均值，仅需要保证广告主全天的ROI即可
  • ROI出价下，广告主对流量没有没有除ROI外的倾向 ：由于ROI出价下，广告主已经表达了自己对流量价值的真实评估 ，所以可以假定广告主对整个周期内流量是没有除ROI外的倾向的，即所有流量价值都可通过统一的ROI来表达
    • 注意：这里是因为广告主出价已经在ROI上了，可以认为全周期内流量价值是无倾向的 ，如果出价点只到CPS上或还有更深的转化点，则无法假设全周期内流量均匀（比如CPS出价下，按照天粒度为周期出价，则可能出现早上的均单价高于晚上的均单价的情况，此时ROI在全天不是完全统一的）
  • 不调价才能保证社会福利最大化 ：由于可以假定整个周期内广告主的ROI是真实的且不变的，所以我们认为每一次请求，广告主的真实ROI是不变的，由此问题可转化为单次拍卖下oCPX问题 ，根据前面单次拍卖下oCPX的效率讨论结论可以知，不调价才能保证社会福利最大化

PID的作用

  • 对不准确预估值进行修正 ：可以部分修正预估值不准确的情况，特别是均值
    • 比如模型保障的是7天的PCOC，单天的无法保证，但oCPX周期为一天
    • 比如某个广场突然开了一个演唱会，广告主的预估值不再能表达真实值
  • 降低随机波动带来的影响 ：可以减少因为随机波动导致的广告主ROI无法达成的情况
    • 正常的随机波动可能导致某一段时间内欠成本或超成本（即使预估值准确），PID的引入可以在欠成本时刻意提升出价、超成本时刻意降低出价，使得ROI成本在有限的竞价轮次内尽快达成

附录：预估值准确了为什么还需要PID？

  • 如果无限拉长周期 ，在预估值 \(CVR_i \cdot Price_i\) 准确（特别是保证PCOC为1）的情况下，无需调整出价（直接按照PID系数 \(k_i=1\) 来出价），在无限次拍卖下 ，统计意义上广告主的ROI是可以保证达成的，这一点由大数定理来保证；
  • 在现实场景中，每个广告主拍卖次数是有限的，且广告主的后验转化率在有限的周期内等会在期望附近波动（这是随机性导致的，即使预估模型足够准确也会出现）。此时如果不调整出价 ，无法保证在单个有限拍卖次数的周期内能达成ROI
    • 具体表现为：广告主长远来看ROI是达成的 ，但是广告主的ROI在一个周期内超成本 ，在另一个周期内欠成本 ，来回波动
    • 解决方案：针对后验转化率 ，对出价系数进行调整，比如PID方法 ，尽量保证每个周期内都能达成

附录：预算有限的情况下结论一样吗？

  • 预算有限的情况下，以上结论不成立：此时广告主可以有取舍，在不同流量上会有不同的ROI出价，有选择的对流量进行取舍，从而提升平台整体的的社会福利
    • 预算有限场景的举例：
      • 两个广告主A，B；两个请求（请求1,2依次发生）
      • 广告主A预算为10，对请求1福利为10，广告主A对请求2福利为9；
      • 广告主B预算为20，对请求1福利为10，广告主B对请求2福利为1；
      • 则广告主A在请求1上不花钱（说假话），且在请求2上花10整体社会福利为19，广告主A在请求1上说真话时社会福利为11

Myerson拍卖

  • Myerson机制就是单物品拍卖下，可以获得最大化期望收益的最优机制

    from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
    Myerson机制就是可以获得最大化期望收益的最优机制。首先定义虚拟估值 \(\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}\)，它和私有估值以及分布有关；然后可以论证在满足DSIC的机制空间上对期望收益最大化 ，可以等同于在同一个空间对期望虚拟福利最大化 ，这样原本关心的收益最大化问题就转变为了分配最优化问题， \(Rev = \max\sum_{i=1}^n \varphi_i(v_i) x_i\)，与前文2.1.章节中 \(SW = \max\sum_{i=1}^n v_i x_i\) 相比仅仅是将私有估值 \(v_i\) 转换为对应的虚拟估值 \(\varphi_i(v_i)\)，其他分配规则的细节以及扣费规则都与社会福利最大化一模一样；最后只需要保证 \(\varphi_i(v_i)\) 是单调的，即私有估值的分布 \(F_i(v_i)\) 是正则分布 ，许多常见分布基本都是正则分布，例如normal、lognormal、uniform and exponential distributions等；非正则分布包括多峰分布和长尾分布，分配的单调性是机制DSIC性质的前提。论证过程可详见文献
    可以发现虚拟估值 \(\varphi_i(v_i)\) 可能为负，在分配的过程中如果遇到 \(\varphi_i(v_i) < 0\) 的竞拍者会被剥夺竞拍资格，如果所有竞拍者的虚拟估值均为负，则流拍，所以 \(\varphi_i^{-1}(0)\) 即虚拟估值为0的逆函数起到了个性化保留价的功能。如果假设所有竞拍者的私有估值服从独立但不同分布，则不仅会有各自不同的保留价，还会遇到如实报价情况下报价高，但虚拟估值不一定高，导致没有竞得更好的资源位，也好理解，此时虚拟估值代表了个性化自己和自己对比的报价意愿强烈程度；如果假设所有竞拍者的私有估值服从独立同分布，因为估值分布相同则虚拟估值函数 \(\varphi\) 也相同，又因为估值分布 \(F\) 服从正则分布，则 \(\varphi\) 严格递增，那么虚拟估值最高的竞拍者就是私有估值最高的竞拍者，这样虚拟福利最大化机制就和带有保留价 \(\varphi_i^{-1}(0)\) 的二价机制相同，回答上文提到的两个竞拍者估值服从独立同分布 \([0,1]\) 均匀分布的例子，\(\varphi_i^{-1}(0)=\frac{1}{2}\) S确实是最优保留价。以下是单物品拍卖的几个机制对比：

VCG

  • Vickrey-Clarke-Groves (VCG)

普通的VCG

WVCG

  • Weighted Vickrey-Clarke-Groves (WVCG)，带权重的VCG机制，是对原始VCG的改进，收入高于VCG机制

VVCA

SW-VCG

GSP

普通的GSP

uGSP

  • Utility-based Generalized Second Price auction (uGSP)，最早提出于论文 Optimising trade-offs among stakeholders in ad auctions, Microsoft Research, 2014. 是对GSP的一种扩展，其分配规则中的排序公式为：
    $$ r_i(b_i) = \lambda_1 \times b_i \times pCTR_i + o_i $$
    • 其中 \(o_i\) 表示其他效用指标，比如作者使用了 \(o_i = \lambda_2 \times pCTR_i + \lambda_3 \times pCVR_i\)
  • 支付规则与GSP相同，都是通过下一位的排序分反算计费

wGSP

  • wGSP（weighted GSP，weighted体现在广告质量分的引入），排序时会在出价上乘以这个权重 \(\beta \cdot bid\) 来排序

mGSP

  • mGSP（myerson GSP）机制，将Myerson保留价技术直接应用到wGSP机制上

    from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
    和单物品拍卖的设计思路类似，Myerson保留价最核心的虚拟估值依赖广告主的私有估值分布，系统可以酌情根据独立同分布的颗粒度进行假设的调整，例如客户之间完全独立不同分布、相同搜索词的客户之间独立同分布、整体流量客户独立同分布等。因为广告系统是多轮拍卖系统，假设广告主是如实报价，则私有估值分布可以根据广告主历史报价进行不同粒度的分布拟合，从而得到虚拟估值。有了虚拟估值和保留价，在分配规则方面有两种类型可做尝试：Eager模式，先过滤后排序，即先根据保留价过滤没有竞争力的广告主，再按照虚拟估值排序；Lazy模式，先排序后过滤。Eager模式对最高报价无法胜出保留价的情形更友好，Lazy模式对第2高报价无法胜出保留价的情形更友好，多数情况下Eager模式在提营收方面会比Lazy更有优势

aGSP

  • aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式

    from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
    第二种是aGSP（anchoring GSP）机制，是对mGSP机制一种松弛方式，业务落地过程中虚拟估值的求逆计算和私有估值的正则分布要求等均会让机制实现不够简洁且解释性较差，略牺牲效果的情况下精简机制设计也是可接受的迭代方向。首先保留价的计算方法和mGSP机制相同，一般保留价的颗粒度会选择数据积累较为充分的粒度。其次主要差异点就是将虚拟估值由 \(\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}\) 简化为 \(\varphi_i(v_i) = v_i - r_i\)，如果假设私有估值分布是均匀分布，化简的表达式就非常接近，求逆也方便，而且业务含义与myerson思路很吻合，报价竞争力更多看重每个广告主超出个性化保留价的那部分

rGSP

  • rGSP（reserve GSP）机制，是对aGSP机制更加进一步的松弛

    from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
    因为有文献提出，为了解决私有估值和虚拟估值趋势不一致问题，虚拟估值可以仅用于个性化保留价的过滤，分配和扣费依然按照私有估值进行，这样虽然对营收有折损但是机制实现更加简洁且易解释

iGSP

  • iGSP（iterated GSP）可以最大限度保证 existence of efficient equilibria，但也仅限2个资源位同时拍卖，如果遇到3个及以上就仍然是一个 open question，不过还算乐观的情况是移动端的资源位往往较少

sGSP

  • 原始论文：Revenue analysis of a family of ranking rules for keyword auctions
  • sGSP(squashing GSP)

    from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
    另外一类不是在报价因子上做文章，而是在wGSP的广告质量点击率上做文章，通过对广告质量点击率进行挤压，也能达到提升营收的效果，这类机制叫做sGSP（squashing GSP）机制。分配规则是按照 \(\beta^s_i b_i\) 进行排序，其中 \(s\) 就是挤压因子，扣费规则按照 \(p_i = \frac{\beta^s_{i+1} b_{i+1}}{\beta^s_i} = \left( \frac{\beta_{i+1}}{\beta_i} \right)^s b_{i+1}\)。该挤压因子能够体现三方面的结论：1）Efficiency视角：当 \(s=1\) 是社会福利最大化及Efficiency最大化，凡是 \(s \neq 1\) 的调节都提升平台的短期收入，从而影响广告主价值；2）Relevance视角：只要 \(s\) 往大调节，整体点击率就会提升，相关性就会变好；3）Revenue视角，当相邻广告质量随排序递减即 \(\frac{\beta_{i+1}}{\beta_i} < 1\) ，在不改变排序的情况下调小 \(s\)，\(p_i\)变大，利好营收增加，当相邻广告质量随排序递增即 \(\frac{\beta_{i+1}}{\beta_i} < 1\)，在不改变排序的情况下调大 \(s\)，\(p_i\)变大，利好营收增加。这一方案为了进一步挖掘营收空间，可以升级为分位置调控挤压因子等，具体详见文献

Deep GSP

Deep Neural Auction (DNA)

NMA

(RegretNet)Optimal Auctions through Deep Learning

(AMA)Affine maximizer auction

附录：一些特殊拍卖

BDFPA

PFPA

  • pacing first-price auction

BROA

  • Bayesian revenue-optimal auction

BDSPA

  • bid-discount second-price auction

PSPA

  • pacing second-price auction

综合对比

集资拍卖相关

(JAMA)Joint-Bidding-in-Ad-Auctions

(JRegNet)Joint Auction in the Online Advertising Market