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{如果 }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{如果 }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的效率

整体总结

其他已有机制盘点

关键挑战提出

方案概述

相关工作（论文直译）

问题建模

多槽位拍卖场景

问题公式化建模

NMA拍卖方案

上下文感知列表预测模块

列表深度排序模块

列表可微分排序模块

社会福利最大化辅助损失

Experiments

Experiment Setup

数据集

评估指标

超参数

基线

离线实验

性能比较（RQ1）

消融研究（RQ2）

超参数分析（RQ3）

在线结果

结论