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 。

整体思路总结（摘要）

前置讨论

问题定义及讨论

多槽拍卖与Permutation-level外部性

最优多槽拍卖

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

CGA 架构说明

生成器：自回归生成模块

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

支付计算

优化与训练

G-E框架的优化

PaymentNet的优化

Experiments

Experiment Setup

数据集

基线方法

性能指标

实现

离线比较（RQ1 & RQ2）

消融研究（RQ3）

在线A/B测试（RQ4）

相关工作（论文直译）

结论