CA——oCPX中PID对效率的影响讨论

本文简单讨论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

CA——M-PID

参考链接：
- 原始论文：Bid Optimization by Multivariable Control in Display Advertising, KDD 2019, Alibaba

整体思路介绍

实时竞价（RTB）是展示广告中的重要范式，广告主利用需求方平台（DSP）提供的信息和算法来提升广告效果
- DSP面临的一个常见问题是在预算约束下帮助广告主获取最大价值
- 实际场景中，广告主通常会添加某些关键绩效指标（KPI）约束，广告 campaign 必须满足这些约束
论文研究广告主旨在最大化转化量并将每次点击成本（CPC）作为KPI约束的常见情况
- 论文将此问题转化为线性规划问题，并利用 primal-dual 方法推导出最优竞价策略
- 为了解决适用性问题，论文提出了一种基于反馈控制的解决方案，并设计了多变量控制系统
基于淘宝网真实数据的实证研究验证了论文的方法相比行业最新实践的有效性和优越性

一些讨论

在在线展示广告中，广告主为展示广告的机会支付一定费用。实时竞价（RTB）是展示广告中最流行的范式。RTB允许广告主在展示级别对广告机会进行竞价，出价最高的广告主赢得展示其广告的机会（每个广告机会的竞价价格可以跟随其效用和成本而改变，这使得广告主能够利用DSP提供的扩展信息和算法）
DSP面临的一个常见问题是在预算约束下帮助广告主获取尽可能多的价值。已有一些竞价策略和算法被提出，用于在预算约束下最大化广告价值。因此，广告主只需设置广告 campaign 的预算，DSP会代表广告主计算竞价价格
除了预算约束外，广告主通常会添加某些关键绩效指标（key performance indicator，KPI）约束，广告 campaign 必须满足这些约束
- KPI设置的必要性 ：广告主设置此类KPI约束是因为仅具有单一预算约束的广告 campaign 可能会受到竞价环境波动导致的流量巨大变化的影响。例如，某些日期的广告机会可能变得非常昂贵，以至于广告主无法承担所有预算
- 解决方案1 ：一种解决方案是不断调整每日预算以控制投资，这对广告主来说成本高昂甚至不切实际
- 解决方案2 ：另一种解决方案是设置某些KPI约束，每千次展示成本（CPM）和每次点击成本（CPC）约束，对广告投放的总成本有很强的影响
  - 通过设置此类KPI约束，广告主可以对总成本施加限制，并在广告机会不值得时避免花费所有预算，从而免去频繁调整广告 campaign 设置的繁重工作
  - 此外，KPI约束还作为实时代理来调节广告效果。在大多数情况下，广告主最终希望获得转化。然而，转化是稀疏且延迟的，这使得广告主无法实时评估广告效果。因此，广告主使用DSP提供的KPI来评估广告的预期价值 ，并将其设置为约束以确保广告效果可控
- 论文重点关注CPC约束 ，这是最常见的KPI约束之一。论文的方法可以推广到其他与成本相关的KPI约束 ，如CPM约束
论文提出了在预算和CPC约束下最大化广告转化量的最优竞价策略。在这项工作中，竞价优化被表述为一个线性规划问题，并利用 primal-dual 方法推导出最优竞价策略
论文提出了基于最优竞价策略的多变量控制系统 ，以解决适用性问题，特别是在工业应用中面临的动态环境
- PID控制系统 ：基于对竞价策略中超参数的分析，论文声称这些超参数在实现相应约束方面具有强大的控制能力，并设计了独立的PID控制系统
- 模型预测控制系统 ：考虑到耦合效应，论文通过提出模型预测控制系统进一步提高了系统的性能
论文所提出的系统已在真实工业数据集上实现和评估。基于淘宝网真实数据的实验表明，这些系统在实现约束方面具有强大的控制能力。论文还将论文的方法与行业最新实践进行了比较，结果显示了论文方法的优越性。论文工作的主要贡献可以总结如下：
- 论文提出了在预算和CPC约束下最大化转化量的最优竞价策略
- 论文设计了多变量控制系统 ，以应对在工业应用中应用竞价策略时的动态环境
- 进行了广泛的实验，结果证明了论文方法的优势

竞价策略

在本节中，论文首先回顾RTB生态系统的一些基础知识，然后提出竞价优化问题。接着，论文推导最优竞价策略，并讨论竞价策略的特性

RTB生态系统

RTB的工作流程如图1所示，每一步如下：
- 1）用户访问一个支持广告的网站，网站向广告交换平台发送广告请求
- 2）广告交换平台发起拍卖并向DSP请求竞价
- 3）DSP代表广告主向广告交换平台提交竞价价格和广告
- 4）广告交换平台进行拍卖并向获胜的DSP收取广告机会费用
- 5）获胜者的广告被发送到网站
- 6）用户的后续反馈会被发送回相应的DSP
当DSP从广告交换平台接收到竞价请求时，它会通过其竞价策略为广告主计算竞价价格。由于转化是大多数广告主的目标事件 ，几乎所有竞价策略（包括论文的策略）都严重依赖于学习模型的能力来估计广告点击率（CTR）和转化率（CVR）。此外，一些DSP还可能基于对获胜价格（竞价环境预测）的预测来制定竞价策略。论文假设估计和预测问题已经解决，点击和转化的预期概率可以分别通过CTR和CVR量化
当DSP在拍卖中赢得展示广告的机会时，它会被收取一个价格。在广义第二价格（GSP）拍卖机制下，该价格等于第二高的竞价价格，该机制在工业平台中被广泛采用。还有一些其他拍卖机制，如Vickrey-Clarke-Groves拍卖机制（VCG）。在论文中，不失一般性，论文基于最常见的GSP拍卖机制进行讨论和建模
用户对广告的任何反馈，如点击和转化，都会被发送回相应的DSP。DSP可以利用这些反馈来训练预测模型，并及时调整其竞价策略。此外，这些反馈会被DSP整合并暴露给广告主。在论文提出的系统中，论文利用这些反馈，并在广告 campaign 的生命周期中持续微调竞价策略

问题建模

假设一天中有 $N$ 个广告机会，论文按生成顺序将每个广告机会索引为 $opportunity_i$ 。每个广告机会对广告主具有不同的价值，论文用 $v_i = CTR_i \cdot CVR_i$ 表示 $opportunity_i$ 对广告主的价值。基于 $v_i$ ，计算竞价价格 $bid_i$ 并提交给广告交换平台。每个广告机会有一个获胜价格 $wp_i$ 。从广告主的角度来看， $wp_i$ 等于其他广告主的最高竞价价格。如果 $bid_i$ 高于 $wp_i$ ，这意味着广告主将赢得广告机会并在GSP拍卖机制下被收取 $wp_i$ ，论文将 $x_i$ 设为1，否则设为0。广告 campaign 的总价值和总成本如公式（1）和公式（2）所示
$$
Value = \sum_{i=1\ldots N} x_i \cdot v_i \\
Cost = \sum_{i=1\ldots N} x_i \cdot wp_i
$$
论文在公式（3）中定义CPC。值得注意的是，论文用CTR替换了实际点击，这为论文提供了更简洁的公式。这种替换在很大程度上促进了论文的理论分析，并且对后续的实际系统设计影响很小
$$CPC = \frac{\sum_{i=1\ldots N} x_i \cdot wp_i}{\sum_{i=1\ldots N} x_i \cdot CTR_i} \tag{3}$$
转化是广告主最终希望的结果。因此，论文通过 $CTR_i \cdot CVR_i$ 量化 $v_i$ 。请注意，必须考虑 $CTR_i$ ，因为只有在点击后才能生成转化，而CVR是以点击为条件的。论文将问题总结如下，并将其建模为（LP1，包含约束（4）和约束（5）），论文在预算 $B$ 下最大化广告转化量，并保证CPC不超过给定值 $C$ ：
$$
\begin{align}
\max_{x_i} \sum_{i=1\ldots N} x_i \cdot CTR_i \cdot &CVR_i \text{(LP1)}\\
\text{s.t.} \quad \quad \sum_{i=1\ldots N} x_i \cdot wp_i &\leq B \\
\frac{\sum_{i=1\ldots N} x_i \cdot wp_i}{\sum_{i=1\ldots N} x_i \cdot CTR_i} &\leq C \\
0 \leq x_i &\leq 1, \forall i
\end{align}
$$

最优竞价策略

问题（LP1）实际上是一个线性规划问题，即在线性约束下找到最优的 $x_i$ 以最大化目标函数。已有许多算法直接解决此类问题，但论文的目标是推导最优竞价策略而非分配策略。换句话说，论文本质上并不关心 $x_i$ 的值，而是关心内在影响 $x_i$ 的竞价策略。基于此考虑，论文创造性地采用 primal-dual 方法。每个线性规划问题（称为原始问题）都可以转换为对偶问题。此外，根据对偶定理（duality theorem），最优原始解可以通过相应的对偶解获得。这些数学特性为论文提供了一些启示，论文整合原始空间和对偶空间，推导出以下定理：
定理2.1 ：最优竞价策略的公式为：
$$bid_i = \frac{1}{p + q} \cdot CTR_i \cdot CVR_i + \frac{q}{p + q} \cdot CTR_i \cdot C \tag{6}$$
- 最优竞价策略在公式（6）中给出，其中 $p$ 和 $q$ 是从对偶空间引入的超参数，对应于最优对偶解。论文将在后续章节中研究 $p$ 和 $q$ 的性质。现在，论文给出定理2.1的证明
证明：（LP1）被转换为对偶问题：
$$
\begin{align}
\min_{p, q, r_i} B \cdot p + \sum_{i=1\ldots N} r_i \quad &\text{(LP2)} \\
\text{s.t.} wp_i \cdot p + (wp_i - CTR_i \cdot C) q + r_i &\geq CTR_i \cdot CVR_i, \forall i \\
p &\geq 0,\\ q &\geq 0,\\ r_i &\geq 0, \forall i
\end{align}
$$
- 假设原始问题（LP1）的最优解为 $x_i^*, \forall i = 1, \ldots, n$ ，对应的对偶问题（LP2）的最优解为 $p^*, q^*, \{r_i^* | i = 1, \ldots, n\}$ 。根据互补松弛定理，论文得到：
  $$x_i^* \cdot (CTR_i \cdot CVR_i - wp_i \cdot p - (wp_i - CTR_i \cdot C) q - r_i) = 0, \forall i \\
  (x_i^* - 1) \cdot r_i^* = 0, \forall i \tag{8&9}$$
- 论文巧妙地设最优出价形式为：
  $$\color{red}{bid_i^* = \frac{1}{p^* + q^*} CTR_i \cdot CVR_i + \frac{q^*}{p^* + q^*} C \cdot CTR_i}$$
  - 特别说明 ：这里的公式形式是有规律的，直接对原始问题构造拉格朗日函数，然后令原始拉格朗日函数对 $x_i$ 的偏导数为0，即可得到 $wp_i$ 的形式，其他类似约束问题也可以这样求解最优出价形式
- 最优出价形式的验证 ：
  - 将公式（8）转换为公式（10）：
    $$x_i^* \cdot ((bid_i^* - wp_i)(p^* + q^*) - r_i^*) = 0, \forall i \tag{10}$$
  - 根据公式（10）：
    - 如果广告 campaign 赢得 $opportunity_i$ ，即 $\color{red}{x_i^* > 0}$ ，则 $(bid_i^* - wp_i)(p^* + q^*) - r_i^* = 0$ 。同时， $p^* \geq 0, q^* \geq 0, r_k \geq 0$ ，因此 $\color{red}{bid_i^* \geq wp_i}$
    - 如果广告 campaign 失去 $opportunity_i$ ，即 $\color{red}{x_i^* = 0}$ ，我们可以从公式（9）推导出 $r_i^* = 0$ 。因此，根据公式（7），论文得到 $(bid_i^* - wp_i)(p^* + q^*) < 0$ ，即 $\color{red}{bid_i^* \leq wp_i}$
综上所述，对于任何 $opportunity_i$ ，竞价策略将保证 $x_i$ 是最优的，从而得到（LP1）的最优解。也就是说，当最优 $x_i$ 为1（广告 campaign 应赢得 $opportunity_i$ ）时，基于最优竞价策略的竞价价格 $bid_i$ 高于 $wp_i$ ，这将保证广告 campaign 赢得 $opportunity_i$ 。当最优 $x_i$ 为0时，推理相同。因此，广告 campaign 只需按照公式（6）中的最优竞价策略进行竞价，总广告价值将在约束条件下最大化。
关于 $p$ 和 $q$ 的讨论 ：公式（6）并未明确给出 $p$ 和 $q$ 的值。实际上，通过使用成熟的线性规划算法求解对偶问题，可以轻松推导出最优的 $p$ 和 $q$ 。此类工作对论文的理解没有贡献，因此论文在此不讨论如何计算 $p$ 和 $q$ 的值
引入点击出价 $c\_bid_i$ 变量 ：论文将（LP1）的最优竞价策略重新表述为两个阶段，如公式（11）、公式（12）和图2所示，其中 $c\_bid_i$ 可以视为点击的竞价价格。当一个广告机会到来时，论文首先确定点击的竞价价格，即 $c\_bid_i$ 。在确定 $c\_bid_i$ 后，最终竞价价格通过将 $c\_bid_i$ 与 $CTR_i$ 相乘来计算，这一过程可以自动完成，并在后续讨论中省略
$$c\_bid_i = \frac{1}{p + q} \cdot CVR_i + \frac{q}{p + q} \cdot C \tag{11}$$
进一步地，有曝光出价为：
$$
\begin{align}
bid_i &= c\_bid_i \cdot CTR_i \\
&= \left( \frac{1}{p + q} \cdot CVR_i + \frac{q}{p + q} \cdot C \right) \cdot CTR_i \tag{12}
\end{align}
$$
此外，在GSP拍卖机制下，点击的成本自然不高于点击的竞价价格，因此 $c\_bid_i$ 直接与CPC相关。因此，为了便于演示，论文将讨论重点放在点击的竞价价格（ $c\_bid_i$ ）上，而非最终竞价价格
论文以一些明显的事实开始讨论最优竞价策略，如图2a所示
- 第一，点击的竞价价格与 $CVR_i$ 严格正相关。这很有道理：论文应该为更有价值的点击提供更高的竞价价格，为价值较低的点击提供较低的价格
- 第二，竞价价格相对于 $CVR_i$ 是线性的。这是一个自然的结果，因为论文要最大化价值的和，而价值是相对于 $CVR_i$ 本身的线性函数
- 第三，竞价策略肯定会穿过图中强调的两个点。论文将在后续分析中详细讨论这一点
- CVR为0时，点击出价不为0 ：论文中有一个不寻常的事实：与广泛采用的竞价策略不同，该函数不一定通过原点。具体来说，即使广告机会对广告主没有价值，竞价价格也可能非零。论文为一个没有价值的广告机会出非零价格有点反直觉
  - 论文陈述原因如下：考虑到给定CPC约束 ，竞价策略试图赢得一些廉价的广告机会，即使没有任何价值，以降低整体CPC ，从而赢得一些具有高CPC的有价值广告机会

系统设计

在本节中，论文解决了竞价策略在工业场景中的适用性问题，并提出了基于反馈控制的解决方案。基于对最优竞价策略中超参数的分析，论文提出了多变量控制系统

适用性问题

如（LP2）所示，为了求解线性规划问题并获得最优竞价策略，论文需要准确知道一天中每个广告机会的信息，包括获胜价格、CTR和CVR。然而，在现实世界中，这些信息直到一天结束时才能获得，而最优竞价策略需要在广告 campaign 开始前确定
除了在广告 campaign 开始前难以精确预测所有这些信息之外，如何预测一天中的广告机会本身仍然是一个开放性问题 ，因为动态环境（dynamic environment）
- 有人可能认为有许多统计算法可以解决此类问题：可以从足够的历史数据中推导出最优解，并应用于未来（此类算法的一个强假设是变量的分布是平稳的）。然而，在动态RTB环境中，不仅广告机会的分布 ，其他因素如获胜价格、CTR和CVR的分布也不是平稳的。因此，基于历史数据推导的最优竞价策略对未来不再最优 ，甚至可能打破CPC约束

基于反馈控制的解决方案

如上一节所述，由于动态竞价环境，论文基于历史数据推导的竞价策略可能不可靠。因此，论文需要利用实时信息来调整竞价策略。反馈控制通过从系统输出和外部噪声中处理动态系统(dynamic system)（Kumar等，2014），因其鲁棒性和有效性而在工业中被广泛采用。反馈控制系统(feedback control problem)通过基于系统输出的反馈调整系统输入来实现理想的性能
在论文的场景中，论文自然可以将竞价策略和RTB环境集成为一个动态系统 ，并将竞价策略的超参数 $p$ 和 $q$ 视为系统的输入。通过这样做，问题被转化为反馈控制问题
仍然有一个问题：什么是理想的性能，因此论文应该关心输出的哪些反馈？首先，论文的目标是最大化广告价值并控制CPC。其次，为了最大化广告价值，论文应该在时间上分散预算支出以赢得有价值的广告机会。因此，论文需要同时控制预算支出和CPC。论文提出以下反馈解决方案：为了提高广告性能，论文基于实时反馈控制预算支出和CPC
关于控制器的介绍 ：论文简要介绍标准的反馈控制系统。反馈控制系统的框图如图3所示。输出的期望值称为参考值 ，根据具体任务预先设定。传感器从系统输出中测量变量的实际值，并将其传输给控制器。通过比较测量值和参考值 ，控制器会根据其预定义的算法或策略调整系统输入，以减小它们之间的差异
- 比例-积分-微分（Proportional-Integral-Derivative，PID）控制器（Bennett，1993）是工业中最广泛采用的反馈控制器。已知PID控制器在缺乏对底层过程了解的情况下提供最佳性能（Åström和Hägglund，1995）
- PID控制器用法介绍 ：PID控制器在每个时间步 $t$ 连续计算测量值 $y(t)$ 和参考值 $r(t)$ 之间的误差 $e(t)$ ，并基于误差的比例、积分和微分项的组合产生控制信号 $u(t)$ 。控制信号 $u(t)$ 然后被发送以通过执行器模型 $\phi(x(0), u(t))$ 调整系统输入 $x(t)$ 。在在线广告场景中，使用离散时间步 $(t_1, t_2, \ldots)$ 是实际和常见的，因此PID的过程可以表示为以下公式，其中 $k_p$ 、 $k_i$ 和 $k_d$ 是PID控制器的权重参数

$$e(t) = r(t) - y(t) \tag{13}$$

$$u(t) = k_p e(t) + k_i \sum_{k=1\ldots t} e(k) + k_d (e(t) - e(t-1)) \tag{14}$$

$$x(t+1) = \phi(x(0), u(t)) \tag{15}$$

超参数分析

多变量下的控制方法 ：论文已经将问题转化为反馈控制问题，并在上一节中确定了动态系统（竞价策略和RTB）、输入参数（ $p$ 和 $q$ ）和输出变量（预算支出和CPC）。挑战在于如何通过调整 $p$ 和 $q$ 同时控制预算支出和CPC。由于多输入参数和多输出变量，论文不能直接在论文的场景中应用PID控制器（PID是单输入参数和单输出变量系统设计的）。已有一些多变量控制方法，如模型预测控制（Rawlings和Mayne，2009），用于处理此类系统，论文将在下一节的设计中利用其基本思想。在本节中，论文重新审视公式（11）中的最优竞价策略，并分享论文设计多变量控制系统的想法
回顾最优点击出价公式：
$$c\_bid_i = \frac{1}{p + q} \cdot CVR_i + \frac{q}{p + q} \cdot C \tag{11}$$
论文分析超参数 $p$ 和 $q$ 如何对公式（11）中的竞价策略做出贡献。请回顾 $p$ 和 $q$ 是由约束（4）和（5）引入的对偶变量，论文探讨它们与相应约束的关系
图4显示了在固定 $q$ 的情况下 ， $p$ 分别减小、增大、等于0和等于 $\infty$ 时的最优竞价策略。值得注意的是，竞价价格将直接影响预期成本：更高的竞价价格会导致更多成本，因为广告 campaign 可能赢得更多广告机会。如图4所示，随着 $p$ 的增加或减少，竞价价格通常会降低或提升
- 当论文增加 $p$ 时 ，竞价策略将围绕点 $(-q \cdot C, 0)$ 顺时针旋转。结果是：高于零的竞价价格将降低 ，低于零的竞价价格将提升（注：低于零的价格图上没有画出来，实际上，低于0时不会出价），从而预期成本将减少。以 $p = \infty$ 和 $p = 0$ 作为极端例子。当 $p = \infty$ 时，广告 campaign 的竞价价格始终为零，因此永远不会被收费。当 $p = 0$ 时，预算不再是一个约束。竞价价格不会无限高，因为仍然存在CPC约束，并且竞价策略的斜率完全由 $q$ 控制。如果论文同时将 $q$ 设为0，这意味着CPC约束也被移除，竞价价格将无限高，广告 campaign 将赢得所有广告机会。根据图示，论文声称 $p$ 对预算支出具有直接和有效的控制能力，并且可以明确降低预算支出速度
以类似的方式，论文固定 $p$ 并将 $q$ 分别设为减小、增大、等于0和等于 $\infty$ 。如图5所示， $q$ 对最优竞价策略的影响与 $p$ 的影响显著不同
- 当论文增加 $q$ 时 ，竞价策略将围绕点 $(p \cdot C, C)$ 顺时针旋转。增加 $q$ 时，高于 $C$ 的竞价价格将降低，低于 $C$ 的竞价价格将提升。因此，广告 campaign 将赢得更多CPC低于 $C$ 的广告机会，而减少CPC高于 $C$ 的广告机会。综合结果是CPC更有可能低于 $C$ 。在极端情况下，当 $q = \infty$ 时，CPC将保证低于 $C$ 。当 $q$ 设为0时，意味着CPC约束被移除，竞价策略由 $p$ 决定 ，并退化为（Perlich等，2012；Zhang等，2016）中的最优预算约束竞价策略。基于分析，论文声称CPC可以通过 $q$ 明确控制。论文提出以下两个陈述：
  - 1）超参数 $p$ 对预算支出具有直接和有效的控制能力，并且在任何 $q$ 值下，预算支出速度都可以通过 $p$ 明确降低
  - 2）超参数 $q$ 对CPC具有直接和有效的控制能力，并且在任何 $p$ 值下，CPC约束都可以通过调整 $q$ 明确实现

多变量控制

如上一节所述，预算支出和CPC可以分别通过 $p$ 和 $q$ 明确控制。换句话说， $p$ 和 $q$ 可以用于独立控制预算支出和CPC，并将彼此视为外部噪声。因此，我们可以将多变量反馈控制问题分解为两个单变量反馈控制问题。通过这样做，PID控制器可以轻松部署，论文提出了图6中的独立PID设计，其中论文稍微滥用下标 $p$ 和 $q$ 以区分两个控制器
进一步，论文重新审视之前的分析。如图4所示，增加 $p$ 通常会降低竞价价格并减少预算支出速度。增加 $p$ 引起的另一个 non-trivial 影响是预期CPC也会降低。根据这些观察，调整 $p$ 实际上会对CPC产生影响。类似地，调整 $q$ 也会对预算支出产生了影响。尽管论文的独立PID控制系统可以处理这种耦合效应（控制器将其视为外部噪声），但通过解决此类问题，可以进一步提高系统的性能。然而，由于论文对动态系统没有明确的了解，这种耦合效应难以量化和补偿
为了解决上述问题，论文利用模型预测控制（MPC）（Rawlings和Mayne，2009）的基本思想来预测和补偿耦合效应。值得注意的是，论文没有直接在控制系统中应用MPC ，因为建模高度非线性的RTB环境成本高昂甚至不切实际。在论文的设计中，结合人类知识，模型预测模块仅需预测耦合效应，这可以通过线性模型近似。如图7所示，在PID控制器之后部署了一个模型预测模块，通过解决耦合效应来调节控制信号
MPC最重要的组成部分之一是表示动态系统行为的模型。在论文的案例中，论文针对成本和CPC对竞价环境进行建模：
- 如公式（16）所示，其中 $\mathbf{X}$ 是一个 $2 \times 2$ 矩阵， $\mathbf{b}$ 是一个 $2 \times 1$ 矩阵
- 在从反馈中获得预期的 $\Delta cost$ 和 $\Delta CPC$ 后，我们可以通过求解公式（17）中的方程来调整 $p$ 和 $q$ ，并推导出如公式（18）所示的结果
- 公式（18）表明， $p$ 和 $q$ 的控制信号应该是成本和CPC变化的线性组合
- 因此，论文通过公式（19）定义模型预测模块：
  - 其中 $\Delta cost$ 和 $\Delta CPC$ 分别由 $u_p(t)$ 和 $u_q(t)$ 量化，
  - 而 $[\mathbf{X}]^{-1}$ 由 $\alpha$ 和 $\beta$ 确定的 $2 \times 2$ 矩阵近似
  - 通过近似 $[\mathbf{X}]^{-1}$ ，我们可以简单地将 $\alpha$ 和 $\beta$ 视为两个权重参数，并在训练集中搜索其最佳值
    - 尽管这种近似削弱了表示系统的能力，但它使控制器在变化的环境中更加鲁棒和稳定
    - 问题： $\alpha$ 和 $\beta$ 的最佳值如何搜索？是类似PID的参数 $K_p,K_i,K_d$ 等一样搜索吗？
- 值得注意的是，论文提出了矩阵 $\mathbf{X}$ 和 $\mathbf{b}$ 来建模动态系统，然而，这些矩阵的确切值并不明确需要。如公式（19）所示，论文利用这些矩阵来解决耦合效应，并获得仅由 $\alpha$ 和 $\beta$ 确定的近似函数

$$\begin{bmatrix}
cost \\
CPC
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{X} & \mathbf{b}
\end{bmatrix}
\begin{bmatrix}
p \\
q \\
1
\end{bmatrix}
\tag{16}$$

$$\begin{bmatrix}
\Delta cost \\
\Delta CPC
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{X}
\end{bmatrix}
\begin{bmatrix}
\Delta p \\
\Delta q
\end{bmatrix}
\tag{17}$$

$$\begin{bmatrix}
\Delta p \\
\Delta q
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{X}
\end{bmatrix}^{-1}
\begin{bmatrix}
\Delta cost \\
\Delta CPC
\end{bmatrix}
\tag{18}$$

$$\begin{bmatrix}
u’_p(t) \\
u’_q(t)
\end{bmatrix}
=
\begin{bmatrix}
\alpha & 1 - \alpha \\
1 - \beta & \beta
\end{bmatrix}
\begin{bmatrix}
u_p(t) \\
u_q(t)
\end{bmatrix}
\tag{19}$$

实证研究

在本节中，论文进行了全面的实验，以证明论文的陈述和多变量控制系统的优势
论文在示例广告 campaign 上进行了实验，以证明超参数的控制能力
为了展示论文系统的优越性，论文在大量广告 campaign 上将论文的方法与行业最新实践进行了比较

Experiment Setup

数据集

论文基于淘宝网的真实数据集进行实验。数据集包含40个广告 campaign 在连续多天的数据，总计2000万条竞价日志。根据日期将其分为训练数据集和测试数据集。从特定广告 campaign 的角度来看，数据集的关键信息可以总结为表1
论文主要使用获胜价格、CTR和CVR的信息。每个广告机会的获胜价格在每次在线拍卖结束后记录。由于淘宝网也是一个发布商，即使广告主在在线拍卖中错过了广告机会，也可以观察到获胜价格。CTR和CVR由在线部署的模型估计，这些模型利用了用户和广告的广泛实时和历史信息。有关在线部署的估计模型的详细信息，请参阅（Zhou等，2018）

指标

竞价策略和系统的目标是最大化赢得广告机会的总价值，并将CPC控制在给定阈值以下。论文通过 $CTR \cdot CVR$ 的总和量化广告价值，这对应于转化的预期结果。值得注意的是，论文将 $CTR \cdot CVR$ 视为价值，而非实际转化事件，以排除估计模型不准确带来的影响（注：尽管一些先前的工作通过实际转化评估竞价策略，但作者认为估计误差实际上对结果产生了 non-trivial 影响）。所以，具有固定竞价策略的广告 campaign 可能仅通过优化估计模型就获得更多点击/转化，因此论文将 $CTR \cdot CVR$ 视为真实转化以减少这种影响
- (1) $R$ 表示广告 campaign 的广告价值
- (2) $R^*$ 表示广告 campaign 在预算和CPC约束下可以实现的最高广告价值
- (3) $R/R^*$ 可用于评估广告性能与理想结果的接近程度
- (4) $CPC_{ratio}$ 是满足CPC约束（允许10%的超调）的广告 campaign 比例，可用于在大量广告 campaign 上比较不同方法时评估CPC控制能力
- (5) $Value_{ratio}$ 是在CPC约束成立的广告 campaign 上的平均 $R/R^*$ ，用于评估广告价值的实现。对于那些打破CPC约束的广告 campaign ，论文在计算 $Value_{ratio}$ 时排除了它们的 $R/R^*$ ，因为在论文的场景中，通过打破CPC约束赢得更多价值是不允许的

实现细节

论文在PID控制器和基线策略中采用了公式（20）所示的执行器，其中 $u(t)$ 的符号取决于输入参数和输出变量之间的关系
$$x(t+1) = x(0) \cdot \exp(-u(t)) \tag{20}$$
此外，需要注意的是，论文实际上关心的是广告 campaign 结束时的累计CPC，而每个时间步的实时CPC对累计CPC的贡献不同，因为每个时间步的点击量不同。传统的PID误差无法解决论文场景中的不同权重问题，因此论文通过点击量对误差进行加权，并修改 $q$ 的控制信号，如公式（21）和公式（22）所示，其中 $u(t)$ 由公式（14）计算， $click(t)$ 表示时间步 $t$ 的点击量。通过这种修改，PID控制器将不断增加其对累计CPC的关注，并为每个时间步赋予不同的权重：
$$e_q(t) = click(t) \cdot (r(t) - y(t)) \tag{21}$$

$$u_q(t) = \frac{1}{\sum_{i=1\ldots t}^T click(t)} \cdot u(t) \tag{22}$$

$$u(t) = k_p e(t) + k_i \sum_{k=1\ldots t} e(k) + k_d (e(t) - e(t-1)) \tag{14}$$

针对上述公式的理解：
- $e(t) = click(t) \cdot (r(t) - y(t))$ 表示当前时间片 $t$ 的累计收入差异（注意：这样得到的是目标消耗和真实消耗的差异）
  $$
  \begin{align}
  e(t) &= click(t) \cdot (r(t) - y(t)) \\
  &= click(t) \cdot (\frac{targetCharge(t)}{click(t)} - \frac{realCharge(t)}{click(t)}) \\
  &= targetCharge(t) - realCharge(t)
  \end{align}
  $$
- 从上面的推导进一步可以得到，经过这样处理的后的积分项 $\sum_{k=1\ldots t} e(k)$ 表示全天截止到当前目标消耗与真实消耗的差异，在一些无法分时间片做特征的场景中，可以用这一项去替换这个值
  - 补充思考 ：考虑到越到后面，积分项影响越大，比例项影响越小，真实场景中如果没有的话，甚至可以不使用比例项
为了确定PID控制器的权重参数以及权重参数 $\alpha$ 和 $\beta$ ，论文在训练数据集上网格搜索最佳设置，并将其应用于测试数据集。论文将每小时视为一个时间步，因此最大时间步 $T$ 等于24
参考值设定 ：如论文在前面章节中讨论的，PID控制器需要一个参考值（目标值）。在论文的实验中，广告主给出的CPC被设为控制 $q$ 的恒定参考值。考虑到广告机会和获胜价格对成本有直接影响，并且在时间步上表现出不同的统计特征，成本参考值应根据时间步定制（如果目标就是全天达到商家的某个固定目标值呢？）。论文计算训练数据集上的成本分布，即每天每个时间步的理想成本归一化为总成本，作为成本参考
论文的实验流程步骤如下：
- 1）在训练数据集上计算最优的 $p$ 和 $q$ ；
- 2）在测试数据集上模拟竞价过程，其中计算出的 $p$ 和 $q$ 作为初始超参数应用；
- 3）当广告 campaign 预算耗尽或没有更多广告机会时，模拟结束

控制能力

在本节中，论文进行实验以证明论文的陈述，即预算支出和CPC可以分别通过 $p$ 和 $q$ 独立控制。论文同时调整两个超参数，而不使用模型预测模块，并在示例广告 campaign 上分别展示预算支出和CPC的控制性能。控制性能如图8和图9所示：
如图8所示，由 $p$ 控制的每个时间步的成本围绕成本参考值波动，累计成本相对于累计成本参考值得到了良好控制。如图9所示，每个时间步的CPC迅速被限制在可容忍的范围内，累计CPC成功控制在给定的参考值以下。值得注意的是，实时CPC在时间步上表现出可观察的波动，因为论文对实时CPC的关注逐渐减少（因为积分项的影响会逐渐增大）。与实时CPC相比，累计CPC表现出稳定的性能，如图9b所示。根据实验，尽管 $p$ 和 $q$ 相互干扰，但它们可以独立调整以控制相应的输出变量

性能评估

在本节中，论文将论文的方法与行业最新实践进行比较。论文首先介绍基线策略，并在真实数据集上评估它们

基线策略

Cost-min ：Cost-min（Kitts等，2017）是一种在广告场景中解决多约束的通用算法，可以应用于论文的场景如下。采用竞价策略公式（23）。论文通过PID控制器根据成本参考值调整 $b_0$ ，并将 $c\_bid_i$ 的上限设为 $C$ 。由于截断的竞价价格，广告 campaign 的CPC约束将始终成立。论文将给定的CPC除以广告 campaign 所有竞价日志的平均CVR来初始化 $b_0$
$$ c\_bid_i = b_0 \cdot CVR_i \tag{23} $$
Fb-Control ：Zhang等提出了一种动态调整竞价以控制CPC的反馈控制机制（Zhang等，2016）。在他们的工作中，他们采用了广义竞价策略，如公式（24）所示，并通过PID控制器根据CPC的反馈不断调整 $b_0$ 。给定的CPC被设为 $b_0$ 的初始值。为简单起见，论文将他们的方法称为Fb-Control
$$ c\_bid_i = b_0 \tag{24} $$
Fb-Control-M ：Fb-Control没有考虑点击的价值（即CVR），这对提高广告性能很重要。因此，论文修改了他们的竞价策略以更好地适应论文的场景，如公式（23）所示，其中 $b_0$ 通过PID控制器根据论文的成本参考值进行调整，而 $c\_bid_i$ 的上限通过独立的PID控制器根据CPC的反馈进行控制。上限由给定的CPC初始化，将在每次竞价时截断 $c\_bid_i$

评估结果

论文在40个广告 campaign 上评估了所有方法，并计算了 $CPC_{ratio}$ 和 $Value_{ratio}$ 。结果总结在表2中。从表2可以看出，所有方法都能成功控制CPC，因为它们的 $CPC_{ratio}$ 均为1.0。然而，论文的方法在广告价值实现方面显著优于基线策略。具体来说，独立PID控制系统（I-PID）和模型预测PID控制系统（M-PID）分别实现了0.892和0.928的 $Value_{ratio}$ ，而最佳基线策略Fb-Control-M仅实现了0.709。此外，M-PID的性能优于I-PID，这表明模型预测模块通过解决耦合效应进一步提高了系统的性能

附录：相关工作（原文直译）

注：为方便check，这里均保留引用信息

论文的工作与在线广告中的竞价策略和反馈控制密切相关。在线广告中的竞价策略已被广泛研究（Wang和Yuan，2015）。Zhang等（Zhang等，2014）提出了一种在预算约束下最大化点击量的最优竞价策略。Perlich等（Perlich等，2012）提出了一种基于库存评分的竞价策略。Lee等（Lee等，2013）提出了一种在预算平滑约束下的实时竞价优化方法。Zhang等（Zhang等，2016）提出了一种广义竞价策略，并通过反馈控制机制动态调整竞价以控制CPC。论文的工作与他们的不同之处在于，论文同时考虑了预算和KPI约束，并推导出最优竞价策略
馈控制在在线广告中的应用也得到了广泛研究（Karlsson和Zhang，2013）。Jamali等（Jamali等，2012）提出了一种基于控制理论的推荐系统。Zhang等（Zhang等，2016）提出了一种基于反馈控制的竞价策略。论文的工作与他们的不同之处在于，论文设计了一个多变量控制系统，以同时控制预算支出和CPC
此外，论文的工作还与线性规划和 primal-dual 方法相关。线性规划已被广泛应用于在线广告中的资源分配问题（Agrawal等，2014）。 primal-dual 方法已被用于解决在线线性规划问题（Buchbinder等，2007）。论文的工作与他们的不同之处在于，论文采用这种方法推导最优竞价策略而非分配策略。为了解决动态环境问题，论文利用了反馈控制理论，该理论已被许多工作证明在多种场景中有效（Jamali等，2012；Karlsson和Zhang，2013；Zhang等，2016）。其他相关工作包括点击率估计（McMahan等，2013；Zhou等，2018）、转化率估计（Lee等，2012；Yang，2017）、获胜价格预测（Wang等，2016；Wu等，2018）和预算平滑（Xu等，2015；Song等，2017）。

CA——Neural-Multi-slot-Auctions(NMA)

参考链接：
- 原始论文：NMA: Neural Multi-slot Auctions with Externalities for Online Advertising, 2022, ArXiv preprint, Meituan

整体总结

其他已有机制盘点

广义第二价格拍卖（GSP）（也包括uGSP），因其易于解释和部署，几乎已成为广告拍卖机制的基准。但GSP拍卖机制忽略了外部性（假设了用户点击仅依赖于广告本身）
深度神经拍卖（DNA） ，通过深度神经网络升级GSP，并在一定程度上建模了局部外部性(注：DNA忽略了广告的顺序和展示位置)，然而，它仅考虑了拍卖中的集合级上下文，忽略了广告的顺序和展示位置，仍然不够
Vickrey-Clarke-Groves（VCG） ，与GSP和DNA相比，代表性的真实拍卖Vickrey-Clarke-Groves（VCG）考虑了外部item的影响，并在理论上可以建模全局外部性。然而，VCG导致平台收入下降，这对大多数工业界广告平台来说是不可接受的
加权Vickrey-Clarke-Groves（WVCG） ，可以建模全局外部性，并在一定程度上解决了VCG的收入下降问题。然而，参数求解的高复杂性使其难以在工业场景中实际应用

关键挑战提出

通过分析上述代表性拍卖机制的问题，作者认为在设计具有外部性的多槽位拍卖机制时面临三个关键挑战：
- i）大多数拍卖机制要么仅建模局部外部性，要么低效地建模全局外部性。如何高效地建模全局外部性已成为关键点
- ii）平台收入和社会福利（SW）是设计拍卖机制的核心指标。大多数现有工作要么专注于平台收入的最大化，要么专注于社会福利的最大化，缺乏对两者的有效平衡
- iii）一些方法专注于理论拍卖设置，缺乏大规模工业部署的洞察

方案概述

神经多槽位拍卖（NMA） ：一种端到端学习的多槽位拍卖机制，以在最大化平台收入的同时减少社会福利的下降。包括四个部分：
- 所有候选分配通过上下文感知的列表预测模块输入，该模块有效地建模了全局外部性
- List深度排序模块，通过将参数建模为神经网络，使得复杂的拍卖机制可以端到端训练
- List可微分排序模块，通过真实系统奖励反馈有效地训练级联的深度神经网络
- 社会福利的辅助损失，以在最大化收入的同时有效减少其下降
主要贡献总结如下：
- 多槽位拍卖的新框架 ：论文提出了一种名为NMA的端到端学习框架，能够准确建模全局外部性，并有效平衡设计拍卖机制的关键指标
- 建模全局外部性的优越方法 ：论文采用精心设计的神经网络来建模每个分配的列表级信息和拍卖中的公共信息，大大提高了全局外部性建模的有效性和预测值的准确性
- 平衡收入和社会福利的有效方法 ：论文设计了社会福利最大化的辅助损失，能够有效平衡平台收入和社会福利
- 详细的工业实践经验 ：论文成功将NMA部署在美团外卖平台上。离线模拟和在线A/B实验的结果表明，与GSP、DNA、VCG和WVCG相比，NMA在点击率和平台收入方面带来了显著提升

问题建模

多槽位拍卖场景

电子商务广告中典型的多槽位拍卖场景中，形式上，当用户发起页面浏览请求时，电子商务平台向用户展示 $J$ 个item，其中包含 $K(K\leq J)$ 个广告。 $N$ 个广告主竞争 $K(K\leq N)$ 个广告位，每个广告主 $a_{i}$ 根据私有信息（如PCTR等）提交一个出价 $b_{i}$ 。论文通过 $\mathcal{M}(\mathcal{R},\mathcal{P})$ 表示拍卖机制。 $\mathcal{R}$ 是广告分配方案，用于从 $N$ 个候选广告主中选择 $K$ 个获胜广告，并按顺序展示在相应的 $K$ 个固定广告位上。 $\mathcal{P}$ 是支付规则，用于计算获胜广告的支付，并经过精心设计以保证拍卖机制的经济属性和收入

问题公式化建模

在多槽位拍卖中，论文将广告集合表示为 $\mathcal{A}={a_{1},\ldots,a_{N}}$ ，广告位集合表示为 $\mathcal{K}={1,\ldots,K}$ 。然后，分配 $\theta$ 定义为从 $N$ 个候选中选择 $K$ 个广告并按顺序放置在 $K$ 个广告位上。给定广告主的出价和预测的点击率，论文的目标是设计具有外部性的多槽位拍卖机制 $\mathcal{M}(\mathcal{R},\mathcal{P})$ ，以在基本假设下最大化平台收入并减少社会福利的下降，如下所示：
$$
\begin{align}
\underset{\mathcal{M}}{\text{maximize}} &\mathbb{E}_{\theta\in\Theta}[\sum_{a_{j}\in\text{ads}(\theta)}p(\theta,a_{j})\cdot\hat{q}(\theta,a_{j})],\\
\text{s.t.}\quad &\textit{Incentive Compatibility (IC) constraint,}\\
&\textit{Individual Rationality (IR) constraint,}\\
&\textit{Social Welfare (SW) constraint,}
\end{align}
$$
- 其中 $\Theta$ 是所有可能分配的集合， $\theta^{*}$ 是最佳分配， $\text{ads}(\theta)$ 是分配 $\theta$ 中的广告子集， $p(\theta,a_{j})$ 是分配 $\theta$ 中广告 $a_{j}$ 的支付， $\hat{q}(\theta,a_{j})$ 是分配 $\theta$ 中广告 $a_{j}$ 的预测点击率
- IC和IR约束保证了广告主会如实报告出价，并且不会为其分配支付超过其最大愿意支付的价格。社会福利是在线广告的关键指标，因为它衡量了广告主和用户匹配的效率，也是广告平台总收入的上限。SW约束定义如下：
  $$
  1-\frac{\textit{SW}(\theta^{*},\mathbf{b})}{\textit{SW}^{*}}<\varepsilon,
  $$
  - 其中 $\textit{SW}(\theta^{*},\mathbf{b})$ 是最佳分配 $\theta^{*}$ 的社会福利， $\textit{SW}^{*}$ 是 $\Theta$ 中的最大社会福利， $\varepsilon$ 是根据业务场景制定的社会福利下降阈值

$\mathcal{M}(\mathcal{R},\mathcal{P})$ 中的分配方案和支付规则如下：
- 分配方案 $\mathcal{R}:\times_{a_{j}\in\mathcal{A}}\mathcal{V}_{j}\longrightarrow\Theta$
- 每个广告的支付规则 $\mathcal{P}:\times_{a_{j}\in\mathcal{A}}\mathcal{B}_{j}\longrightarrow\mathbb{R }^{+}$，
- 其中 $\mathcal{V}_{j}$ 是广告 $a_{j}$ 的可能价值集合，$\mathcal{B}_{j}$ 是广告 $a_{j}$ 的可能出价集合。具体来说，论文将广告 $a_{i}$ 的实际点击价值表示为 $v_{i}$，广告 $a_{j}$ 的提交点击价值表示为 $b_{j}$
如果拍卖机制是激励相容的（IC），那么每个广告主如实揭示其最大愿意支付价格是最有利的，即 $b_{j}=v_{j}$。如果拍卖机制是个体理性的（IR），那么广告主 $a_{j}$ 的支付金额不会超过其报告的价值，即如果广告 $a_{j}$ 被展示并点击，则 $p(\theta,a_{j})\lt b_{j}$；否则不支付任何费用。有了这两个属性，广告主不需要花费精力计算出价策略，并且可以无风险地参与拍卖。在线平台也能获得真实可靠的广告主价值。由于论文遵循了 WVCG 的理论基础，WVCG 已被证明是 IC 和 IR 的 [Kumar et al., 2019]，因此论文用 $b_{i}$ 表示第 $i$ 个广告主的实际点击价值
为了清晰起见，论文在表 1 中列出了论文中使用的关键符号

NMA拍卖方案

整体方案图：
- 如图2所示，NMA将所有候选广告列表（即每个广告列表代表一个分配 $\theta$ ）和三种类型的公共信息作为输入，并使用三个模块来选择获胜广告列表
  - 上下文感知列表预测模块（CLPM）：CLPM建模每个广告列表的位置依赖外部性和广告依赖外部性，并根据请求的公共信息和广告列表的上下文信息预测每个广告的列表级pCTR
  - 列表深度排序模块（LDRM）：LDRM将拍卖机制与深度学习相结合，并使用子网络建模每个广告列表的信息，旨在提高排序公式的表达能力，同时保证IC和IR属性
  - 列表可微分排序模块（LDSM）：LDSM对拍卖中的排序操作进行连续松弛，并输出一个行随机的置换矩阵。我们可以使用这个行随机置换矩阵来表达预期收入，并端到端学习最优列表
  - 其他辅助损失：社会福利最大化的辅助损失，以满足社会福利约束并减少社会福利的下降

上下文感知列表预测模块

大多数传统的广告拍卖机制使用点级pCTR来计算分配和支付过程中的排序分数。然而，点级pCTR不仅缺乏对拍卖中公共信息的利用，还未能考虑一个列表中广告之间的交互。最近，Liu等人考虑了广告的交互，并提出了一个名为集合编码器的模块来自动建模拍卖中的集合级信息。但它仅建模了局部外部性，因此仍然不够优化。为此，论文提出了上下文感知列表预测模块，以显式建模全局外部性，输出每个广告在列表中的更准确的列表级pCTR
CLPM采用参数共享结构处理所有候选广告列表。这里论文以广告列表 $\theta$ 为例进行说明。如图2所示，CLPM将广告列表 $\theta$ 和三种类型的公共信息（即请求信息、用户画像和当前请求中的Organic Item）作为输入，并输出列表中每个广告的列表级pCTR。论文首先使用嵌入层从原始输入中提取嵌入。广告列表和Organic Item列表的嵌入矩阵分别表示为 $\mathbf{E}_{\text{ad}}\in\mathbb{R}^{K\times d}$ 和 $\mathbf{E}_{\text{oi}}\in\mathbb{R}^{M\times d}$ ，其中 $K$ 是 $\theta$ 中的广告数量， $M$ 是当前请求中Organic Item的数量， $d$ 是嵌入的维度。同时，用户画像和请求信息的嵌入分别表示为 $\mathbf{e}^{\text{u}}$ 和 $\mathbf{e}^{\text{r}}$
使用自注意力单元（SAU）来建模Organic Item列表的序列信息：
$$
\mathbf{H}_{\text{oi}}=\text{Self-Att}(\mathbf{Q}_{\text{oi}},\mathbf{K}_{\text{oi}},\mathbf{V}_{\text{oi}})=\text{soft max}(\frac{\mathbf{Q}_{\text{oi}}\mathbf{K}_{\text{oi}}^{\top}}{\sqrt{d}})\mathbf{V}_{\text{oi}},
$$
- 其中 $\mathbf{Q}_{\text{oi}},\mathbf{K}_{\text{oi}},\mathbf{V}_{\text{oi}}$ 分别表示查询、键和值。这里查询、键和值是从Organic Item的嵌入矩阵线性变换得到的，如下所示：
  $$
  \mathbf{Q}_{\text{oi}}=\mathbf{E}_{\text{oi}}\mathbf{W}_{\text{oi}}^{O}, \mathbf{K}_{\text{oi}}=\mathbf{E}_{\text{oi}}\mathbf{W}_{\text{oi}}^{K}, \mathbf{V}_{\text{oi}}=\mathbf{E}_{\text{oi}}\mathbf{W}_{\text{oi}}^{V}.
  $$
接下来，使用目标注意力单元（TAU）来编码Organic Item与广告列表中每个广告之间的交互：
$$
\begin{align}
\mathbf{h}_{j}^{\text{ad}} &=\text{Tgt-Att}\big(\mathbf{e}_{j}^{\text{ad}},(\mathbf{h}_{i}^{\text{oi}})_{i=1}^{M}\big) \\
&=\mathbf{e}_{j}^{\text{ad}}\cdot\text{MLP}_{\text{att}}(\mathbf{e}_{j}^{\text{ad}}|\mathbf{h}_{i}^{\text{oi}})+\cdots+\mathbf{e}_{j}^{\text{ad}}\cdot\text{MLP}_{\text{att}}(\mathbf{e}_{j}^{\text{ad}}|\mathbf{h}_{M}^{\text{oi}}),\forall j\in[K],
\end{align}
$$
- 其中 $|$ 表示连接， $\mathbf{e}_{j}^{\text{ad}}$ 是广告列表 $\theta$ 中第 $j$ 个广告的嵌入，MLP ${}_{\text{att}}$ 是一个多层感知器（MLP），它将广告和Organic Item对的嵌入作为输入并输出一个注意力权重， $\mathbf{h}_{i}^{\text{oi}}$ 是从前一个单元生成的有序item列表中第 $i$ 个Organic Item的表示
  $$
  \mathbf{e}^{\text{list}}=\text{MLP}_{\text{list}}\Big{(}(\mathbf{e}_{1}^{\text{ad}}|\mathbf{h}_{1}^{\text{ad}}|\text{CTR}_{1}^{\text{ad}})|\cdots|(\mathbf{e}_{K}^{\text{ad}}|\mathbf{h}_{K}^{\text{ad}}|\text{CTR}_{K}^{\text{ad}})\Big{)},
  $$
然后，将第 $j$ 个广告的表示与其对应的嵌入和点级pCTR连接起来，作为其最终表示。广告列表 $\theta$ 中所有广告的表示被输入到一个MLP中，以建模全局外部性：
$$
\hat{q}(\theta,a_{j})=\sigma\Big{(}\text{FC}_{j}(\mathbf{e}^{\text{list}}|\mathbf{e}^{u}|\mathbf{e}^{r})\Big{)},\forall j\in[K],
$$
- 其中CTR表示点级pCTR， $\sigma$ 表示sigmoid函数， $\hat{q}(\theta,a_{j})$ 表示广告列表 $\theta$ 中第 $j$ 个广告的列表级pCTR。为了使CLPM更好地收敛，论文基于每个广告的真实反馈提出了CLPM的辅助损失：
  $$
  L_{list}=\sum_{j=1}^{K}\Big{(}-y_{j}^{\text{ad}}\log(\hat{q}(\theta,a_{j}))-(1-y_{j}^{\text{ad}})\log(1-\hat{q}(\theta,a_{j}))\Big{)},
  $$
  - 其中 $y_{j}^{\text{ad}}\in{0,1}$ 表示用户是否点击了广告列表 $\theta$ 中的第 $j$ 个广告。通过CLPM，我们可以有效地建模全局外部性，输出广告列表的列表级pCTR。与点级pCTR相比，列表级pCTR能够建模位置依赖的外部性，并且更准确，这有助于NMA实现更好的性能。需要注意的是，这里论文仅以CTR为例。通过建模全局外部性来提高预测值准确性的CLPM框架可以轻松转移到其他预测问题，如CVR预测、订单价格预测等

列表深度排序模块

LDRM拍卖机制与深度学习相结合，以提高排序公式的表达能力，同时保证IC和IR属性。首先，论文提取广告列表中广告的出价、嵌入和列表级pCTR作为输入。根据拍卖理论，论文设计了一个子网络（即 $\mu$-Net）来计算每个广告列表的排序分数。 $\mu$-Net的输出对应于WVCG中的权重，用作增加收入的加权因子。然而，WVCG的MAB方法在高工业场景中难以优化。因此，论文升级了深度神经网络以进行端到端优化，它具有丰富的表达能力，可以自动优化仿射参数
数学上，论文将 $\mu$-Net表示为 $f_{\mu}(\cdot)$ ，它将每个广告的分配无关特征作为输入以确保IC，并输出相应广告的私有价值：
$$
f_{\mu}(a_{j})=\sigma\Big{(}\text{MLP}_{\mu}(\mathbf{e}_{j}^{\text{ad}})\Big{)},\forall j\in[K].
$$
然后，广告列表 $\theta$ 的排序分数计算如下：
$$
\mathcal{RS}(\theta,\mathbf{b})=\sum_{a_{j}\in\text{ads}(\theta)}f_{\mu}(a_{j})\cdot b_{j}\cdot\hat{q}(\theta,a_{j})
=\sum_{j=1}^{K}f_{\mu}(a_{j})\cdot b_{j}\cdot\hat{q}(\theta,a_{j}).
$$
最佳广告列表 $\theta^{*}$ 的支付规则为：
$$
p(\theta,a_{j})=\frac{1}{\int_{\Omega}(a_{j})\cdot\hat{q}(\theta,a_{j})}\left[RS(\theta^{*}_{-j},\mathbf{b}_{-j})-RS_{-j}(\theta^{*},\mathbf{b})\right], \forall j\in[K],
$$
- 其中 $a_{j}\in\text{ads}(\theta^{*})$ 且 $\theta^{*}_{-j}$ 是当 $a_{j}$ 不存在时的最佳广告列表
显然，给定支付规则，每个广告的支付低于其出价，这保证了NMA的IR。广告列表 $\theta$ 的预期收入计算如下：
$$
r(\theta)=\sum_{j=1}^{K}\hat{q}(\theta,a_{j})\cdot p(\theta,a_{j}).
$$
为了研究此问题对IC属性的影响，论文在第5.2.1节中进行了综合实验，以计算NMA的数据驱动IC指标。论文将NMA在复杂拍卖场景中的严格IC保留为未来工作的一个有趣开放问题

列表可微分排序模块

LDRM可以有效地计算不同广告列表的排序分数，并选择最佳广告列表进行支付。然而，将分配和支付置于模型学习之外（即作为不可知环境）在某种程度上不适合深度学习。也就是说，分配和支付的过程（实际上是排序操作）本身是不可微分的。Liu等人提出了一个可微分排序引擎来解决这个问题。但在基于VCG的拍卖中，论文对不同的广告列表进行排序，而不是对广告进行排序，这使得之前的可微分排序解决方案在论文的场景中不适用。为此，论文提出了列表可微分排序模块，它将可微分排序从点级广告排序升级到列表级广告列表排序，使得复杂的拍卖机制可以端到端训练
给定集合 $\text{RS}=\left[\text{RS}(\theta_{1},\mathbf{b}),\text{RS}(\theta_{2},\mathbf{b}),\cdots,\text{RS}(\theta_{N_{L}},\mathbf{b})\right]^{T}$ ，论文将argsort操作符定义为从 $N_{L}$ 维实向量 $\text{RS}\in\mathbb{R}^{\tilde{N}_{L}}$ 到 $N_{L}$ 个广告列表的排列的映射，其中置换矩阵 $M_{rs}$ 表示为：
$$
M_{rs}[j,i]=\begin{cases}1&\text{If }i=\text{argsort}(\text{RS})\lfloor j\rfloor\\
0&\text{Otherwise}\end{cases},
$$
- 其中 $M_{rs}[j,i]$ 表示 $\text{RS}(\theta_{i},\mathbf{b})$ 是否是RS中广告列表的第 $j$ 大排序分数。结果来自[15]显示了恒等式：
  $$
  M_{rs}[j,i]=\begin{cases}1&\text{If }i=\text{argmax}(c_{j})\\
  0&\text{Otherwise}\end{cases},
  $$
其中 $c_{j}=(N_{L}+1-2j);\text{RS}-\text{A}_{\text{RS}}\mathbf{I},$ $\text{A}_{\text{RS}}[m,n]$ 表示元素的绝对成对差异， $\mathbf{I}$ 表示全1列向量。根据之前的工作[15, 25]，论文将Eq. (14)中的argmax操作符松弛如下：
$$
\hat{M}_{rs}[j,:]=\text{softmax}(\frac{c_{j}}{r}),
$$
- 其中 $r$ 是温度参数。直观上， $M_{rs}$ 的第 $j$ 行可以解释为在所有广告列表上获得第 $j$ 个最佳广告列表的选择概率
论文将由Eq. (12)计算的所有广告列表的预期收入表示为 $\text{R}=\left[r(\theta_{1}),r(\theta_{2}),…,r(\theta_{N_{L}})\right]^{T}$ ，然后多槽位拍卖的端到端学习问题可以表述为最小化前1预期收入的总和：
$$
L_{tgt}=-\hat{M}_{rs}[1,:]\cdot\text{R}.
$$

社会福利最大化辅助损失

如Eq. (16)所述，广告收入仅与获胜广告列表相关，这使得端到端过程难以学习，并导致社会福利下降。因此，论文设计了一个社会福利最大化的辅助损失，以加速学习过程并减少社会福利的下降
具体来说，广告列表 $\theta$ 的社会福利定义为：
$$
SW(\theta,\mathbf{b})=\sum_{j=1}^{K}b_{j}\cdot\hat{q}(\theta,a_{j}).
$$
- 请注意，论文在Eq 17中有 $v_{j}=b_{j}$ 。由于论文遵循WVCG的理论基础，它被证明是IC的
显然，具有最大社会福利的广告列表是VCG的结果，其中 $f_{p}(\cdot)=1$ 。这里论文首先形成一个置换矩阵 $M_{y}$ ，它通过排序所有广告列表的社会福利来计算。然后，论文使用真实置换矩阵和预测的行随机置换矩阵之间的行级交叉熵（CE）来构建社会福利最大化辅助损失：
$$
L_{ce}=\frac{1}{N_{L}}\sum_{k=1}^{N_{L}}\sum_{j=1}^{N_{L}}\mathbb{I}(M_{y}[k,j]=1)\log\hat{M}_{rs}[k,:].
$$
社会福利最大化辅助损失可以帮助预测的行随机置换矩阵 $\hat{M}_{rs}$ 向最大化社会福利的方向收敛，并有效减少社会福利的下降
然后，NMA的最终训练损失为：
$$
L=L_{tgt}+\alpha_{1}L_{ce}+\alpha_{2}L_{list},
$$
- 其中 $\alpha_{1},\alpha_{2}$ 是用于平衡三个损失的系数。我们可以通过调整这两个参数的值来平衡NMA的性能，并确保NMA满足社会福利约束

Experiments

在本节中，论文在公共和工业数据集上进行了广泛的离线实验，并在美团外卖平台上进行了在线A/B测试，旨在回答以下研究问题：
- RQ1 ：与工业平台上广泛使用的拍卖机制相比，NMA在平台收入和社会福利方面的表现如何？
- RQ2 ：不同模块（即CLPM、LDRM、LDSM、社会福利最大化辅助损失）如何影响NMA的性能？
- RQ3 ：不同的关键超参数设置（即 $\alpha_{1},\alpha_{2}$ ）如何影响NMA的性能？

Experiment Setup

数据集

在离线实验中，论文在公共和工业数据集上提供了NMA有效性的经验证据。两个数据集的统计信息总结在表2中，论文详细描述这两个数据集如下：
- Avito ：公共Avito数据集来自avito.ru的用户搜索日志随机样本。每次搜索对应一个包含五个item的搜索页面，其中两个item有标签并被视为展示广告，其他三个被视为Organic Item。对于每个样本，论文构建候选广告集合 $\mathcal{A}$ ，其中包含用户点击的N-2个item和当前搜索中的2个展示广告，并通过全排列算法生成集合 $\Theta$ 。公共信息包括用户ID、搜索ID和搜索日期。每个item的特征包括itemID、类别ID和标题。每个广告的出价独立地从0.5到1.5的均匀分布中采样。这里论文使用20150428到20150515的数据作为训练集，20150516到20150520的数据作为测试集，以避免数据泄露
- Meituan ：工业Meituan数据集是在2022年4月期间在美团外卖平台上通过GSP拍卖收集的。每个请求转换的样本包括两部分：特征和标签。特征包括所有候选广告列表的信息和公共信息。这些候选广告列表是通过对展示广告集合进行全排列算法生成的。在一个广告列表中，每个广告的信息包括其出价和稀疏特征（如ID、类别、品牌等）。标签包括最终展示的广告列表、该列表的广告收入以及列表中每个广告的二进制点击标签。根据数据收集的日期，论文将数据集按8:2的比例划分为训练集和测试集

评估指标

论文构建了一个离线模拟系统，以确保离线和在线性能趋势一致。每个实验重复5次，使用不同的随机种子，每个结果以均值±标准差的形式呈现。论文在离线实验和在线A/B测试中考虑了以下指标。对于论文中的所有实验，实验结果都归一化到相同的尺度
- 点击率（CTR） ：CTR = $\frac{\sum click}{\sum impression}$
- 每千次展示收入（RPM） ：RPM = $\frac{\sum click\times payment}{\sum impression}\times 1000$
- 每千次展示社会福利（SWPM） ：SWPM = $\frac{\sum click\times bid}{\sum impression}\times 1000$
- 社会福利最大化比率（SWMR） ：SWMR = $\frac{\text{SWPM}}{\text{SWPM}^{+}}\times 100%$ ，其中SWPM ${}^{+}$ 是VCG的SWPM。论文优先考虑收入指标，同时也考虑社会福利指标，因为它是收入的上限。尽管VCG具有最高的社会福利，但其收入非常低。在实际工业场景中，社会福利可以在一定范围内减少，以确保最大收入。需要注意的是，由于实际广告收入与平台的隐私相关，论文转换了出价和支付的绝对值，仅显示RPM和SWPM的相对趋势
除了上述指标外，论文还评估了论文设计的多槽位拍卖机制在IC属性上的有效性

超参数

在Avito和Meituan数据集中，论文使用每个PV请求中展示的top- $K$ 广告（即 $K$ 槽位拍卖）的设置，并根据业务需求将 $\epsilon$ 设置为0.05。论文使用网格搜索尝试了NMA中的不同超参数。由于篇幅限制，论文仅展示最佳结果。在Avito数据集中， $d$ 为8， $\alpha_{1}$ 为0.2， $\tau$ 为1， $\alpha_{2}$ 为0.01，学习率为 $10^{-3}$ ，优化器为Adam，批量大小为1,024，MLP ${}_{\text{list}}$ 和MLP ${}_{\mu}$ 的隐藏层大小分别为 $(32,16,8)$ 和 $(32,8,1)$ 。在Meituan数据集中， $d$ 为8， $\tau$ 为0.1， $\alpha_{1}$ 为0.4， $\alpha_{2}$ 为0.3，学习率为 $10^{-3}$ ，优化器为Adam，批量大小为8,192，MLP ${}_{\text{list}}$ 和MLP ${}_{\mu}$ 的隐藏层大小分别为 $(60,32,10)$ 和 $(32,8,1)$ 。需要注意的是，实验中的广告数量 $N$ 和Organic Item数量 $M$ 被截断以简化。因此，在Avito数据集中， $K$ 为2， $N$ 为10， $M$ 为4；在Meituan数据集中， $K$ 为4， $N$ 为20， $M$ 为50。但显然，NMA可以扩展到具有更多广告和Organic Item的场景

基线

论文将NMA与以下四种代表性的拍卖机制进行比较，这些机制在工业广告平台上广泛使用：
- 广义第二价格拍卖（GSP） ：经典GSP中的排序分数简单地是出价乘以pCTR，即有效每千次展示成本（eCPM）。论文表示第 $i$ 个广告的排序分数为 $rs_{i}=bid_{i}\times pCTR_{i}$ 。其支付为 $p_{i}=rs_{i}^{-1}(rs_{i+1}(b+1))$ ，其中 $rs_{i+1}(b+1)$ 是下一个最高广告主的排序分数， $rs_{i}^{-1}$ 是 $r_{i}(\cdot)$ 的反函数
- 深度神经拍卖（DNA） ：DNA是基于GSP的端到端神经拍卖机制。DNA可以使用历史拍卖结果的真实反馈优化多个性能指标。在论文中，论文统一优化eCPM以确保DNA和NMA的公平比较。但值得注意的是，论文的实验结论很容易类比到具有多个性能指标的实验
- Vickrey-Clarke-Groves（VCG） ：具有外部性的VCG使用社会福利评估所有分配。具有最大社会福利的分配获胜，其支付规则为：获胜分配中的每个广告因其导致的社会福利损失而被收费，即没有该广告的最佳分配的社会福利与获胜分配的社会福利之间的差异
- 加权Vickrey-Clarke-Groves（WVCG） ：WVCG通过参数线性加权每个分配的社会福利，并使用MAB求解参数

离线实验

性能比较（RQ1）

论文构建了一个离线模拟系统，以确保离线和在线性能趋势一致。每个离线实验重复5次，使用不同的随机种子，每个结果以均值±标准差的形式呈现。论文在公共和工业数据集上的详细实验结果总结在表3中。与代表性拍卖机制相比，论文从实验结果中得出以下观察：i）直观上，NMA在两种数据集上的所有三个指标上都比DNA和GSP有显著改进。一个合理的解释是，NMA可以有效地建模全局外部性，而DNA仅建模了局部外部性。ii）与VCG相比，NMA在广告收入和社会福利之间有更好的平衡，这意味着NMA在较小的社会福利下降下实现了更高的广告收入。这也表明VCG以广告收入为代价最大化社会福利，这对大多数工业实践来说是不可接受的。iii）显然，WVCG在RPM方面被NMA压倒。这一实验结果验证了NMA强大的表达能力和高效的端到端学习能力
此外，论文还应用IC-R（表示效用最大化者的事后遗憾）来量化NMA的IC。IC-R的较大值表示广告主可以通过操纵出价获得更大的效用。例如，表4中的0.309表示广告主可以通过修改其出价在GFP拍卖中增加约30.9%的效用。具体来说，论文每次在Avito上进行 $2000\times 10$ 次测试，在Meituan上进行 $2000\times 25$ 次测试，其中2000是测试拍卖的数量，10（或25）是每次拍卖的广告数量。对于广告 $a_{i}$ ，论文仅将其出价 $b_{i}$ 替换为 $\beta\times b_{i}$ ，其中 $\beta\in{0.1,0.3,0.5,\cdots,1.9}$ 是乘法扰动因子。该拍卖中其他广告的所有特征和出价保持不变。基于上述设置，论文随机抽样数据并重复实验20次，以观察三种拍卖的IC-R。如表4所示，NMA与VCG具有相同的性能——两者都优于广义第一价格（GFP），这验证了NMA有效地满足了IC约束

消融研究（RQ2）

为了验证不同模块（即CLPM、LDRM、LDSM、社会福利最大化辅助损失）的影响，论文在Meituan数据集上研究了NMA的三个消融变*
- NMA (-CLPM) ：不使用上下文感知列表预测模块，并使用原始点级pCTR计算排序分数。对于具有相同排序分数的分配，论文随机选择一个作为获胜广告列表
- NMA (-LDRM-LDSM) ：同时屏蔽列表深度排序模块和列表可微分排序模块，并使用WVCG计算每个分配的排序分数和支付
- NMA (-SW Aux Loss) ：移除社会福利最大化的辅助损失，即 $\alpha_{2}=0$
从表6中的实验结果来看，论文有以下发现：i）没有CLPM的变体表现不如NMA。这一现象证明了论文提出的CLPM可以有效地建模全局外部性，并帮助NMA实现更好的性能。ii）NMA(-LDRM-LDSM)的实验结果在所有三个指标上都比NMA差。这支持了训练升级可以促进性能提升的观点。iii）有和没有社会福利最大化辅助损失的SWPM性能差距明显。这表明辅助损失使论文能够在最大化广告收入的同时减少社会福利的下降
此外，论文还观察了有和没有CLPM的AUC和Logloss指标，以验证CLPM在CTR预测方面的改进。如表5所示，CLPM在Avito和Meituan上分别比原始点级pCTR结果提高了0.006和0.016的AUC，这说明CLPM能够有效地建模全局外部性，并提高预测值的准确性

超参数分析（RQ3）

论文分析了两个超参数的敏感性： $\alpha_{1}$ 和 $\alpha_{2}$ 。具体来说， $\alpha_{1}$ 和 $\alpha_{2}$ 分别是社会福利最大化辅助损失和CLPM辅助损失的系数。RPM和SWPM的曲线如图3所示，论文有以下发现：i）随着 $\alpha_{1}$ 的增加，NMA的SWPM增加，但RPM下降。这一现象表明，论文的社会福利最大化辅助损失有助于NMA在广告收入和社会福利之间实现更好的平衡。当 $\alpha_{1}$ 增加时，论文更关注社会福利。当 $\alpha_{1}$ 减少时，论文更关注广告收入。ii）在一定范围内增加 $\alpha_{2}$ 可以提高性能。但如果 $\alpha_{2}$ 过大，会导致性能下降。一个可能的解释是，CLPM的辅助损失可以在一定范围内有效地引导NMA朝着目标方向学习。但如果辅助任务的权重过大，可能会导致学习方向被该任务主导，从而导致整体性能下降

在线结果

论文将NMA与GSP进行比较，并通过在线A/B测试将两种拍卖机制部署在美团外卖平台上。对于候选广告列表，论文使用全排列算法在线获取所有候选广告列表，超参数 $K$ 、 $N$ 、 $M$ 与离线相同。需要注意的是，在论文的基于位置的服务（LBS）场景中，广告数量 $N$ 非常少。因此，论文还将NMA扩展到具有大量广告的场景，以验证其可行性，其中论文使用一些列表生成算法来减少时间复杂度并近似生成候选广告列表
论文从2022年5月20日到2022年6月20日（一个月）进行了在线A/B测试，使用了1%的生产流量。在长期观察下，性能稳定。结果发现，CTR、RPM和SWPM分别增加了6.37%、10.88%和6.22% ，这表明NMA可以实现更高的平台收入和社会福利。值得注意的是，离线实验中的增加值为6.97%、11.20%和6.49%。绝对值差异的一些可能原因是数据分布的差异和离线评估中的小误差

结论

一句话总结 ：论文提出了具有外部性的神经多槽位拍卖（NMA），旨在为在线广告学习端到端的多槽位拍卖机制，并在减少社会福利下降的同时获得更高的收入
细节简述 ：具体来说，论文通过上下文感知列表预测模块有效地建模了全局外部性。论文设计了一个列表深度排序模块，以确保端到端学习中的IC；论文还提出了一个社会福利最大化的辅助损失，以在最大化收入的同时有效减少社会福利的下降
应用情况 ：作者已将NMA机制部署在美团外卖平台上。离线实验结果和在线A/B测试表明，NMA显著优于其他现有的拍卖机制基线
一些讨论 ：论文中提到，全排列可以替换为列表生成模块 ，如启发式方法，这可以满足工业部署需求（全排列需要搜索的空间大，耗时长），但这可能会对有效性产生影响
未来：未来需要进一步优化以提高方案线上serving的效率

CA——oCPX产品赔付机制的讨论

本文简单讨论oCPX产品赔付机制

参考链接：

百度赔付规则

赔付统计周期
- 3个自然日，今日投放，则未来3天内都是统计周期
赔付条件
- 1）在返款统计周期内转化数累计≥5；
- 2）超出广告主预期消费20%，（实际消费-预期消费）／预期消费>20%；
- 3）在返款核算评估期间，每天修改广告单元出价的次数≤2次；
赔付金额
- 1）预期消费 =（目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …（目标成本n*对应转化数）
- 2）返款金额 = 实际消费 - 预期消费

字节赔付规则

赔付统计周期
- 5个自然日，今日投放，则未来5天内都是统计周期
赔付条件
- 1. 超成本比例：转化成本超过目标成本的20%以上（举例：目标成本10元，转化成本≥12元）
- 1. 赔付时间范围：以广告计划首次投放出去的时间为起始，至之后的3个自然日内（投放时间以平台统计为准）
- 1. 修改要求：每天修改广告计划出价或定向其中任意一个的次数不能超过2次
- 1. 转化数量要求（不含一键起量、账户优选起量的转化数），这里不同的媒体平台和计费模式不同
    - oCPM场景，一般在2-6个转化不等，oCPC场景，要求大于31个转化才赔付
- 1. 广告主无异常作弊等操作行为
赔付金额
- 1. 总预期消耗 =（目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …
- 1. 赔付金额 = 总实际消耗 - 总预期消耗

快手赔付规则

赔付统计周期
- 14个自然日，今日投放，则未来14天内都是统计周期，其中直播推广的商品点击等场景是2个自然日
赔付条件
- 超过120%
- 同一天内修改次数小于等于两次（注意是同一天内小于等于2次，任意一天不满足都不赔付）
- 转化数超过一定阈值
赔付金额
- 同字节和百度

趣头条赔付规则

赔付统计周期
- 3个自然日，今日投放，则未来3天内都是统计周期
赔付条件
- 单元所在赔付周期内，实际转化成本超过目标出价的20%以上（举例：目标出价30元，则在单元实际成本>36元时享有赔付资格）；
- 在一个赔付周期内，单元的出价（含目标出价、深度转化出价、目标次留率）及单元定向，每天修改次数分别不超过2次，如超过则所在周期失去赔付资格；
  - 注意这里是赔付周期内不能修改超过2次（其他公司常用每天不超过2次）
- 赔付周期内转化数超过一定阈值
赔付金额
- 同字节和百度

拼多多

无赔付（截止到25年4月）

整体总结

赔付统计周期
- 一般在3-14天不等（主要是面临转化归因慢的问题）
赔付条件
- 超过120%（主要是避免因为正常波动导致的超成本）
- 同一天内改价次数不能超过2次（主要用于防止广告主频繁改价作弊，同时也防止出价目标变化太快，系统来不及调整）
- 赔付周期内有一定的转化数（减少广告主不回传/说假话）
赔付金额
- 赔付金额 = 总实际消耗 - 总预期消耗 = 总实际消耗 - （目标成本1 * 对应转化数）+（目标成本2 * 对应转化数）+ …（主要是保证广告主改价的体验）

一些特殊场景的oCPX赔付规则思考

子问题：在订单闭环、广告主广告理解能力弱、对平台信任度低、广告主订单数据特别稀疏的场景中，可以如下设置赔付规则？
赔付周期：
- 1天为周期赔付（促进广告主信任和理解）
赔付条件：
- 超成本就赔付（促进广告主理解和信任，120%赔付下给广告主的解释成本较高，后续可以逐步尝试）
- 转化数无要求（闭环情况下，广告主无法说假话）
- 消耗金额给与一定要求（防止广告主投放中途为了赔付而关闭投放）
- 改价次数尽量少（防止目标波动）
赔付金额：
- 规则设计：赔付金额 = 总实际消耗 - （总转化数 * 当日最大目标成本）
- 这样设计的好处有：
  - 能起到不鼓励广告主改价的效果，因为从赔付金额计算方式来看，广告主改价一定是亏的（有效促进系统稳定性）
  - 方便系统统计和归因（不需要记录成本改价时间和订单具体归因时间，部分订单是难以归属上准确时间的）
  - 容易给到广告主解释（比如11点改价，那么10:59点击带来的11:02分下单的订单如何归因？广告主理解成本较高）
- 这样设计的坏处有：
  - 这种情况不鼓励广告主改价，从而广告主可能也不愿意向上提价（这里通过提价后系统给扶持来部分缓解）
  - 系统策略可能hack规则不论广告主是否改价都按照最高价收（需要注意为了价格杠杆考虑，也为了广告主利益考虑，不应该按照最高价出价，而应该在每个时刻都按照广告主当前设置目标出价）

CA——各种拍卖机制总结

参考链接：
- 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）

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

SW-VCG, Score-Weighted VCG
原始论文：Learning-Based Ad Auction Design with Externalities: The Framework and A Matching-Based Approach
博客：KDD’23 | Score-Weighted VCG：考虑外部性的智能拍卖机制设计

GSP

一些对比 from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）：

普通的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

原始论文：NMA: Neural Multi-slot Auctions with Externalities for Online Advertising, 2022, ArXiv preprint, Meituan

(RegretNet)Optimal Auctions through Deep Learning

(AMA)Affine maximizer auction

参考论文：A Scalable Neural Network for DSIC Affine Maximizer Auction Design, NeurIPS 2023, PKU，Spotlight

附录：一些特殊拍卖

BDFPA

折价一价拍卖(bid-discount first-price auction,BDFPA)，来源于文章Budget-Constrained Auctions with Unassured Priors: Strategic Equivalence and Structural Properties, Tencent

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

参考论文：Joint Bidding in Ad Auctions, pp 344–354, TAMC 2024, Meituan

(JRegNet)Joint Auction in the Online Advertising Market

参考论文：Joint Auction in the Online Advertising Market, KDD 2024, Meituan

CA——多任务学习总结

多任务学习，multi-task learning

参考链接：

多任务学习的结构

预估任务中一般包含ESMM及扩展，MMoE及相关变体
NLP中的MoE则是挑选部分网络，会丢弃部分网络

多任务学习的损失函数权重设置

基于人工经验的人工优化

一般思想是对齐损失函数均值，并按照业务偏好有所倾斜，如果愿意花时间尝试，往往能拿到不错的结果

基于贝叶斯推论的权重优化

基于不确定性的权重设置方法（Uncertainty Weighting）
基本公式
$$
L(\mathbf{W}, \sigma_1, \sigma_2,…,\sigma_K) = \sum_{k=1}^K \frac{1}{2\sigma^2}L(\mathbf{W}) + \log \sigma^2
$$
- 上述公式可通过推导得出Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics
  - 可以推导，无论是回归问题还是分类问题（也可以是分类和回归问题的混合），都可以按照上面的方法设置损失函数（分类问题证明中会使用到一个近似值，不是严格推导）
  - 推导是在假设
- $\sigma$ 是可学习的参数，初始设置固定值，然后使用梯度更新学习即可
- 使用简单，实际使用时效果也确实不错，建议人工调参也可以在先使用该方案拿到权重量级后继续

帕累托最优权重优化

原始论文：Multi-Task Learning as Multi-Objective Optimization
内积的含义：向量A到向量B的投影长度与向量B长度的乘积
Algorithm1展示的是，对于两个任务的情况，图示展示了二维向量的情况，可以通过判断向量之间的关系确定求解 $\alpha$ 的方式
- Algorithm2中的FrankWolfeSlover算法则是对Algorithm1的多任务扩展
其他参考，阿里巴巴多任务学习帕累托最优论文：A Pareto-Efficient Algorithm for Multiple Objective Optimization in E-Commerce Recommendation

损失函数优化

损失函数归一化

可用于解决由于不同任务损失函数量级差异带来的问题

普通版本

$$
L_{norm} = \frac{L_k(\mathbf{W})}{L_0(\mathbf{W_0})}
$$

使用各个任务自己的第一次输出的损失函数作为基础损失函数，其中 $L_0(\mathbf{W_0}$ 为第一次计算loss的到的损失函数

滑动平均版本

$$
L_{base} = \alpha L_{base} + (1-\alpha) L_k \\
L_{norm} = \frac{L_k(\mathbf{W})}{L_{base}} \\
$$

使用滑动平均来记录基础损失函数，该方案可进一步减少由于初始化损失误差过大带来的问题

梯度归一化（GradNorm）

原始论文：GradNorm: Gradient Normalization for Adaptive Loss Balancing in Deep Multitask Networks
核心思想是对各任务的损失函数进行加权($w_i$)求和得到更新共享参数的损失函数
“GradNorm”这个名字的由来是因为权重 $w_i$ 是与梯度2范数的期望等有关的？
公式中 $w_i$ 是各个任务损失函数对共享参数损失函数的权重，该权重初始值为1，在训练过程中逐步更新，每一步最后都保持该权重加和为 $T$ （ $T$ 为任务数量，即保证权重均值为1）
问题：文中没有明确各个任务各自的参数如何更新，猜测各自更新即可

最佳实践

一般情况下，根据业务特点，尽量使用类似于ESMM结构
权重设置尝试次序：
- 对损失函数进行归一化（梯度归一化好像效果一般？）
- 权重设置时，先使用不确定性权重（Uncertainty Weighting）跑一版，得到基线
- 在Uncertainty Weighting的基础上，人工可以根据业务需要微调，可以偏向于需要的任务
- 帕累托最优实现复杂，且不一定有收益
  - 复杂体现在：需要在每个batch上重新求解最优化问题，得到当前的loss权重（用上一个batch的梯度求解这一个batch的最优权重）

CA——拍卖机制设计概述

注：论文主要参考自万字长文，漫谈广告技术中的拍卖机制设计（经典篇）等资料，有一些自己的思考

参考链接：
- 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）

名词解释

竞拍者 ：需求方，在广告系统中就是广告主
机制拍卖中的一般假设 ：一般假设竞拍者是理性的，即满足个体理性（收益非负），且有能力通过调整自己的策略来获得更高的收益，
私有信息（Private Value） ：也称为私有估值 ，竞拍者对物品、广告位的估值一般是私有信息，一些论文也称为Type类型 ，该信息是外部不可知的
- 一些机制设计的目标就是诱导竞拍者在博弈中真实表达自己的私有信息（所以要设计他们说真话是他们的最优策略的机制）
拍卖机制 ：包含分配规则（Allocation Rule）和计费规则（Payment Rule）两个部分
效用（Utility） ：一般是价值减去支出即效用函数 = 广告主获得的价值 - 广告主的支付价格，即 $u = v - p$
广告主偏好 ：通常包含效用最大化（Utility Maximizer）和价值最大化（Value Maximizer）两种类型
社会福利（Social Welfare） ：指的是整体广告主的价值和，单个广告主对单个广告位置的价值 = 广告主获得广告位的概率 * 广告位对广告主的价值
- $n$ 个竞拍者的社会福利可表示为 $SW = \sum_{i=1}^n v_i x_i$，其中 $x_i$ 是竞拍者 $i$ 获得物品的分配概率，$v_i$ 是竞拍者 $i$ 对该物品的估值
- 社会福利的另一个视角：广告主效用为0时（即商家说真话且按照一价计费时），社会福利等于买家从广告主手里获得的收入 ，所以社会福利也可以表达为在满足 IR 的情况下，社会福利等于买家可以从广告主手里获得的最大收入
流动性福利（Liquid welfare）【未找到精确定义，待补充】 ：流动性福利是指存在预算约束情况下的社会福利（目前看到的都是预算约束下的流动性社会福利定义），表示在不违反财务约束的情况下可以从竞拍者中提取的最大收入 ，Auto-bidding and Auctions in Online Advertising: A Survey, 202408, Google 中有相关的定义（Truthful Auctions for Automated Bidding in Online Advertising, IJCAI 2023, Alibaba 中有ROI约束+预算约束下的定义）
- $n$ 个竞拍者的流动性福利可表示为$\text{LW}=\sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0}\min\left(\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}},B_{i}\right)$，其中 $R_i,B_i,v_i(\mathbf{t}^{\prime})$ 分别表示广告主设置的ROI，预算和广告主的累计价值 ，关于社会福利和流动性福利的更多讨论见附录
有效机制（efficient mechanism） ：社会福利最大化的机制是对资源最有效率的配置方式，所以该类型的机制也叫有效机制
最优机制（optimal mechanism） ：平台收入最大化的机制称为最优机制
拍卖机制的目标 ：使得广告主竞价博弈收敛结果符合平台预期（平台预期包括平台收益、社会福利等）
- 常见的目标包括社会福利最大化和平台营收最大化
激励相容（Incentive Compatibility） ：鼓励竞拍者讲真话
优势策略激励相容（Dominant-Strategy Incentive Compatibility，简称DSIC） ：不管其他智能体如何报告自己的私有信息，如实报告（即讲真话）都是每个广告主的最优决策，即说真话时广告主效用最大化（效用最大化类型的用户）；
贝叶斯纳什激励相容（Bayes-Nash Incentive Compatibility，简称BIC） ：如果其他广告主是如实报告自己的私有信息的，那么广告主最优反应也是如实报告
完全信息设定 ：参与者知道其他参与方的真实类型
不完全信息设定 ：参与者只知道其他参与方的类型分布（而不是真实类型）
博弈均衡 ：博弈均衡是博弈论中的一个核心概念，它描述了在给定的博弈规则下 ，参与者选择某种策略后所达到的一种均衡状态（稳定状态）。在这种状态下 ，每个参与者都无法通过单方面改变自己的策略来获得更好的结果。换句话说，博弈均衡是一种策略组合 ，使得任何一个参与者都没有动机去单方面改变自己的策略
- 纳什均衡 Nash Equilibrium（NE） ：在完全信息设定下的，一种在给定其他参与者策略时，任何单个参与者都没有动机去改变自己的策略的均衡状态
  - 囚徒困境是一个典型的纳什均衡，两者都选择说真话就是囚徒困境的纳什均衡状态
- 贝叶斯纳什均衡 Bayesian Nash Equilibrium（BNE） ：一种在不完全信息设定下得，一种在给定其他参与者策略和类型分布（注意：只知道类型分布，不知道真实类型）时，没有参与者有动机单独改变其策略的均衡状态
  - 贝叶斯纳什均衡可以看做是对纳什均衡的一个扩展，用于处理不完全信息的情况
- 优势策略均衡 Dominant Strategy Equilibrium（DSE） ：一种在完全信息或不完全信息设定下得，无论其他参与者选择什么策略 ，每个参与者策略总有自己的最优策略的均衡状态
  - 如果存在优势策略均衡，则它一定是唯一的纳什均衡 ，因为每个参与者都有明确的最佳行动，不受其他参与者行为的影响
  - 优势策略均衡一定是一个纳什均衡
- 注：一个好的机制下，博弈结果可以有一个均衡 ，也可以有多个均衡 ，但不能是非均衡的
直接显示机制（direct-revelation mechanism） ：要求参与者直接如实报告自己的私有信息（例如在拍卖中直接出价，而非通过复杂的行为间接传递信息）
- 直接显示机制不一定满足 DSIC ：实际上，参与者会报告一个自己的类型空间中的值（不一定是真实的），即
- 直接显示机制不一定存在均衡状态 ：可能竞拍者会来回调整他的报价，尝试拿到更优的收益
- 注意：在一些书籍或博客中，会表达直接显示机制要求竞拍者如实报价 ，这会让人误以为直接显示机制都是 DSIC 的，我的理解是这并不代表机制是 DSIC 的，要求只是表达一个期望，要求了竞价者也不一定会如实上报
可实施的分配规则 ：对于一个分配规则x ，如果存在一个扣费规则p ，使得直接显示机制 (x, p) 是满足 DISC 性质的，那么就称这个分配规则x是可实施的；

理想的拍卖机制是怎样的？

高效率保证 ：多项式时间（一般近似线性）内完成分配和扣费两个计算过程
- 为了可以应用，这个规则一般不可以做松弛
高效果保证 ：存在均衡 ，且均衡结果满足引导预期 ，社会福利最大化或平台营收最大化；
- 为了保证高效率保证 ，这个要求可以被松弛，主要是涉及到分配规则
  
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  因为最优分配问题本质是一个背包问题，而背包问题是NP困难问题，分配规则不可能在多项式时间内被实现，所以往往采用启发式的贪心算法，也就是业界常用的排序策略。这样分配问题就转化为了排序问题，例如论文开头Rankscore计算公式的设计，可以获得高效率的近似最优解
高动机保证 ：优势策略激励相容（DSIC） ，即如实报价是参与者的优势策略（注意此时均衡不仅存在，而且是以最严格的优势策略均衡（DSE）的形式存在）；
- 为了保证高效率保证 ，这个要求也可以被松弛，主要涉及到扣费规则
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  - Myerson引理证明当分配规则确定 ，扣费规则就是唯一的、且有明确的表达式 ，假设该表达式是a。可是实际环境非常复杂，或因为计算效率问题，或因为业务约束问题，导致实际采用的扣费规则没有用a，却用了b，那么DSIC就会被破坏
  - 但是非DSIC机制就一定很糟糕吗？答案非也。前文提到，优势策略均衡是最理想的均衡结果 ，机制设计的底限是要有均衡的预期 ，有均衡预期就有足够假设来预测智能体的行为，那么机制结果就能有效推演。所以非DSIC机制也可以有不错的均衡性质 ，它们在实际中很常见
  - 例如广告拍卖机制中，假设广告主偏好模式是Utility Maximizer ，平台优化目标是社会福利最大化 ，那么只有VCG机制满足 DSIC ，GSP机制不满足 DSIC ，但是也不妨碍GSP机制盛行，详细内容下文会重点介绍
个人理解：
- 拍卖机制能最大化社会福利的前提是竞拍者真实报告自己的类型，否则无法实现，故而要尽量保证 DSIC 才能尽量做到社会福利最大化

Myerson 引理

分配规则 ：一个分配规则是可实施 ，当且仅当它是单调的；
扣费规则 ：如果分配规则是单调的，那么存在唯一的扣费规则 ，使得直接显示机制是 DSIC 的，且这个扣费规则有明确的表达式

拍卖形式的分类

单物品拍卖和多物品拍卖 ：按拍卖品数量划分，有些文章也称为单位置拍卖和多位置拍卖
单参数拍卖和多参数拍卖 ：按照竞拍者报价数量划分，注意是一次拍卖中，上报多个估值还是上报一个估值划分
单轮拍卖和多轮拍卖 ：按照竞拍论述划分

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
轮数越多，竞拍者的私有信息Type会越来越成为公有信息，使得竞拍者能有更多的信息做决策从而调整报价策略。虽然多轮拍卖更加契合实际广告拍卖场景，广告主一笔预算往往会参与很多轮的请求报价，但是多轮的机制设计比单轮复杂很多，一般简化为单轮拍卖形式进行分析讨论
无约束拍卖和有约束拍卖 ：按照竞拍者目标是否带着约束划分

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
有约束是指在广告主追求营销目标最大化的同时会带有指标约束，例如预算约束或者ROI约束等，这样广告主报价策略会从短期收益最大化调整为长期收益最大化，这对机制性质也会带来不小挑战
注意：一般的广告拍卖场景中（包括万字长文，漫谈广告技术中的拍卖机制设计（经典篇）），一般都将广告的经典机制设计范畴规约在“异质多物品、单参数、单轮和无约束”拍卖形式下（简称多物品拍卖）

社会福利最大化的拍卖机制

社会福利最大化的机制是对资源最有效率的配置方式，所以该类型的机制也叫有效机制（efficient mechanism）

SW最大化-单物品拍卖的有效机制

二价计费（Second-price auction，简称SP）机制，也叫 Vickrey auction，是社会福利最大化的 DSIC 机制

SW最大化-多物品拍卖下VCG和GSP机制比较

VCG机制

多物品拍卖下，若想要实现社会福利最大化 ，分配规则应该按照报价从高到低排序，第 $i$ 高报价的竞拍者获得第 $i$ 好的物品，此时，通过Myerson引理可以证明，满足DSIC的唯一支付公式是VCG扣费方式：
$$ p_i = \sum_{j=i}^k b_{j+1} \frac{\alpha_j - \alpha_{j+1}}{\alpha_i} $$
- 付费是该竞拍者赢得广告位后，给其他广告主带来的收益损失是该竞拍者需要支付的费用；直观理解为：从自己获得的这一物品起，后续所有物品上对其他人造成的损失和（因为后面每个竞拍者都因为竞拍者 $i$ 的存在而后移一位，所以可以如上式表示社会福利），一般的论文中，也常常也表示为：
  $$ p_i = SW_{-i} - (SW - v_i x_i) $$
  - $SW_{-i}$ 是竞拍者 $i$ 不参与竞拍时的其他人获得的总社会福利
  - $SW - v_i x_i$ 是竞拍者 $i$ 参与竞拍时的其他人获得的总社会福利 ， $SW$ 则表示包括竞拍者 $i$ 在内的总体社会福利
多物品拍卖下的Vickrey–Clarke–Groves auction（简称VCG机制）是单物品拍卖下的Vickrey auction（也称SP机制）有效升级，下图准确表示了 VCG 机制是满足 DSIC 的：
- $z$ 表示估值分布，$v$ 表示真实估值，$b$ 表示报价；$x(z)$ 表示分配结果（对应为点击率），$p(v)$ 或 $p(b)$ 表示计费结果
- 三列分别为出真实价值 $b = v$，出高价 $b > v$ 和出低价 $b < v$ 的情况
- 第一行表示不同出价 $b$ 下获得的价值，第二行表示支付金额，第三行表示效用(Utility) = 价值 - 支付，即 $u = v\cdot x(b) - p(b)$
- 阶梯函数是因为在不同的位置，点击率不同，但同一个位置，随着出价变化，点击率是相同的
- 图中绿色部分就是收益部分（注：第三行第二列中绿色区间还要减去阴影部分才可以），显然说真话是效用是最大的
多物品拍卖下，若目标是社会福利最大化 ，则VCG机制是满足 DSIC 机制的唯一机制
- 单物品拍卖下，若目标是社会福利最大化 ，SP机制是满足 DSIC 机制的唯一机制
- 单物品拍卖下，若目标是平台收入最大化 ，Myerson拍卖机制是满足 DSIC 机制的机制（并非唯一？）
VCG机制的缺点 ：
- 计算复杂 ：运行效率低下，运算复杂（比如一些场景中需要做listwise的CTR预估）
- 平台收入低 ：平台收入较低（比GSP等都低，可以认为是常见的收入最低的拍卖形式，唯一的优点是满足 DSIC）
- 解释成本高 ：给广告主解释困难

GSP机制

GSP机制（Generalized second-price auction）分配规则和VCG一样，按照下一位出价计费：
$$ p_i = b_{i+1} $$
类似上面 VCG 机制的分析图，下图展示了 GSP 机制的分析情况：
- 可以看到，报高价没有正向收益（第三行第二列），但是报低价有可能获得更高的效用（第三行第三列和第三行第一列的绿色区域孰高孰低不一定）
广告主是效用最大化类型时，GSP虽然不是 DSIC 的，但是其有不错的均衡性质（机制要求均衡且均衡状态满足机制目标即可，不一定要 DSIC ，DSIC 是个非常强的性质），GSP包含两个视角的均衡 ：
- Pure Nash Equilibrium under Full-Information Setting ：完全信息设定下的纳什均衡？
- Bayesian Nash Equilibrium under Partial-Information Setting ：不完全信息设定下的贝叶斯纳什均衡？
  
  from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
  以前者（理解：这里指Pure Nash Equilibrium under Full-Information Setting）为例，假设多轮竞价交互之后广告主的估值成为公有信息，GSP机制达到的一种均衡结果是广告主会认为保留当前位置是最优策略，不愿意与比他顺位高的人换位置，不然利润受损，这种均衡叫 locally envy-free equilibrium（也称symmetric Nash equilibrium），对应广告主的报价策略不再是如实报价，详细可见文献
GSP优点缺点总结 ：
- 计算简单 ：仅需一个简单公式，容易落地
- 平台收入高 ：收入更高，对照VCG和GSP的分析图中第二行可得
- 容易解释 ：按照下一位出价计费，简单易懂
- DSIC讨论 ：在广告主是效用最大化类型时，GSP不是 DSIC的（有文献提到，在广告主是Value最大化类型时，GSP机制是 DSIC 的）
- 均衡性讨论 ：GSP存在多个均衡，GSP的其中一个均衡结果和VCG等价（注：此时因为扣费大于VCG，所以平台营收会比VCG更高）
  - 问题：这里的与VCG等价是说，在这个均衡状态下，大家都会说真话吗？存在部分竞拍者会试探低价吧？

SW最大化-GSP机制关于点击率的升级

下面的内容主要考虑关于点击广告（按点击售卖的广告）场景，目标还是如何优化社会福利，更好的实现社会福利最大化，提高资源分配效率

GSP

普通的GSP认为点击率只与广告位置有关，与广告主无关，未考虑不同竞拍者（广告实体）的点击率在同一个位置会不同
下文中也称广告自身的点击率为广告质量分

wGSP

wGSP（weighted GSP）引入一个与竞拍者 $i$ 相关的点击率 $\beta_i$（也称为广告质量分）
- 注：wGSP并没有假设广告在不同位置会有不同的广告质量分（理解：这里的质量分是与广告位置无关的，用户和广告之间的匹配分数）
此时社会福利是（$n$ 个广告主， $k$ 个资源位）：
$$ SW = \sum_{i=1}^n \sum_{j=1}^k v_i \beta_i \alpha_j $$
广告主的效用是：$u_i = \beta_i \alpha_j(v_i - p_i)$，注：效用也是效用最大化类型广告主的优化目标
wGSP分配规则 ：按照 $\beta b $ 排序
wGSP计费规则为：
$$ p_i = \frac{\beta_{i+1} b_{i+1}}{\beta_i} $$

iGSP

wGSP没有考虑广告在不同位置会有不同的广告质量分（点击率），实际上，不同位置上、同一位置不同上下文情况下广告的点击率均会有不同
iGSP（iterated GSP）考虑了广告在不同位置会有不同的广告点击率，但仅仅可以在做到2个资源位同时拍卖的情况下，最大限度保证 existence of efficient equilibria ，3个资源位的情况还没解决
- 问题：如何理解最大限度保证 existence of efficient equilibria？
iGSP分配规则 ：逐个位置拍卖，逐个位置预估考虑到上下文、位置因素下的每个广告主的点击率 $\gamma_{ij}$，然后按照价高者得
iGSP计费规则 ：每次拍卖时，对当前拍卖位置的首位广告主（当前位置竞胜者）进行二价计费：
$$p_{1j} = \frac{\gamma_{2j}b_2}{\gamma_{1j}}$$
竞胜后的广告主不参与下一轮位置竞争，遍历拍卖至资源分配完
iGSP的总结：相对于wGSP，拍卖流程更复杂，但因为考虑到广告在不同位置下的质量分，会使得社会福利更优（资源配置效率更高）

平台收入最大化的拍卖机制

满足 DSIC 性质，且使得平台收入最大化（Revenue最大化，简称Rev最大化）的机制称为 最优机制（optimal mechanism）

Rev最大化-VCG与GSP的平台收入比较

GSP的收入更高，对平台来说，GSP机制更受欢迎
GSP机制不再是 DSIC 的（从前文看，广告主有隐瞒估值，刻意报低价的动机），但GSP机制有均衡性质（注意：均衡结果是最起码的要求，否则从长期博弈结果来看短期的平台营收都不可持续）

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
换个角度解释这个现象，GSP机制不是DSIC的，广告主有隐瞒估值低报价的动机，所以长期来看会随着广告主低报价整体社会福利不如VCG，使得虽然在分蛋糕方面GSP有优势但在做大蛋糕方面存在不利因素，此消彼长，长期看平台营收GSP一定会打折扣。GSP有不错的均衡性质尚且如此，更何况其他粗暴魔改扣费规则的机制了，所以事情看来没有那么简单

Rev最大化-单物品拍卖的最优机制

SP机制：Second Price，二价计费
SP+保留价机制：二价计费，同时带有保留价，当低于保留价时，不售卖，高于保留价时，保留价参与二价计算（即广告主计费不会低于保留价）
Myerson机制：可以获得最大化期望收益的最优机制
- 注：在竞拍者私有估值服从独立同步分布时，Myerson拍卖机制等价于SP+保留价 $\varphi_i^{-1}(0)$ 机制
其他补充：

from 万字长文，漫谈广告技术中的拍卖机制设计（经典篇）
首先定义虚拟估值 $\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$，它和私有估值 $v_i$ 以及分布 $F$ 有关；然后可以论证在满足DSIC的机制空间上对期望收益最大化 ，可以等同于在同一个空间对期望虚拟福利最大化 ，这样原本关心的收益最大化问题就转变为了分配最优化问题， $Rev = \max\sum_{i=1}^n \varphi_i(v_i) x_i$，与前文章节中 $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确实是最优保留价。以下是单物品拍卖的几个机制对比：

Rev最大化-多物品拍卖下GSP的改造

Myerson拍卖无法应对多物品拍卖位置，实际上，自1981年Myerson拍卖问世以来，至今没有找到多物品拍卖设定下的最优拍卖机制，多物品拍卖设定下的最优拍卖机制（满足 DSIC 的收益最大化拍卖）设计是一个开放性问题
在多物品拍卖场景，广告多坑位拍卖一般围绕改造 GSP 机制来近似实现最优结果，具体来说，是将Myerson机制和GSP机制结合起来

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

一些讨论

机制设计应该关注用户体验 ：相对免费资源位置，付费资源位置本质是在牺牲用户体验，换取社会福利和平台收入，机制设计时还需要考虑用户体验，否则如果用户失去对付费资源的关注度，则平台将彻底失去流量变现机会
未来方向：
- 广告主偏好：论文主要是以效用Utility最大化为目标，后续可考虑以价值Value最大化为目标的情况
- 结合自动出价（Auto-Bidding）：自动出价的场景越来越多，但相关的机制研究较少
- 基于学习的机制（数据驱动）
- 生成式拍卖

附录：社会福利和流动性福利的讨论

社会福利（Social Welfare） ：指的是整体广告主的价值和，单个广告主对单个广告位置的价值 = 广告主获得广告位的概率 * 广告位对广告主的价值
- $n$ 个竞拍者的社会福利可表示为
  $$SW = \sum_{i=1}^n v_i x_i$$
  - 其中 $x_i$ 是竞拍者 $i$ 获得物品的分配概率，$v_i$ 是竞拍者 $i$ 对该物品的估值
- 社会福利的另一个视角：广告主效用为0时（即商家说真话且按照一价计费时），社会福利等于买家从广告主手里获得的收入 ，所以社会福利也可以表达为在满足 IR 的情况下，社会福利等于买家可以从广告主手里获得的最大收入
  - 对最大的理解 ：这里最大是指刚好满足 IR，即商家效用为0时的值，是社会福利定义里面针对约束而言的“最大”，拍卖机制中常说的社会福利最大化的“最大”是分配效率
  - 机制拍卖的目标 ：这个视角同时暗示了，平台收入小于等于社会福利 ，平时我们拍卖机制设计中，最大化社会，一方面在提升资源分配率 ，另一方面也等价于是在提升平台收入空间（因为在IR约束下，平台收入不会超过社会福利）
流动性福利（Liquid welfare）【未找到精确定义，待补充】 ：流动性福利是指存在预算约束情况下的社会福利（目前看到的都是预算约束下的流动性社会福利定义），表示在不违反财务约束的情况下可以从竞拍者中提取的最大收入 ，Auto-bidding and Auctions in Online Advertising: A Survey, 202408, Google 中有相关的定义（Truthful Auctions for Automated Bidding in Online Advertising, IJCAI 2023, Alibaba 中有ROI约束+预算约束下的定义）
- $n$ 个竞拍者的流动性福利可表示为
  $$\text{LW}=\sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0}\min\left(\color{red}{\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}}},B_{i}\right)$$
  - 其中 $R_i,B_i,v_i(\mathbf{t}^{\prime})$ 分别表示广告主设置的ROI，预算和广告主的累计价值
  - 注意，其实 $\color{red}{\frac{v_{i }(\mathbf{t}^{\prime})}{R_{i}}}$ 就是ROI出价下的社会福利，为了方便理解，可以推导出价点在ROI上的商家的曝光 $j$ 上的私有价值等于 $CTR_{ij} \times CVR_{ij} \times Price_{ij} \times \frac{1}{ROI}$，而广告主 $i$ 的累计收益为 $\color{red}{v_i(\mathbf{t}^{\prime})} = \sum_j CTR_{ij} \times CVR_{ij} \times Price_{ij}$
流动性福利和社会福利的本质是一样的（可以理解为是同一个指标在不同场景下的不同定义），都是在满足一定约束条件下，买家可以从广告主手里获得的最大收入（这里的最大是针对约束而言的）
- 社会福利 ：只有 IR 约束 ，这个 IR 约束主要针对出价，出价就是商家的私有价值，可以是 ROI 约束 或 CPA 约束
- 流动性福利 ：除了 IR 约束，还有预算约束
- 在预算约束无限时（或不生效时） ，社会福利等价于流动性福利 ，此时有:
  $$SW = LW = \sum_{i\in[n],u_{i}(t_{i},\mathbf{t}^{\prime})\geq 0} \color{red}{\frac{v_i(\mathbf{t}^{\prime})}{R_i}}$$

CA——生成式拍卖-Contextual-Generative-Auction(CGA)

参考链接：
- 原始论文：Contextual Generative Auction with Permutation-level Externalities for Online Advertising, KDD 2025, Alibaba
- 博客：KDD’25 | 生成式拍卖：感知排列外部性的整页优化机制 - 阿里妈妈技术的文章 - 知乎

整体思路总结（摘要）

问题提出 ：传统的拍卖机制（如GSP）依赖于独立的点击率（CTR）假设，未能考虑其他同时被展示 item 的影响（即外部性）。近年来，基于学习的拍卖机制（learning-based auctions）在高维上下文特征编码方面取得了进展。然而，现有方法受限于“预测后分配”的设计范式，仅在候选广告集内建模Set-level外部性（the candidate ad set），未能考虑最终分配的序列上下文，导致次优结果
论文解法 ：论文提出了上下文生成拍卖（Contextual Generative Auction，CGA），这是一个在多槽广告拍卖中引入Permutation-level外部性的新框架。基于论文理论推导的最优解结构，CGA将分配和支付的优化解耦。论文构建了一个自回归生成模型用于分配，并将激励兼容性（IC）约束重新表述为最小化支持梯度计算的事后遗憾（ex-post regret），从而实现最优支付规则的端到端学习
有效性论证 ：大量的离线和在线实验表明，CGA在平台收入和CTR方面显著优于现有方法，同时有效逼近了具有近乎最大收入和最小遗憾的最优拍卖

前置讨论

最优广告拍卖 ：目标是在满足经济属性（如激励兼容性（IC）和个体理性（IR））的同时最大化平台收入。当然，线上部署时还要考虑在线部署的计算复杂性约束
传统的广告拍卖（不考虑外部性）：同时考虑广告主的出价和广告的点击率（CTR）。广义第二价格（GSP）拍卖由于其可解释性和易于实现的特点，长期以来一直是广告拍卖的基准，并进一步演变为诸如 uGSP 和 DeepGSP 等变体。尽管现有方法表现出显著的性能，但 GSP 采用的独立 CTR 假设（即用户的点击仅取决于广告本身）限制了模型的预测能力，因为它忽略了其他同时被展示的广告。实际上，呈现给用户的结果页面包含多个广告，用户在做出决策之前会比较价格和外观等因素；因此，其他同时被展示的广告会影响目标广告的 CTR
外部性 ：外部广告的影响被定义为在线广告中的外部性。关于用户行为的实证研究也表明，最优的广告拍卖设计必须考虑外部性
基于学习的拍卖方法（如深度神经拍卖（DNA）和加权 VCG（SW-VCG）），被提出以更好地捕捉外部性并提升平台收入。然而，这些方法受到“预测后分配”设计范式的限制，因为预测过程仍然对分配结果中的上下文信息一无所知。本质上，这些方法仅对候选广告集中的信息进行建模（Set-level外部性），未能纳入影响最终分配中每个广告 CTR 的序列上下文（Permutation-level外部性），从而导致次优的分配。推荐系统中的重排序研究同样考虑了展示列表中的广告相关性。然而，它们专注于提升整体用户反馈，忽略了广告主的策略行为，因此未能纳入 IC 和 IR 等经济约束，阻碍了它们在在线拍卖环境中最大化收入的适用性
为在线广告平台设计具有Permutation-level外部性的最优拍卖面临三个关键挑战：
- (i) 现有的“预测后分配”设计范式无法在预测广告价值时感知序列上下文
- (ii) 采用类似 VCG 的方法遍历所有排列可以实现最优分配，但其高计算复杂性使其无法适用于在线应用。挑战在于如何在排列空间的阶乘级别内高效探索最优序列
- (iii) IC 条件要求每个广告主的预期价值随其出价非递减。虽然大多数现有方法确保更高的出价能为广告主赢得相同或更高的广告位，但Permutation-level外部性可能导致更高的广告位产生更低的 CTR。如图1所示，来自淘宝平台的工业数据表明，广告的Permutation-level CTR 并不随其分配的广告位单调递增。因此，在Permutation-level外部性下设计具有 IC 约束的广告拍卖是一个 non-trivial 的问题
论文提出了上下文生成拍卖（CGA） ，旨在优化平台收入并保证经济属性(IC和IR)。CGA 的框架遵循论文从理论上推导出的最优 DSIC（占优策略激励兼容）拍卖的结构，将分配和支付的优化解耦。CGA 采用生成器-评估器（G-E）范式来捕捉Permutation-level外部性。具体来说，生成器利用自回归方法生成广告序列作为分配，由训练过的评估器指导，评估器在广告序列中细化上下文交互。此外，直接计算最优支付规则是不可行的，因为 CGA 的分配规则是通过生成模型实现的。受多物品拍卖设计中使用神经网络有效恢复解析解的启发，论文将 IC 约束 重新表述为 要求广告拍卖的预期事后遗憾为零 ，并通过最小化可微分的事后遗憾来学习最优支付规则
论文的主要贡献总结如下：
- 论文提出了具有Permutation-level外部性的多广告位拍卖问题，并从理论上推导出最优的 DSIC 拍卖，为生成拍卖设计提供了理论保证
- 为了建模Permutation-level外部性，论文打破了基于学习的拍卖中的“预测后分配”设计范式，引入了一个自回归生成模型，直接生成分配。基于最优机制的结构，提出的 CGA 利用 G-E 范式优化分配，并通过最小化可微分的事后遗憾来学习最优支付规则
- 在大规模工业数据和在线 A/B 测试中的实验表明，CGA 在平台收入和 CTR 方面优于现有方法，并有效逼近了具有近乎最大收入和可忽略遗憾的最优 DSIC 拍卖

问题定义及讨论

多槽拍卖与Permutation-level外部性

多槽拍卖。在线广告的广告拍卖可以抽象为一个典型的多槽拍卖设计问题。形式上，当用户请求到达时，有 $n$ 个广告主竞标 $k$ 个广告位，每个广告主 $i$ 根据其点击广告 $ad_{i}$ 的私人价值 $v_{i}$ 提交一个出价 $b_{i}$ 。广告主 $i$ 的私人价值是从分布 $f_{i}(\cdot)$ 中独立抽取的， $F_{i}(\cdot)$ 表示概率密度函数（pdf） $f_{i}(\cdot)$ 的累积分布函数（cdf）。令 $\boldsymbol{v}=(v_{1},v_{2},\cdots,v_{n})$ 表示所有广告主的价值分布， $\boldsymbol{v}_{-i}$ 表示排除元素 $a_{i}$ 的价值分布，类似地定义 $\boldsymbol{b}$ 和 $\boldsymbol{b}_{-i}$ 。拍卖者，即广告平台，知道分布 $f=(f_{1},f_{2},\cdots,f_{n})$ （从历史数据中推导），但不知道真实的价值分布 $\boldsymbol{v}$
给定出价分布 $\boldsymbol{b}$ 、用户特征向量 $\boldsymbol{u}$ 以及所有广告特征向量的集合 $\boldsymbol{X}=(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\cdots,\boldsymbol{x}_{n})$ ，广告拍卖机制被形式化为 $\mathcal{M}(\mathcal{A}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),\mathcal{P}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}))$ 。分配规则 $\mathcal{A}$ 决定广告位的分配，表示为分配矩阵 $\boldsymbol{A}=(a_{ij})_{n\times k}\in\{0,1\}^{n\times k}$ ，其中 $a_{ij}=1$ 表示广告 $i$ 被分配到广告位 $j$ ，否则 $a_{ij}=\mathbf{0}$ 。注意，一个广告最多分配到一个广告位，每个广告位必须分配一个广告，因此可行的分配矩阵 $\boldsymbol{A}$ 满足 $\sum_{j=1}^{k}a_{ij}\leq 1,\forall i$ 和 $\sum_{i=1}^{n}a_{ij}=1,\forall j$ ；支付规则 $\mathcal{P}$ 决定每个广告的支付，表示为支付向量 $\boldsymbol{p}=(p_{i})_{n}\in\mathbb{R}^{n}$
Permutation-level外部性。广告拍卖中的外部性意味着获胜广告的效用也受到其他获胜广告的影响[15]。对于多槽广告拍卖，外部性效应体现在广告的CTR中。具体来说，CTR模型可以抽象为从广告特征和用户特征映射到用户点击广告概率的函数。论文进一步考虑一个排列感知的CTR模型 $\Theta$ ，它以分配 $\boldsymbol{A}$ 和相关特征为输入，并捕捉 $\boldsymbol{A}$ 内的广告间影响。注意，模型 $\Theta$ 是排列感知的，这意味着即使两个分配包含相同的广告集，如 $\boldsymbol{A}_{1}=(ad_{1},ad_{2},ad_{3})$ 和 $\boldsymbol{A}_{2}=(ad_{3},ad_{2}.ad_{1})$ ，不同的排列会导致广告 $ad_{2}$ 的外部影响差异。形式上，论文将广告 $ad_{i}$ 的CTR表示为 $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$ 。为简化表示，令 $\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})=\Theta(\boldsymbol{x}_{i};\mathcal{A}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),\boldsymbol{X},\boldsymbol{u})$ 。Permutation-level外部性通过模型 $\Theta$ 从分配 $\boldsymbol{A}$ 到CTR的映射过程中编码
问题表述。给定机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ ，具有估值 $v_{i}$ 的广告主的预期效用为：
$$u_{i}(v_{i};\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})=(v_{i}-p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}))\cdot\Theta _{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}).$$
考虑到广告主可以通过虚报其价值来最大化其效用，论文引入广告拍卖的两个基本属性以确保广告平台的稳定性：主导策略激励兼容性（DSIC，或IC）和个体理性（IR）
定义1 ：一个拍卖是DSIC或IC的，如果每个广告主通过如实报告其价值来最大化其效用，无论其他广告主如何报告。形式上，
$$u_{i}(v_{i};v_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})\geq u_{i}(v_{i};\boldsymbol{b}_{i},\boldsymbol{b}_ {-i};\boldsymbol{X},\boldsymbol{u}),\forall i\in[n],\forall v_{i},\boldsymbol{b}_{i}\in\mathbb{R}^{+}.$$
定义2 ：一个拍卖是IR的，如果每个广告主的支付不超过其提交的出价。形式上，
$$p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})\leq b_{i},\forall i\in[n].$$
目标是找到一个拍卖机制 $\mathcal{M}$ ，最大化广告平台的预期收入：
$$\mathbb{E}_{\boldsymbol{v}\sim F}Rev^{\mathcal{M}}(\boldsymbol{b},\boldsymbol{X},\boldsymbol{u})=\sum_{i=1}^{n }p_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u}),$$
同时需要满足IC和IR约束，可以表述为问题（1） ：
$$
\begin{align}
\max_{\mathcal{M}(\mathcal{A},\mathcal{P})}\mathbb{E}_{\boldsymbol{v}\sim F} Rev^{ \mathcal{M}}(\boldsymbol{b},\boldsymbol{X},\boldsymbol{u}),\\
\text{s.t.} \ \text{ IC and IR constraints.}
\end{align}
$$

最优多槽拍卖

为了解决上述具有IC和IR约束的收入最大化拍卖设计问题，一种直观的方法是遵循著名的Myerson拍卖[26]。Myerson拍卖可以适应Permutation-level外部性的设置如下：
定义3 ：（具有Permutation-level外部性的Myerson拍卖）：
- 分配：
  $$\mathcal{A}\in\text{argmax}_{\boldsymbol{A}}\sum_{i=A_{i}}^{A_{k}}\hat{\phi}( \boldsymbol{b},F_{i})\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u});$$
- 支付：
  $$p_{i}=\begin{cases}b_{i}-\frac{\int_{0}^{b_{i}}\Theta_{i}(\boldsymbol{t}, \boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})d\mathbf{t}}{\Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})}&if \ \Theta_{i}(\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})>0;\\ 0,&\text{Otherwise},\end{cases}$$
- 其中 $\hat{\phi}(0,F_{i})$ 表示熨平虚拟价值函数（ironed virtual value function），它在 $v$ 中是单调的，注意这里用户的私有价值是点击价值，所以排序时要乘以CTR $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$
  - 熨平虚拟价值函数（ironed virtual value function）：当虚拟价值函数非单调时，通过“熨平”（ironed）处理使其单调（用常数替代非单调区间使其单调），熨平后的函数简化了优化问题，确保机制设计的可实施性
回顾Myerson引理，如下述定理1所述。注意，引入Permutation-level外部性与传统的Myerson拍卖不同，因为它根据分配结果影响每个广告的CTR。因此，广告 $ad_{i}$ 的出价增加并不一定会增加其CTR，因为分配结果中的广告间影响可能会违反定理1的单调分配要求。论文通过证明，即使存在Permutation-level外部性，如果分配规则最大化虚拟福利，Myerson引理中的单调分配条件仍然成立，如引理1所示。由于篇幅限制，论文将证明放在附录A.1中
定理1 ：（Myerson引理）。对于单参数环境，分配规则 $\mathcal{A}$ 是可实现的，如果存在支付规则 $\mathcal{P}$ 使得机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ 是DSIC的。以下两个命题成立：
- （1）分配规则是可实现的，当且仅当它是单调的
- （2）如果分配规则 $\mathcal{A}$ 是单调的，则存在唯一的支付规则 $\mathcal{P}$ 使得机制 $\mathcal{M}(\mathcal{A},\mathcal{P})$ 是DSIC的。它由下式给出：
  $$\mathcal{P}_{i}(\boldsymbol{b}_{i},\boldsymbol{b}_{-i})=b_{i}\mathcal{A}_{i}(b_{i},\boldsymbol{b}_{-i}) -\int_{0}^{b_{i}}\mathcal{A}_{i}(\boldsymbol{t},\boldsymbol{b}_{-i})d\mathbf{t}.$$
引理1 ：（具有Permutation-level外部性的单调分配）。对于每个广告 $ad_{i}$ 和 $\boldsymbol{b}_{-i}$ ，获得的CTR $\Theta(\boldsymbol{x}_{i};\mathcal{A}(b_{i},\boldsymbol{b}_{-i}),\boldsymbol{X},\boldsymbol{u})$ 在其出价 $b_{i}$ 中是非递减的（或者说 $\mathcal{A}$ 是单调的），如果分配规则 $\mathcal{A}$ 最大化预期虚拟福利
定理2 ：对于单参数环境，在DSIC拍卖空间中最大化预期收入等于最大化预期虚拟福利
基于定理1、定理2和引理1，我们可以推导出推论1，即定义3中具有Permutation-level外部性的Myerson拍卖构成了问题（1）的最优解
推论1 ：广告拍卖机制 $\mathcal{M}$ ，由定义3中的分配规则 $\mathcal{A}$ 和支付规则 $\mathcal{P}$ 表征，代表了具有Permutation-level外部性的最优机制，能够在满足IC和IR约束的同时最大化平台的预期收入

拍卖设计作为基于学习的问题

直接实现定义3中的分配规则 $\mathcal{A}$ 涉及枚举所有排列以选择最大化虚拟福利的排列，计算复杂度为 $P(n,k)=\frac{n!}{(n-k)!}$ （$n$ 个广告主竞标 $k$ 个广告位）。然而，对于在线广告，以淘宝为例，其中 $n\approx 50$ 和 $k\approx 5$ ，高计算复杂度无法满足在线实时推理需求。因此，论文将拍卖机制参数化为 $\mathcal{M}^{\text{w}}=\langle\mathcal{A}^{\text{w}_{a}},\mathcal{P}^{\text{w}_ {p}}\rangle$ ，参数为 $\text{w}_{a}$ 和 $\text{w}_{p}$ ，并通过解决学习问题来确定这些参数
为了在基于学习的拍卖中施加IC约束并确保优化过程的可微性，类似于基于学习的多物品拍卖的原始工作，论文引入了每个广告主的事后遗憾概念，以量化偏离IC条件的程度。具体来说，广告主 $ad_{i}$ 的事后遗憾定义为通过虚报 $b^{\prime}_{i}$ 可以获得的最大效用增加：
$$rgt_{i}(v_{i},\boldsymbol{X},\boldsymbol{u})=\max_{b^{\prime}_{i}}{u_{i}(v_{i};b^{ \prime}_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})-u_{i}(v_{i};\boldsymbol{b};\boldsymbol{X},\boldsymbol{u})}.$$
因此，当且仅当每个广告主 $ad_{i}$ 的事后遗憾为零时，IC约束得到满足。给定从分布F中抽取的 $L$ 个估值样本，论文得到广告主 $ad_{i}$ 的经验事后遗憾：
$$\widehat{rgt}_{i}=\frac{1}{L}\sum_{l=1}^{L}rgt_{i}(v^{\prime}_{i}, \boldsymbol{X},\boldsymbol{u}).$$
然后论文将拍卖设计问题（1）重新表述为问题（3） ，即最小化预期负收入，约束条件是每个广告主 $ad_{i}$ 的经验事后遗憾为零：
$$
\begin{align}
&\ \min_{\text{w}}-\mathbb{E}_{v\sim F}Rec^{\mathcal{M}^{\text{w}}}\\
&\text{s.t.} \ \widehat{rgt}_{i}=0, \forall i\in[n].
\end{align}
$$

CGA 架构说明

本节详细讨论上下文生成拍卖（CGA）。为了克服“预测后分配”范式在捕捉Permutation-level外部性方面的局限性，CGA采用了生成器-评估器（G-E）架构，如图2所示。生成器利用自回归模块，感知已建立的先前上下文以生成广告序列。评估器估计整个广告序列中的排列感知奖励，通过策略梯度引导生成器实现最优分配。对于在线推理，仅部署生成器，确保广告分配期间的计算延迟最小。此外，引入了一个专用的PaymentNet模块来学习最优支付规则，通过优化可微的事后遗憾进行训练

生成器：自回归生成模块

根据定理2和推论1，生成器的目标是从 $n$ 个候选广告中生成长度为 $k$ 的广告序列 $A$ ，以最大化预期虚拟福利。论文开发了一个自回归生成模块，包括两个关键组件：排列不变的集级编码器和排列等变的解码器。排列不变性[42]是一种架构属性，其中输出对输入的排列保持不变，DNA已证明其在提高广告拍卖平台收入方面的有效性。排列等变性[42]意味着任何输入的排列都会导致输出的相同排列。该属性在自动拍卖设计中被广泛采用[31, 18, 10]，Qin等[30]证明了其在提高基于学习的拍卖的泛化能力方面的有效性。(注：这里刻意保留论文引用序号方便查看原文)
排列不变的集级编码器。广告编码器旨在通过建模Set-level外部性来增强每个广告的表示。它编码候选广告集并提供上下文嵌入 $\boldsymbol{c}$ 作为解码器的初始输入。首先，论文采用自注意力层来捕捉 $n$ 个候选广告之间的相互影响，生成每个广告 $i$ 的集级增强嵌入 $\boldsymbol{h}_{i}$ ：
$$[\boldsymbol{h}_{1},\boldsymbol{h}_{2},\cdots,\boldsymbol{h}_{\boldsymbol{n}}]=self\cdot attention([\boldsymbol{e}_{1}, \boldsymbol{e}_{2},\cdots,\boldsymbol{e}_{\boldsymbol{n}}]),$$
其中 $\boldsymbol{e}_{i}$ 表示广告 $a_{i}$ 的嵌入。由于编码器处理的是无序的广告集，上述注意力层排除了位置编码，论文对 $\boldsymbol{h}_{i},i\in[n]$ 进行求和池化，确保改变输入广告的排列保持相同的输出上下文嵌入 $\boldsymbol{c}$ ：
$$\boldsymbol{c}=MLP([\sum_{i=1}^{n}\boldsymbol{h}_{i};\boldsymbol{h}_{\boldsymbol{u}}]),$$
其中 $\boldsymbol{h}_{\boldsymbol{u}}$ 表示用户表示
排列等变的自回归解码器。为了解决拍卖设计中“预测后分配”范式的局限性，论文引入了一个自回归解码器。该模型有效地捕捉输出广告序列的联合分布[4]以生成广告序列。给定上下文嵌入 $\boldsymbol{c}$ ，概率生成模型学习每个广告序列 $\boldsymbol{A}_{m}$ 的条件概率 $p(\boldsymbol{A}_{m}|\boldsymbol{c})$ 。在推理过程中，模型根据此条件概率从其输出空间中选择特定的分配。在多槽拍卖设置中， $\boldsymbol{A}_{m}$ 由 $k$ 个广告组成： $a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m_{k}}}$ ，且 $a_{A_{m_{l}}}$ 不是独立的，自回归解码器使用乘积规则对联合输出分布进行建模：
$$p(a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m_{k}}}|\boldsymbol{c})= p(a_{A_{m_{1}}}|\boldsymbol{c})p(a_{A_{m_{2}}}|\boldsymbol{c},a_{A_{m_{1}}})\cdots$$ $$p(a_{A_{m_{k}}}|\boldsymbol{c},a_{A_{m_{1}}},a_{A_{m_{2}}},\cdots,a_{A_{m _{k-1}}}).$$
论文进一步采用GRU单元来建模每个候选广告 $a_{i}$ 在槽 $t\in[k](a_{A_{m_{0}}}=\emptyset)$ 的条件概率 $p(a_{i}|\boldsymbol{c},a_{A_{m_{1}}},\cdots,a_{A_{m_{l-1}}})$ 。在解码开始时，上下文嵌入 $\boldsymbol{c}$ 初始化GRU的隐藏状态，并将表示“开始”的特殊标记作为初始输入馈入GRU。迭代地，第 $t$ 个GRU单元公式化为：
$$\boldsymbol{s}_{t}=GRU(\boldsymbol{s}_{t-1},\boldsymbol{h}_{\mathcal{A}_{1}-1}), t=1,2,\cdots,k,$$
其中 $\boldsymbol{h}_{\mathcal{A}_{1}-1}$ 表示在槽 $t-1$ 中选择的广告的编码表示（ $\boldsymbol{h}_{\mathcal{A}_{0}}=START$ ）， $\boldsymbol{s}_{t-1}$ 表示先前的上下文信息（ $\boldsymbol{s}_{0}=c$ ）。因此，给定槽 $t$ 的状态 $\boldsymbol{s}_{t}$ ，论文得到每个候选广告 $a_{i}$ 的分配概率 $z_{i}^{t}$ （公式（5））：
$$z_{i}^{t}=softmax([MLP([\boldsymbol{s}_{t};\boldsymbol{h}_{i}])+e^{w}\tilde{\phi}_{i}]_{t=1}^{n })_{i},$$
- 其中 $w$ 是一个可学习参数，使得 $e^{w}$ 保持正数，确保更高的虚拟价值导致更大的分配概率，与最大化虚拟福利的目标一致。在槽 $t$ 之前分配的广告被屏蔽，基于 $\boldsymbol{z}^{t}$ 的采样策略确定分配到槽 $t$ 的广告。此采样仅在训练期间进行，以探索多样化的序列生成策略。在推理过程中，选择 $\boldsymbol{z}^{t}$ 中值最高的广告。此选择过程重复 $k$ 次以生成长度为 $k$ 的广告序列，表示为 $\boldsymbol{A}=\left[\boldsymbol{a}_{A_{1}},\boldsymbol{a}_{A_{2}},\cdots,\boldsymbol{a}_{A_{k}}\right]$
此外，由于生成器中的MLP和GRU单元在每个状态-广告对上操作，并且编码器满足排列不变性，解码器表现出排列等变性

评估器：排列感知预测模块

评估器的目标是预测广告分配 $\boldsymbol{A}$ 中每个广告 $\boldsymbol{a}_{A_{i}}$ 的排列感知CTR $\Theta(\boldsymbol{x}_{i};\boldsymbol{A},\boldsymbol{X},\boldsymbol{u})$ 。评估器以分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}=\left[\boldsymbol{h}_{A_{1}},\boldsymbol{h}_{A_{2}},\cdots,\boldsymbol{h}_{A_{k}}\right]$ 、用户嵌入 $\boldsymbol{e}_{u}$ 和点级CTR $\boldsymbol{\alpha}_{\boldsymbol{A}}\in[0,1]^{k}$ 为输入，并输出排列感知CTR。每个广告 $\boldsymbol{a}_{A_{i}}$ 的嵌入 $\boldsymbol{h}_{A_{i}}$ 来自生成器的编码器，如公式（4）所定义。由于CGA在三阶段广告系统（匹配、预测和拍卖）的末尾运行，为了充分利用在前几个阶段捕捉到的用户兴趣，评估器利用从预测阶段输出的点级CTR $\boldsymbol{\alpha}_{\boldsymbol{A}}$ ，并构建一个Permutation-level广告编码器来估计个性化的外部性感知校准向量 $\boldsymbol{y}_{\boldsymbol{A}}\in(0,2)^{k}$ 。这两个向量随后逐元素相乘以获得排列感知CTR： $\Theta_{\boldsymbol{A}}=min(\boldsymbol{\alpha}_{\boldsymbol{A}}\odot\boldsymbol{y}_{\boldsymbol{A}},1)$
具体来说，论文采用Bi-LSTM层和多头自注意力层来编码广告序列嵌入 $\boldsymbol{H}_{\boldsymbol{A}}$ ，其中Bi-LSTM有效捕捉双向序列信息，而自注意力有效捕捉序列中远距离广告之间的交互。形式上，自注意力层的序列表示定义为：
$$\boldsymbol{H}_{\boldsymbol{A}}^{\boldsymbol{s}}=softmax\left(\frac{\mathcal{Q}_{\boldsymbol{A}}\boldsymbol{K}_{\boldsymbol{A }}^{\top}}{\sqrt{d}}\right)\boldsymbol{V}_{\boldsymbol{A}},$$
其中 $d$ 表示嵌入的维度， $\mathcal{Q}_{\boldsymbol{A}},\boldsymbol{K}_{\boldsymbol{A}},\boldsymbol{V}_{\boldsymbol{A}}$ 表示查询、键和值矩阵，它们从分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}$ 和位置编码 $\boldsymbol{P}\boldsymbol{E}_{\boldsymbol{A}}$ 的线性变换中得出。论文采用的位置编码机制遵循中的正弦版本，赋予自注意力层辨别排列信息的能力
接下来，论文通过Bi-LSTM层获得 $\boldsymbol{H}_{\boldsymbol{A}}$ 的前向输出状态 $\boldsymbol{H}_{\boldsymbol{A}}^{f}$ 和后向输出状态 $\boldsymbol{H}_{\boldsymbol{A}}^{b}$：
$$\boldsymbol{H}_{\boldsymbol{A}}^{f} =\text{Bi-LSTM}_{\text{forward}}(\boldsymbol{H}_{\boldsymbol{A}})$$ $$\boldsymbol{H}_{\boldsymbol{A}}^{b} =\text{Bi-LSTM}_{\text{backward}}(\boldsymbol{H}_{\boldsymbol{A}}).$$
为简洁起见，论文省略了Bi-LSTM的实现细节，包括输入门、遗忘门、输出门和单元状态

支付计算

根据推论1，最优支付在定义3中定义，其中积分项可以重写为期望：
$$\int_{0}^{b_{i}}\Theta_{i}(t,\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})dt=b_{i}E_{t_{i}-U[0,b_{i}] }[\Theta_{i}(t_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})],$$
可以使用蒙特卡罗采样进行近似。然而，注意 $\Theta_{i}(t_{i},\boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u})=\Theta(\boldsymbol{x}_{i};\mathcal{A}(t_{i}, \boldsymbol{b}_{-i};\boldsymbol{X},\boldsymbol{u}),\boldsymbol{X},\boldsymbol{u})$ 。处理每个样本需要调用生成器 $\mathcal{A}$ 和评估器 $\Theta$ ，导致推理期间的高计算成本。减少样本数量可以缓解这一问题，但会增加支付方差，直接影响平台收入和广告主效用
受[11]中神经网络在多物品拍卖设置中有效逼近最优机制的成功应用启发，论文引入PaymentNet来学习最优支付规则。具体来说，输入包括分配嵌入 $\boldsymbol{H}_{\boldsymbol{A}}\in\mathbb{R}^{K\times d}$ 、自排除出价分布 $\boldsymbol{B}^{-}=[\boldsymbol{b}_{-\boldsymbol{A}_{1}},\boldsymbol{b}_{-\boldsymbol{A}_{2}},\cdots,\boldsymbol{b}_{- \boldsymbol{A}_{k}}]\in\mathbb{R}^{K\times(k-1)}$ ，以及预期价值分布 $\boldsymbol{Z}\cdot\Theta\in\mathbb{R}^{L\times 1}$ ，其中 $\boldsymbol{Z}=[ z^{1}_{\boldsymbol{A}_{1}},z^{2}_{\boldsymbol{A}_{2}},\cdots,z^{k}_{\boldsymbol{A}_{k}} ]$ 表示公式（5）中定义的分配概率， $\boldsymbol{\Theta}=[\Theta_{\boldsymbol{A}_{1}},\Theta_{\boldsymbol{A}_{2}},\cdots,\Theta_{\boldsymbol {A}_{k}}]$ 表示评估器估计的排列感知CTR。此外，为了满足IR约束，如定义2所述，PaymentNet采用sigmoid激活函数计算支付率 $\tilde{\boldsymbol{p}}\in[0,1]^{k}$ ，随后输出支付 $\boldsymbol{p}=\tilde{\boldsymbol{p}}\odot\boldsymbol{b}$ 。形式上，支付率定义为：
$$\tilde{\boldsymbol{p}}=\sigma(r(r(\lfloor\boldsymbol{H}_{\boldsymbol{A}};\boldsymbol{B}^{-};\boldsymbol{Z}\cdot\Theta \rfloor))),$$
其中 $\sigma(\cdot)$ 和 $r(\cdot)$ 分别表示具有sigmoid和ReLU激活函数的全连接层

优化与训练

根据推论1，最优分配规则仅需要最大化虚拟福利，并且与支付规则无关。因此，论文将G-E框架和PaymentNet的优化解耦，这保持了CGA的最优性

G-E框架的优化

在G-E框架中，评估器负责捕捉Permutation-level外部性并引导生成器获得最优分配
首先进行评估器训练 ：使用 List-wise 广告点击数据训练评估器 $\Theta$ 至收敛。每个样本 $l\in\mathcal{D}$ 是暴露给用户的长度为 $k$ 的广告序列，标签 $y^{l}_{i}\in\{0,1\}$ 表示用户是否点击了第 $i$ 个广告。二元交叉熵损失定义为：
$$\mathcal{L}_{E}=-\frac{1}{|\mathcal{D}|}\sum_{l\in\mathcal{D}}\sum_{i=1}^{k}(y ^{l}_{i}\log\theta^{l}_{i}+(1-y^{l}_{i})\log(1-\theta^{l}_{i})),$$
- 其中 $\theta^{l}_{i}$ 表示评估器预测的广告序列 $l$ 中第 $i$ 个广告的排列感知CTR
在训练评估器 $\Theta$ 至收敛后，论文冻结其参数并使用来自评估器的奖励通过策略梯度训练生成器。在每个槽 $t$ ，上下文信息 $\boldsymbol{s}_{t}$ 作为状态，生成器输出的分配概率 $z^{t}_{i}$ 作为动作。由于 $\boldsymbol{s}_{t}$ 仅编码先前的上下文，为了捕捉双向上下文信息，论文使用训练有素的评估器来估计完整广告序列 $\boldsymbol{A}$ 中每个候选广告的排列感知奖励。类似于，论文将此排列感知奖励分解为两部分
自身奖励（Self-Reward）：与最优分配的目标一致，论文使用评估器 $\Theta$ 来估计每个选定广告 $a_{A_{i}}$ 的预期虚拟福利，称为自我奖励：
$$r^{self}_{A_{i}}=\hat{\phi_{i}}\cdot\Theta_{i}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u}).$$
外部奖励（External-Reward）：每个选定的广告不仅贡献其奖励，还由于Permutation-level外部性影响其他广告的CTR。类似于经典VCG机制中应用的边际贡献，论文将此外部效应建模为外部奖励：
$$r^{external}_{A_{i}}=\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}; \boldsymbol{A},\boldsymbol{u})-\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i}; \boldsymbol{A}_{-i},\boldsymbol{u}),$$
- 其中 $\boldsymbol{A}_{-i}$ 表示排除 $a_{A_{i}}$ 的广告序列
结合上述两个奖励，论文得到选择 $a_{A_{i}}$ 的排列感知奖励，定义为：
$$
\begin{align}
r_{A_{i}} &=r^{self}_{A_{i}}+r^{external}_{A_{i}} \\
&=\hat{\phi_{i}}\Theta_{i}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u})+\sum_{j\in\boldsymbol{A}_ {-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u})-\sum_{j\in\boldsymbol{A}_{-i}} \tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i};\boldsymbol{A}_{-i},\boldsymbol{u})\\
&=\sum_{j\in\boldsymbol{A}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b};\boldsymbol{A},\boldsymbol{u })-\sum_{j\in\boldsymbol{A}_{-i}}\tilde{\phi_{j}}\Theta_{j}(\boldsymbol{b}_{-i};\boldsymbol{A}_{-i}, \boldsymbol{u}).
\end{align}
$$
最后，生成器的损失函数定义为：
$$\mathcal{L}_{G}=-\frac{1}{|\mathcal{D}|}\sum_{s\in\mathcal{D}}\sum_{i\in k}r_{ A^{s}_{i}}\log z_{A^{s}_{i}},$$
- 其中 $s$ 表示数据集 $\mathcal{D}$ 中的一个样本，代表请求的候选广告集， $A^{s}_{i}$ 表示生成器基于输入广告集 $s$ 输出的广告分配中的第 $i$ 个广告， $z_{A^{s}_{i}}$ 表示Generator 公式（5）中的分配概率

PaymentNet的优化

在训练生成器 $\mathcal{A}$ 和评估器 $\Theta$ 至收敛后，论文冻结其参数，然后应用增广拉格朗日方法来解决约束优化问题（3）以优化PaymentNet。增广拉格朗日函数定义为：
$$\mathcal{L}_{P}=-\frac{1}{|\mathcal{D}|}\sum_{s\in\mathcal{D}}(\sum_{i\in k} \mathcal{P}_{i}(\boldsymbol{A}^{s})\Theta_{i}(\boldsymbol{A}^{s})-\sum_{i\in k}\lambda_{i} \widehat{rgt}^{s}_{i}-\frac{\rho}{2}\sum_{i\in k}(\widehat{rgt}^{s}_{i})^{2}),$$
- 其中 $\boldsymbol{A}^{s}$ 表示冻结生成器 $\mathcal{A}$ 基于广告集 $s$ 的输入输出的分配， $\lambda_{i}$ 表示拉格朗日乘数， $\rho>0$ 表示IC惩罚项的超参数
类似于[11]，基于上述拉格朗日函数（10）的优化过程包括
- （i）更新PaymentNet： $\boldsymbol{w}_{\boldsymbol{p}}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}}=\textit{argmin}_{\lambda\boldsymbol{w}\rho} \mathcal{L}_{P}(\boldsymbol{w}_{\boldsymbol{p}}^{\sigma Id};\boldsymbol{\lambda}^{\sigma Id})$
- （ii）更新拉格朗日乘数： $\boldsymbol{\lambda}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}}=\boldsymbol{\lambda}^{\sigma Id}+\rho\ \overline{r} \boldsymbol{g}^{\intercal}(\boldsymbol{w}_{\boldsymbol{p}}^{\boldsymbol{n}\boldsymbol{e}\boldsymbol{w}})$
注意问题（3）是非凸的。因此，上述拉格朗日方法不能保证收敛到全局最优。然而，实验结果表明，优化后的CGA可以逼近最优收入，且遗憾最小，如原始论文第5.2节实验所述

Experiments

在本节中，论文进行了离线实验和在线A/B测试，以评估CGA的有效性，主要关注以下问题：
- RQ1 ：与现有广告拍卖相比，CGA在平台收入和CTR等关键指标上的表现如何？
- RQ2 ：与集级和无外部性相比，建模Permutation-level外部性的效果如何？
- RQ3 ：CGA的各种设计如何影响其性能？
- RQ4 ：论文提出的CGA在高效部署的实际广告拍卖场景中表现如何？

Experiment Setup

数据集

在离线实验中，论文使用从2024年1月期间从领先的电子商务平台淘宝收集的真实日志来评估CGA的性能。训练集包括从1月20日至1月23日随机选择的500,000次拍卖，涉及1,100,875个唯一广告主，而测试集包括从1月25日随机选择的100,000次拍卖，涉及452,671个唯一广告主。对于数据集中的每个拍卖样本，广告系统选择大约30个广告主作为拍卖阶段的候选者，他们提交出价以竞争广告位。论文在离线实验中设置广告位数量 $k=3$

基线方法

论文将CGA与代表性的拍卖机制进行比较。基线方法根据外部性建模的粒度分为三组
无外部性（W/O externalities） ：
- GSP ：GSP根据出价和预测CTR的乘积对广告进行排名，不建模外部性
Set-level外部性（Set-level externalities） ：
- DNA ：在GSP的基础上，DNA通过建模候选广告的Set-level外部性来预测每个广告的排名分数，并相应地进行分配，不考虑广告列表中广告之间的相互影响
- SW-VCG ：SW-VCG将多槽拍卖设计形式化为广告和广告位之间的最大加权二分匹配问题，仅捕捉候选广告的Set-level外部性以估计边权重
Permutation-level外部性（Permutation-level externalities） ：
- 具有Permutation-level外部性的VCG拍卖（VCG）：VCG选择最大化社会福利的广告排列进行分配，并结合支付规则以满足IC。论文使用CGA的评估器评估所有候选广告的排列，使VCG能够捕捉Permutation-level外部性
- EdgeNet ：EdgeNet利用Transformer替换DNA的集编码器，并采用贪婪策略依次分配广告，建模部分Permutation-level外部性
- Optimal ：为了评估CGA对理论上界的逼近，根据推论1，论文通过遍历所有排列以最大化虚拟福利并使用蒙特卡罗采样计算支付来构建此基线

性能指标

论文考虑以下指标来分别衡量平台收入、用户体验和广告主的事后遗憾
- 每千次展示收入： $\text{RPM}=\frac{\sum click\textit{$\times$payment}}{\sum impression}\times 1000$
- 点击率： $\text{CTR}=\frac{\sum click}{\sum impression}$
- IC指标： $\Psi=\frac{1}{|D|}\sum_{s\in D}\sum_{i\in k}\frac{\overrightarrow{rg^{i}_{i}}}{ u_{i}(v^{i}_{h},\boldsymbol{b}^{s};\boldsymbol{X}^{i},\boldsymbol{u}^{s})}$ ，其中 $\overrightarrow{rg^{i}_{i}}$ 在公式（2）中定义。这是广告拍卖机制IC测试的常用指标[7, 23, 25, 33]，衡量广告主通过操纵出价可以获得的效用相对增加。与[38]中的评估过程一致，论文对每个广告主的出价进行反事实扰动，将 $b_{i}$ 替换为 $a\times b_{i}$ ，其中 $a\in{0.2\times j\mid j=1,2,\cdots,10}$

实现

在CGA中，论文将特征的嵌入大小设置为8。为了从不同的表示子空间中捕捉更丰富的信息，所有注意力层都使用具有4个注意力头的多头注意力机制。外部性感知校准向量 $\boldsymbol{\gamma_{A}}$ 和支付率 $\hat{\boldsymbol{p}}$ 使用具有128和32大小隐藏层的MLP得出。CGA使用Adam优化器以1e-3的学习率和512的批量大小进行训练。所有基于学习的基线方法通过网格搜索调整超参数，探索学习率{1e-5, 1e-4, 1e-3, 1e-2}、批量大小{256, 512, 1024, 2048}和隐藏大小{8,16,32,64}

离线比较（RQ1 & RQ2）

CGA和基线-Optimal涉及铁虚拟价值函数，这需要了解每个广告主的价值分布 $f_{i}(\cdot)$ 。从历史数据中估计 $f_{i}(\cdot)$ 在现有研究中已有充分覆盖[6, 21, 27, 28]。论文不深入探讨此估计，因为CGA专注于使用生成模型捕捉Permutation-level外部性，与分布估计技术无关。为了避免分布估计方法在比较实验中的偏差，遵循[22]，论文预设每个广告主的价值的条件分布为均匀分布和指数分布 ，并相应地重新生成出价。对于SW-VCG，由于其预测的广告分数 $Scr_{i}$ 旨在拟合虚拟价值，论文直接将 $Scr_{i}$ 设置为 $\hat{\phi}_{i}$ 进行比较
在上述两种分布下的实验结果如表I所示。论文的主要观察结果如下：
- (1) 随着外部性建模从无外部性到集级再到Permutation-level，拍卖性能在三个指标上都有所提高（更高的RPM和CTR，更低的遗憾）5。这突显了在拍卖设计中建模细粒度外部性的重要性（RQ2）。为了进一步研究外部性的影响，论文在CTR预测任务上进行了比较实验。结果如表2所示，其中“无外部性”表示使用点级pCTR，“集级”表示使用集级广告编码器（如第3.2节所述）替换评估器的Permutation-level广告编码器。结果表明，具有Permutation-level外部性的评估器提高了预测值的准确性，解释了拍卖指标的改进
- (2) 与基于枚举的基线-Optimal相比，CGA实现了约95%的收入最大化，且事后遗憾可忽略不计。这表明CGA能够高效地进行广告分配，并紧密逼近最优拍卖机制

消融研究（RQ3）

为了验证CGA各种设计考虑的有效性，论文构建了以下变体：
- CGA- $\Theta$ 移除了评估器 $\Theta$ ，并使用点级CTR来评估每个广告分配的虚拟福利
- CGA（端到端）直接使用公式（10）中的 $\mathcal{L}_{P}$ 训练生成器和PaymentNet。相比之下，CGA首先训练生成器至收敛，冻结其参数，然后训练PaymentNet
- CGA- $r^{self}$ 移除了生成器损失函数 $\mathcal{L}_{G}$ 中的自我奖励 $r^{self}$ （公式（7））
- CGA- $r^{external}$ 移除了生成器损失函数 $\mathcal{L}_{G}$ 中的外部奖励 $r^{external}$ （公式（8））
- CGA- $\tilde{\phi}$ 将虚拟价值 $\hat{\phi_{i}}$ 替换为 $b_{i}$ 在 $\mathcal{L}_{G}$ 中
结果如表3所示，论文观察到：
- (1) CGA- $\Theta$ 表现不如CGA，表明生成器本身无法完全捕捉Permutation-level外部性，因为自回归模型仅感知先前的上下文。G-E框架通过策略梯度将完整的序列知识提炼到生成器中
- (2) CGA（端到端）表现较差。一个可能的原因是CGA使用PaymentNet来学习最优支付，因此在端到端训练时，收入梯度必须通过PaymentNet才能到达生成器，这使得收敛到最优分配变得复杂。此外，推论1确保解耦优化保持最优性，因此生成器可以专注于最大化虚拟福利
- (3) CGA- $r^{self}$ 表现最差，因为缺少每个选定广告的自身价值增量。CGA优于CGA- $r^{external}$ ，因为它使用外部奖励来建模每个选定广告对最终分配列表的影响
- (4) 估计价值分布 $\hat{f}(\cdot)$ 需要对出价策略进行经验假设，因为广告平台只能观察到出价，导致估计的 $\hat{f}(\cdot)$ 存在偏差。为了评估移除价值分布对CGA性能的影响，论文构建了变体CGA- $\tilde{\phi}$ 。如表3所示，CGA- $\tilde{\phi}$ 在收入（2.6%）和CTR（1.9%）方面仅略有下降。这一小幅下降可能是由于CGA对外部性的建模，捕捉了广告间的相关性，并通过其他广告主的出价部分反映了缺失的价值分布信息

在线A/B测试（RQ4）

为了验证CGA在现实世界中的有效性，论文通过在线A/B测试将CGA与完全部署在淘宝广告系统中的DNA进行比较。表4展示了2023年8月19日至8月25日期间使用2%总生产流量进行的在线A/B测试结果。CGA在RPM上实现了3.2%的提升，同时在线响应时间（RT）每请求平均增加了3毫秒（相对增加1.6%），表明CGA能够通过生成模型高效探索分配空间并提升平台收入。此外，广告主的投资回报率（ROI）提高表明，CGA的收入提升并非来自虚高的支付，而是通过捕捉Permutation-level外部性优化广告分配，这一点从CTR和总商品交易额（GMV）的显著提升中得到了证明

结论

一句话总结 ：论文提出了上下文生成拍卖（CGA），旨在将Permutation-level外部性引入在线多槽广告拍卖中
方案细节 ：论文的主要理论结果表明，经典的Myerson拍卖在适应Permutation-level外部性时保持了它的最优性。这一见解推动了CGA框架的设计，该框架将分配和支付的优化解耦。具体来说，论文开发了一个具有G-E学习范式的自回归生成模型来优化分配，并通过将IC约束量化为预期事后遗憾来学习最优支付
有效性论证 ：大量的离线和在线实验验证了CGA的有效性
特别说明 ：CGA的自回归生成过程不限于特定的生成模型，可以适应各种先进的解决方案
未来展望 ：未来的研究将扩展这种上下文生成机制，以整合来自不同渠道的异构 item 。

CA——Google-Ad-Click-Prediction

参考文献：Google KDD 2013，Ad Click Prediction: a View from the Trenches(引用量500+)
介绍了截止到2013年之前的点击率预估常用算法，FTRL是Google三年的结晶（2010-2013）
在线学习优化算法的发展历程：SGD->TG->FOBOS->RDA->FTRL-Proximal

核心贡献

基于传统的逻辑回归算法(Regularized Logistic Regression，正则化的逻辑回归)在点击率预估时的不足，提出一种在线逻辑回归算法，FTRL(Follow The Regularized Leader)
per-coordinate learning rate

一些模型的比较和介绍

传统逻辑回归算法中使用OGD(Online Gradient Descent)是非常高效的，使用很小的计算资源就能得到较好的精确度.
但是OGD在生成稀疏模型方面表现不好(OGD + L1)
其他在稀疏性方面表现良好的方法有FOBOS, 截断梯度（Truncated Gradient）和 RDA（Regularized Dual Averaging）
- RDA在精确度和稀疏性方面做tradeoff，效果好于FOBOS
FTRL-Proximal号称可以同时获得RDA的稀疏性和OGD的精确度
RDA模型是微软提出的一种在线优化算法，与OGD完全不同，能得到更加稀疏的模型，但是精确度不如OGD

FTRL-Proximal Learning (Online Learning And Sparsity)

也是通过L1正则化控制模型的稀疏度

推导过程

FTL(Follow The Leader)的介绍

OGD的更新方式

更新规则：
$$
\begin{align}
\mathbf{w}_{t+1} &= \mathbf{w}_t-\eta_t\mathbf{g}_t
\end{align}
$$

FTLR(Follow The Regularized Leader)

加上正则项的FTL

更新规则：
$$
\begin{align}
\mathbf{w}_{t+1} &= \mathop{\arg\min}_{\mathbf{w}}\left ( \mathbf{g}_{1:t}\cdot \mathbf{w} + \frac{1}{2}\sum_{s=1}^t \sigma_s || \mathbf{w} - \mathbf{w}_s||_2^2 + \lambda_1||\mathbf{w}||_1 \right ) \\
\mathbf{g}_{1:t} &= \sum_{i=1}^t\mathbf{g}_i
\end{align}
$$
- 第一项是对损失函数梯度的贡献的一个估计
- 第二项是控制参数 $\mathbf{w}$ 在每次迭代中变化不要太大
- 第三项是L1正则化，用于使模型变得稀疏（除了L1正则化项以外，也可以再加上L2正则化）
- 去掉正则化项就是FTL（Follow The Leader）
- $\sigma_s$ 是学习速率
- 这个学习速率可以用Per-Coordinate Learning Rate:
  $$
  \begin{align}
  \eta_{t, i} &= \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^t g_{s,i}^2}} \\
  \mathbf{g}_s &= \nabla l_s(\mathbf{w})
  \end{align}
  $$

Per-Coordinate Learning Rates

对参数的每一维度分开训练，每个维度有自己的学习率
某个特征出现的次数越多，说明当前该特征对应的参数值越可信，学习率就应该越小
考虑了数据在每个特征上的分布不均匀性
- 参数某个维度上的样本数越少，这些样本就会得到越大的利用(具体表现就是该特征的学习率会比较大)

一个思考

问题：为什么机器学习中的学习率都是越来越小？
答案：因为刚开始训练时，参数的值不太可信（也就是说最终参数与当前参数的置信度比较低），所以更新时应该更新的步骤大一些，让当前的参数变化大一些，训练到后来，随着参数的值越来越可信（当前参数的置信度比较高），更新的步骤就应该小一些，让当前的变化小一些

一些工程上的Trick

Saving Memory at Massive Scale

Probabilistic Feature Inclusion

在高维数据中，大量的特征是出现频率非常低的(rare)，半数的唯一特征甚至只出现一次
统计这些特征的代价是非常昂贵的，有些特征可能永远不会被实际使用(这里如何理解昂贵？也就是说训练了也没用？)
额外的读写数据是昂贵的，如果能丢弃一部分出现评论特别低的特征(比如出现频率低于k次)
实现稀疏可以使用L1正则化，也可以使用Probabilistic Feature Inclusion
关于Probabilistic Feature Inclusion的做法
- 当一个特征第一次出现时，以一定的概率接受这个新特征
- 效果作用于数据预处理阶段，但是可以在在线执行中设置

Possion Inclusion

对于新的特征，以概率p添加入模型
对于已经存在模型中的特征，正常更新其系数

Bloom Filter Inclusion

用布隆过滤器仅仅保留出现次数在n次以上的特征

Encoding Values with Fewer Bits

常用的OGD使用32或者64位浮点数编码来存储模型的系数
Google提出可以使用16位浮点数来存储系数，同时加上一些策略
实验结果：将64位的浮点值换为为系数存储节省了75%的RAM内存空间(这还用实验？直接计算就得到了啊)

Training Many Similar Models

同时训练多个模型是超参数选择常用的方法
将可以共享的东西共享
在节省内存的同时，还可以节约网络带宽(存储一份Per-coordinate学习率，节省内存和带宽等)，CPU(用同一个hash表检索特征，节省CPU)和硬盘空间

A Single Value Structure

有时候我们希望评估大量的模型在只有少量的特征组(groups of features)添加或者删除时的变化
对于每一维度(coordinate),仅仅存储一个系数值而不是多个(正常应该为每个模型存储一个)
存储该维度对应特征组的模型共享该系数
对每个特征，训练时每个模型都会计算自己的值，然后所有模型的取平均作为所有包含该维度特征模型的共享

Computing Learning Rates with Counts

对于每个特征来说，梯度和以及梯度平方和是必须计算的
梯度的计算必须准确，但是计算学习率却是可以粗糙计算的
仅仅统计样本出现次数(Counts)就能大概计算学习率

推导

假设包含一个给定特征的所有事件(events)具有有相同的概率(一般来说，这个近似是不可能的，但是在这个目标里面是可行的)
- 如何理解这个假设的意义呢？*对于具有某个特征的所有样本，其取值为(正负例)是的概率是相等的，正例(click)概率都为 $p$ *
进一步假设模型已经精确地学习到了概率
如果有分别有 $P，N$ 个正负样本(events),则有 $p=\frac{P}{N+P}$
则有对于逻辑回归($p(1-p)$)来说，正例的梯度为 $p-1$，负例的梯度为 $p$
$$
\begin{align}
\sum g_{t,i}^2 &= \sum_\text{positive events}(1-p_t)^2 + \sum_\text{negative events}p_t^2 \\
&\approx P(1-\frac{P}{N+P})^2 + N(\frac{P}{N+P})^2 \\
&= \frac{PN}{N+P}
\end{align}
$$
也就是说，为了近似计算 $\sum g_{t,i}^2$，我们仅需要记录 $P，N$ 即可

Subsampling Traning Data

典型的CTRs是远远低于50%，数据偏差很大，正例(点击)的样本很稀疏
在模型训练中正例样本相对而言更有价值
使用下采样：很大程度上降低数据量，同时保证对精度最小程度的影响

采样方法：

保留所有至少被点击过一次的请求(Query，也就是样本)
以一定比例 $r\in(0, 1]$ 采样没有被点击过的请求
因为包含通用的特征(Feature Phase)计算，所以这种方法是合理的，但是需要纠偏(直接用采样后的样本训练会造成预测偏差)
加入一个重要性权重 $w_t$
- $w_t = 1$ for clicked queries
- $w_t = \frac{1}{r}$ for queries with no clicks
- 本质上可以理解为这里是将采样时造成的负例比例偏差补齐

模型性能评估

Progressive Validation

Progressive验证又称为在线损失(online loss)
与交叉验证(cross-validation)或留出法(hold out)验证是不同的
在服务查询中，在线损失能很好的代表我们的精度，因为在训练模型前，它仅仅在最新数据上评估其性能(因为这准确的模拟了当模型进行服务查询时发生了什么)
由于用了100%的数据作为训练和测试，在线损失比留出法验证有更好的统计数据
绝对指标往往会带来误导
- 即使预测是完美的，对数损失和其他指标的差异也依赖着问题的困难程度
- 不同的国家，不同请求的点击率不同(同为对数损失的最佳实践，50%的点击率会好于2%的点击率)
所以使用相对变化，看指标相对于base line改变了多少
从经验来看，相对指标在整个时间段内都很稳定
相同的指标计算应该对应在完全相同的数据(比如不同时段的损失比较是没有意义的)

置信度评估(Confidence Estimates)

对很多应用来说，除了评估广告的CTR，还要量化预测的期望精确度(the expected accuracy of the prediction)

校正预测(Calibrating Predictions)

系统偏差(Systematic Bias)指平均预测CTR(Average Predicted CTR)和观测CTR(Observed CTR)的差异
造成系统偏差的原因包括：
- 不精确的模型假设
- 学习算法的缺陷
- 在训练或者服务(预测)时不可用的隐藏特征
解决方案：
- 添加一个校正层将预测CTRs与观测CTR做匹配(match predicted CTRSs to observed click-through rates)
- 暂时不能提供有效的保证，保证校正影响的有效
- 校正的本质是找到(拟合)一个函数映射 $g$，使得模型输出值与真实概率值一一对应
- 逻辑回归中的sigmoid函数可以看做是一个校正预测的函数吗？
更多参考
- 风险模型 - 概率校准
- 机器学习：概率校准, 文中有代码示例
- 概率校准 Probability Calibration

一些说明

参考博客：https://blog.csdn.net/fzcoolbaby/article/details/99174601?utm_source=distribute.pc_relevant.none-task

概率模型的搭建过程中，由于抽样与正则化等原因，导致模型的输出概率值明显偏离真实概率值
- [待更新：为什么抽样和正则化会影响模型的输出概率发生变化？]
此时的模型输出概率值仅仅有排序的意义，其绝对值没有意义(定序值，而非定距数值)
校正预测的过程就是把模型输出概率值的校正成真实的概率的过程，使得校正后的概率有绝对值意义

自动特征管理(Automated Feature Management)

将特征空间描绘成上下文和语义信号，每个信号都可以被翻译成一个在学习时有真实值的特征集合
[待更新]

一些不成功的实验记录(Unsuccessful Experiments)

本节记录google的一些失败的尝试方向(有些可能会让人很惊讶)，这些方向模型没有明显收益

Aggressive Feature Hashing

关于特征哈希(Feature Hashing)的相关知识可参考Feature-Hashing

Feature Hashing for Large Scale Multitask Learning论文指出，Feature Hashing方法效果显著
- 报告显示使用特征hashing技巧，可以能将学习一个垃圾邮件过滤模型的特征空间映射成包含 $2^24$ 个特征的特征空间(疑问：这里的特征原来不止 $2^24$ 个吗？)
但是实验证明，使用 Feature Hashing 方法并不能提升我们的方法，所以建议保留 interpretable(non-hashed)的特征向量

Dropout

Google用网格搜索的方法测试了从0.1到0.5的Dropout特征丢弃概率
所有情况均没有带来任何收益(包括精度指标和泛化能力)，还往往给模型带来损害(detriment)
Google给出的一个解释是：Dropout在图像领域取得较好收益的原因是因为图像领域的数据特征分布与计算广告领域不同
- 图像领域：稠密特征，此时Dropout把结果(effect)从强相关的特征中分离开来，从而得到泛化效果更好的分类器
- 计算广告：稀疏特征，且有噪音

Feature Bagging

对特征进行overlapping采样(注意，样本Bagging和特征Bagging不同)，然后训练多个独立的模型，最后取平均值
实验证明模型的的AucLoss降低了0.1%-0.6%

Feature Vector Normalization

$\mathbf{x} = \frac{\mathbf{x}}{||\mathbf{x}||}$
开始有一点精度上的收益，但是后面也出现了一定程度的detriment
Google的解释是可能是由于per-coordinate learning rates和正则化的影响

Hexo——Next主题搜索窗口无法弹出

参考博客： https://www.sqlsec.com/2017/12/hexosearch.html

问题描述

有时候会遇到在Mac上Next主题窗口无法弹出的问题
问题分为两类
- 一类为找不到 search.xml 文件：加载 search.xml 时错误为404
- 另一类为文章中有特殊字符：加载 search.xml 检查时错误为304

解决方案

404类

修改最外层配置文件./_config.yml,添加以下语句(实测这一步非必须)
1
2
3
4
5
search:
path: search.xml
field: post
format: html
limit: 10000

安装搜索插件

1	npm install hexo-generator-searchdb --save

304类

304状态说明是加载文件存在，但是无法正常解析文件
直接用浏览器访问 search.xml 文件链接，然后查看文件解析异常出现在哪个地方，然后删除特殊字符即可
- 个人理解，从哪个文件不能搜索，特殊字符就出现在哪个文件中
- 说明：目前还没遇到过这种情况，后面遇到会再补充

Joe Zhou

Stay Hungry. Stay Foolish.

GitHub E-Mail

本文的 oCPX 场景设定

单次拍卖下oCPX的效率讨论

多轮拍卖下oCPX的效率讨论

PID的作用

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

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

整体思路介绍

一些讨论

竞价策略

RTB生态系统

问题建模

最优竞价策略

系统设计

适用性问题

基于反馈控制的解决方案

超参数分析

多变量控制

实证研究

Experiment Setup

数据集

指标

实现细节

控制能力

性能评估

基线策略

评估结果

附录：相关工作（原文直译）

整体总结

其他已有机制盘点

关键挑战提出

方案概述

相关工作（论文直译）

问题建模

多槽位拍卖场景

问题公式化建模

NMA拍卖方案

上下文感知列表预测模块

列表深度排序模块

列表可微分排序模块

社会福利最大化辅助损失

Experiments

Experiment Setup

数据集

评估指标

超参数

基线

离线实验

性能比较（RQ1）

消融研究（RQ2）

超参数分析（RQ3）

在线结果

结论

百度赔付规则

字节赔付规则

快手赔付规则

趣头条赔付规则

拼多多

整体总结

一些特殊场景的oCPX赔付规则思考

Myerson拍卖

VCG

普通的VCG

WVCG

VVCA

SW-VCG

GSP

普通的GSP

uGSP

wGSP

mGSP

aGSP

rGSP

iGSP

sGSP

Deep GSP

Deep Neural Auction (DNA)

NMA

(RegretNet)Optimal Auctions through Deep Learning

(AMA)Affine maximizer auction

附录：一些特殊拍卖