CA——(MIAA)Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed

参考链接：
- 原始论文：Deep Automated Mechanism Design for Integrating Ad Auction and Allocation in Feed, SIGIR 2024, Meituan

整体思路说明（摘要）

电子商务平台通常会在每个用户的页面浏览请求中展示一个有序列表，其中包含多个自然商品和一个广告。这个列表是广告拍卖和分配过程的结果，直接影响平台的广告收入和商品交易总额（GMV）。具体来说，广告拍卖决定了展示哪个广告以及相应的支付金额，而广告分配则决定了广告和自然商品的展示位置
目前普遍的方法将广告拍卖和分配分为两个独立的阶段，面临两个问题：
- 1）广告拍卖没有考虑外部性，例如实际展示位置和上下文对广告点击率（CTR）的影响；
- 2）广告分配利用拍卖获胜广告的支付金额动态决定展示位置，但无法保持广告的激励兼容性（IC）。例如，在使用传统广义第二价格（GSP）的拍卖阶段，即使获胜广告提高出价，其支付金额也不会改变。这意味着广告无法获得更好的位置，从而失去了在后续广告分配阶段实现更高效用的机会
以往的研究通常只关注其中一个阶段，忽略了这两个阶段的问题，可能导致次优结果
论文提出了一种深度自动化机制：
- 将广告拍卖和分配集成在一起，确保在存在外部性的情况下同时满足IC和个体合理性（IR），并最大化收入和GMV
- 该机制以候选广告和自然商品的有序列表作为输入
  - 对于每个候选广告，通过在自然商品列表的不同位置插入广告生成多个候选分配
  - 对于每个候选分配，列表模型将整个分配作为输入，并输出每个广告和自然商品的预测结果，以建模全局外部性
  - 最后，通过深度神经网络建模的自动化拍卖机制执行，选择最优分配
- 因此，该机制同时决定了广告的排名、支付金额和展示位置
论文机制在离线实验和在线A/B测试中比 SOTA 基线方法实现了更高的收入和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测试中比 SOTA 基线方法实现了更高的收入和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

问题公式化

给定广告主的出价和有序的自然商品列表，论文表示一个广告拍卖与分配机制 $\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}
  $$
对于广告拍卖机制的设计，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}).$$
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对机制中的排序操作进行连续松弛，并输出表示每个候选分配获胜概率的向量
平台的预期收入和GMV可以通过端到端学习方式可微分地计算和优化

外部性感知预测模块（EPM）

外部性感知预测模块（ Externality-aware Prediction Module，EPM）

在大多数传统拍卖机制中，广告的位置和上下文信息只能在拍卖后得知，因此CTR预测模型无法提前获取这些信息。然而，拍卖依赖于预测模型的pCTR。为了解决这种相互依赖问题并获得稳定的分配结果，机制设计基于分离的CTR假设，即广告的最终CTR等于其自身内容的CTR与其位置的CTR的乘积，忽略了上下文商品的影响。因此，在这种假设下，通常使用点模型来预测CTR，该模型不考虑广告展示位置和广告与自然商品之间的相互作用的影响。一些模型相继提出，捕捉局部外部性，仅关注广告的展示位置或广告的局部上下文。为此，论文使用列表预测模块显式建模全局外部性，为每个项目输出更准确的pCTR
第一步 ，对于每个候选广告，通过在有序自然商品列表的不同位置插入广告生成多个候选分配。此步骤对应的时间复杂度为 $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{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$ 个项目
外部性感知预测模块（EPM）以候选分配为输入，并输出分配中每个位置的pCTR。它是独立构建和训练的，不与下游模块耦合。EPM是一个通用框架，可以轻松扩展到多个目标预测，如转化率（CVR）和GMV。下文中的 $g_{j}(\mathbf{a})$ 可以在EPM中同时预测，无需进一步阐述。与点模型相比，列表模型捕捉了全局外部性并输出了更准确的结果，这有助于后续模块实现更好的性能

自动化拍卖模块（AAM）

自动化拍卖模块（Automated Auction Module，AAM）

该模块从所有可能的候选分配中选择最优分配，同时决定广告的排名、支付金额和展示位置。将AMA扩展为深度自动化机制， $\mu$ 和 $\lambda(\cdot)$ 被建模为深度神经网络 $\mu$ -网络和 $\lambda$ -网络，以提高排名公式的表达能力，同时保证IC和IR属性
$\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的比例划分为训练集和测试集

评估指标

论文基于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指标上表现优于点模型

机制的性能比较（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

在线结果

论文通过在美团零售配送平台上部署所提出的机制来展示在线实验。在信息流的生产环境中，对于每个页面请求，系统返回一个包含一个广告和三个自然商品的有序列表。有两个基线，一个是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方面实现了最高的提升

CA——(JRegNet)Joint-Auction-in-the-Online-Advertising-Market

参考论文：Joint Auction in the Online Advertising Market, KDD 2024, Meituan

整体说明

联合拍卖 ：论文提出一种新颖的品牌商供应商与零售商联合拍卖的场景，一个商品可能同时有品牌商和零售商出资，目前使用的广告模式无法同时满足零售商和品牌商供应商的需求
模式建模 ：为了解决这一问题，论文创新性地提出了一种名为 “联合拍卖” 的联合广告模式，允许品牌商供应商和零售商共同竞拍广告位，以满足双方的需求
论文的方案 ：传统的广告拍卖机制并不适用于这种新场景，论文提出了JRegNet ，这是一种用于优化联合拍卖设计的神经网络架构，它可以生成能够实现最优收益，并保证（近似）占优策略激励相容和个体理性的机制
相关实验 ：论文在合成数据和真实数据上进行了多项实验，证明与已知的基线方法相比，论文提出的联合拍卖显著提高了平台的收入

联合拍卖设计

在本节中，论文首先正式介绍联合拍卖的模型，然后将最优机制设计问题转化为学习问题

联合拍卖

在联合拍卖的背景下，每当用户搜索某个关键词时，平台会返回一个包含 $ K $ 个广告位的界面，每个广告位显示一个由零售商和品牌商组成的广告捆绑（）信息。用 $\alpha_k$ 表示第 $ k $ 个广告位的点击率（CTR），其中 $ k \in \{1, \ldots, K\} $。不失一般性，假设 $ 1 > \alpha_1 \geq \cdots \geq \alpha_K > 0 $
有 $ m $ 家零售商和 $ n $ 个品牌商参与联合拍卖。对于零售商 $ i \in M = \{1, \ldots, m\} $ 和品牌商 $ j \in N = \{1, \ldots, n\} $，论文定义一个指示变量 $ \mathbf{1}_{ij} $ 来表示零售商 $ i $ 和品牌商 $ j $ 是否可以组成一个捆绑。具体来说，$ \mathbf{1}_{ij} = 1 $ 表示零售商 $ i $ 和品牌商 $ j $ 存在合作关系。此外，论文用一个矩阵来表示所有零售商和品牌商之间的捆绑关系，其中每个实体是一个定义在零售商和品牌商对上的指示变量（如图 2 示例）。在同一联合拍卖场景中，不同搜索查询样本的矩阵中的联合拍卖关系可能不同
零售商 $ i $ 单次点击价值记为 $ v_{i \cdot } $, 品牌商 $ j $ 单次点击价值记为 $ v_{ \cdot j} $（这些是零售商 $ i $或品牌商 $ j $的私有信息）。假设 $ v_{i \cdot } $ 和 $ v_{ \cdot j} $ 是从一个已知的分布中抽取的（理解：论文中假设品牌商和零售商价值服从同一个分布），取值空间为 $ V_{i \cdot } $ 和 $ V_{ \cdot j} $。价值 profile 可以表示为 $ \boldsymbol{v} = (v_{1 \cdot}, \ldots, v_{m \cdot}, v_{\cdot 1}, \ldots, v_{\cdot n}) \in \mathbb{V} $，其中 $ \mathbb{V} = V_{1 \cdot} \times \cdots \times V_{m \cdot} \times V_{\cdot 1} \times \cdots \times V_{\cdot n} $。此外，用 $ \boldsymbol{v}_{-i \cdot } $ 表示除零售商 $ i $ 之外的价值 profile ，即 $ \boldsymbol{v}_{-i \cdot } = (v_{1 \cdot}, \ldots, v_{(i-1) \cdot}, v_{(i+1) \cdot}, \ldots, v_{\cdot n}) $。类似的定义也适用于品牌商 $ j $。由于零售商（或品牌商）可能进行策略性竞价，论文用 $ b_{i \cdot } $ 和 $ b_{ \cdot j} $ 表示竞价价格。类似地，用 $ \boldsymbol{b} $、$ \boldsymbol{b}_{-i \cdot } $ 和 $ \boldsymbol{b}_{-j} $ 表示相关的竞价特征
- 问题：为什么使用 $ v_{i \cdot } $ 而不是 $ v_{i} $ 表示零售商 $i$ 的单次点击价值？
- 回答：是为了方便和品牌商 $ j $ 的单次点击价值 $ v_{ \cdot j} $ 区分开，否则下标相同无法区分（个人理解：实际上加个上标可能是最好的选择，因为这种表达容易让人觉得是一个函数，且 $\cdot$ 看起来像是另一个变量的样子，难以理解）
在联合拍卖的设置中，拍卖机制 $ \mathcal{M}(g, p) $ 包含两部分：分配规则 $ g $ 和支付规则 $ p $。具体来说，$ g = ((g_{i \cdot })_{i \in M}, (g_{ \cdot j})_{j \in N}) $，其中 $ g_{i \cdot } $ 和 $ g_{ \cdot j} $：$ \mathbb{V} \rightarrow \mathbb{R}^{+} \cup \{0\} $ 表示零售商 $ i $ 和品牌商 $ j $ 可以获得的预期点击率。即：
$$
g_{i \cdot }(\boldsymbol{b}) = \sum_{k=1}^{K} s_{i \cdot k}(\boldsymbol{b}) \alpha_k,
$$
其中 $ s_{i \cdot k}(\boldsymbol{b}) $ 表示零售商 $ i $ 被分配到第 $ k $ 个广告位的概率。支付规则 $ p = ((p_{i \cdot })_{i \in M}, (p_{ \cdot j})_{j \in N}) $ 表示零售商 $ i $ 和品牌商 $ j $ 需要支付的金额。与传统广告拍卖不同，在联合拍卖中，每个广告位最多分配给一个捆绑，每个捆绑最多获得一个广告位。换句话说，一家零售商和一个品牌商组成一个捆绑，展示在一个广告位上
每家零售商 $ i $ 和每个品牌商 $ j $ 的目标都是最大化自身效用，零售商的效用定义为拟线性形式：
$$
u_{i \cdot }(v_{i \cdot }; \boldsymbol{b}) = v_{i \cdot }(g_{i \cdot }(\boldsymbol{b})) - p_{i \cdot }(\boldsymbol{b}), \quad \forall i \in M
$$
- 理解：品牌商的效用形式类似可表示为：
  $$
  u_{\cdot j}(v_{\cdot j}; \boldsymbol{b}) = v_{\cdot j}(g_{\cdot j}(\boldsymbol{b})) - p_{\cdot j}(\boldsymbol{b}), \quad \forall j \in N
  $$

注：论文关注满足占优策略激励相容性（DSIC）和个体理性（IR）的机制

占优策略激励相容性保证对于任何竞标者，真实竞价能带来最大效用，即：
- 定义 1（DSIC） ：如果对于任何零售商 $ i $和品牌商 $ j $，无论其他竞标者如何报告，真实报告都能最大化其效用，则联合拍卖是显性策略激励相容的。即：
  $$
  \color{red}{u_{i \cdot }(v_{i \cdot }; (v_{i \cdot }, \boldsymbol{b}_{-i \cdot })) \geq u_{i \cdot }(v_{i \cdot }; (b_{i \cdot }, \boldsymbol{b}_{-i \cdot }))}, \quad \forall i \in M, v_{i \cdot } \in V_{i \cdot }, b_{i \cdot } \in V_{i \cdot }, \boldsymbol{b}_{-i \cdot } \in \mathbb{V}_{-i \cdot }
  $$
- 且：
  $$
  \color{red}{u_{ \cdot j}(v_{ \cdot j}; (v_{ \cdot j}, \boldsymbol{b}_{- \cdot j})) \geq u_{ \cdot j}(v_{ \cdot j}; (b_{ \cdot j}, \boldsymbol{b}_{- \cdot j}))}, \quad \forall j \in N, v_{ \cdot j} \in V_{ \cdot j}, b_{ \cdot j} \in V_{ \cdot j}, \boldsymbol{b}_{- \cdot j} \in \mathbb{V}_{- \cdot j}
  $$
个体理性意味着任何拍卖参与者都能获得非负效用，定义如下：
- 定义 2（IR） ：联合拍卖是事后个体理性的，如果任何零售商 $ i $（或品牌商 $ j $）在真实参与时获得非负效用，即：
  $$
  \color{red}{u_{i \cdot }(v_{i \cdot }; (v_{i \cdot }, \boldsymbol{b}_{-i \cdot })) \geq 0}, \quad \forall i \in M, \forall v_{i \cdot } \in V_{i \cdot }, \forall \boldsymbol{b}_{-i \cdot } \in \mathbb{V}_{-i \cdot },
  $$
- 且：
  $$
  \color{red}{u_{ \cdot j}(v_{ \cdot j}; (v_{ \cdot j}, \boldsymbol{b}_{- \cdot j})) \geq 0}, \quad \forall j \in N, \forall v_{ \cdot j} \in V_{ \cdot j}, \forall \boldsymbol{b}_{- \cdot j} \in \mathbb{V}_{- \cdot j}.
  $$
- 在满足 DSIC 和 IR 的联合拍卖中，平台的预期收益等于所有零售商和品牌商的总支付，定义为：
  $$
  rev := \mathbb{E}_{\boldsymbol{v} \sim F}\left[\sum_{i=1}^{m} p_{i \cdot }(\boldsymbol{v}) + \sum_{j=1}^{n} p_{ \cdot j}(\boldsymbol{v})\right],
  $$
- 其中 $ F $ 是所有零售商和品牌商价值的联合分布
最优联合拍卖设计的目标是找到一个拍卖机制 ，在满足 DSIC 和 IR 条件的同时，最大化预期收益

基于学习的联合拍卖设计问题建模

论文将设计最优联合拍卖的问题表述为一个学习问题。首先，为了满足 DSIC 条件，论文引入了事后遗憾（ex-post regret）的概念。固定其他竞标者的竞价，零售商 $ i $ 的事后遗憾是其通过虚假报告可以获得的效用最大增量，即（注：原始文章中错误的使用了 $rgt_{i \cdot }\color{red}{(\boldsymbol{v})}$，从后面的文章和RegretNet文章看，事后遗憾 $rgt_{i \cdot }$ 与 $\color{red}{(\boldsymbol{v})}$ 无关，是关于 $\color{red}{(\boldsymbol{v})} \sim F$的期望，接下来，博客内容将对该符号进行修正）：
$$
rgt_{i \cdot } = \mathbb{E}_{\boldsymbol{v} \sim F}\left[\max_{ {v’}_{i \cdot } \in V_{i \cdot } } u_{i \cdot }(v_{i \cdot }; ({v’}_{i \cdot }, \boldsymbol{v}_{-i \cdot })) - u_{i \cdot }(v_{i \cdot }; \boldsymbol{v})\right].
$$
- 品牌商 $ j $ 的事后遗憾可以类似以上定义
- 特别说明：$V_{i \cdot }$ 是价值取值空间（价值空间，包含所有可能的价值集合）
- 个人理解：$rgt_{i \cdot } \geq 0 $ 可衡量一个机制的满足 DSIC 条件的程度。任意一个 $\boldsymbol{v}$ 都是一个包含所有竞拍者真实私有价值 ，$u_{i \cdot }$ 则与机制 $\mathcal{M}(g,p)$ 有关，由于 $\boldsymbol{v}$ 是竞拍者真实私有估值（相当于都在说真话），此时满足 DSIC 条件的机制下，应该有事后遗憾 $rgt_{i \cdot } = 0 $。从更加广义的松弛视角看，机制越满足 DSIC 条件，则事后遗憾值应该越小，最小值为0
- 模型训练中，$rgt_{i \cdot }$ 越小的机制越满足 DSIC 条件
因此，拍卖机制满足 DSIC 条件当且仅当 $ rgt_{i \cdot } = 0 $ 和 $ rgt_{ \cdot j} = 0 $ 对所有零售商和品牌商成立。此外，我们可以将设计最优联合拍卖的问题表述为约束优化问题（1） ：
$$
\begin{align}
\min_{(g,p) \in \mathcal{M} } &-\mathbb{E}_{\boldsymbol{v} \sim F}\left[\sum_{i=1}^{m} p_{i \cdot }(\boldsymbol{v}) + \sum_{j=1}^{n} p_{ \cdot j}(\boldsymbol{v})\right] \\
\text{s.t.} \quad &rgt_{i \cdot } = 0, \quad i = 1, \ldots, m, \\
&rgt_{ \cdot j} = 0, \quad j = 1, \ldots, n,
\end{align}
$$
其中 $ \mathcal{M} $ 是满足 IR 的所有联合拍卖机制的集合。由于约束复杂，该优化问题通常难以直接求解。为了解决这个优化问题，论文通过参数 $ w \in \mathbb{R}^d $（其中 $ d $ 是参数 $ w $ 的维度）将拍卖机制参数化为 $ \mathcal{M}^w(g^w, p^w) \subseteq \mathcal{M}(g, p) $。然后，论文转而计算机制 $ \mathcal{M}^w(g^w, p^w) $，通过优化参数 $ w $ 来最大化预期收益 $ \mathbb{E}_{\boldsymbol{v} \sim F}\left[\sum_{i=1}^{m} p_{i \cdot }^w(\boldsymbol{v}) + \sum_{j=1}^{n} p_{ \cdot j}^w(\boldsymbol{v})\right] $，同时满足 DSIC 和 IR 条件
给定一个样本集合 $ \mathcal{L} $，包含从联合分布 $ F $ 中抽取的 $ L $ 个价值 profile 集合 $\{ (\color{blue}{v_{1\cdot}^{(\ell)},v_{2\cdot}^{(\ell)},\cdots, v_{M\cdot}^{(\ell)}}, \color{red}{v_{\cdot 1}^{(\ell)},v_{\cdot 2}^{(\ell)},\cdots, v_{\cdot N}^{(\ell)}}) \}_{l=1}^L$，其中，每个样本 $\boldsymbol{v}^{(\ell)} = (\color{blue}{v_{1\cdot}^{(\ell)},v_{2\cdot}^{(\ell)},\cdots, v_{M\cdot}^{(\ell)}}, \color{red}{v_{\cdot 1}^{(\ell)},v_{\cdot 2}^{(\ell)},\cdots, v_{\cdot N}^{(\ell)}})$ ，机制 $ \mathcal{M}^w(g^w, p^w) $ 的零售商 $ i $ 的实证事后遗憾估计为：
$$
\widehat{rgt}_{i \cdot }(w) = \frac{1}{L} \sum_{l=1}^{L} \left[\max_{ {v’}_{i \cdot } \in V_{i \cdot } } u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; ({v’}_{i \cdot }, \boldsymbol{v}_{-i \cdot }^{(\ell)})) - u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; \boldsymbol{v}^{(\ell)})\right].
$$
- 类似地，品牌商 $ j $ 的实证事后遗憾估计为：
  $$
  \widehat{rgt}_{ \cdot j }(w) = \frac{1}{L} \sum_{l=1}^{L} \left[\max_{ {v’}_{ \cdot j } \in V_{ \cdot j } } u_{ \cdot j }^w(v_{ \cdot j }^{(\ell)}; ({v’}_{ \cdot j }, \boldsymbol{v}_{- \cdot j }^{(\ell)})) - u_{ \cdot j }^w(v_{ \cdot j }^{(\ell)}; \boldsymbol{v}^{(\ell)})\right].
  $$
将约束优化问题 (1) 重写为：
$$
\begin{align}
\min_{w \in \mathbb{R}^{d_w} } &-\frac{1}{L} \sum_{l=1}^{L} \left[\sum_{i=1}^{m} p_{i \cdot }^w(\boldsymbol{v}^{(\ell)}) + \sum_{j=1}^{n} p_{ \cdot j}^w(\boldsymbol{v}^{(\ell)})\right] \\
\text{s.t} \quad &\widehat{rgt}_{i \cdot }(w) = 0, \quad i = 1, \ldots, m, \\
&\widehat{rgt}_{ \cdot j}(w) = 0, \quad j = 1, \ldots, n.
\end{align}
$$
此外，通过网络架构，论文确保 IR 条件成立，具体细节将在JRegNet建模中描述

JRegNet 方案

在本节中，论文将最优联合拍卖设计建模为学习问题后，提出了一种称为联合遗憾网络（JRegNet）的神经网络架构，用于最优联合拍卖设计

JRegNet 架构

本小节介绍为联合拍卖场景设计的 JRegNet 网络架构，如图 3 所示。JRegNet 架构包含两部分：编码分配规则的分配网络和编码支付规则的支付网络。两个网络的输出用于计算竞标者的效用、收益、遗憾以及整个网络的损失函数值。接下来，论文详细介绍 JRegNet 的主要组成部分
JRegNet的输入 ：在 JRegNet 中，神经网络以 $ \mathbf{1}_{ij} $、$ e_{i \cdot k} $ 和 $ e_{ \cdot jk} $ 作为输入，定义为：
$$
\begin{cases}
e_{i \cdot k} = \alpha_k b_{i \cdot }, & \forall i \in M, \forall k \in \{1, \ldots, K\}, \\
e_{ \cdot jk} = \alpha_k b_{ \cdot j}, & \forall j \in N, \forall k \in \{1, \ldots, K\},
\end{cases}
$$
- 其中 $ e_{i \cdot k} $ 和 $ e_{ \cdot jk} $ 分别表示零售商 $ i $ 和品牌商 $ j $ 在广告位 $ k $ 上的预期竞价（理解：$CPM = CTR \times Bid_\text{CPC}$）
- $ \{\mathbf{1}_{ij}\}_{i \in M, j \in N} $ 表示零售商和品牌商之间的联合关系矩阵。由于联合关系在不同搜索请求样本中可能不同（即使在同一联合拍卖场景下，即相同的零售商和品牌商），JRegNet 将 $ \{\mathbf{1}_{ij}\}_{i \in M, j \in N} $ 作为输入之一
JRegNet的输出 ：在 JRegNet 中，为了适应联合拍卖场景，JRegNet的输出分几个部分
- 分配网络首先输出捆绑的分配概率矩阵 $ A_{Q,K+1} $：矩阵 $ A $ 包含每个由零售商和品牌商组成的捆绑在每个广告位上的分配概率
- 在获得矩阵 $ A $ 后，分配网络进一步输出竞标者的分配概率矩阵 $ S_{M+N,K} $：矩阵 $ S $ 包含每个零售商和品牌商在每个广告位上的分配概率
- 随后，支付网络输出所有竞标者的支付矩阵 $ P_{M+N} $：矩阵 $ P $ 包含每个零售商竞标者和品牌商竞标者的支付金额
计算捆绑的分配概率矩阵 $ A $ ：为了计算竞标者的分配概率矩阵 $ S $，论文首先需要计算捆绑的分配概率矩阵 $ A $，因为需要通过 $ A $ 实现若干约束。然后，基于 $ A $ 计算 $ S $。此外，矩阵 $ A $ 可用于将广告位分配给由零售商和品牌商组成的捆绑。此部分的输入是通过前向传播获得的矩阵 $ C $ 和 $ R $，如图 3 中的黄色和紫色神经元所示
- 论文用 $ Q $ 表示捆绑的总数，其中捆绑 $ q \in \{1, \ldots, Q\} $ 对应于矩阵 $ \{\mathbf{1}_{ij}\} $ 中所有值为 1 的条目按行遍历后的第 $ q $ 个条目。分配概率矩阵 $ A $ 中捆绑 $ q $ 在广告位 $ k $ 上的分配概率定义为 $ a_{qk} $
- 在论文的模型中，输出矩阵 $ A $ 必须满足两个约束：
  - (a) 每个广告位最多分配给一个捆绑，即 $ \sum_{q=1}^{Q} a_{qk} \leq 1, \forall k \in \{1, \ldots, K\} $；
  - (b) 每个捆绑最多获得一个广告位，即 $ \sum_{k=1}^{K} a_{qk} \leq 1, \forall q \in \{1, \ldots, Q\} $
- 为了强制满足约束 (a) 和 (b) ，论文将分配概率矩阵 $ A $ 设计为一个双随机矩阵（bi-stochastic matrix，行和列的和都等于1的矩阵，论文和 RegretNet 中将双随机矩阵的行列和定义为小于等于1）。为了将 $ A $ 构造为双随机矩阵，需要对 $ C $ 和 $ R $ 进行一些操作。矩阵 $ C $ 通过 softmax 函数按列归一化为矩阵 $ \tilde{C} $，矩阵 $ R $ 通过 softmax 函数按行归一化为矩阵 $ \tilde{R} $。因为在联合拍卖场景中，特定的捆绑可能不会被分配到任何广告位，论文在 softmax 归一化中为每个捆绑添加了一个虚拟神经元。虚拟神经元的输出表示捆绑未被分配到任何广告位的概率。矩阵 $ \tilde{C} $ 和 $ \tilde{R} $ 中的条目分别定义为 $ \tilde{c}_{qk} $ 和 $ \tilde{r}_{qk} $。然后，论文通过以下方式计算矩阵 $ A $ 中每个捆绑的分配概率：
  $$
  a_{qk} = \min\{\tilde{c}_{qk}, \tilde{r}_{qk}\}, \quad \forall q \in \{1, \ldots, Q\}, \forall k \in \{1, \ldots, K+1\}.
  $$
  - 问题：为什么是取 $\min$?
  - 回答：可以通过引理1得到证明，取 $\min$ 以后得到的是一个双随机矩阵（bi-stochastic matrix）？
根据引理1 ，以这种方式构造的矩阵 $ A $ 是一个双随机矩阵（bi-stochastic matrix）。计算分配概率矩阵 $ A $ 的具体公式为：
$$
a_{qk} = \varphi^{BS}_{qk}(C, R) = \min \left\{ \frac{e^{c_{qk} } }{\sum_{t=1}^{Q} e^{c_{tk} } }, \frac{e^{r_{qk} } }{\sum_{t=1}^{K+1} e^{r_{qt} } } \right\},
$$
- 其中 $ \frac{e^{c_{qk} } }{\sum_{t=1}^{Q} e^{c_{tk} } } $ 和 $ \frac{e^{r_{qk} } }{\sum_{t=1}^{K+1} e^{r_{qt} } } $ 分别是 $ c_{qk} $ 的行归一化和 $ r_{qk} $ 的列归一化，索引 $ K+1 $ 对应捆绑未被分配到任何广告位的情况。这部分内容如图 3 所示
引理 1 ：矩阵 $ \varphi^{BS}_{qk}(c, r) $ 对于所有 $ c, r \in \mathbb{R}^{QK} $ 是双随机的。对于任何双随机矩阵 $ a \in [0,1]^{QK} $，存在 $ c, r \in \mathbb{R}^{QK} $ 使得 $ a = \varphi^{BS}_{qk}(c, r) $
- 注：双随机矩阵是指行和列的和都等于1的矩阵，论文和 RegretNet 中将双随机矩阵的行列和定义为小于等于1 ，所以引理1才能成立，否则是不成立的
将分配概率矩阵 $ A $ 转换为分配概率矩阵 $ S $ ：在竞标者的分配概率矩阵 $ S $ 中，零售商 $ i $ 和品牌商 $ j $ 在广告位 $ k $ 上的分配概率分别记为 $ s_{i \cdot k} $ 和 $ s_{ \cdot jk} $。在获得捆绑的分配概率矩阵 $ A $ 后，通过以下方式计算 $ S $ 中的分配概率：
$$
\begin{cases}
s_{i \cdot k} = \sum_{q \in Q_{i \cdot } } a_{qk}, & \forall k \in \{1, \ldots, K\}, \\
s_{ \cdot jk} = \sum_{q \in Q_{ \cdot j} } a_{qk}, & \forall k \in \{1, \ldots, K\},
\end{cases}
$$
- 其中 $ Q_{i \cdot } $ 和 $ Q_{ \cdot j} $ 分别表示包含零售商 $ i $ 和品牌商 $ j $ 的所有捆绑的集合。即，零售商 $ i $ 在广告位 $ k $ 上的分配概率是所有包含零售商 $ i $ 的捆绑在广告位 $ k $ 上的分配概率之和，品牌商 $ j $ 的计算类似
- 理解：原始分配时为每个捆绑 $q$ 分配概率，上述转换是在将捆绑分配概率转换给对应的零售商和品牌商，对捆绑 $q \in Q_{i \cdot } $ 做积分是因为每个品牌商和零售商可能都有多个Bundle 在同时竞争同一个位置 $k$
计算支付矩阵 $ P $ ：在获得竞标者的分配概率矩阵 $ S $ 后，论文将其传播到支付网络以计算支付矩阵 $ P $，如图 3 所示。在矩阵 $ P \in \mathbb{R}_{\geq 0}^{I+J} $ 中，前 $ m $ 行和后 $ n $ 行分别表示零售商和品牌商的支付金额。矩阵 $ P $ 中零售商 $ i $ 和品牌商 $ j $ 的支付分别记为 $ p_{i \cdot } $ 和 $ p_{ \cdot j} $。支付金额通过以下方式计算：
$$
\begin{cases}
p_{i \cdot } = \tilde{p}_{i \cdot } \left( \sum_{k=1}^{K} s_{i \cdot k} e_{i \cdot k} \right), & \forall i \in M, \\
p_{ \cdot j} = \tilde{p}_{ \cdot j} \left( \sum_{k=1}^{K} s_{ \cdot jk} e_{ \cdot jk} \right), & \forall j \in N,
\end{cases}
$$
- 其中 $ \tilde{p}_{i \cdot } \in [0,1] $ 和 $ \tilde{p}_{ \cdot j} \in [0,1] $ 是通过 sigmoid 函数计算的归一化因子，如图 3 中的绿色方块所示。在满足 DSIC 的条件下，由于 $ \tilde{p}_{i \cdot } \in [0,1] $，且零售商的效用 $ u_{i \cdot } = \sum_{k=1}^{K} s_{i \cdot k} e_{i \cdot k} - p_{i \cdot } $，每家零售商的效用必须非负，满足 IR 条件。品牌商的证明类似

问题: 实际场景位置分配

问题：实际场景中，如何根据概率分配矩阵实现位置分配？按照分配概率做采样还是做 argmax?
回答：TODO，待确认

JRegNet 的训练

本小节介绍 JRegNet 的训练过程，包括目标函数的转换、训练样本的划分、最优虚假报告的寻找以及模型参数和拉格朗日乘子的更新
从约束优化问题到无约束优化问题的转换 ：为了训练 JRegNet，论文首先需要一个目标函数。约束优化目标如式 (3) 所示。论文使用增广拉格朗日方法将约束优化问题转化为无约束优化问题，从而得到以下目标函数：
$$
\begin{align}
C_{\rho}(w; \lambda) = &-\frac{1}{L} \sum_{l=1}^{L} \left[ \sum_{i=1}^{m} p_{i \cdot }^w(\boldsymbol{v}^{(\ell)}) + \sum_{j=1}^{n} p_{ \cdot j}^w(\boldsymbol{v}^{(\ell)}) \right] \\
&+ \sum_{i=1}^{m} \lambda_{i \cdot } \widehat{rgt}_{i \cdot }(w) + \sum_{j=1}^{n} \lambda_{ \cdot j} \widehat{rgt}_{ \cdot j}(w) \\
&+ \frac{\rho}{2} \sum_{i=1}^{m} (\widehat{rgt}_{i \cdot }(w))^2 + \frac{\rho}{2} \sum_{j=1}^{n} (\widehat{rgt}_{ \cdot j}(w))^2,
\end{align}
$$
- 其中 $ \lambda \in \mathbb{R}^n $ 是拉格朗日乘子，$ \rho > 0 $ 是惩罚因子
- 问题：在训练时如何计算 $\widehat{rgt}_{i \cdot }(w)$ 和 $\widehat{rgt}_{ \cdot j}(w)$ ?
- 回答：$\widehat{rgt}_{i \cdot }(w)$ 计算公式为
  $$
  \widehat{rgt}_{i \cdot }(w) = \frac{1}{L} \sum_{l=1}^{L} \left[\max_{ {v’}_{i \cdot } \in V_{i \cdot } } u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; ({v’}_{i \cdot }, \boldsymbol{v}_{-i \cdot }^{(\ell)})) - u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; \boldsymbol{v}^{(\ell)})\right].
  $$
  - 类似地，品牌商 $ j $ 的实证事后遗憾$\widehat{rgt}_{ \cdot j}(w)$ 估计为：
    $$
    \widehat{rgt}_{ \cdot j }(w) = \frac{1}{L} \sum_{l=1}^{L} \left[\max_{ {v’}_{ \cdot j } \in V_{ \cdot j } } u_{ \cdot j }^w(v_{ \cdot j }^{(\ell)}; ({v’}_{ \cdot j }, \boldsymbol{v}_{- \cdot j }^{(\ell)})) - u_{ \cdot j }^w(v_{ \cdot j }^{(\ell)}; \boldsymbol{v}^{(\ell)})\right].
    $$
  - 其中 $V_{ i \cdot }, V_{ \cdot j }$ 是各自出价可能的取值集合（即取值空间），猜测可以通过随机采样几个值 ，或提前定义几个按照固定间隔采样取值，再取他们对应效用函数中的最大值即可作为近似最大效用函数
在获得训练所需的目标函数后，论文需要划分样本以训练 JRegNet
训练样本的划分 ：训练样本 $ \mathcal{L} $ 被随机划分为大小为 $ B $ 的 minibatchs。用 $ T $ 表示总迭代次数。对于每次迭代 $ t \in \{1, \ldots, T\} $，论文采样一个 minibatchs $ \mathcal{L}_t $，记为 $ \mathcal{L}_t = \{\boldsymbol{v}^{(1)}, \ldots, \boldsymbol{v}^{(B)}\} $，并将其输入 JRegNet 进行训练，直到该划分中的所有 minibatchs 都被使用。之后，训练样本 $ \mathcal{L} $ 被重新随机划分为新的 minibatchs。重复上述过程，直到完成所有迭代
在训练过程中，为了计算 $ C_{\rho}(w; \lambda) $ 中的遗憾，论文需要找到最大化遗憾的最优虚假报告
寻找最优虚假报告 ：为了计算最优虚假报告，论文使用梯度上升法。对于每个 minibatchs ，通过多次梯度上升计算每个零售商 $ i $ 或品牌商 $ j $ 以及每个价值 profile $ \ell $ 的虚假报告 $ {v’}_{i \cdot }^{(\ell)} $ 或 $ {v’}_{ \cdot j}^{(\ell)} $，并保留所有虚假报告以初始化下一轮的虚假报告。梯度上升的公式如下（其中 $ \gamma > 0 $）：
$$
\begin{cases}
{v’}_{i \cdot }^{(\ell)} = {v’}_{i \cdot }^{(\ell)} + \gamma \nabla_{ {v’}_{i \cdot } } \left. u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; ({v’}_{i \cdot }, \boldsymbol{v}_{-i \cdot }^{(\ell)})) \right|_{ {v’}_{i \cdot } = {v’}_{i \cdot }^{(\ell)} }, \\
{v’}_{ \cdot j}^{(\ell)} = {v’}_{ \cdot j}^{(\ell)} + \gamma \nabla_{ {v’}_{ \cdot j} } \left. u_{ \cdot j}^w(v_{ \cdot j}^{(\ell)}; ({v’}_{ \cdot j}, \boldsymbol{v}_{- \cdot j}^{(\ell)})) \right|_{ {v’}_{ \cdot j} = {v’}_{ \cdot j}^{(\ell)} },
\end{cases}
$$
更新模型参数和拉格朗日乘子。随后，我们可以计算 $ C_{\rho}(w; \lambda) $ 的值，执行反向传播并更新神经网络参数 $ w $ 以最小化 $ C_{\rho}(w; \lambda) $。此外，在模型训练过程中，每隔固定次数的迭代更新拉格朗日乘子：
$$
\begin{cases}
\lambda_{i \cdot }^{t+1} = \lambda_{i \cdot }^t + \rho^t \widehat{rgt}_{i \cdot }(w^{t+1}), & \forall i \in M, \\
\lambda_{ \cdot j}^{t+1} = \lambda_{ \cdot j}^t + \rho^t \widehat{rgt}_{ \cdot j}(w^{t+1}), & \forall j \in N,
\end{cases}
$$
- 其中 $ t $ 表示迭代次数，$ \widehat{rgt}_{i \cdot }(w) $ 和 $ \widehat{rgt}_{ \cdot j}(w) $ 是基于式 (2) 在 minibatchs $ \mathcal{S}_t $ 上计算的实证遗憾。模型参数和拉格朗日乘子的更新交替进行。训练 JRegNet 的具体完整算法流程如算法 1 所示
对于固定的 $ \lambda^t $，$ C_{\rho} $ 关于 $ w $ 的梯度可以表示为：
$$
\begin{align}
\nabla_w C_{\rho}(w; \lambda^t) = &-\frac{1}{B} \sum_{\ell=1}^{B} \left[ \sum_{i=1}^{m} \nabla_w p_{i \cdot }^w(\boldsymbol{v}^{(\ell)}) + \sum_{j=1}^{n} \nabla_w p_{ \cdot j}^w(\boldsymbol{v}^{(\ell)}) \right] \\
&+ \sum_{\ell=1}^{B} \left[ \sum_{i=1}^{m} \lambda_{i \cdot }^t g_{\ell,i \cdot } + \sum_{j=1}^{n} \lambda_{ \cdot j}^t g_{\ell, \cdot j} \right] \\
&+ \rho \sum_{\ell=1}^{B} \left[ \sum_{i=1}^{m} \widehat{rgt}_{i \cdot }(w) g_{\ell,i \cdot } + \sum_{j=1}^{n} \widehat{rgt}_{ \cdot j}(w) g_{\ell, \cdot j} \right],
\end{align}
$$
- 其中：
  $$
  \begin{cases}
  g_{\ell,i \cdot } = \nabla_w \left[ \max_{ {v’}_{i \cdot } \in V_{i \cdot } } u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; ({v’}_{i \cdot }, \boldsymbol{v}_{-i \cdot }^{(\ell)})) - u_{i \cdot }^w(v_{i \cdot }^{(\ell)}; \boldsymbol{v}^{(\ell)}) \right], \\
  g_{\ell, \cdot j} = \nabla_w \left[ \max_{ {v’}_{ \cdot j} \in V_{ \cdot j} } u_{ \cdot j}^w(v_{ \cdot j}^{(\ell)}; ({v’}_{ \cdot j}, \boldsymbol{v}_{- \cdot j}^{(\ell)})) - u_{ \cdot j}^w(v_{ \cdot j}^{(\ell)}; \boldsymbol{v}^{(\ell)}) \right].
  \end{cases}
  $$

Experiments

本节通过实证实验评估联合广告模型及JRegNet的有效性。实验运行于配备NVIDIA GPU核心的计算集群上

基线方法

论文将JRegNet与以下基线进行比较：
- RegretNet ：一种用于传统广告拍卖（仅包含零售商）的神经网络架构，可设计近似DSIC机制并实现最优收入
- 独立遗憾网络（JRegNet） ：一种广告拍卖场景下的最优机制设计神经网络架构，其中零售商与品牌商作为独立候选者竞争不同广告位（即每个广告位仅展示零售商或品牌商广告，此场景实际中不存在）
- VCG ：一种满足DSIC和IR的经典机制。实验中直接将其应用于联合广告场景
需说明的是，RegretNet的竞拍者仅为零售商；其他机制的竞拍者同时包含零售商与品牌商，其余属性均相同

评估指标

对任意给定的数据集 $ \mathcal{L} $，包含从联合分布 $ F $ 中抽取的 $ L $ 个价值 profile $\{ (\color{blue}{v_{1\cdot}^{(\ell)},v_{2\cdot}^{(\ell)},\cdots, v_{M\cdot}^{(\ell)}}, \color{red}{v_{\cdot 1}^{(\ell)},v_{\cdot 2}^{(\ell)},\cdots, v_{\cdot N}^{(\ell)}}) \}_{l=1}^L$，其中，每个样本 $\boldsymbol{v}^{(\ell)} = (\color{blue}{v_{1\cdot}^{(\ell)},v_{2\cdot}^{(\ell)},\cdots, v_{M\cdot}^{(\ell)}}, \color{red}{v_{\cdot 1}^{(\ell)},v_{\cdot 2}^{(\ell)},\cdots, v_{\cdot N}^{(\ell)}})$
采用以下指标评估各方法性能：
- 竞拍者平均经验事后遗憾值 ：
  $$
  rgt := \frac{1}{n+m}\left(\sum_{i=1}^{m} rgt_{i\cdot} + \sum_{j=1}^{n} rgt_{\cdot j}\right)
  $$
- 经验收入 ：
  $$
  rev := \frac{1}{L}\sum_{\ell=1}^{L}\left[\sum_{i=1}^{m} p_{i\cdot}^{w}\left(\boldsymbol{v}^{(\ell)}\right) + \sum_{j=1}^{n} p_{\cdot j}^{w}\left(\boldsymbol{v}^{(\ell)}\right)\right]
  $$
- 经验社会福利 ：
  $$
  sw := \frac{1}{L}\sum_{\ell=1}^{L}\left(\sum_{i=1}^{m}\sum_{k=1}^{K} s_{i.k}^{(\ell)}\alpha_{k}v_{i\cdot}^{(\ell)} + \sum_{j=1}^{n}\sum_{k=1}^{K} s_{\cdot jk}^{(\ell)}\alpha_{k}v_{\cdot j}^{(\ell)}\right)
  $$

合成数据

实现细节

为每组实验创建训练集与测试集。训练集中， minibatchs size $ B = 128 $，迭代次数为200,000， minibatchs 数量为5,000；测试集中， minibatchs size 为128， minibatchs 数量为100。因此，训练样本 size $ \mathcal{L} = 640,000 $，测试样本 size 为12,800
所有合成数据实验中，零售商与品牌商的联合关系矩阵 $\{\mathbf{1}_{ij}\}_{i\in M,j\in N}$ 为每个搜索请求样本随机生成。若某零售商（或品牌商）与任何品牌商（或零售商）无联合关系，则默认其出价为零，因其无法形成展示组合
测试JRegNet时（仅测试阶段），对每位竞拍者，在100组不同初始虚报值上执行2000次梯度上升 ，得到100组经验遗憾值 ，取最大值作为该竞拍者的经验遗憾值。RegretNet、JRegNet与JRegNet的实验结果均为测试样本上3次运行的平均值
- 问题：测试时，虚报值如何采样，均匀采样吗？
- 问题：此时时，每位竞拍者虚报值时，其他竞拍者是否固定为他们的真实出价？
- 问题：训练样本使用的是所有竞拍者的真实出价吗？还是应该包含他们各自的虚假出价？
  - 回答：训练时使用真实估值数据（至少模型会认为大家都在说真话），以计算经验事后遗憾值，训练时的目标就是让事后经验值为0

JRegNet与基线的比较

为验证联合广告模型的优越性及JRegNet的有效性，论文在以下设置中对比JRegNet生成的机制与基线：
- (A) 3 零售商、4品牌商、1广告位（CTR $\boldsymbol{\alpha} = (0.7)$），各零售商与品牌商价值独立取自均匀分布 $ U[0,1] $
- (B) 3 零售商、5品牌商、3广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3, 0.15)$），价值分布同A
- (C) 3 零售商、5品牌商、5广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3, 0.15, 0.1, 0.03)$），价值分布同A
- (D) 4 零售商、5品牌商、3广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3, 0.15)$），价值分布同A
表1展示了设置A至D的实验结果。首先，在所有自动化机制设计方法中，当遗憾值小于0.001时，JRegNet生成的机制收入显著高于RegretNet与JRegNet，表明联合广告模型能较传统模型获得更高收入。此外，在联合广告场景中，JRegNet的收入亦显著优于VCG，尽管存在一定社会福利损失。这说明JRegNet生成的机制在收入方面表现优异，且JRegNet架构有效
为进一步评估联合广告模型及JRegNet性能，论文在不同价值分布、CTR及广告位数量下进行实验

不同价值分布

在设置B下，对三种价值分布重复实验：均匀分布 $ U[0,1] $、正态分布 $ N(0.5, 0.0256) $（$ v \in [0,1] $）、对数正态分布 $ LN(0.1, 1.44) $（$ v \in [0,1] $）。表2结果显示，JRegNet在三种分布下均实现最高收入，表明其机制对不同价值分布具有稳定性与鲁棒性

不同广告位CTR

基于设置B，调整CTR值并运行所有机制：
- B1 ：CTRs $\boldsymbol{\alpha} = (0.4, 0.3, 0.15)$
- B2 ：CTRs $\boldsymbol{\alpha} = (0.5, 0.4, 0.15)$
- B3 ：CTRs $\boldsymbol{\alpha} = (0.5, 0.4, 0.25)$
**图4(a)**显示，CTR增加时JRegNet收入随之提升，且首槽CTR变化的影响大于末槽。在所有设置中，JRegNet生成的机制收入均为最高，证明其对不同CTR仍能保持优异性能
- 【补充】CTR增加时JRegNet收入随之提升，且首槽CTR变化的影响大于末槽的证据：可以看到：**图4(a)**中，依次为首位CTR增大、次位CTR增大、末位CTR增大，最终曲线增长逐渐变慢

不同广告位数量

基于设置D，增减广告位数量：
- D1 ：2广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3)$）
- D2 ：4广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3, 0.15, 0.1)$）
- D3 ：5广告位（CTRs $\boldsymbol{\alpha} = (0.5, 0.3, 0.15, 0.1, 0.03)$）
**图4(b)**显示，JRegNet生成的机制在所有设置中表现最佳，且其收入随广告位数量严格递增，而其他机制未呈现此规律

真实数据集

使用美团电商平台的在线拍卖日志数据训练与评估模型。每次用户搜索查询对应一次广告拍卖。实际场景中，广告系统通过召回、粗排与精排阶段筛选约10个组合作为候选，并从中选取最多10家零售商与10个品牌商，最终通过拍卖机制分配最多5个广告位。因此，论文聚焦于10 零售商、10品牌商、5广告位的设置。由于原始数据中竞拍者数量可变，对部分记录进行截断或填充以确保每样本包含10 零售商与10品牌商（填充竞拍者的点击价值为0）。使用6912组真实样本进行测试，日志数据特征包括：每家零售商与品牌商的出价及ID、零售商与品牌商的联合关系、各广告位的预测CTR
因真实数据与模拟数据的价值函数分布差异，仅用遗憾值衡量DSIC不再适用。为此，采用以下指标评估DSIC： $$
ru := \frac{1}{L}\sum_{\ell=1}^{L}\frac{\sum_{i=1}^{m} rgt_{i\cdot}^{(\ell)} + \sum_{j=1}^{n} rgt_{\cdot j}^{(\ell)}} {\sum_{i=1}^{m} \mu_{i\cdot}^{(\ell)} + \sum_{j=1}^{n} \mu_{\cdot j}^{(\ell)}}
$$
- 其中 $ rgt_{i\cdot} := \max_{v^{\prime}_{i\cdot} \in V_{i\cdot} } u_{i\cdot}(v_{i\cdot}; (v^{\prime}_{i\cdot}, \boldsymbol{v}_{-i\cdot})) - u_{i\cdot}(v_{i\cdot}, \boldsymbol{v}) $（品牌商同理）。$ ru $ 表示虚报带来的效用增长与真实报告的效用之比。对于GSP，测试时采用枚举法[27]获取虚报值（虚报值为 $ \beta v $，$ \beta \in \{0, 0.1, \ldots, 1.9\} $），并选取该集合中能获得最大效用的虚报计算GSP的遗憾值
- 对分子的理解 ：此时也在假设商家出价是真实的，然后看修改商家出价后，商家的遗憾值多大，这个值越小，说明越满足 DSIC 条件
- 对分母的理解 ：分母上是竞拍者（品牌商和零售商）的总效用，用于归一化最终的输出，方便观察影响
使用三个不同时间段的真实数据训练JRegNet，并分别用三个时间点的数据测试。附录A.2的图5与图6展示了训练与测试所用的真实搜索查询样本数量。表3列出了所有真实数据实验中JRegNet、VCG与GSP在测试集上的性能表现（GSP为美团在联合拍卖场景中最初采用的在线机制）
表3显示，在所有真实数据实验中，当 $ ru $ 极小时，JRegNet的收入显著高于VCG；当 $ ru $ 接近时，JRegNet的收入亦显著优于GSP（配对t检验 $ p < 0.05 $）。这些实验证明了JRegNet在真实联合拍卖场景中的有效性。需注意的是，GSP不满足DSIC，导致广告主投标策略复杂化，且联合拍卖场景中其均衡状态难以预测。实验中GSP的收入基于广告主真实投标的假设计算，而均衡状态下广告主的出价低于真实值，因此GSP的实际收入低于表中所示
JRegNet可应用于实际场景。若使用1个GPU与32个CPU的服务器运行此真实设置，训练30,000次迭代约需2至4小时。由于JRegNet的训练可离线进行，尽管离线训练较慢，但调用训练好的模型进行前向传播以获取分配与支付矩阵的速度极快（每搜索查询样本约1至3毫秒），不影响在线部署与决策

未来规划

作者的未来规划：未来研究方向包括将联合拍卖应用于直播销售、多品牌商协作等其他场景
说明：如果能做城市DID实验，观察商家调价行为是否增加/是否有降价情况可能更具说服力

CA——(MIAA)Deep-Automated-Mechanism-Design-for-Integrating-Ad-Auction-and-Allocation-in-Feed

整体思路说明（摘要）

Introduction and Discussion

Preliminary

广告拍卖与分配的场景设置

问题公式化

自动化机制设计

MIAA拍卖机制

外部性感知预测模块（EPM）

自动化拍卖模块（AAM）

可微分排序模块（DSM）

训练与在线服务

Experiments

Experiment Setup

数据集

评估指标

基线

离线实验

外部性建模的性能比较（Q1）

机制的性能比较（Q2）

在线结果

CA——(JRegNet)Joint-Auction-in-the-Online-Advertising-Market

整体说明

更多讨论

论文主要贡献

机制相关工作讨论

联合拍卖设计

联合拍卖

基于学习的联合拍卖设计问题建模

JRegNet 方案

JRegNet 架构

问题: 实际场景位置分配

JRegNet 的训练

Experiments

基线方法

评估指标

合成数据

真实数据集

未来规划