KDD’25 | 生成式拍卖：感知排列外部性的整页优化机制

量子位的朋友们
2024-12-28
21:48:18

来源：量子位

从“先预估后分配”的判别式方法，到直接面向最终拍卖结果的生成式方法，生成式模型能否为在线广告的拍卖机制优化带来持续增量？

本文介绍阿里妈妈展示广告机制策略团队在 AIGA（AI-Generated Auction）方向的前沿探索-生成式拍卖研究工作。

基于该项工作整理的论文已被KDD’25 Research Track接收。

摘要

广告拍卖机制设计作为在线广告系统的重要一环，在持续优化广告主和平台收益方面起着至关重要的作用。传统的广义二价拍卖（GSP）等拍卖机制依赖于点击率分离假设（将广告点击率拆分为广告自身质量分和广告位曝光权重的乘积），忽略了页面中同时展示的其它商品的影响，即外部性影响。

近年来，基于深度学习的拍卖机制显著增强了对高维上下文特征的编码能力，但是现有方法仍受限于“先预估后分配”的设计范式。这种范式只能建模参竞广告集合内的外部性，无法捕捉最终分配结果的整页上下文信息（即排列外部性），因此难以收敛到全局最优解。本文系统分析了在排列外部性影响下的最优拍卖机制，在理论最优解的基础上，研究团队提出了首个使用生成式模型建模排列外部性的广告拍卖机制-生成式拍卖（Contextual Generative Auction, CGA）。

该框架通过自回归模型生成广告分配结果，并将激励兼容（Incentive Compatibility, IC）条件量化为最小化事后后悔（ex-post regret），实现端到端学习最优计费规则。大规模离线实验和在线 A/B 实验表明 CGA 能显著提升平台收入等关键指标，同时有效逼近理论最优拍卖的结果。

论文：Contextual Generative Auction with Permutation-level Externalities for Online Advertising
作者：Ruitao Zhu, Yangsu Liu, Dagui Chen, Zhenjia Ma, Chufeng Shi, Zhenzhe Zheng, Jie Zhang, Jian Xu, Bo Zheng, Fan Wu
下载：https://arxiv.org/abs/2412.11544

引言

在线广告系统的最优拍卖机制旨在最大化平台期望收入，同时满足经济学性质，包括激励兼容和个体理性（Individual Rationality, IR），并且需要满足系统在线部署的计算时延要求。IC 条件要求广告主真实报价最大化其自身效用，IR条件要求广告主的效用非负。

在典型的点击计费（Cost-per-Click, CPC）多坑广告场景下，广告拍卖机制的效果依赖于对广告点击率（CTR）的预估准度。广泛使用的 GSP 等机制使用精排阶段的单点预估 CTR，忽略了页面展示的其它商品的影响。而实际场景中，用户浏览的页面包括多个商品，用户在决策前通常会对不同商品进行比较，因此同时曝光的其它商品会对目标广告的 CTR 产生影响，称为“外部性” [1]。

基于深度学习的拍卖机制，如 Deep Neural Auction（DNA [2]）和 Score Weighted VCG（SW-VCG [3]）等工作考虑使用深度网络刻画外部性影响以提升平台收入。然而无论是 DNA 采用的先预估广告 rankscore 再进行排序，还是 SW-VCG 使用的先预估单调性分数再求解二部图最大匹配，这些方法本质上都受到“先预估后分配”（allocation-after-prediction）范式的局限，预估时的上下文信息与分配后的最终上下文信息不一致，因此模型只能捕捉到粗粒度的广告候选集层面的外部性。另一方面，Neural Multi-slot Auction（NMA [4]）等机制采用类似 VCG 拍卖的方式，遍历所有可能的排列结果以求解最优分配，但是极高的计算复杂度使其难以应用于在线场景。

根据 Myerson 拍卖理论 [5]，拍卖机制的 IC 条件要求广告主获得的期望价值关于其出价满足非递减关系。大多数现有方法通过保证排序公式中出价的权重为正，使得广告主提高出价能获得相同或更前置的广告位。但是在排列外部性的影响下，即使广告候选集保持不变，将广告分配到的坑位前置反而可能导致其期望价值下降。图 1 给出了不同广告的分坑位 [点击率 * 曝光率]（表示 CPC 机制下的广告主期望价值）的实验数据，二者的关系并不满足单调性。因此，在排列外部性影响下，如何设计满足激励兼容条件的分配规则是一个非平凡的问题。

△图1：广告分坑位 [点击率 * 曝光率]

本文旨在探索在排列外部性影响下，满足 IC 和 IR 约束的收入最大化广告拍卖机制的基本形式和高效实现。我们首先给出系统性的理论分析，证明最优解保留 Myerson 最优拍卖的基本形式，即分配规则和计费规则可以进行解耦。在理论最优解的基础上，引入经典的生成器-评估器（Generator-Evaluator）架构，构建感知排列外部性的生成式拍卖。最后，进行工业数据集上的离在线实验，在多维度指标上对比现有的拍卖机制研究工作。

问题建模与理论分析

在线广告场景可以抽象成一个典型的多坑拍卖问题。对于每条用户请求，由

个广告主（可以是手动调整出价或者自动出价代理）对 个广告位进行出价。广告主根据自身的私有估值 提交出价 , 其中服从价值分布 。给定出价向量, 用户特征向量 以及所有参竞广告的特征向量 ，平台的拍卖机制决定分配方案 以及广告主的计费 ，其中 表示广告 分配到广告位

。

广告拍卖中的外部性指的是竞胜广告主的效用会受到其它竞胜广告的影响 [1]。对于 CPC 多坑拍卖，外部性影响主要反映在广告 CTR 上。我们用

表示任意感知排列外部性的 CTR 模型，广告 的 CTR 可以表示为 ，可以简化表示为

。

在上述排列外部性的拍卖机制建模下，广告主

的期望效用为

拍卖机制的激励兼容（IC）条件要求真实报价

最大化其期望效用

，个体理性（IR）条件则要求广告主效用非负。广告拍卖机制目标为最大化平台期望收入

且满足IC和IR约束。

求解收入最大化机制的直观想法是遵循经典的 Myerson 拍卖，我们将排列外部性引入 Myerson 拍卖，可以写成如下形式，其中

表示经过 iron 操作后的虚拟价值函数（确保函数单调性）：

• 分配规则：

• 计费规则：

需要注意的是，由于排列外部性的引入，在最终分配结果中其它广告的影响下，广告主提高出价不一定会提高最终的 CTR，因此 Myerson 理论中的“单调分配”性质在排列外部性影响下是否成立需要重新论证。我们理论证明了上述“单调分配”的性质仍然保持，具体表述为如下引理 1，完整证明请参考论文原文附录 A.1。

引理1: 在排列外部性建模下，若拍卖机制的分配规则

最大化期望虚拟福利，则对于任意广告主以及其它广告主的出价向量，关于出价单调不减，或者称分配规则

为单调的。

结合引理 1 和 Myerson 拍卖理论，可以证明上述引入排列外部性的 Myerson 拍卖为满足IC、IR约束且最大化平台期望收入的最优拍卖机制，完整推导过程请参考论文原文 2.2 节。

直接求解上述最优分配结果需要枚举参竞广告的所有可能排列结果，再进行选优，枚举过程的计算复杂度为

，线上场景下,，枚举过程的高复杂度无法满足线上推理实验要求。因此我们考虑将拍卖机制进行参数化，通过数据驱动的方式进行学习。为了在端到端学习的过程中满足 IC 约束并保持优化过程的可微性，类似多物品拍卖的研究工作 RegretNet [6]，我们将机制偏离 IC 条件的程度量化为每个广告主的 ex-post regret，即广告主通过虚报出价

可以获得的最大效用增加值：

给定价值分布

中的 条采样，则广告主

的经验 ex-post regret 为

拍卖机制设计问题可以进一步改写成如下约束优化问题：

生成式拍卖

前文提到，现有的基于深度学习的拍卖机制受限于“先预估后分配”的设计范式，无法感知排列级外部性。我们提出的生成式拍卖引入了生成器-评估器的基本架构，模型整体架构如图 2 所示。生成器采用自回归模型，逐坑位感知已经决策完成的序列信息，生成广告序列。评估器捕捉广告序列中的商品相互影响，对精排阶段的单点 pCTR 结合序列上下文信息进行校准，在训练时为生成器提供奖励信号。在线推理时，仅部署生成器，以保证线上推理时延。此外，我们构建了 PaymentNet 模块，通过优化 ex-post regret 学习最优计费规则。

△图2：感知排列外部性的生成式拍卖整体框架

1、生成器

根据理论推导的最优分配形式，生成器的目标为根据

个参竞广告，生成长度为的广告序列

，以最大化期望虚拟福利。我们构建的生成器包括两部分：满足排列不变性（permutation-invariant）的集合编码器，以及满足排列同变性（permutation-equivariant）的自回归解码器。排列不变性指的是改变模型输入元素的排列顺序不会改变模型输出的结果，排列同变性指的是输入元素的排列顺序改变会引起输出结果的排列顺序产生相同的改变。前者保证输入模型的参竞广告顺序不影响分配结果，后者在自动机制设计 [7-9] 的研究工作中广泛应用，[10] 进一步论证了排列同变性可以提升机制的泛化性。

集合编码器旨在通过建模参竞集合粒度的外部性来增强每个广告的表征。编码器首先通过 self-attention layer 编码广告 embedding 序列：

再经过 sum-pooling 层和 MLP 层得到集合粒度上下文编码：

解码器使用自回归模型建模长度为

的广告序列的联合概率分布：

我们使用 GRU 单元建模参竞广告在坑位的条件概率：，第

个 GRU 单元迭代式地定义为：

其中

为可学习的参数，始终非负，确保更高的虚拟价值获得更大的分配概率，与最大化虚拟福利的目标保持一致。我们接下来对在坑位之前分配的广告进行 mask 操作，并基于概率进行采样以决策分配到当前坑位的广告。重复次采样过程，得到长度为

的广告序列即为最终分配结果。注意到生成器中的 MLP 和 GRU 单元作用在每个 state-ad 对，且编码器满足排列不变性，因此解码器满足排列同变性。

2、评估器

评估器的目标为预估分配结果

中每个广告的 CTR ，进一步在训练过程中为生成器提供奖励信号。为了复用精排阶段从用户行为序列中提取的用户兴趣信息，避免冗余建模，评估器在精排单点 pCTR的基础上，预估排列外部性校准向量，再将二者进行逐元素相乘得到最终预估的 CTR：

。模型结构上同时引入了双向 LSTM 和 self-attention 模块提取序列上下文信息，最终将聚合用户 embedding 后的表征送入 MLP 层得到外部性校准向量：

具体实现细节请参考论文原文。

3、计费模块

注意到第 2 节中理论推导的最优计费规则包括积分项

通过蒙特卡洛采样近似计算积分时，每次采样都需要调用生成器

和评估器，在实时推理时的计算开销过大。在前文中，我们将 IC 条件改写为每个广告主的经验 ex-post regret 等于 0，这使得我们可以通过数据驱动的方式构建计费模块学习上述最优计费规则。计费模块输入包括广告分配序列的表征，出价矩阵 ，以及期望价值向量，其中表示生成器输出的广告分配概率，表示评估器输出的外部性校准后的 CTR。为了满足 IR 条件，计费模型通过 sigmoid 激活函数输出计费比

，再与出价相乘得到最终计费

。

4、训练流程

根据第 2 节中推导的结论，最优分配最大化虚拟福利，与计费规则无关，因此我们在训练时将基于生成器-评估器架构的分配求解模块与计费模块的优化进行解耦。

我们首先使用列表级的广告点击数据训练评估器，交叉熵损失函数定义为：

其中

表示用户是否点击列表 中的第 个广告，

表示评估器的外部性校准后的预估 CTR。

在评估器训练收敛后，我们冻结其参数，指导生成器训练。类似推荐系统重排工作 GRN [11] 的损失函数设计思路，我们将奖励函数拆解为两部分。Self-Reward 直接刻画每个分配的广告带来的虚拟福利增量，即

External-Reward 刻画每个分配的广告带来的外部性影响，即

类似 VCG 拍卖中的边际贡献的概念。二者相加即可得到分配广告

的整体奖励函数：

其中

表示排除广告

后的广告序列。最后，我们使用 Policy Gradient 定义生成器的损失函数为：

在生成器-评估器架构训练收敛后，我们冻结其参数，使用增广拉格朗日方法求解第 2 节最后定义的约束优化问题以优化计费模块，对违反 IC 条件施加惩罚项，增广拉格朗日函数定义为：

计费模块的优化过程包括以下两个过程的迭代：

（1）更新计费模块的参数

（2）更新拉格朗日乘子

实验

我们在淘宝展示广告场景的真实数据集上以及线上环境中评估生成式拍卖的有效性。对比的基线方法按照外部性建模的粒度可以分为三类：

• 无外部性建模：GSP 广义二价拍卖。
• 集合粒度外部性建模：DNA [2]；SW-VCG [3]。
• 排列级外部性建模：基于枚举实现的 VCG 拍卖；EdgeNet [12]；理论推导的最优拍卖机制。

1、离线实验

离线实验使用的训练集和测试集分别包括不同日期随机采样的 50 万条和 10 万条拍卖日志，每次拍卖约有30个广告参竞。我们考虑广告主出价的条件分布分别服从均匀分布（uniform）和指数分布（exponential），在两种条件下分别进行评估。评估指标包括平台收入指标 RPM（Revenue Per Mille），CTR 以及评估机制 IC 条件的指标

衡量广告主通过非真实出价能够获得的效用相对增量。

实验结果如表 1 所示。可以观察到随着外部性建模从不考虑外部性到集合粒度外部性，再到排列级外部性，三个指标均趋向更优。此外，注意到与基于枚举法实现的理论最优上界相比，生成式拍卖（CGA）达到了95%的平台收入以及极低的

值，表明生成式拍卖可以高效近似理论最优机制。

△表1：离线对比实验。指标后的百分比增减量表示基线方法相比 CGA 的相对值

2、在线实验

我们在展示广告场景进行了线上 A/B 实验，基线为线上使用的 DNA [2] 机制。实验结果表明，生成式拍卖在推理时延仅增加 1.6% 的情况下，平台收入指标 RPM 提高了 3.2%，CTR 提升 1.4%，成交 GMV 提升6.4%，广告主 ROI 提升 3.5%。实验结果表明生成式拍卖带来的收入提升不是由于直接抬高广告主计费，而是通过感知排列级外部性优化广告分配，实现更精准的广告触达，反映于 CTR、GMV 以及广告主 ROI 的提升。

总结

本文从广告拍卖机制中的排列级外部性影响出发，打破“先预估后分配”的设计范式，针对在线广告场景提出了感知排列外部性的生成式拍卖。结果表明，经典的 Myerson 拍卖在迁移到排列级外部性的形式后，仍然保持其最优性。

基于这一结论，团队设计的生成式拍卖架构将分配和计费模块解耦。在具体实现上，构建了基于生成器-评估器的自回归生成式结构来优化分配，并将 IC 约束量化为最小化期望事后后悔来学习最优支付规则。工业级场景的离在线实验验证了生成式拍卖的有效性。值得注意的是，提出的生成式拍卖框架并不局限于特定的生成式模型。

未来的研究工作将探索引入更加高效的生成式架构，并在拍卖机制中统一分配来自多渠道的商品，例如自然结果与广告的融合混排。

关于团队

阿里妈妈展示广告机制策略算法团队，致力于不断优化阿里展示广告技术体系，驱动业务增长，推动技术持续创新；不断升级工程架构以支撑阿里妈妈展示广告业务稳健&高效迭代，深挖商业化价值并优化广告主投放效果，孵化创新产品和创新商业化模式，优化广告生态健壮性；驱动机制升级，并已迈入 Deep Learning for Mechanisms 时代，团队创新工作发表于 KDD、WWW、ICML、CIKM、WSDM、AAMAS、AAAI 等领域知名会议。在此真诚欢迎有ML背景的同学加入！

投递简历邮箱（请注明-展示广告机制策略）：

alimama_tech@service.alibaba.com

参考文献

[1] Arpita Ghosh and Mohammad Mahdian. Externalities in online advertising. WWW’08.
[2] Xiangyu Liu, Chuan Yu, Zhilin Zhang, Zhenzhe Zheng, Yu Rong, Hongtao Lv, Da Huo, Yiqing Wang, Dagui Chen, Jian Xu, Fan Wu, Guihai Chen, and Xiaoqiang Zhu. Neural auction: End-to-end learning of auction mechanisms for e-commerce advertising. KDD’21.
[3] Ningyuan Li, Yunxuan Ma, Yang Zhao, Zhijian Duan, Yurong Chen, Zhilin Zhang, Jian Xu, Bo Zheng, and Xiaotie Deng. Learning-Based Ad Auction Design with Externalities: The Framework and A Matching-Based Approach. KDD’23.
[4] Guogang Liao, Xuejian Li, Ze Wang, Fan Yang, Muzhi Guan, Bingqi Zhu, Yongkang Wang, Xingxing Wang, and Dong Wang. 2022. NMA: Neural Multi-slot Auctions with Externalities for Online Advertising. arXiv preprint arXiv:2205.10018 (2022).
[5] Roger B Myerson. 1981. Optimal auction design. Mathematics of operations research 6, 1 (1981), 58–73.
[6] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. ICML’19.
[7] Zhijian Duan, Haoran Sun, Yurong Chen, and Xiaotie Deng. A scalable neural network for dsic affine maximizer auction design. NeurIPS’24.
[8] Dmitry Ivanov, Iskander Safiulin, Igor Filippov, and Ksenia Balabaeva. Optimal-er auctions through attention. NeurIPS’22.
[9] Jad Rahme, Samy Jelassi, Joan Bruna, and S Matthew Weinberg. A permutation-equivariant neural network architecture for auction design. AAAI’21.
[10] Tian Qin, Fengxiang He, Dingfeng Shi, Wenbing Huang, and Dacheng Tao. Benefits of permutation-equivariance in auction mechanisms. NeurIPS’22.
[11] Yufei Feng, Binbin Hu, Yu Gong, Fei Sun, Qingwen Liu, and Wenwu Ou. 2021. GRN: Generative Rerank Network for Context-wise Recommendation. arXiv preprint arXiv:2104.00860 (2021).
[12] Guangyuan Shen, Shengjie Sun, Dehong Gao, Duanxiao Song, Libin Yang, Zhen Wang, Yongping Shi, and Wei Ning. EdgeNet: Encoder-decoder generative Network for Auction Design in E-commerce Online Advertising. CIKM’23.

Read More