今天小編分享的科學經驗：生成式拍賣：感知排列外部性的整頁優化機制，歡迎閲讀。
The following article is from 阿裏媽媽技術 Author 衡言
從 " 先預估後分配 " 的判别式方法，到直接面向最終拍賣結果的生成式方法，生成式模型能否為在線廣告的拍賣機制優化帶來持續增量？
本文介紹阿裏媽媽展示廣告機制策略團隊在 AIGA（AI-Generated Auction）方向的前沿探索 - 生成式拍賣研究工作。
基于該項工作整理的論文已被KDD ’ 25 Research Track接收。
廣告拍賣機制設計作為在線廣告系統的重要一環，在持續優化廣告主和平台收益方面起着至關重要的作用。傳統的廣義二價拍賣（GSP）等拍賣機制依賴于點擊率分離假設（将廣告點擊率拆分為廣告自身質量分和廣告位曝光權重的乘積），忽略了頁面中同時展示的其它商品的影響，即外部性影響。
近年來，基于深度學習的拍賣機制顯著增強了對高維上下文特征的編碼能力，但是現有方法仍受限于 " 先預估後分配 " 的設計範式。這種範式只能建模參競廣告集合内的外部性，無法捕捉最終分配結果的整頁上下文信息（即排列外部性），因此難以收斂到全局最優解。本文系統分析了在排列外部性影響下的最優拍賣機制，在理論最優解的基礎上，研究團隊提出了首個使用生成式模型建模排列外部性的廣告拍賣機制 - 生成式拍賣（Contextual Generative Auction, CGA）。
該框架通過自回歸模型生成廣告分配結果，并将激勵兼容（Incentive Compatibility, IC）條件量化為最小化事後後悔（ex-post regret），實現端到端學習最優計費規則。大規模離線實驗和在線 A/B 實驗表明 CGA 能顯著提升平台收入等關鍵指标，同時有效逼近理論最優拍賣的結果。
引言
在線廣告系統的最優拍賣機制旨在最大化平台期望收入，同時滿足經濟學性質，包括激勵兼容和個體理性（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 背景的同學加入！
參考文獻
[ 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.
* 本文系量子位獲授權刊載，觀點僅為作者所有。
— 完 —
量子位 QbitAI
վ ' ᴗ ' ի 追蹤 AI 技術和產品新動态
一鍵三連「分享」、「點贊」和「在看」
科技前沿進展日日相見 ~
>
