整体思路说明（摘要）
- 电子商务平台通常会在每个用户的页面浏览请求中展示一个有序列表，其中包含多个自然商品和一个广告。这个列表是广告拍卖和分配过程的结果，直接影响平台的广告收入和商品交易总额（GMV）。具体来说，广告拍卖决定了展示哪个广告以及相应的支付金额，而广告分配则决定了广告和自然商品的展示位置
- 目前普遍的方法将广告拍卖和分配分为两个独立的阶段，面临两个问题：
- 1）广告拍卖没有考虑外部性，例如实际展示位置和上下文对广告点击率（CTR）的影响；
- 2）广告分配利用拍卖获胜广告的支付金额动态决定展示位置，但无法保持广告的激励兼容性（IC）。例如，在使用传统广义第二价格（GSP）的拍卖阶段，即使获胜广告提高出价，其支付金额也不会改变。这意味着广告无法获得更好的位置，从而失去了在后续广告分配阶段实现更高效用的机会
- 以往的研究通常只关注其中一个阶段，忽略了这两个阶段的问题，可能导致次优结果
- 论文提出了一种深度自动化机制：
- 将广告拍卖和分配集成在一起，确保在存在外部性的情况下同时满足IC和个体合理性（IR），并最大化收入和GMV
- 该机制以候选广告和自然商品的有序列表作为输入
- 对于每个候选广告，通过在自然商品列表的不同位置插入广告生成多个候选分配
- 对于每个候选分配，列表模型将整个分配作为输入，并输出每个广告和自然商品的预测结果，以建模全局外部性
- 最后，通过深度神经网络建模的自动化拍卖机制执行，选择最优分配
- 因此，该机制同时决定了广告的排名、支付金额和展示位置
- 论文机制在离线实验和在线A/B测试中比最先进的基线方法实现了更高的收入和GMV
Introduction and Discussion
- 在许多电子商务信息流中，每个用户的页面浏览请求都会展示一个有序列表，其中包含多个自然商品和一个按点击付费的广告（如果用户点击广告，平台将向相应的广告主收费，这是平台收入的关键来源。同时，如果用户购买了自然商品或广告中的产品，平台的商品交易总额（GMV）将增加
- 实际上，这个列表由广告拍卖和分配过程生成，直接决定了平台的收入和GMV
- 广告拍卖 ：决定了展示哪个广告以及广告的支付金额
- 广告分配 ：决定了广告和自然商品在信息流中的展示位置
- 广告拍卖和分配是相互影响的
- 引出问题 ：设计广告拍卖和分配机制以最大化平台收入和GMV成为一个非常有意义且具有挑战性的问题
- 传统广告拍卖和位置分配方法 ：将广告拍卖和分配分为两个阶段
- 首先，在广告拍卖中，例如经典的GSP，候选广告通过eCPM（预计每千次展示收入）进行排名，eCPM由广告的预测点击率（pCTR）和出价计算得出，eCPM最高的广告获胜，其支付金额为下一个排名广告的eCPM除以其自身的pCTR。显然，获胜广告的支付金额取决于下一个排名广告的出价，而不是其自身的出价。同时，自然商品列表按估计的GMV排序
- 随后，广告分配算法动态地将拍卖获胜的广告插入到有序的自然商品列表中，其中获胜广告的支付金额用于位置决策，旨在最大化收入和GMV
- 从广告机制设计的角度来看，传统这种将广告拍卖和分配分为两个独立阶段的方法面临以下两个问题：
- 广告拍卖未考虑外部性。广告外部性通常指其展示位置和上下文对其CTR的影响。传统拍卖，包括GSP，通常不考虑外部性，并基于分离的CTR假设获得稳定的结果。然而，在实际中，广告被自然商品包围时的CTR受其实际展示位置和上下文的影响。外部性导致广告主之间复杂的战略竞争，阻碍了稳定结果和社会福利优化。因此，在考虑外部性时，传统拍卖并不适用。（比如：在美团零售配送平台上，信息流中的广告“乐事薯片”与外部自然商品一起展示给用户。用户是否点击广告很容易受到广告位置和上下文的影响）
- 广告分配无法保持激励兼容性（IC）。广告分配利用拍卖获胜广告的支付价格动态确定显示位置，无法保持广告的激励兼容性。例如，在使用传统GSP的拍卖阶段，即使获胜广告增加其出价，其支付价格仍保持不变。这意味着广告无法获得更好的位置，从而失去了在后续广告分配阶段实现更高效用的机会
- 个人理解：不激励兼容可以理解为，用户在和自然竞争时，拿到更好或者更坏的位置，价格不会发生变化，即广告位置分配与出价无关导致了不激励兼容
- 以往的研究通常只关注其中一个阶段，忽略了这两个阶段的问题，这可能导致次优结果。因此，论文提出了一种深度自动化机制，将广告拍卖和分配整合在一起，确保在存在外部性的情况下同时满足激励兼容性（IC）和个体合理性（IR） ，并最大化收入和GMV
- 该机制以候选广告和有机商品的有序列表作为输入。对于每个候选广告，通过在有机商品列表的不同位置插入广告生成多个候选分配；对于每个候选分配，列表模型将整个分配作为输入，并输出每个广告和有机商品的预测结果，以建模全局外部性；最后，执行由深度神经网络建模的自动化拍卖机制，以选择最佳分配
- 也就是说，该机制同时决定了广告的排名、支付价格和显示位置
- 最后：论文所提出的机制在离线实验和在线A/B测试中比最先进的基线方法实现了更高的收入和GMV
- 注：论文旨在设计一种深度自动化机制，集成信息流中的广告拍卖和分配，在存在外部性的情况下同时满足IC和IR，并最大化收入和GMV
Preliminary
广告拍卖与分配的场景设置
- 论文考虑在信息流中集成按点击付费广告拍卖和分配的机制设计。对于每个用户的页面浏览请求，有 \(m\) 个可用位置用于放置广告和自然商品。有 \(n\) 个广告主竞争一个广告位置，其他 \(m-1\) 个位置由自然商品填充。由于平台业务划分的限制，论文假设这些自然商品已根据估计的GMV进行了排序。在后续过程中，自然商品的相对排名不会被修改，但它们的CTR和GMV将被重新预测。论文的主要符号总结在表1中
- 每个广告主 \(i\in[n]\) 对其广告有一个私有的点击价值 \(v_{i}\in\mathcal{B}\subseteq R^{+}\) ，并提交一个点击出价 \(b_{i}\in\mathcal{B}\subseteq R^{+}\) 进行拍卖。论文假设自然商品的点击价值和出价为0。设 \(\mathbf{v}=(v_{1},v_{2},\ldots,v_{n})\in\mathcal{B}^{n}\) 和 \(\mathbf{b}=(b_{1},b_{2},\ldots,b_{n})\in\mathcal{B}^{n}\) 分别为所有广告的价值分布和出价分布。论文使用 \(\mathbf{v}_{-i}\) 和 \(\mathbf{b}_{-i}\) 表示除广告 \(i\) 之外的所有广告的价值分布和出价分布。广告分配可以表示为 \(\mathbf{a}=\mathit{a}(i,j)\) ，其中 \(\mathit{a}(i,j)\) 表示广告 \(i\) 被插入到第 \(j\) 个位置。设 \(j=\sigma(i)\) 表示广告 \(i\) 在分配中的位置索引。所有可能分配的集合表示为 \(\mathcal{A}=\{\mathit{a}(i,j):\forall i\in[n],j\in[m]\}\)
- 形式上，一个分配（具体某个分配）就是一个包含多个自然商品和一个广告的有序列表。在建模全局外部性的影响时，CTR预测需要考虑多个方面，例如广告本身的属性、广告的位置和上下文以及周围自然商品的属性。论文将分配 \(\mathbf{a}\) 中第 \(j\) 个项目的pCTR表示为 \(q_{j}(\mathbf{a})\) 。设 \(g_{j}(\mathbf{a})\) 为分配中第 \(j\) 个项目的估计每点击商品交易额。为了方便起见，论文使用 \(e_{j}\in\mathcal{E}\subseteq R\) 表示分配中第 \(j\) 个项目的外部性，如CTR和GMV
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Key-Symbols.png)
问题公式化
- 给定广告主的出价和有序的自然商品列表，论文表示一个广告拍卖与分配机制 \(\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle\) ，其中：
- \(\mathcal{R}(\mathbf{b};\mathbf{e}):\mathcal{B}^{n}\times\mathcal{E}^{m}\to \mathcal{A}\) 是广告分配规则，用于从 \(n\) 个广告主中选择一个获胜广告，并将其插入到自然商品列表的某个位置
- \(\mathcal{P}(\mathbf{b};\mathbf{e})\) 是支付规则， \(p_{i}(\mathbf{b};\mathbf{e})\) 是广告主 \(i\) 的按点击支付价格
- 对于机制 \(\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle\) ：
- 广告主 \(i\) 的预期效用为：
$$u_{i}^{\mathcal{M}}(v_{i};\mathbf{b};\mathbf{e})=(v_{i}-p_{i}(\mathbf{b}; \mathbf{e}))\times q_{\sigma(i)}\left(\mathcal{R}(\mathbf{b};\mathbf{e})\right),$$ - 平台的预期收入和GMV为：
$$\begin{align}
\text{Rev}^{\mathcal{M}}(\mathbf{b};\mathbf{e}) =\sum_{i=1}^{n}p_{i}(\mathbf{b};\mathbf{e}))\times q_{\sigma(i)} \left(\mathcal{R}(\mathbf{b};\mathbf{e})\right)\\
\text{Gmv}^{\mathcal{M}}(\mathbf{b};\mathbf{e}) =\sum_{j=1}^{m}g_{j}(\mathcal{R}(\mathbf{b};\mathbf{e}))\times q _{j}(\mathcal{R}(\mathbf{b};\mathbf{e}))
\end{align}
$$
- 广告主 \(i\) 的预期效用为：
- 对于广告拍卖机制的设计，IC和IR是必须考虑的标准经济约束。一个拍卖机制 \(\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle\) 是IC的，如果每个广告主如实报告其出价 \(b_{i}=v_{i}\) ，则其效用最大化。形式上，对于任何 \(\mathbf{e}\) ，对于每个 \(i\) ，有
$$u_{i}(v_{i};v_{i},\mathbf{b}_{-1};\mathbf{e})\geq u_{i}(v_{i};b_{i}, \mathbf{b}_{-1};\mathbf{e}),\forall b_{i}\in\mathcal{B},$$ - 一个拍卖机制 \(\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle\) 是IR的，如果每个广告主不会被收取超过其出价的分配费用。形式上，对于任何 \(\mathbf{e}\) ，对于每个 \(i\) ，有
$$p_{i}(\mathbf{b};\mathbf{e})\leq b_{i}.$$ - 论文的目标是设计一个机制 \(\mathcal{M}\langle\mathcal{R},\mathcal{P}\rangle\) ，在存在外部性的情况下同时满足IC和IR，并最大化平台的收入和GMV，如下所示：
$$
\begin{align}
\max_{\mathcal{M}}\inf_{z\in\mathbf{e}} z \mathbb{E}_{\mathbf{a}\in\mathcal{A}}&[\text{Rev}(\mathbf{b};\mathbf{e})+ \alpha\text{Gmv}(\mathbf{b};\mathbf{e})],\\
\text{s.t.} \quad &\textit{IC and IR constraint}
\end{align}
$$- 其中 \(\alpha\) 是平台设置的权重系数，用于平衡收入和GMV
自动化机制设计
- 形式上，广告拍卖与分配的集成可以看作广告和自然商品的组合拍卖（CA），其中自然商品的点击私有价值和出价可以假设为0。Sandholm和Likhodedov提出了一种基于VCG的自动化机制AMA，用于最大化收入的组合拍卖。AMA定义如下
- 每个投标人 \(j\) 提交一个估值函数 \(v_{j}\) 。分配 \(\mathbf{a}^{*}\) 被计算为最大化
$$\text{SW}^{\mu}_{\lambda}(\mathbf{a})=\sum_{j=1}^{m}\mu_{j}v_{j }(\mathbf{a})+\lambda(\mathbf{a}),$$ - 其中 \(\mu_{j}\) 是一个正数，与投标人 \(j\) 的价值分布相关，但与分配无关，同时 \(\lambda(\mathbf{a})\) 是分配的任意函数。支付为:
$$p_{j}(\mathbf{a}^{*})=\frac{1}{\mu_{j}}\Big[\text{SW}^{\mu}_{ \lambda}(\mathbf{a}^{*}_{-j})-\sum_{i\neq j}\mu_{i}v_{i}(\mathbf{a}^{*})- \lambda(\mathbf{a}^{*})\Big],$$ - 其中 \(\mathbf{a}^{*}_{-j}\) 是投标人 \(j\) 不存在时的最佳分配:
$$\mathbf{a}^{*}_{-j}=\max_{\mathbf{a}\in\mathcal{A}}\lim_{i\to \infty}z\in\text{SW}^{\mu}_{\lambda}(\mathbf{a}).$$
- 每个投标人 \(j\) 提交一个估值函数 \(v_{j}\) 。分配 \(\mathbf{a}^{*}\) 被计算为最大化
- AMA是一系列机制，由向量 \(\mu\) 和 \(\lambda\) 参数化。VCG是特殊情况，其中对于所有投标人 \(j\) 和任何分配， \(\mu_{j}=1\) 且 \(\lambda(\cdot)=0\) 。 \(\mu_{j}\) 和 \(\lambda(\cdot)\) 通过自动化搜索理论求解以最大化收入。Roberts等和Lavi等已经证明，只有AMA在所有CA设置中都是IC和IR的。因此，受AMA启发，论文将其应用扩展到集成广告拍卖与分配。与搜索理论不同，论文中 \(\mu_{j}\) 和 \(\lambda(\cdot)\) 被建模为深度神经网络，并通过端到端学习方法进行训练
MIAA拍卖机制
- 在本节中，论文介绍了集成信息流中广告拍卖与分配的深度自动化机制MIAA的细节，该机制在存在外部性的情况下同时满足IC和IR，并最大化收入和GMV。如图2所示，MIAA以候选广告和有序的自然商品列表作为输入，并通过三个模块输出最优分配。MIAA的三个模块是外部性感知预测模块（ Externality-aware Prediction Module，EPM）、自动化拍卖模块（Automated Auction Module，AAM）和可微分排序模块（Differentiable Sorting Module，DSM）
- EPM以分配为输入，建模全局外部性的影响，并输出每个广告和自然商品的预测结果
- AAM使用两个深度神经网络来建模机制参数 \(\mu_{j}\) 和 \(\lambda(\cdot)\) ，旨在提高该自动化机制的表达能力，同时保证IC和IR
- DSM使用多分类模型softmax对机制中的排序操作进行连续松弛，并输出表示每个候选分配获胜概率的向量
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Architecture.png)
- 平台的预期收入和GMV可以通过端到端学习方式可微分地计算和优化
外部性感知预测模块（EPM）
外部性感知预测模块（ Externality-aware Prediction Module，EPM）
- 在大多数传统拍卖机制中，广告的位置和上下文信息只能在拍卖后得知，因此CTR预测模型无法提前获取这些信息。然而，拍卖依赖于预测模型的pCTR。为了解决这种相互依赖问题并获得稳定的分配结果，机制设计基于分离的CTR假设，即广告的最终CTR等于其自身内容的CTR与其位置的CTR的乘积，忽略了上下文商品的影响。因此，在这种假设下，通常使用点模型来预测CTR，该模型不考虑广告展示位置和广告与自然商品之间的相互作用的影响。一些模型相继提出，捕捉局部外部性，仅关注广告的展示位置或广告的局部上下文。为此，论文使用列表预测模块显式建模全局外部性，为每个项目输出更准确的pCTR
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-EPM.png)
- 第一步 ，对于每个候选广告，通过在有序自然商品列表的不同位置插入广告生成多个候选分配。此步骤对应的时间复杂度为 \(O(m\times n)\) 。在实际生产过程中， \(m\) 的值通常不大于5，这在平台性能方面是可以接受的
- 第二步 ，EPM对所有候选分配采用参数共享结构。这里论文以分配 \(\mathbf{a}\) 为例进行说明。如图2所示，EPM以分配 \(\mathbf{a}\) 和两种类型的公共信息（即请求信息、当前请求中的用户画像）作为输入，并输出分配中每个项目的pCTR。论文首先使用嵌入层从原始稀疏特征中提取嵌入，然后将密集特征与嵌入连接起来，形成第 \(j\) 个项目的 \(d\) 维特征向量 \(\mathbf{z}_{j}\in\mathbb{R}^{d}\) 。分配 \(\mathbf{a}\) 的特征矩阵表示为 \(\mathbf{Z}^{\mathbf{a}}\in\mathbb{R}^{m\times d}\) ，而请求信息和用户画像的特征向量分别表示为 \(\mathbf{z}^{\prime\prime}\) 和 \(\mathbf{z}^{\prime}\)
- 第三步 ，论文使用自注意力单元来建模候选分配中广告与自然商品之间的相互作用：
$$\mathbf{H}^{\mathbf{a}}=\text{SelfAtt}\left(\mathbf{Q}^{\mathbf{a}},\mathbf{K}^{ \mathbf{a}},\mathbf{V}^{\mathbf{a}}\right)=\text{softmax}\left(\frac{\mathbf{Q}^ {\mathbf{a}}(\mathbf{K}^{\mathbf{a}})^{\top}}{\sqrt{d}}\right)\mathbf{v}^{ \mathbf{a}},$$- 其中 \(\mathbf{Q}^{\mathbf{a}}\) 、 \(\mathbf{K}^{\mathbf{a}}\) 、 \(\mathbf{V}^{\mathbf{a}}\) 分别表示查询、键和值。这里查询、键和值从分配 \(\mathbf{a}\) 的特征信息线性变换而来，如下所示：
$$\mathbf{Q}^{\mathbf{a}}=\mathbf{Z}^{\mathbf{a}}\mathbf{W}^{Q},\mathbf{K}^{ \mathbf{a}}=\mathbf{Z}^{\mathbf{a}}\mathbf{W}^{K},\mathbf{V}^{\mathbf{a}}= \mathbf{Z}^{\mathbf{a}}\mathbf{W}^{V}.$$
- 其中 \(\mathbf{Q}^{\mathbf{a}}\) 、 \(\mathbf{K}^{\mathbf{a}}\) 、 \(\mathbf{V}^{\mathbf{a}}\) 分别表示查询、键和值。这里查询、键和值从分配 \(\mathbf{a}\) 的特征信息线性变换而来，如下所示：
- 第四步 ，论文将 \(\mathbf{H}^{\mathbf{a}}\) 重塑为一个向量 \(\mathbf{h}^{\mathbf{a}}\in\mathbb{R}^{md}\) ，并将 \(\mathbf{z}^{u}\) 、 \(\mathbf{z}^{r}\) 连接起来，放入多层感知机（MLP）中以建模全局外部性：
$$\hat{q}_{j}=q_{j}(\mathbf{a})=\text{Sigmoid}\left(\text{FC}_{j} \left(\text{MLP}^{\mathbf{c}}\left(\mathbf{h}^{\mathbf{a}}|\mathbf{z}^{u}|\mathbf{z}^{r}\right)\right)\right),;\forall j\in[m],$$- 其中 \(q_{j}(\mathbf{a})\) 表示分配中第 \(j\) 个项目的pCTR。在EPM中，通过每个项目的真实点击行为计算交叉熵损失来训练该列表模型：
$$\text{Loss}_{\text{ec}}=-\sum_{j=1}^{m}\left(y_{j}\text{log}(q_{j}(\mathbf{a})) +(1-y_{j})\text{log}(1-q_{j}(\mathbf{a}))\right).$$- 其中 \(y_{j}\in{0,1}\) 表示用户是否点击了分配中的第 \(j\) 个项目
- 其中 \(q_{j}(\mathbf{a})\) 表示分配中第 \(j\) 个项目的pCTR。在EPM中，通过每个项目的真实点击行为计算交叉熵损失来训练该列表模型：
- 外部性感知预测模块（EPM）以候选分配为输入，并输出分配中每个位置的pCTR。它是独立构建和训练的，不与下游模块耦合。EPM是一个通用框架，可以轻松扩展到多个目标预测，如转化率（CVR）和GMV。下文中的 \(g_{j}(\mathbf{a})\) 可以在EPM中同时预测，无需进一步阐述。与点模型相比，列表模型捕捉了全局外部性并输出了更准确的结果，这有助于后续模块实现更好的性能
自动化拍卖模块（AAM）
自动化拍卖模块（Automated Auction Module，AAM）
- 该模块从所有可能的候选分配中选择最优分配，同时决定广告的排名、支付金额和展示位置。将AMA扩展为深度自动化机制， \(\mu\) 和 \(\lambda(\cdot)\) 被建模为深度神经网络 \(\mu\) -网络和 \(\lambda\) -网络，以提高排名公式的表达能力，同时保证IC和IR属性
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-AAM.png)
- \(\mu\) 表示项目出价能力的强度，与分配无关（Kumar等，2019）。因此，更具体地说，广告的价值分布信息、请求信息的特征、用户画像和项目的特征是 \(\mu\) -网络的主要输入特征。设 \(\mathbf{x}_{j}\) 表示分配中第 \(j\) 个项目的价值分布信息向量。 \(\mu\) -网络可以形式化表示为：
$$f_{j}^{\mu}=\text{Sigmoid}\left(\text{MLP}^{\mu}(\mathbf{x}_{j}|\mathbf{z}^{\mu}| \mathbf{z}^{r})\right),\forall j\in[m],$$- 其中sigmoid函数确保输出为正。每个项目都有一个 \(f_{j}^{\mu}\) 来表示其竞争能力
- \(\lambda\) 是分配 \(\mathbf{a}\) 的任意函数。分配 \(\mathbf{a}\) 中每个项目的特征被连接起来以表示整个分配，分配 \(\mathbf{a}\) 的 \(\lambda\) -网络为：
$$f^{\lambda}(\mathbf{a})=\text{MLP}^{\lambda}\left(\mathbf{o}_{1}|\mathbf{o}_{2}| \dots|\mathbf{o}_{m}|\mathbf{z}^{\mu}|\mathbf{z}^{r}\right),$$- 其中 \(\mathbf{o}_{j}=\mathbf{x}_{j}|g_{j}(\mathbf{a})|g_{j}(\mathbf{a})\)
- 分配 \(\mathbf{a}\) 的社会福利计算为：
$$\text{SW}_{\lambda}^{\mu}(\mathbf{a})=\sum_{j=1}^{m}f_{j}^{\mu}\times\text{eCPM}_ {j}(\mathbf{a})+f^{\lambda}(\mathbf{a}),$$- 其中 \(\text{eCPM}_{j}(\mathbf{a})=b_{j}\times q_{j}(\mathbf{a})\) 是分配 \(\mathbf{a}\) 中第 \(j\) 个项目的估值函数
- 最优分配 \(\mathbf{a}^{*}\) 被计算为最大化 \(\text{SW}_{\lambda}^{\mu}(\cdot)\) 。分配 \(\mathbf{a}^{*}\) 中第 \(\sigma(i)\) 个位置的广告 \(i\) 的按点击支付为
$$p_{i}(\mathbf{a}^{*})=\frac{1}{f_{\sigma(i)}^{\mu}(\mathbf{a}^{*})}\left[\text{ SW}_{\lambda}^{\mu}(\mathbf{a}^{*}_{-i})-\text{SW}_{\lambda}^{\mu}(\mathbf{a}^{* })_{-i}\right]\times\frac{1}{q_{\sigma(i)}(\mathbf{a}^{*})},$$- 其中 \(\mathbf{a}^{*}_{-i}\) 是广告 \(i\) 不存在时的最优分配， \(\text{SW}_{\lambda}^{\mu}(\mathbf{a}^{*})_{-i}=\sum_{j\neq\sigma(i)}f_{j}^{\mu} \cdot b_{j}\cdot q_{j}(\mathbf{a}^{*})+f^{\lambda}(\mathbf{a}^{*})\) 。因为分配中只有一个广告，且每个自然商品的出价为0，所以 \(\text{SW}_{\lambda}^{\mu}(\mathbf{a}^{*})_{-i}=f^{\lambda}(\mathbf{a}^{*})\)
- 显然，该过程保持了AMA的IC和IR属性。 \(\mu\) -网络和 \(\lambda\) -网络在下一个模块DSM中通过端到端学习进行训练
可微分排序模块（DSM）
可微分排序模块（Differentiable Sorting Module，DSM）
- AMA（Kumar等，2019）中用于求解 \(\mu\) 和 \(\lambda\) 参数的搜索理论效率低下。论文旨在通过端到端学习方式提高解决该机制问题的效率和有效性。然而，论文面临两个挑战，第一个是拍卖中排序过程的不可微性，第二个是缺乏用户真实行为反馈
- 在AAM中，获取最优分配的排序操作导致整个过程的不可微性。受Liu等（Liu等，2020）提出的可微分排序引擎启发，论文使用多分类模型softmax对机制中的排序操作进行连续松弛。给定分配集 \(\mathbf{SW}=[\text{SW}_{\lambda}^{\mu}(\mathbf{a}_{1}),\dots,\text{SW}_{\lambda }^{\mu}(\mathbf{a}_{mn})]\) ，分配向量 \(\mathbf{Pr}\) 通过softmax函数映射：
$$\mathbf{Pr}=\text{softmax}(\frac{\mathbf{SW}}{\tau})=[Pr(\mathbf{a}_{1}),Pr( \mathbf{a}_{2}),\dots,Pr(\mathbf{a}_{mn})],$$- 其中 \(\tau\) 是温度参数。直观上， \(\mathbf{Pr}\) 可以解释为所有分配的获胜概率
- 论文使用pCTR和预测GMV（pGMV）指标来模拟用户行为，并计算分配的性能指标，然后用于反馈训练。因此，分配的预期收入和GMV通过公式(2)计算为：
$$\begin{split}\mathbf{Rev}=&[\text{Rev}(\mathbf{a}_{ 1}),\text{Rev}(\mathbf{a}_{2}),\dots,\text{Rev}(\mathbf{a}_{mn})],\ \mathbf{Gmv}=&[\text{Gmv}(\mathbf{a}_{1}),\text{Gmv}( \mathbf{a}_{2}),\dots,\text{Gmv}(\mathbf{a}_{mn})].\end{split}$$ - 具体来说，只有获胜分配的收入大于0，而非获胜分配的收入为0。最后，整体优化目标是最大化 \(\text{Reward}_{\lambda}^{\mu}\) ，即最小化
$$\text{Loss}=-\text{Reward}_{\lambda}^{\mu}=-\sum_{k=1}^{mn}Pr(\mathbf{a}_{k}) \left(\text{Rev}(\mathbf{a}_{k})+\alpha\text{Gmv}(\mathbf{a}_{k})\right).$$ - 该损失为训练 \(\mu\) -网络和 \(\lambda\) -网络提供了直接反馈，这是一种部分可微的方法。该训练过程高度依赖于pCTR和pGMV的准确性，这可能导致该机制的离线和在线效果不一致。因此，有必要提高EPM中pCTR和pGMV的预测性能，并对它们进行列表校准（Bernstein等，2018）
训练与在线服务
- 每个请求中的数据（例如候选广告集、自然商品列表、真实展示的有序列表等）应记录下来用于MIAA的训练。AAM中 \(\mu\) -网络和 \(\lambda\) -网络的训练依赖于EPM中列表模型的预测输出。因此，EPM中的列表模型首先需要单独训练，使用真实展示的有序列表数据。然后，对于每个请求记录，基于候选广告和自然商品列表生成所有可能的分配。接下来，EPM中训练好的列表模型为每个分配提供pCTR和pGMV的预测结果，这些结果将用于后续AAM中 \(\mu\) -网络和 \(\lambda\) -网络的训练。该训练过程无法获得真实的用户行为反馈，因此依赖于预测数据来评估模型性能
- EPM和AAM中训练好的模型同时部署在线，并按照以下过程提供在线服务：
- 步骤1 ：生成所有可能的分配
- 步骤2 ：通过EPM预测每个分配的pCTR和pGMV
- 步骤3 ：通过AAM从所有可能的分配中选择最优分配
- 步骤4 ：返回获胜广告及其位置
Experiments
- 在本节中，论文评估了所提出的机制MIAA的有效性，旨在回答以下问题：
- Q1 ：与点模型pCTR相比，论文的列表模型在CTR预测方面的表现如何？
- Q2 ：与工业平台中广泛使用的广告拍卖和分配机制相比，论文的机制在平台收入和GMV方面的表现如何？
- 论文在公共和工业数据集上进行了广泛的离线实验，并在美团零售配送平台上进行了在线A/B测试
Experiment Setup
数据集
- 在离线实验中，论文在公共和工业数据集上提供了论文机制有效性的实证证据。两个数据集的统计信息总结在表2中，详细描述如下：
- Avito1。公共数据集是用于Kaggle的Avito上下文广告点击竞赛的Avito数据集。它是avito.ru上至少连续26天内先前选择的用户搜索的随机样本。在每个搜索结果页面中，仅记录了位置1、2、6、7、8中的五个项目。并且只有第1和第7位置的项目（即上下文广告）标记了用户是否点击。对于后续实验，论文基于第1和第7位置的点击行为模拟用户是否点击第2和第6位置的项目。设CTR \({}_{j}\) 表示位置 \(j\) 的CTR。CTR \({}_{1}\) 和CTR \({}_{7}\) 可以通过统计分析获得。然后，CTR \({}_{2}\) 被模拟为遵循正态分布 \(N(0.8\text{CTR}_{1}+0.2\text{CTR}_{7},0.1\text{CTR}_{1})\) ，而CTR \({}_{6}\) 被模拟为遵循正态分布 \(N(0.2\text{CTR}_{1}+0.8\text{CTR}_{7},0.1\text{CTR}_{7})\) 。公共信息包括搜索ID、用户ID和搜索日期，而项目信息包括广告ID、位置ID、类别ID和标题。对于每个样本，论文选择第1和第7位置的项目作为候选广告，其余三个项目被视为自然商品。因此，每个候选分配由一个候选广告和这三个自然商品组成。这里论文使用20150425到20150517的数据作为训练集，20150518到20150520的数据作为测试集，以避免数据泄露
- 美团数据 ：工业数据集是在2023年12月期间在美团零售配送平台上使用GSP拍卖和固定位置收集的。从每个信息流请求转换而来，每个样本包含由候选广告和自然商品组成的所有可能候选分配，以及最终获胜的最优分配。每个候选分配由一个候选广告和三个自然商品组成。在每个候选分配中，每个项目的信息包括出价、稀疏特征（例如ID、类别、品牌等）、密集特征（例如历史CTR、销售量、价值分布信息等）。此外，生产环境中的点模型pCTR被记录下来用于后续性能比较。根据数据收集的日期，论文将数据集按8:2的比例划分为训练集和测试集
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Datasets.png)
评估指标
- 论文基于pCTR和pGMV构建了一个离线模拟系统，以评估MIAA的有效性。每个实验使用不同的随机种子重复5次，每个结果以均值±标准差的形式呈现。论文的离线实验和在线A/B测试中使用了以下评估指标
- 点击率 ：CTR = \(\frac{\sum click}{\sum impression}\)
- AUC ：AUC代表曲线下面积，通常用于评估机器学习模型的性能。AUC值越接近1，模型表现越好
- PCOC ：PCOC代表预测CTR与后验CTR之比，是预测准确性的度量。如果PCOC值接近1，则表示预测准确性高
- 每千次展示收入 ：RPM = \(\frac{\sum click\times payment}{\sum impression}\times 1000\)
- 每千次展示GMV ：GPM = \(\frac{\sum GMV}{\sum impression}\times 1000\)
基线
- 在外部性建模方面，论文将所提出的列表模型的pCTR与点模型的pCTR进行比较。在平台收入和GMV方面，论文将MIAA与以下四种常见的拍卖和分配机制进行比较：
- GSP和固定位置 ：这是一种将广告拍卖和分配分为两个阶段的机制。首先，使用GSP机制选择获胜广告，然后将该广告展示在固定位置
- GSP和Cross DQN ：GSP中的获胜广告与自然商品形成多个候选位置的组合，通过Cross DQN进行评估和选择，最终确定广告的展示位置
- Score-Weighted VCG ：Score-Weighted VCG框架将最优拍卖设计分解为两部分：设计单调评分函数和基于匹配的分配算法。但它没有考虑平台GMV及其激励效果
- IAS ：IAS将自然商品视为出价为0的特殊广告，并将广告和自然商品集成到最优拍卖中以获得它们的排名
离线实验
外部性建模的性能比较（Q1）
在公共Avito数据集上，论文需要构建EPM的点模型和列表模型。点模型是一个具有多个全连接层 \(256\times 128\times 64\times 32\times 1\) 的深度神经网络。对于每个请求，提取第1、2、6和7位置的项目以形成列表，用于构建EPM的列表模型。如前所述，该列表中只有第1和第4位置有真实的用户点击行为数据，可用于评估这两个模型的性能。Avito数据集上的详细实验结果如表3所示。对于分配中的所有位置，EPM中的列表模型pCTR比点模型pCTR提高了0.0036的AUC，并且其PCOC更接近1。在每个位置，EPM中列表模型的预测结果优于点模型
在美团工业数据集上，生产环境中已经包含了DIN[34]模型的点模型pCTR。因此，论文只需要构建EPM的列表模型来预测CTR，然后与前者进行比较。美团工业数据集上的详细实验结果如表4所示。从结果来看，EPM中的列表模型显著提高了所有位置的AUC，从点模型的0.6485提高到0.7077，并且所有位置的PCOC更接近1。考虑到位置外部性，EPM中的列表模型解决了点模型在第一位置预测低的问题
显然，考虑到外部性（例如广告的展示位置和上下文），EPM中的列表模型在公共Avito数据集和美团工业数据集上的AUC和PCOC指标上表现优于点模型
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Table3.png)
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Table4.png)
机制的性能比较（Q2）
- 为了验证所提出机制在提高平台收入和GMV方面的有效性，论文在两个数据集上实现了GSP和固定位置、GSP和Cross DQN、Score-Weighted VCG和IAS进行比较分析。在公共Avito数据集上，论文选择第1和第7位置的项目作为候选广告，其余三个项目被视为自然商品。此外，论文为每个广告提供模拟出价，并为每个项目提供模拟的每点击pGMV。每个广告的出价独立地从0.5到1.0的均匀分布中采样。同时，自然商品的每点击pGMV独立地从3.5到6.0的均匀分布中采样，广告的每点击pGMV独立地从2.0到4.0的均匀分布中采样。在这两个数据集上，GSP和固定位置基线中的固定位置设置为2。特别指出的是，由于离线模拟系统无法获得不同机制下的实际用户行为数据，这些实验的有效性评估是基于用户对项目的pCTR和pGMV统计得出的。考虑到商业数据的保密性，美团数据集上的实验结果基于GSP和固定位置呈现。公共和工业数据集上的详细实验结果如表5所示
- 从实验结果可以看出，MIAA在所有基线机制中实现了最高的收入和GMV。与GSP和固定位置相比，MIAA实现了显著改进，因为具有更高eCPM或GMV的项目获得了更好的位置，并且广告的支付金额增加。MIAA考虑到自然商品对广告的激励效果，与GSP和Cross DQN相比，实现了更高的pRPM。Score-Weighted VCG在不考虑GMV损失的情况下实现了最大的pRPM。与IAS相比，MIAA考虑到外部性，实现了更高的pRPM和pGMV
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Table5.png)
在线结果
- 论文通过在美团零售配送平台上部署所提出的机制来展示在线实验。在信息流的生产环境中，对于每个页面请求，系统返回一个包含一个广告和三个自然商品的有序列表。有两个基线，一个是GSP和固定位置（即广告插入在第二位置），另一个是GSP和Cross DQN，其中广告被动态分配到某个位置
- 为了展示所提出机制的性能，论文在2023年10月15日至2023年12月15日期间使用5%的生产流量进行了在线A/B测试。在实际生产环境中，论文无法基于广告主进行A/B测试。使用基于用户的流量进行A/B测试使得难以评估所提出机制对广告主出价的激励效果。因此，论文只关注实验中的收入、GMV、RPM和GPM的表现。为了在生产流量中公平高效地比较不同基线，论文将实验组中的广告展示次数与基线中的广告展示次数相等。在线A/B测试的实验结果如表6所示。从结果可以看出，与GSP和固定位置以及GSP和Cross DQN相比，所提出的机制在收入、GMV、RPM和GPM方面实现了最高的提升
Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed/MIAA-Table6.png)