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——(JRegNet)Joint-Auction-in-the-Online-Advertising-Market

整体说明

更多讨论

论文主要贡献

机制相关工作讨论

联合拍卖设计

联合拍卖

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

JRegNet 方案

JRegNet 架构

问题: 实际场景位置分配

JRegNet 的训练

Experiments

基线方法

评估指标

合成数据

真实数据集

未来规划