CA——(AMA)Affine-maximizer-auction机制

参考链接：
- 其他参考论文：A Scalable Neural Network for DSIC Affine Maximizer Auction Design, NeurIPS 2023, PKU，Spotlight

AMA是什么？

仿射最大化拍卖（Affine Maximizer Auction, AMA）是一种机制设计，它旨在最大化卖家的收益同时确保买家在占优策略下报价（DSIC，Dominant Strategy Incentive Compatible）和个体理性（IR，Individually Rational）。AMA是Vickrey-Clarke-Groves (VCG) 拍卖的一种泛化形式

分配规则

假设有 $n$ 个买家竞拍一个位置，给定买家出价 $ B $，以及一组预定义的分配方案菜单 $ \mathcal{A} $，AMA选择一个分配方案 $ A^* \in \mathcal{A} $，使得如下仿射福利函数最大：
$$ A^* = \arg\max_{A \in \mathcal{A}} \left( \sum_{i=1}^{n} w_i \cdot u_i(A, B) + \lambda(A) \right) $$
- $ w_i $ 是买家 $ i $ 的权重，$ w_i \in \mathbb{R}_{+} $；
- $ u_i(A, B) $ 是买家 $ i $ 在分配方案 $ A $ 下根据出价 $ B $ 计算的效用。在其他商家出价不变时， $ u_i(A, B) $ 是关于商家自身出价 $b_i$ 是非减函数；
- $ \lambda(A) $ 是对每个分配方案 $ A $ 的增强变量（也称为仿射项），它是一个实数值

计费规则

对于每个买家 $ k $，其需要支付的价格 $ p_k $ 为她在其他买家出价情况下所带来的外部性。具体来说，买家 $ k $ 需要支付的价格为：
$$ p_k = \sum_{i \neq k} w_i \cdot u_i(A_{-k}^*, B_{-k}) + \lambda(A_{-k}^*) - \left( \sum_{i \neq k} w_i \cdot u_i(A^*, B) + \lambda(A^*) \right) $$
- $ A_{-k}^* $ 是去除买家 $ k $ 后最大化其他人仿射福利的分配方案；
- $ B_{-k} $ 表示除买家 $ k $ 外所有买家的出价集合；
- $ A^* $ 是包括买家 $ k $ 在内的最优分配方案
计费规则分析：
- 这个价格计算方法下，如果其他买家的出价保持不变，保证了即使买家 $ k $ 改变她的出价，也不会影响她实际需要支付的价格
- 此外，由于买家的真实估值不会导致负效用，所以这个机制也是个体理性的（IR）

AMA 和 VCG的比较

Vickrey-Clarke-Groves (VCG) 机制：核心目标是最大化社会福利 ，而不是直接优化卖家的收益，其分配规则选择使总效用最大化的方案，支付规则基于买家对其他买家造成的外部性来计算
Affine Maximizer Auction (AMA)机制：核心目标是最大化放射函数 ，AMA是VCG机制的一种泛化形式，它引入了仿射项（affine term）和权重参数，从而允许更灵活地设计拍卖规则，由于引入了仿射项 $ \lambda(A) $，AMA可以在保持DSIC的同时，通过适当选择 $ \lambda(A) $ 来提高卖家的收益
从理论上讲，AMA的收益上限不低于VCG ，因为：
- VCG机制是AMA的一个特例，当 $ w_i = 1 $ 且 $ \lambda(A) = 0 $ 时，AMA退化为VCG
- AMA通过调整 $ w_i $ 和 $ \lambda(A) $，可以在保持DSIC的同时探索更大的收益空间
实际收益取决于具体的买家估值分布、市场环境以及机制设计的细节：
- 如果买家估值分布较为均匀，VCG机制通常已经接近最优收益，AMA的优势可能不明显
- 如果买家估值分布不均匀或市场存在不对称性，AMA可以通过调整 $ \lambda(A) $ 来更好地提取剩余价值，从而实现更高的收益

CA——(JAMA)Joint-Bidding-in-Ad-Auctions

参考链接：
- 参考论文：Joint Bidding in Ad Auctions, pp 344–354, TAMC 2024, Meituan

前置：对文章的整体评价

提出了新颖的供应商与零售商联合拍卖场景
文章中部分内部不是很Solid，比如对原始VCG的分析不太合理
文章缺少对模型细节的详细描述

整体说明

提出问题 ：与传统拍卖方式不同，单个商品可能同时由零售商和供应商赞助，在零售商和供应商联合投标广告位这种现实场景下，传统的机制，如广义第一价格拍卖（GFP）、广义第二价格拍卖（GSP）和迈尔森拍卖，无法直接应用。此外，VCG机制在JAS中会导致负收益（存疑，待讨论）
论文工作 ：
- 论文将这种新颖的广告模式称为联合广告系统（joint advertising system，以下简称JAS）
- 论文修改了VCG的支付规则，创建了一种修正的VCG机制，以保证激励相容性、个体理性和弱预算平衡
- 论文利用仿射最大化拍卖（AMA）的结构和自动机制设计技术来训练联合AMA

讨论

论文定义了零售商和供应商对同一商品出价的全新场景
论文引入了一种创新机制，称为修正的VCG机制（revised VCG mechanism，简称RVCG），它在修改VCG支付规则的同时，满足IC、IR和WBB约束（WBB定义：平台收入不为负）
为了进一步提高收入，论文将AMA推广到联合投标场景，称为联合AMA（JAMA），并采用自动机制设计技术来训练联合AMA的参数，以提高收入
论文通过归一化和调整神经网络结构进一步限制参数的搜索空间，从而提高了模型的扩展性
- VCG机制可以最大化社会福利，而AMA最大化的是加权和 boost 后的社会福利。通过调整参数，AMA可以在保持IC和IR的同时获得比VCG更高的收入

模型与预备知识

在JAS中，有 $n$ 个零售商(Retailer) $R = \{r_1, \ldots, r_n\}$ 和 $m$个供应商(Saller) $S = \{s_1, \ldots, s_m\}$
- 零售商和供应商之间的合作关系可以用一个二分图 $G = (V, E)$ 表示，其中顶点集 $V = R \cup S$ 包含所有零售商和供应商，边集 $E$ 表示零售商和供应商之间的协作关系
- 一条边 $e = (r_i, s_j) \in E$ 意味着供应商 $j$ 为零售商 $i$ 提供商品，或者零售商 $i$ 销售供应商 $j$ 的商品
- $D(r_i) = \{s_j | (r_i, s_j) \in E\}$ 为与零售商 $r_i$ 合作的供应商集合， $C(s_j) = \{r_i | (r_i, s_j) \in E\}$ 为供应商 $s_j$ 的合作零售商集合
假设一次拍卖有$K$ 个广告位，索引为 $k \in \{1, 2, \ldots, K\}$，第k个广告位的点击率为 $\lambda_k$ ，且索引越小的广告位点击率越高，即 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_K \geq 0$
每个零售商 $r_i$ 对每次点击都有一个私人价值 $v_{r_i}$，供应商 $s_j$ 的点击私人价值为 $v_{s_j}$，假设 $v_{r_i}$ 和 $v_{s_j}$都是从一个公开已知的分布 $F(v)$ 中独立同分布抽取的，其概率密度函数为 $f(v)$
分别用 $\mathbf{v}^R = (v_{r_1}, \ldots, v_{r_n})$ 和 $\mathbf{v}^S = (v_{s_1}, \ldots, v_{s_m})$ 表示零售商和供应商的价值向量。用 $v = (\mathbf{v}^R, \mathbf{v}^S)$、$v_{-r_i}$、$v_{-s_j}$ 表示所有广告主的价值向量、除零售商 $i$、供应商 $j$ 之外的所有广告主的价值向量。类似地，对于出价向量，论文也使用类似的符号，例如 $\mathbf{b}^R$ 、 $\mathbf{b}^S$ 、 $\mathbf{b}$ 、 $\mathbf{b}_{-r_i}$ 和 $\mathbf{b}_{-s_j}$
在论文的模型中，一个广告商品由两方赞助：一个零售商和一个供应商。因此，对于所有 $e = (r_i, s_j) \in E$ ，论文将这样一个组合的联合投标定义为 $b_{ij} = b_{r_i} + b_{s_j}$ 。有时论文也用 “组合” 来表示一个广告商品
有了这些符号，我们可以定义JAS中的拍卖机制。一个机制 $\mathcal{M} = (\mathbf{a}(\mathbf{b}), \mathbf{p}(\mathbf{b}))$ 两部分组成：
- 分配规则：$a(\mathbf{b}) = (a_i(\mathbf{b}))_{i \in R \cup S}$
- 支付规则：$p(\mathbf{b}) = (p_i(\mathbf{b}))_{i \in R \cup S}$
- 在这里，对于任何广告主 $i$ ， $a_i(\mathbf{b}) = \sum_{k = 1}^{K} a_{ik}(\mathbf{b})\lambda_k$ 代表总点击率，其中 $a_{ik}(\mathbf{b})$ 是一个指示函数，用于决定分配到第k个广告位的广告商品是否包含广告主 $i$
由于一个广告位应分配给一个组合，且一个组合最多分配到一个广告位， $a_{ik}(\mathbf{b})$ 应满足以下可行性约束，记为$\mathcal{A}$：
$$
\sum_{k = 1}^{K}[a_{ik}(\mathbf{b}) \cdot a_{jk}(\mathbf{b})] \leq 1, \forall e = (r_i, s_j) \in E \\
\sum_{i \in R} a_{ik}(\mathbf{b}) + \sum_{j \in S} a_{jk}(\mathbf{b}) = 2, \forall k \in K \\
\sum_{i \in R} a_{ik}(\mathbf{b}) \leq 1, \sum_{j \in S} a_{jk}(\mathbf{b}) \leq 1, \forall k \in K \\
a_{ik}(\mathbf{b}) \in \{0, 1\}, \forall i \in R \cup S, k \in K
$$
- 问题：为什么是等于2？实际上就是表示各等于1吧
给定分配规则和支付规则，任何零售商或供应商 $i$ 的效用可以表示为：
$$u_i(\mathbf{b}) = v_i \cdot a_i(\mathbf{b}) - p_i(\mathbf{b})$$
拍卖机制的收入是广告主的总支付，即：
$$Rev(\mathbf{b}) = \sum_{i \in R} p_i(\mathbf{b}) + \sum_{j \in S} p_j(\mathbf{b})$$
拍卖机制的社会福利定义为广告主的总价值，即：
$$SW(\mathbf{b}) = \sum_{i \in R \cup S} v_i \cdot a_i(\mathbf{b})$$
在论文中，论文主要关注具有一些理想特性的可行机制，如激励相容性、个体理性和弱预算平衡，正式定义如下：
- 定义1（激励相容性） ：在JAS中，如果对于任何广告主 $i$ 、任何投标 $b_i’$ 和任何投标向量 $\mathbf{b}_{-i}$ ，都有 $u_i(v_i, \mathbf{b}_{-i}) \geq u_i(b_i’, \mathbf{b}_{-i})$ ，则该机制是激励相容的
- 定义2（个体理性） ：在JAS中，如果对于任何广告主 $i$ 和任何投标向量 $\mathbf{b}_{-i}$ ，都有 $u_i(v_i, \mathbf{b}_{-i}) \geq 0$ ，则该机制是个体理性的
- 定义3（弱预算平衡） ：在JAS中，如果收入总是非负的，即 $Rev(\mathbf{b}) = \sum_{i \in R} p_i(\mathbf{b}) + \sum_{j \in S} p_j(\mathbf{b}) \geq 0$ ，则该机制是弱预算平衡的
也就是说，IC和IR保证所有广告主都会如实投标并获得非负效用。WBB确保收入始终非负。在论文的其余部分，论文主要关注设计具有IC、IR和WBB的可行机制

经典拍卖机制

在本节中，论文首先主要关注经典的VCG机制，并展示它在JAS中起作用，但不能保证WBB（待讨论）。然后，论文修改VCG机制的支付规则以满足WBB，并将其称为修正的VCG机制

修正的VCG机制

在JAS中，由于一个广告位由一个零售商 $r_i$ 和与 $r_i$ 有合作关系的一个供应商 $s_j$ 组成的组合占据，分配规则更多地关注可行组合的投标。首先，论文引入分配规则（算法1），当所有广告主如实投标时，该规则可以实现最优社会福利
引理1 ：在联合广告系统中，当所有广告主如实投标时，算法1输出的分配可以实现最优社会福利
现在，论文详细阐述JAS中的VCG机制。实际上，VCG机制的分配规则遵循算法1的步骤。直观地说，VCG机制的支付规则是对每个广告主 $i$ 的外部性进行收费，即有广告主 $i$ 和没有广告主 $i$ 时所有其他广告主的社会福利之差。用 $SW^*(\mathbf{b})$ 表示投标向量 $\mathbf{b}$ 下的最优社会福利。VCG机制对广告主 $i$ 的支付可以定义为：
$$ p_i(\mathbf{b}) = SW^*(\mathbf{b}_{-i}) - [SW^*(\mathbf{b}) - a_i(\mathbf{b}) \cdot b_i] $$
不难发现，VCG机制是IR和IC的，因为任何广告主的支付都与她自己的投标无关。然而，基于联合投标的模式，当一个投标者不参加拍卖时，她的合作伙伴将失去形成组合并竞争广告位的机会，这可能会导致最优社会福利的损失。在下面的例子中，论文展示当一个投标者退出拍卖时，其他广告主的最优总价值会下降。这意味着一个广告主的支付可能为负，从而违反WBB
示例1 ：假设有两个零售商 $\{r_1, r_2\}$ 和两个供应商 $\{s_1, s_2\}$ ，只有两个合作关系 $\{(r_1, s_1), (r_2, s_2)\}$ 。设零售商和供应商的价值分别为 $(v_{r_1}, v_{r_2}) = (3, 2)$ 和 $(v_{s_1}, v_{s_2}) = (5, 1)$ 。只有一个广告位， $\lambda_1 = 1$ ，在这种情况下，VCG机制会将广告位分配给组合 $(r_1, s_1)$ ，此时社会福利为8；
- $r_1$ 的支付为 $p_{r_1}=SW_{-r_1}^* - (SW^* - \lambda_1v_{r_1}) = 1\times(0+5) - (8 - 1\times3)= 0$，直观理解就是无论是否加入 $r_1$，这个位置都会是 $s_1$ 的，所以 $r_1$ 不应该付钱
- $s_1$ 的支付为 $p_{s_1}=SW_{-s_1}^* - (SW^* - \lambda_1v_{s_1}) = 1\times(2 + 1) - (8 - 1\times5)=0$，直观理解就是无论是否加入 $s_1$，这个位置都会是 $r_1$ 的，所以 $s_1$ 不应该付钱
- $p_{s_2}=p_{r_2}=0$
- 总收益为 0，这违反了弱预算平衡的约束
- 注意：论文这里有错误，总收益写的是-2 ，且错误表达为：$r_1$ 的支付为 $p_{r_1}=SW_{-r_1}^* - (SW^* - \lambda_1v_{r_1}) = 1\times(2 + 1) - (8 - 1\times3)= - 2$（这里有错误 ：$SW_{-r_1}^*$应该是等于 $5$ 才对，$r_1$ 不参与的情况下，$s_1$ 靠自己的出价也能拿到这个位置），下面的内容也是基于错误写的：
  - 定理1 ：在联合广告系统中，VCG机制具有激励相容性、个体理性，并且可以实现最优社会福利，但不满足弱预算平衡
  - 例1中导致负收益的主要原因是，如果没有零售商 $r_1$ ，价值较高的供应商 $s_1$ 就会失去竞争机会，从而导致最优社会福利的损失。直观地说，如果论文能够保留供应商 $s_1$ 为社会福利做贡献的权利，那么零售商 $r_1$ 的支付就不会为负，进而可以保证弱预算平衡
  - 基于上述思路，论文修改VCG机制的支付规则：当关键广告商不参与拍卖时，论文假设其出价为0，并且合作关系仍然保留，而不是直接将其剔除。修改后的支付规则可以写成：
    $$p_{i}(\mathbf{b})=SW^{*}\left(0, \mathbf{b}_{-i}\right)-\left[SW^{*}(\mathbf{b})-a_{i}(\mathbf{b}) \cdot b_{i}\right]$$
  - 论文将具有上述支付规则的VCG机制定义为修正的VCG机制，并证明修正的VCG机制可以保证弱预算平衡
  - 定理2 ：在联合广告系统中，修正的VCG机制具有激励相容性、个体理性、弱预算平衡，并且可以实现最优社会福利

联合仿射最大化拍卖

在本节中，论文首先介绍仿射最大化拍卖（AMA），它是VCG机制的广义版本。然后，根据第3节中修正的VCG机制，在JAS的投标环境中扩展传统的AMA，论文将其称为联合AMA（JAMA），并概述JAMA的流程

仿射最大化拍卖概述

如前所述，修正的VCG机制可以确保平台的收入为非负。然而，平台仍然希望在保持激励相容性和个体理性等理想特性的同时，进一步提高收入。因此，论文考虑一种更广泛的机制类型，称为仿射最大化拍卖，它可以看作是VCG机制的推广
与VCG机制不同，AMA有两组参数：权重和 boost 值。每个投标者 $i $都有一个正权重 $w_{i}$ ，并且任何分配方案 $\mathbf{a} $都与一个 boost 值 $u(\mathbf{a}) $相关联。AMA的主要思想是分配物品以最大化仿射社会福利，仿射社会福利是投标者总加权价值与分配 boost 值的总和，并且一个投标者的支付被定义为所有其他投标者仿射社会福利的总减少量。直观地说，AMA可以增加收入，因为它牺牲了社会福利的最优性，使用加权社会福利来衡量投标者的外部性。正式地，给定权重和 boost 值，加权社会福利可以定义为：
$$WSW(\mathbf{b})=\sum_{i \in R \cup S} w_{i} v_{i} \cdot a_{i}(\mathbf{b})+u(\mathbf{a}(\mathbf{b}))$$
AMA的分配为 $\mathbf{a}^{*}(\mathbf{b})=\arg \max_{\mathbf{a}(\mathbf{b})} WSW(\mathbf{b})$ ，任何广告商的支付为：
$$p_{i}(\mathbf{b})=\frac{1}{w_{i}}\left(WSW^{*}\left(\mathbf{b}_{-i}\right)-\left(WSW^{*}(\mathbf{b})-w_{i} b_{i} \cdot a_{i}(\mathbf{b})\right)\right) $$
当给定权重和 boost 值时，AMA具有激励相容性和个体理性。注意，VCG机制是AMA的一种特殊情况 ，其权重为1， boost 值为零。因此，如果论文能够为AMA的参数分配合适的值，AMA的收入将高于VCG的收入
- 然而，文献证明，找到使AMA实现最大收入的最优参数是NP难问题
最近，对于多物品设置，有研究提供了一种新颖的自动机制设计方法来训练AMA的架构（Differentiable economics for randomized affine maximizer auctions），并说明了他们训练的机制在收入方面的优越性。受这种方法的启发，在本节的其余部分，论文旨在将AMA扩展到论文的联合广告系统，并提出相应的训练方法。论文将论文的AMA架构称为联合AMA。图2展示了JAMA的基本结构
论文将零售商和供应商的出价及其权重作为输入。然后根据零售商和供应商之间的合作关系计算联合出价。通过训练分配方案和相应的 boost 值，论文得到优化平台收入的最优参数集。然后输出每个零售商和供应商的分配结果和支付

JAMA架构

整体描述 ：如图2所示，JAMA中有三种可学习的参数：广告商权重 $w_{i}$ 、 boost 变量 $u(\mathbf{a}^{*})$ 以及分配方案 $\mathbf{a}^{*}$
过程：在输入阶段，零售商和供应商提交他们的出价。然后，论文分别通过将每个广告商的出价与其投标权重相结合，得到每个广告商的加权出价，之后，论文根据表示合作关系的出价二分图生成零售商和供应商之间的联合出价
分配方案 ：为了尽可能提高JAMA的收入表现，论文初始化多个分配方案。此外，论文对分配方案进行归一化处理，以满足第2节中定义的可行性约束
boost 值 ：为了得到 boost 变量，论文使用多层感知器（MLP），这是一种全连接神经网络
在得到JAMA的输出参数 $w_{i}$ 、 $\mu(\mathbf{a}^{*})$ 和 $\mathbf{a}^{*}$ 后，我们可以根据第4节中定义的公式计算分配结果并计算支付结果
优化与训练 ：由于JAMA完全具有激励相容性和个体理性，论文的目标是最大化平台的总收入。具体来说，论文将损失函数设置为负的总收入，即 $-[\sum_{i \in R} p_{i}(\mathbf{b})+\sum_{j \in S} p_{j}(\mathbf{b})]$ 。然后，论文通过梯度下降法一起学习这些参数
分配方案初始化 ：对于组合分配概率矩阵的初始化，和相关研究方法一样，论文采用两种方法：第一种是最初保留所有可行的分配。在广告商数量有限，或者合作关系结构相对简单的情况下，这种方法可以很容易地获得最优结果。另一种方法是随机初始化大量的分配，以找到带来最多收入的最佳分配，尽管实际上这些分配中只有少数会被使用。此外，在论文的实验中，获胜的分配矩阵总是确定的，这与实验设置一致
与普通拍卖不同，在联合广告中分配广告位时，论文需要考虑可行性约束（在第2节中定义），即一个组合不能出现在多个广告位中，并且单个广告位不能被重复分配。因此，论文考虑在训练过程中保持分配矩阵为双随机矩阵。论文遵循相关研究中使用的方法，通过软加操作对矩阵进行逐行和逐列归一化，并取结果的最小值
此外：
- 在训练过程中 ，论文遵循相关研究使用的方法，利用softmax函数作为max和argmax操作的可微替代函数
- 在测试时 ，论文使用常规的max运算符

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

参考链接：
- 原始论文：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——(RegretNet)Optimal-Auctions-through-Deep-Learning

参考链接：
- 原始论文：Optimal Auctions through Deep Learning，ICML 2019，London School of Economics & Harvard University
- 博客：【论文阅读】Optimal Auctions Through Deep Learning

整体概述

最优拍卖（收益最大化拍卖） ：激励兼容且能最大化预期收益的拍卖机制（这种机制一般称为最优拍卖(Optimal Aucion)机制），这种机制很复杂，很难设计
Myerson拍卖 ：Myerson 在1981年一篇具有开创性的论文中提出了单一物品下的最优拍卖机制
问题提出 ：然而，即使经过了30-40年的深入研究，对于看似简单的多竞拍者、多物品拍卖场景 ，这个问题仍然没有得到解决
论文的内容 ：
- 创新性方法 ：论文开启了利用深度学习工具自动设计最优拍卖机制的探索。将拍卖建模为一个多层神经网络，把最优拍卖设计框架构建为一个带约束的学习问题，并展示了如何使用标准流程来解决它
- 方法论证 ：论文证明了泛化边界，并进行了大量实验，在多物品拍卖场景中，论文基本上恢复了过去已知的所有解析解，并且在最优机制未知的场景中获得了新的拍卖机制

论文设计思路

最优拍卖（Optimal auction）设计是经济理论的基石之一，具有重要的实际意义。在标准的独立私人估值模型中，每个竞拍者对物品子集都有一个估值函数，这些估值函数独立地从不一定相同的分布中抽取。假设拍卖人知道这些分布，并且能够（也会）在设计拍卖机制时利用这些信息。设计拍卖机制的一个主要困难在于，估值是私人信息 ，需要激励竞拍者如实报告他们的估值。目标是找到一种激励兼容的拍卖机制，以实现收益最大化
Myerson 解决了单一物品拍卖时的最优拍卖设计问题（ Myerson ，1981）。但该方案仅限于单物品拍卖，直到30-40年后的今天，即使是对于有两个竞拍者和两个物品的简单场景，这个问题也没有完全解决。今年来的研究中，大多数适用于较弱的贝叶斯激励兼容（BIC）概念
- 贝叶斯激励兼容（BIC） ：
论文的重点是设计满足占优策略激励兼容（DSIC）的拍卖机制，这是一种更稳健、更理想的激励兼容概念

论文的贡献

论文提供了第一个通用的端到端方法来解决多物品拍卖设计问题。使用多层神经网络对拍卖机制进行编码，将竞拍者的估值作为输入，将物品分配和支付决策作为输出。然后，论文使用从估值分布中抽取的样本来训练网络，以便在满足激励兼容约束的情况下最大化预期收益
为了能够使用标准流程来解决这个问题，论文将激励兼容约束重新表述为要求拍卖的预期事后遗憾为零。论文采用增广拉格朗日方法来解决由此产生的约束优化问题，在每次迭代中，论文通过求解一个内部优化问题来找到每个竞拍者和估值 profile 的最优虚报值，从而通过遗憾项推送梯度
论文描述了针对具有加性、单位需求和组合估值的竞拍者的网络架构（注：这几个概念的详细定义见后面的内容），并进行了大量实验，结果表明：
- 理论保障 ：论文的方法能够恢复过去30-40年中多物品拍卖场景下几乎所有的解析解。通过找到收益几乎最优且遗憾极小的拍卖机制，其分配和支付规则与理论上最优拍卖的规则匹配度非常高
- 最优拍卖 ：在最优拍卖未知的场景中，论文的方法能找到收益高且遗憾可忽略不计的拍卖机制，其性能与当前 SOTA 计算结果相当或更优
- 多竞拍者多物品 ：目前分析文献中研究的最大场景是有2个竞拍者和2个物品，而论文的方法可以为更大的场景学习拍卖机制，例如5个竞拍者、10个物品的场景。在这些场景中，最优拍卖很难设计，而论文的方法能找到遗憾低且收益比强基线更高的拍卖机制
- 注：（其他理论证明）论文还证明了一个新的泛化边界，这意味着，对于论文的架构，在训练数据上的高收益和低遗憾很有可能转化为在新抽取的估值上的高收益和低遗憾

论文中的一些讨论

事后遗憾非论文创新 ：通过关注预期事后遗憾（expected ex post regret），论文采用了对占优策略激励兼容的一种可量化的松弛，这一概念最早在（迪廷等人，2014）中提出。论文的实验表明，这种松弛是逼近最优DSIC拍卖的有效工具
论文的方法更高效 ：虽然最初关于自动拍卖设计的工作将该问题表述为线性规划（LP）（2002；2004），但后续研究已经认识到这种方法存在严重的可扩展性问题，因为它需要的约束和变量数量与参与者和物品的数量呈指数关系（2010）。论文发现，即使对于有2个竞拍者和3个物品的小场景（并且将每个物品的价值离散化为5个区间），LP也需要69个小时才能完成，因为LP需要处理约 $10^5$ 个决策变量和约 $4×10^6$ 个约束。对于相同的场景，论文的方法在9个多小时内就找到了一个遗憾更低的拍卖机制（见表1）

Auction Design as a Learning Problem

拍卖设计基础及符号说明

论文考虑一个有一组 $n$ 个竞拍者 $N = \{1, \ldots, n\}$ 和 $m$ 个物品 $M = \{1, \ldots, m\}$ 的场景。每个竞拍者 $i$ 都有一个估值函数 $v_i: 2^M \to \mathbb{R}_{\geq0}$ ，其中 $v_i(S)$ 表示竞拍者对物品子集 $S \subseteq M$ 的估值。在最简单的情况下，竞拍者可能具有加性估值 ，即她对 $M$ 中单个物品有一个价值，并且她对物品子集 $S \subseteq M$ 的价值为 $v_i(S) = \sum_{j \in S} v_i(\{j\})$。竞拍者 $i$ 的估值函数独立地从分布 $F_i$ 中抽取，取值包含在价值取值空间 $V_i$ 中。论文将估值 profile 写为 $v = (v_1, \ldots, v_n)$ ，并表示 $V = \prod_{i = 1}^{n} V_i$
拍卖人知道分布 $F = (F_1, \ldots, F_n)$ ，但不知道竞拍者实际的估值 $x$ 。竞拍者报告他们的估值（可能不真实），然后拍卖决定将物品分配给哪些竞拍者，并向他们收取费用。论文将拍卖 $(g, p)$ 表示为一对分配规则 $g_i: V \to 2^M$ 和支付规则 $p_i: V \to \mathbb{R}_{\geq0}$ （这些规则可以是随机化的）。给定出价 $b = (b_1, \ldots, b_n) \in V$ ，拍卖计算出分配 $g(b)$ 和支付 $p(b)$
一个估值为 $v_i$ 的竞拍者对出价配置文件 $b$ 的效用为 $u_i(v_i, b) = v_i(g_i(b)) - p_i(b)$ 。竞拍者是策略性的，他们试图最大化自己的效用，可能会报告与他们真实估值不同的出价。令 $v_{-i}$ 表示不包含元素 $v_i$ 的估值 profile $v = (v_1, \ldots, v_n)$ ，类似地定义 $b_{-i}$ ，并令 $V_{-i} = \prod_{j \neq i} V_j$ 表示除竞拍者 $i$ 之外其他竞拍者可能的估值 profile 。如果无论其他竞拍者报告什么，每个竞拍者如实报告时其效用最大，那么这个拍卖就是占优策略激励兼容（DSIC）的。换句话说，对于每个竞拍者 $i$ 、每个估值 $v_i \in V_i$ 、每个出价 $b_i \in V_i$ 以及其他竞拍者的所有出价 $b_{-i} \in V_{-i}$ ，都有 $u_i(v_i, (v_i, b_{-i})) \geq u_i(v_i, (b_i, b_{-i}))$ 。如果每个竞拍者都能获得非零效用，即对于所有 $i \in N$ 、 $v_i \in V_i$ 和 $b_{-i} \in V_{-i}$ ，都有 $u_i(v_i, (v_i, b_{-i})) \geq 0$ ，那么这个拍卖就是（事后）个体理性（IR）的
在DSIC拍卖中，如实报告对每个竞拍者来说是最有利的，因此在估值 profile $v$ 上的收益是 $\sum_{i} p_i(v)$ 。最优拍卖设计旨在找到一个DSIC拍卖，以最大化预期收益

表述为 Learning Problem

论文将最优拍卖设计问题表述为一个学习问题，在这里，论文不使用衡量与目标标签误差的损失函数，而是采用从 $F$ 中抽取的估值上的负预期收益。论文给定一个参数化的拍卖类 $(g^w, p^w) \in \mathcal{M}$ ，其中参数 $w \in \mathbb{R}^d$ （ $d \in \mathbb{N}$ ），以及一个从 $F$ 中独立同分布抽取的竞拍者估值 profile 样本 $S = \{v^{(1)}, \ldots, v^{(L)}\}$ 。目标是在所有满足激励兼容性的拍卖中，找到一个使负预期收益 $-\sum_{i \in N} p_i^w(v)$ 最小的拍卖
特别地，论文在学习问题中引入约束，以确保所选的拍卖满足激励兼容性。为此，论文定义每个竞拍者的事后遗憾，来衡量拍卖违反激励兼容性的程度。固定其他竞拍者的出价，一个竞拍者的事后遗憾是她考虑所有可能的非如实出价时，效用的最大增加量。论文关注竞拍者 $i$ 的预期事后遗憾：
$$rgt_i(w) = \mathbb{E}_{v\sim F}\left[\max_{v_i’ \in V_i} u_i^w(v_i; (v_i’, v_{-i})) - u_i^w(v_i; (v_i, v_{-i}))\right]$$
- 其中期望是对 $v \sim F$ 取的，并且对于给定的模型参数 $w$ ， $u_i^w(v_i, b) = v_i(g_i^w(b)) - p_i^w(b)$ 。论文假设 $F$ 在估值取值空间 $V$ 上具有完全支撑，并且认识到遗憾是非负的，一个拍卖满足DSIC当且仅当对于所有 $i \in N$ ， $rgt_i(w) = 0$
- 特别说明：$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 条件
鉴于此，论文将学习问题重新表述为最小化预期损失，即在每个竞拍者的预期事后遗憾为0的条件下，最小化预期负收益：
$$\min_{w \in \mathbb{R}^d} \mathbb{E}_{v \sim F}\left[-\sum_{i \in N} p_i^w(v)\right] \\ \text{ s.t. } rgt_i(w) = 0, \forall i \in N$$
给定一个来自 $F$ 的 $L$ 个估值 profile 的样本 $S$ ，论文估计竞拍者 $i$ 的经验事后遗憾为：
$$\hat{rgt}_i(w) = \frac{1}{L} \sum_{\ell = 1}^{L} \max_{v_i’ \in V_i} u_i^w(v_i^{(\ell)}; (v_i’, v_{-i}^{(\ell)})) - u_i^w(v_i^{(\ell)}; v^{(\ell)})$$
并寻求在所有竞拍者的经验遗憾为零的条件下，最小化经验损失：
$$\min_{w \in \mathbb{R}^d} -\frac{1}{L} \sum_{\ell = 1}^{L} \sum_{i = 1}^{n} p_i^w(v^{(\ell)}) \\ \text{ s.t. } \hat{rgt}_i(w) = 0, \forall i \in N$$

个体理性

论文还将要求设计的拍卖满足个体理性，这可以通过将搜索空间限制在一类参数化拍卖 $(g^w, p^w)$ 中来实现，这类拍卖向任何竞拍者收取的费用都不超过她对分配的预期效用。在第3节中，论文将分配和支付规则建模为神经网络，并在架构中纳入个体理性要求

泛化边界（TODO）

论文根据抽取的估值 profile 数量来界定预期遗憾和经验遗憾之间的差距。论文对收益也展示了类似的结果。论文的边界适用于从有限容量类中选择的任何拍卖，这意味着用大样本求解（2）式会得到一个预期收益接近最优且预期遗憾接近零的拍卖（论文注意到，在实践中，论文可能无法精确求解（2）式）
论文使用排名文献中使用的覆盖数定义来衡量拍卖类的容量（鲁丁和沙皮尔，2009）。论文定义拍卖 $(g, p)$ ， $(g’, p’) \in \mathcal{M}$ 之间的 $\ell_{\infty, 1}$ 距离为 $\max_{v \in V} \sum_{i, j}|g_{ij}(v) - g_{ij}’(v)| + \sum_{i}|p_i(v) - p_i’(v)|$ 。对于任何 $\epsilon > 0$ ，令 $N_{\infty}(\mathcal{M}, \epsilon)$ 是在 $\ell_{\infty, 1}$ 距离下覆盖 $\mathcal{M}$ 所需的半径为 $\epsilon$ 的最小球数
定理1 ：对于每位竞拍者 $i$，不失一般性地假设其估值函数 $v_{i}(S)\leq1$，其中 $\forall S\subseteq M$。设 $\mathcal{M}$为满足个体理性的拍卖类别。固定 $\delta\in(0,1)$。从 $F$中抽取 $L$个估值 profile 样本 $s$，至少以 $1-\delta$的概率，对于任何 $(g^{w}, p^{w})\in\mathcal{M}$，有：
$$\mathbb{E}_{v\sim F}\left[-\sum_{i\in N}p_{i}^{w}(v)\right]\leq -\frac{1}{L}\sum_{\ell = 1}^{L}\sum_{i = 1}^{n}p_{i}^{w}(v^{(\ell)})+2n\Delta_{L}+Cn\sqrt{\frac{\log(1/\delta)}{L}}$$
- 并且
  $$\frac{1}{n}\sum_{i = 1}^{n}rgt_{i}(w)\leq\frac{1}{n}\sum_{i = 1}^{n}\widehat{rgt}_{i}(w)+2\Delta_{L}+C’\sqrt{\frac{\log(1/\delta)}{L}}$$
  - 其中 $\Delta_{L}=\inf_{\epsilon>0}\left\{\frac{\epsilon}{n}+2\sqrt{\frac{2\log(N_{\infty}(\mathcal{M},\epsilon/2))}{L}}\right\}$，$C$、$C’$为与分布无关的常数
- 证明见附录。若上述边界中的 $\Delta_{L}$项随着样本量 $L$的增加而趋于 0，则当 $L\rightarrow\infty$时，上述边界也趋于 0。在第 3 节的定理 2 中，论文给出了论文所提出神经网络架构的 $\Delta_{L}$上界

神经网络架构

论文描述用于对多物品拍卖进行建模的神经网络架构，称为RegretNet。论文考虑具有加性、单位需求和一般组合估值的竞拍者。该架构包含两个逻辑上不同的组件：分配网络和支付网络

加性估值下的网络架构

如果竞拍者对物品束（bundle of item） $S\subseteq M$的价值是她对 $S$中单个物品价值的总和，即 $v_{i}(S)=\sum_{j\in S}v_{i}(j)$，则该竞拍者具有加性估值。在这种情况下，竞拍者仅报告他们对单个物品的估值。此场景下的架构对随机分配网络 $g^{w}:\mathbb{R}^{nm}\to[0,1]^{nm}$和支付网络 $p^{w}:\mathbb{R}^{nm}\to\mathbb{R}_{\geq0}^{n}$进行建模，这两个网络均被建模为具有双曲正切（tanh）激活函数的前馈全连接网络。网络的输入层由表示竞拍者 $i$对物品 $j$估值的出价 $b_{ij}$组成
分配网络为每个物品 $j\in[m]$输出一个分配概率向量 $z_{1j}=g_{1j}(b),\cdots,z_{nj}=g_{nj}(b)$。为确保可行性，即物品被分配的概率至多为 1，分配概率通过softmax激活函数计算，使得对于所有物品 $j$，$\sum_{i = 1}^{n}z_{ij}\leq1$。为适应物品未分配给任何竞拍者的可能性，论文在softmax计算中引入一个虚拟节点，用于保留剩余的分配概率。由于将物品分配给同一竞拍者的输出单元可能相关，因此可以实现物品捆绑
支付网络 ：为每个竞拍者输出一个支付金额，表示该竞拍者针对此特定出价配置文件的预期支付金额。为确保拍卖满足个体理性，即向竞拍者收取的费用不超过其对分配的预期价值，网络首先使用sigmoid单元为每个竞拍者 $i$计算一个分数支付 $\tilde{p}_{i}\in[0,1]$，并输出支付 $p_{i}=\tilde{p}_{i}\sum_{j = 1}^{m}z_{ij}b_{ij}$，其中 $z_{ij}$是分配网络的输出。架构概述见图1，其中收益和遗憾是根据分配网络和支付网络的参数计算得出的

单位需求估值下的网络架构

（这部分比较晦涩，待进一步理解）

当竞拍者对物品束 $S\subseteq M$ 的价值是她对束中单个物品分配的最大价值时（理解：说明至多只能分配一个物品），即 $v_{i}(S)=\max_{j\in S}v_{i}(j)$，该竞拍者具有单位需求估值。单位需求竞拍者的分配网络是图2所示的前馈网络。在这个场景中为实现收益最大化，可以证明考虑为每个竞拍者分配至多一个物品的分配规则就足够了。在随机分配规则的情况下，这要求每个竞拍者的总分配至多为1，即 $\sum_{j}z_{ij}\leq1$，$\forall i\in[n]$。论文还要求任何物品都不会被过度分配，即 $\sum_{i}z_{ij}\leq1$，$\forall j\in[m]$
- 因此，论文设计的分配网络其输出概率矩阵 $[z_{ij}]_{i,j = 1}^{n}$是双随机的（注：doubly stochastic matrix，双随机矩阵是指每行每列之和为1 ，且单个元素值大于0的矩阵，论文中似乎将行列之和放松为小于等于1了）
具体来说，论文让分配网络计算两组分数 $s_{ij}$和 $s_{ij}’$，第一组分数按行归一化，第二组分数按列归一化。这两组归一化都可以通过将分数输入softmax函数来实现。然后，竞拍者 $i$对物品 $j$的分配计算为相应归一化分数中的最小值：
$$z_{ij}=\varphi_{ij}^{DS}(s,s’)=\min\left\{\frac{e^{s_{ij}}}{\sum_{k = 1}^{n + 1}e^{s_{kj}}},\frac{e^{s_{ij}’}}{\sum_{k = 1}^{m + 1}e^{s_{jk}’}}\right\}$$
- 其中索引 $n + 1$和 $m + 1$表示虚拟输入，分别对应物品未分配给任何竞拍者以及竞拍者未分配到任何物品的情况
引理1 ：对于 $\forall s$，$s’\in\mathbb{R}^{nm}$，$\varphi^{DS}(s,s’)$是双随机的。对于任何双随机分配 $z\in[0,1]^{nm}$，存在 $s$，$s’\in\mathbb{R}^{nm}$，使得 $z=\varphi^{DS}(s,s’)$
- 注：双随机矩阵式行和列的和都等于1的矩阵，论文将双随机矩阵的行列和定义为小于等于1 ，所以引理1才能成立，否则是不成立的
支付网络与图1中的相同

组合估值下的网络架构

论文还考虑具有一般组合估值的竞拍者。在本研究中，论文仅针对少量物品开发了这种架构
在这种情况下，每个竞拍者 $i$针对每个物品束 $S\subseteq M$（空束除外，其估值视为零）报告一个出价 $b_{i,S}$。分配网络为每个竞拍者 $i$和物品束 $S$输出一个 $z_{i,S}\in[0,1]$，表示该竞拍者被分配到该物品束的概率。为防止物品被过度分配，论文要求物品出现在分配给某个竞拍者的物品束中的概率至多为1。论文还要求分配给每个竞拍者的物品束总量至多为1（约束（3）和约束（4））：
$$\sum_{i\in N}\sum_{S\subseteq M:j\in S}z_{i,S}\leq1,\forall j\in M \\
\sum_{S\subseteq M}z_{i,S}\leq1,\forall i\in N$$
- 论文将满足上述约束（3）和（4）的分配称为组合可行分配。为强制执行这些约束，论文让分配网络为每个物品计算一组分数，并为每个竞拍者计算一组分数。具体而言，对于每个竞拍者 $i\in N$，有一组竞拍者相关分数 $s_{i,S}$，$\forall S\subseteq M$；对于每个物品 $j\in M$，有一组物品相关分数 $s_{i,S}^{(j)}$，$\forall i\in N$，$S\subseteq M$。每组分数都使用softmax函数进行归一化：$\bar{s}_{i,S}=\frac{\exp(s_{i,S})}{\sum_{S’}\exp(s_{i,S’})}$和 $\bar{s}_{i,S}^{(j)}=\frac{\exp(s_{i,S}^{(j)})}{\sum_{i’,S’}\exp(s_{i’,S’}^{(j)})}$。竞拍者 $i$对物品束 $S\subseteq M$的分配定义为 $i$的归一化竞拍者相关分数 $\bar{s}_{i,S}$与 $S$中每个物品 $j$的归一化物品相关分数 $\bar{s}_{i,S}^{(j)}$中的最小值：
  $$z_{i,S}=\varphi_{i,S}^{CF}(s,s^{(1)},\cdots,s^{(m)})=\min\left\{\bar{s}_{i,S},\bar{s}_{i,S}^{(j)}:j\in S\right\}$$
引理2 ：对于 $\forall s$，$s^{(1)},\cdots,s^{(m)}\in\mathbb{R}^{n2^{m}}$，$\varphi^{CF}(s,s^{(1)},\cdots,s^{(m)})$是组合可行的。对于任何组合可行分配 $z\in[0,1]^{n2^{m}}$，存在 $s$，$s^{(1)},\cdots,s^{(m)}\in\mathbb{R}^{n2^{m}}$，使得 $z=\varphi^{CF}(s,s^{(1)},\cdots,s^{(m)})$
图2（b）展示了有2个竞拍者和2个物品场景下的网络架构。为便于说明，论文在讨论中忽略空物品束。对于每个竞拍者 $i\in\{1,2\}$，网络为她可能被分配的每个物品束计算三个分数 $s_{i,\{1\}}$，$s_{i,\{2\}}$和 $s_{i,\{1,2\}}$，并使用softmax函数对其进行归一化。网络还为物品1计算四个分数：$s_{1,\{1\}}^{1}$，$s_{2,\{1\}}^{1}$，$s_{1,\{1,2\}}^{1}$和 $s_{2,\{1,2\}}^{1}$，即物品1存在于每个分配中的分数，类似地，为物品2计算四个分数：$s_{1,\{2\}}^{2}$，$s_{2,\{2\}}^{2}$，$s_{1,\{1,2\}}^{2}$和 $s_{2,\{1,2\}}^{2}$。然后，每组分数都通过单独的softmax函数进行归一化。每个竞拍者的最终分配为：$z_{i,\{1\}}=\min\{\bar{s}_{i,\{1\}},\bar{s}_{i,\{1\}}^{1}\}$，$z_{i,\{2\}}=\min\{\bar{s}_{i,\{2\}},\bar{s}_{i,\{2\}}^{2}\}$，$z_{i,\{1,2\}}=\min\{\bar{s}_{i,\{1,2\}},\bar{s}_{i,\{1,2\}}^{1},\bar{s}_{i,\{1,2\}}^{2}\}$
组合竞拍者的支付网络与图1中的结构相同，使用sigmoid单元为每个竞拍者 $i$计算一个分数支付 $\tilde{p}_{i}\in[0,1]$，并输出支付 $p_{i}=\tilde{p}_{i}\sum_{S\subseteq M}z_{i,S}b_{i,S}$，其中 $z_{i,S}$是分配网络的输出

覆盖数边界

论文现在为上述神经网络在定理1的泛化边界中界定 $\Delta_{L}$项
定理2 ：对于具有 $R$个隐藏层、每个隐藏层有 $K$个节点、分配网络有 $d_{a}$个参数、支付网络有 $d_{p}$个参数且所有模型参数向量 $|w|_{1}\leq W$的RegretNet，对于不同竞拍者估值类型，$\Delta_{L}$项的边界如下：
加性估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log(LW\max\{K,mn\})}{L}}\right)$$
单位需求估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log(LW\max\{K,mn\})}{L}}\right)$$
组合估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log\left(LW\max\left\{K,n2^{m}\right\}\right)}{L}}\right)$$
证明见附录。随着样本量 $L\rightarrow\infty$，$\Delta_{L}\rightarrow0$。上述结果对网络层数、节点数和参数的依赖与神经网络的标准覆盖数边界类似（安东尼和巴特利特，2009）。注意，组合估值边界中的对数项抵消了对物品数量 $m$的指数依赖

优化与训练

论文使用增广拉格朗日方法在神经网络参数 $w$的空间上求解（2）式中的约束训练问题。首先，论文为优化问题定义拉格朗日函数，并添加一个用于惩罚违反约束的二次项：
$$\mathcal{C}_{\rho}(w;\lambda)=-\frac{1}{L}\sum_{\ell = 1}^{L}\sum_{i\in N}p_{i}^{w}(v^{(\ell)})+\sum_{i\in N}\lambda_{i}\widehat{rgt}_{i}(w)+\frac{\rho}{2}\left(\sum_{i\in N}\widehat{rgt}_{i}(w)\right)^{2}$$
- 其中 $\lambda\in\mathbb{R}^{n}$是拉格朗日乘子向量，$\rho>0$是一个固定参数，用于控制二次惩罚项的权重。求解器在每次迭代中对模型参数和拉格朗日乘子进行以下交替更新：
  - （a）$w^{new}\in\arg\min_{w}\mathcal{C}_{\rho}(w^{old};\lambda^{old})$；
  - （b）$\lambda_{i}^{new}=\lambda_{i}^{old}+\rho\widehat{rgt}_{i}(w^{new})$，$\forall i\in N$
- 理解：对于 regret 约束，给了一次项惩罚和二次项惩罚
- 问题：在训练时如何计算 $\widehat{rgt}_{i}(w)$ ?
  - 回答：计算公式为
    $$\hat{rgt}_i(w) = \frac{1}{L} \sum_{\ell = 1}^{L} \max_{v_i’ \in V_i} u_i^w(v_i^{(\ell)}; (v_i’, v_{-i}^{(\ell)})) - u_i^w(v_i^{(\ell)}; v^{(\ell)})$$
    - 其中 $V_i$ 出价可能的取值集合（即取值空间），猜测可以通过随机采样几个值 ，或提前定义几个按照固定间隔采样取值，再取他们对应效用函数中的最大值即可作为近似最大效用函数
具体训练流程如下：
求解器如算法1所示。论文将训练样本 $s$划分为大小为 $B$的 minibatch，并对训练样本进行多次遍历（每次遍历后对数据进行随机洗牌）。论文将第 $t$次迭代时收到的 minibatch 记为 $S_{t}=\{u^{(1)},\cdots,u^{(B)}\}$。对模型参数的更新（a）涉及对 $\mathcal{C}_{\rho}$关于 $w$的无约束优化，使用基于梯度的优化器进行。令 $\tilde{rgt}_{i}(w)$表示在 minibatch $S_{t}$上计算的经验遗憾（见（1）式）。对于固定的 $\lambda^{t}$，$\mathcal{C}_{\rho}$关于 $w$的梯度为：
$$\nabla_{w}\mathcal{C}_{\rho}(w;\lambda^{t})=-\frac{1}{B}\sum_{\ell = 1}^{B}\sum_{i\in N}\nabla_{w}p_{i}^{w}(v^{(\ell)})+\sum_{i\in N}\sum_{\ell = 1}^{B}\lambda_{i}^{t}g_{\ell,i}+\rho\sum_{i\in N}\sum_{\ell = 1}^{B}\tilde{rgt}_{i}(w)g_{\ell,i}$$
- 其中
  $$g_{\ell,i}=\nabla_{w}\left[\max_{v_{i}’\in V_{i}}u_{i}^{w}(v_{i}^{(\ell)};(v_{i}’,v_{-i}^{(\ell)})) - u_{i}^{w}(v_{i}^{(\ell)};v^{(\ell)})\right]$$
- 注意，$rgt$和 $g_{\ell,i}$项涉及对每个竞拍者 $i$和估值 profile $\ell$的虚报值求 “最大值”。论文使用另一个基于梯度的优化器求解关于虚报值的内部最大化问题，并通过最优虚报值处的效用差异推送梯度。具体来说，论文为每个 $i$和估值 profile $\ell$维护虚报值 $v_{i}^{(\ell)}$。对于模型参数 $w^{t}$的每次更新，执行 $R$次梯度更新以计算最优虚报值：$v_{i}^{(\ell)}=v_{i}^{\prime(\ell)}+\gamma\nabla_{v_{i}’}u_{i}^{w}(v_{i}^{(\ell)};(v_{i}^{\prime(\ell)},v_{-i}^{(\ell)}))$，其中 $\gamma>0$。在论文的实验中，论文使用Adam优化器（金马和巴，2014）对模型 $w$和 $v_{i}^{(\ell)}$进行更新
由于论文试图解决的优化问题是非凸的，求解器不能保证达到全局最优解。然而，在论文的实验中，论文的方法非常有效。学习到的拍卖机制产生的遗憾非常低，并且在已知最优拍卖结构的场景中，与最优拍卖结构非常匹配

实验结果

论文证明了论文的方法能够在几乎所有已知最优解的场景中找到接近最优的拍卖方案，并且在没有已知解析解的场景中发现新的拍卖方案。论文在附录中给出了完整的实验集，这里展示部分具有代表性的结果

Experiment Setup

框架：论文使用TensorFlow深度学习库实现了论文的框架
架构：所有网络均采用Glorot均匀初始化，隐藏节点使用tanh激活函数
数据集 ：在所有实验中，论文使用640,000个估值 profile 的样本进行训练，10,000个配置文件的样本进行测试
超参数设置 ：增广拉格朗日求解器最多运行80个轮次（epoch）， minibatch （minibatch）大小为128。增广拉格朗日中的超参数ρ初始值设为1.0 ，每2个轮次增加一次。每次 minibatch 更新时，使用学习率为0.001的Adam优化器更新w。每次更新w时，论文以0.1的学习率运行25次虚报更新步骤。在25次更新结束时，当前 minibatch 的优化虚报值会被缓存，并用于下一轮次相同 minibatch 的虚报值初始化。每100个 minibatch 更新一次拉格朗日乘子λ（即Q = 100）
硬件环境 ：论文的实验在配备NVIDIA GPU核心的计算集群上运行

评估指标

除了在测试集上评估学习到的拍卖机制的收益外，论文还评估所有竞拍者和测试估值 profile 上的平均遗憾值，计算公式为 $rgt = \frac{1}{n} \sum_{i = 1}^{n} \widehat{rgt}_{i}(f, p)$。每个 $\widehat{rgt}_{i}$ 都涉及在竞拍者估值 $v_{i}’ \in V_{i}$ 上对效用函数取“最大值”（见公式(1)）。论文通过对 $v_{i}’$ 进行2000次步长为0.1的梯度上升操作来评估这些项（论文测试1000个不同的随机初始 $v_{i}’$，并报告产生最大遗憾值的那个）

单个竞拍者

即使在单竞拍者拍卖的简单场景中，也只有在特殊情况下才有解析解。论文给出了第一种能够处理一般设计问题的计算方法，并与现有的解析结果进行比较。结果表明，论文不仅能够学习到收益接近最优的拍卖机制，而且能够学习到与理论最优规则惊人相似的分配规则
- 场景（I） ：单个竞拍者对2个物品具有加性估值，物品价值从均匀分布U[0,1]中抽取。最优拍卖方案由Manelli & Vincent (2006)给出
- 场景（II） ：单个竞拍者对2个物品具有单位需求估值，物品价值从均匀分布U[2,3]中抽取。最优机制由Pavlov (2011)给出
图3（a）展示了为场景（I）和（II）学习到的最终拍卖机制在测试集上的收益和遗憾值，所使用的网络架构有两个隐藏层，每层100个节点。学习到的拍卖机制的收益非常接近最优收益，遗憾值可忽略不计。在某些情况下，学习到的拍卖机制实现的收益略高于最优激励兼容拍卖。这是因为它们产生了很小的非零遗憾值。图4（a） - （b）中学习到的分配规则可视化结果表明，论文的方法也能很好地还原最优拍卖的结构。图3（c）展示了收益和遗憾值随训练轮次变化的曲线。求解器自适应地调整遗憾值上的拉格朗日乘子，在初始迭代中关注收益，在后续迭代中关注遗憾值

多个竞拍者

接下来，论文将论文的结果与Sandholm和Likhodedov（Sandholm & Likhodedov, 2015）在最优拍卖未知场景下的最先进计算结果进行比较。这些拍卖是通过在一类参数化的激励兼容拍卖中搜索得到的。与这些先前的方法不同，论文不需要在特定的激励兼容拍卖类中搜索，仅受所使用网络的表达能力限制。结果表明，这能产生新颖的拍卖设计，其性能与现有最先进机制相当甚至更优
- 场景（III） ：2个加性估值的竞拍者和2个物品，竞拍者对每个物品的价值从U[0,1]中抽取
- 场景（IV） ：2个竞拍者和2个物品，其中$v_{1,1}, v_{1,2}, v_{2,1}, v_{2,2} \sim U[1,2]$，$v_{1,\{1,2\}} = v_{1,1} + v_{1,2} + C_{1}$，$v_{2,\{1,2\}} = v_{2,1} + v_{2,2} + C_{2}$，$C_{1}, C_{2} \sim U[-1,1]$
- 场景（V） ：2个竞拍者和2个物品，其中$v_{1,1}, v_{1,2} \sim U[1,2]$，$v_{2,1}, v_{2,2} \sim U[1,5]$，$v_{1,\{1,2\}} = v_{1,1} + v_{1,2} + C_{1}$，$v_{2,\{1,2\}} = v_{2,1} + v_{2,2} + C_{2}$，$C_{1}, C_{2} \sim U[-1,1]$
论文采用与场景（I） - （II）相同的实验设置。将训练得到的机制与来自VVCA和 $AMA_{bsym}$ 系列的激励兼容拍卖的最优拍卖方案进行比较（Sandholm & Likhodedov, 2015）。图3（b）总结了论文的结果。论文的方法带来了显著的收益提升，且遗憾值极小。与图3（a）相比，场景（I）中0.004（即0.72%）的遗憾值带来了收益优势，但在这些先前结果的对比下，这种微小的非零遗憾似乎不太可能解释论文方法在收益上的优势

扩展性测试

论文还考虑了多达5个竞拍者和10个物品的场景。由于问题的指数性质，这比现有分析文献所能处理的问题复杂几个数量级。在论文研究的场景中，在竞拍者数量趋于无穷时，对每个物品分别进行Myerson拍卖是最优的（Palfrey, 1983）。这提供了一个很强但仍可改进的基准
- 场景（VI） ：3个加性估值的竞拍者和10个物品，竞拍者对每个物品的价值从U[0,1]中抽取
- 场景（VII） ：5个加性估值的竞拍者和10个物品，竞拍者对每个物品的价值从U[0,1]中抽取
对于场景（VI），论文在图5（a）中展示了使用不同架构在10,000个配置文件的验证样本上学习到的拍卖机制的收益和遗憾值。这里 $(R, K)$ 表示具有R个隐藏层和每层K个节点的架构。在上述两种场景中，(5, 100)架构在所有100节点的网络中遗憾值最低。图5（b）表明，与基线相比，最终学习到的拍卖机制产生了更高的收益（遗憾值极小）

与线性规划（LP）的比较

论文还将论文算法的运行时间与Conitzer和Sandholm（2002; 2004）提出的LP方法进行比较。为了能够完整运行LP，论文考虑一个较小的场景，即2个加性估值的竞拍者和3个物品，物品价值从U[0,1]中抽取。使用商业求解器Gurobi求解LP。论文通过将每个物品的价值离散化为5个区间来处理连续估值（这会产生约 $10^5$ 个决策变量和约 $4×10^6$ 个约束），然后将连续的输入估值 profile 四舍五入到最接近的离散配置文件进行评估。关于LP的进一步讨论见附录
结果如表1所示。论文还报告了LP在测试集上违反个体理性（IR）约束的情况；对于L个估值 profile ，其计算方式为 $\frac{1}{Ln} \sum_{\ell = 1}^{L} \sum_{i \in N} \max(u_{i}(v^{(\ell)}), 0)$。由于粗粒度的离散化，LP方法存在显著的IR约束违反情况（因此产生了更高的收益）。对于更精细的离散化，论文无法在一周以上的计算时间内运行LP。相比之下，论文的方法在大约9小时内就产生了低得多的遗憾值，并且没有IR约束违反情况（因为神经网络在设计上满足IR）。实际上，即使对于更大的场景（VI） - （VII），论文算法的运行时间也不到13小时

附录：双随机矩阵（doubly stochastic matrix）

双随机矩阵（doubly stochastic matrix），在数学中，是一种特殊的方阵，其满足以下条件：
- 非负性：矩阵中的每个元素都是非负的。这意味着对于任意的元素 $P_{ij}$ 来说，都有 $P_{ij} \geq 0$
- 行和为1：每一行的所有元素之和都等于1。即对于所有的行索引 $i$，有 $\sum_j P_{ij} = 1$
- 列和为1：每一列的所有元素之和也都等于1。即对于所有的列索引 $j$，有 $\sum_i P_{ij} = 1$
- 随机这两个字的理解：随机是指概率，也就是行列都可以单抽出来作为一个概率的矩阵
一句话定义 ：每行的元素加起来是1，而且每列的元素加起来也是1，并且所有元素都是非负数，那么这个矩阵就是双随机矩阵
注：论文中对双随机矩阵定义有修改，论文中将双随机矩阵的定义修改为了行列和小于等于1

CA——AIGB

本文主要记录AIGB出价模型

其他参考链接：
- 原始论文：AIGB: Generative Auto-bidding via Diffusion Modeling, Alibaba & Peking University, 2024
- Decision Diffuser原始论文：Is Conditional Generative Modeling all you need for Decision-Making?, MIT, ICLR 2023

核心思路

参考Decision Diffuser方法，对该方法进行微改并应用到出价上
改动一：逆向动力学模型（Acting with Inverse-Dynamics），中使用更多的状态来生成动作，AIGB中使用 $a_t:= f_\phi(s_{t-L:t},s_{t+1})$，原始Decision Diffuser方法则仅使用 $a_t:= f_\phi(s_t,s_{t+1})$

当前存在的问题

轨迹内部的一些规律捕捉不准确，比如同一个序列内部，预算越来越低这个规律无法满足

CA——BCB出价推导

本文主要记录BCB出价的推导

其他参考链接：
- 智能出价——BCB求解
- 互联网广告算法漫谈——浅谈广告中的出价技术：包含许多公式的详细推导

BCB介绍

预算约束的出价，Budget Constrained Bidding（简称BCB），广告主的出价目标是设置一定预算，拿到最多的流量（点击或者订单）

问题定义

一般BCB优化问题的定义:
$$
\begin{align}
\max_{x_{ij}} \sum^N_{i=1} x_{ij} v_{ij} \\
\text{s.t. } \quad\sum^N_{i=1} x_{ij} c_{ij} \le B \\
\sum^M_{j=1} x_{ij} = 1 \\
x_{ij} \in {0, 1}
\end{align}
$$

解法一

根据 RL-MPCA 给出的方案，可以解得最终结果为（求解过程参见RL-MPCA论文）：
$$ j^* = \mathop{\arg\max}_{j} (v_{ij} - \lambda c_{ij}) $$

解法二

如果只有一个广告位置，且使用二价计费 ，原始问题可化简为
$$
\begin{align}
\max_{x_{i}} \sum^N_{i=1} x_{i} v_{i} \\
\text{s.t. } \quad \sum^N_{i=1} x_{i} c_{i} \le B \\
x_{i} \in {0, 1}
\end{align}
$$
最终可解得结果为(求解参考链接：智能出价——BCB求解)：
$$ bid = \frac{v_i}{\lambda} $$

关于两种解法的结果分析

本质上，两种解法结果应该是完全相同的，第一种解法中，如果只有一个广告位置，且使用二价计费，求解到的结果本质于第二种解法结果一致
- 当 $v_{i} > \lambda \cdot Price_{win} $ 时($Price_{win} = c_{i}$，表示净胜价格), 此时选择 $bid > Price_{win}$ 的出价即可获得本次竞拍，此时不管是解法一(取 $v_{ij} - \lambda * c_{ij}$ 最大的动作)还是解法二($bid=v_i/\lambda$)都会选择执行竞拍动作
- 反之，当当 $v_{i} < \lambda \cdot Price_{win}$ 时, 此时选择 $bid < Price_{win}$ 的出价即可获得本次竞拍，此时不管是解法一还是解法二都会选择执行不竞拍动作
解法一适用于任何场景，解法二则仅适用于只有一个广告位置，且使用二价计费的场景
解法二的结果使用起来会更简单：
- 解法一需要预估不同出价下的收益，实际上，在只有一个广告位置，且使用二价计费的场景，不竞争当前广告位置的价值为0，计费为0，若竞争，则价值为 $v_i$，计费为 $c_i$，所以仅需要预估价值 $v_i$，计费 $c_i$
- 解法二则可直接预估一个值 $v_i$ 即可，不需要预估 $c_i$，即在线不需要预估净胜价格
  - 但是离线流量回放求解 $\lambda$ 时，理论上也需要预估一个净胜价格，或者在给出一个价格时，需要知道是否会竞争成功。 $c_i$ 已经隐含在求解到的 $\lambda$ 中
- 若对于任意竞拍，都给定净胜价格，那么解法一和解法二等价，都只需要预估 $v_i$ 一个值即可

CA——Deep-Neural-Auction(DNA)

Deep Neural Auction, 简称 DNA

参考链接：
- 原始论文：Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising, Alibaba, KDD 2021
- 博客：KDD 2021 | Neural Auction: 电商广告中的端到端机制优化方法

问题定义

和 DeepGSP 类似，DNA拍卖问题形式化定义为：
$$
\begin{align}
\mathop{\text{maximize}}_{\mathbf{\mathcal{M}}} &\mathbb{E}_{\mathbf{b} \sim \mathcal{D}}\Big[\sum_{j=1}^L \lambda_j\times f_j(\mathbf{b};\mathbf{\mathcal{M}})\Big]\\
\text{s.t.} &\text{Incentive Compatibility (IC) constraint}, \\
&\text{Individual Rationality (IR) constraint},
\end{align}
$$
- $\mathbf{b}$：广告主出价向量
- $L$：优化目标数
- $\mathcal{D}$：广告主出价分布, $\mathbf{b}$ 是从分布 $\mathcal{D}$ 中采样得到的
- $\lambda_j$：目标权重，是用于控制目标之间重要性的权重因子，可调整目标重要性
- 注：相对 DeepGSP 论文的定义，这里增加了激励兼容(IC)和个体理性约束(IR)，其中个体理性约束是指竞拍者的效用不为负 $u_i = v_i - p_i \ge 0$

Deep Neural Auction 基本思路

分配规则和计费规则

基本思路：按照经典GSP的基本原理，先按照 Rank Score 进行非递减的顺序排序，然后竞胜者按照获得该位置所需要的最小价格计费
分配规则 $\mathcal{R}$ ：按照 Rank Score 排序(Rank Score 是关于出价 bid 非递减的函数)，$r_i(b_i)$，排序中最靠前的 Top-K 个广告主赢得 K 个广告位
计费规则 $\mathcal{P}$ ： $p_i = r_i^{-1}(r_{i+1}(b_{i+1}))$

DNA与传统拍卖模型的区别

DNA与传统拍卖模型的区别对照示意图

经济学属性

Definition 2.1 (Incentive Compatibility)

原始论文表述：

An auction mechanism is IC if it is in the best interest of each advertiser $i$ to truthfully reveal her maximum willing-to-pay price, i.e., $b_i = m_i$.
理解：一个拍卖机制是激励兼容的，意味着每个广告主的最佳利益就是真实的表达他愿意支付的最大出价
注：最大愿意支付价格，即 maximum willing-to-pay price，用 $m_i$ 表示

Definition 2.2 (Value Maximizer)

论文中，作者引入了价值最大化类型广告主（Value Maximizer），同时讨论了，价值最大化类型广告主和效用最大化类型广告主的区别（Utility Maximizer）
讨论：传统经典的拍卖机制，比如 VCG 拍卖或者 Myerson 拍卖，都假定了广告主是效用最大化的类型（Utility Maximizer），即广告主的目标是为了最大化其拟线性效用（Quasi-linear Utility），形式化的定义为： $u_i = v_i - p_i$。然而，作者观察到工业界的电商平台中，这种效用最大化模型不再能建模广告主的行为范式，比如，淘宝广告平台中，oCPC 和 MCB 这两种广告主，他们的目标都是在指定约束下，最大化他们的点击量/转化量，这种类型的广告主会使用自动出价服务，基于当前竞拍环境，为每个请求/PV计算并报告他们的最大 willing-to-pay 价格，这种行为范式可以建模为价值最大化（Value Maximizer）
- 注：MCB一般是指多约束，论文中主要指预算约束+PPA（pay-per-acquisition）或PPC（pay-per-click）约束
原文定义表述：

A value maximizer $i$ optimizes value $v_i$ while keeping payment $p_i$ below her maximum willing-to-pay $m_i$; when value is equal, a lower $p_i$ is preferred
理解：价值最大化类型的竞拍者的目标是在愿意支付的成本约束下（$p_i \le m_i$），最大化拿量；当量相等时，更倾向于更低的价格
在多位置拍卖系统中，在计费不超过最大愿意支付价格 $m_i$ 的情况下，广告主会更喜欢争取更高的位置；同时，在价值量 $v_i$ 相同的情况下，广告主更倾向于支付更低的价格
个人理解：Value Maximizer 只是表象，本质上，广告主的最终目标应该也是 Utility Maximizer（即利润最大化），只是这个效用包含了广告主毛利等私有信息，这部分信息是未知的

IC和IR

激励兼容满足等价于下面两个约束满足：
- Monotonicity: An advertiser would win the same or a higher slot if she reports a higher bid;
- Critical price: The payment for the winning advertiser is the minimum bid that she needs to report to maintain the same slot
个体理性约束：当满足IC要求的两个约束时，个体理性约束自然满足的，因为IC约束中隐含着 $p_i \le m_i$

Deep Neural Auction

整体架构

整体架构图
整体包含三个主要部分：Set Encoder, Context-Aware Rank Score Function, Differentiable Sorting Engine

Set Encoder

用于从整个竞价队列中提取特征，Set Encoder的输出会作为特征输入后续的其他模块
可以用于解决 ambiguity issue，该问题的定义是：在同一个拍卖中，相同的特征可能获得不同的结果：

The second challenge is data efficiency. The current learningbased approaches [20, 39] usually require a large number of samples to learn the optimal auction due to an ambiguity issue we observed in the data from auctions. It is a common case that an advertiser with the same feature profile can result in different outcomes in distinct auctions, e.g., wins in one auction but loses in another, due to the change of the auction context, e.g., the competition from the other advertisers.
编码过程
$$
\begin{align}
h_i &= \sigma(\phi_1(\mathbf{x}_i)) \\
\mathbf{h} &=\{h_i\}_{i=1}^N \\
h_i^\prime &= \sigma(\phi_2(\text{avgpool}(\mathbf{h}_{-i})))
\end{align}
$$
- 其中 $\{\mathbf{x}_i\}_{i=1}^N$ 表示候选广告， $\mathbf{h}_{-i}$ 表示出去广告 $i$ 后的其他广告特征

Context-Aware Rank Score Function

分配规则

输入是单个广告特征和Set Encoder输出的降价队列特征，用于计算 Rank Score 分数
其网络表示如下：
$$rankScore = r(b_i, \mathbf{x}_i^\prime)$$
- 其中 $\mathbf{x}_i^\prime = (\mathbf{x}_i, h_i^\prime)$
为了保证单调性，使用了一种两层的 MinMax 网络：设置 Q 组函数，每次包含 Z 个线性函数：
$$ r_i = \min_{q\in[Q]} \max_{z \in [Z]} (e^{w_{qz}}\times b_i + w^\prime_{qz}\times \mathbf{x}_i^\prime + \alpha_{qz})$$
- 单调性保证：任意给定 $w$ 和 $z$，都存在一个线性函数 $f_{qz}$：$f_{qz}(b_i, \mathbf{x}_i^\prime) = e^{w_{qz}} \times b_i + w^\prime_{qz}\times \mathbf{x}_i^\prime + \alpha_{qz}$，显然该线性函数关于出价 $b_i$ 单调，此时对多个单调的线性函数取 Max 操作不会改变单调性，继续取 Min 操作也不会改变单调性（ $b_i$ 增加时，任意函数 $f_{qz}(b_i, \mathbf{x}_i^\prime)$ 的最大最小值也都在增加）
- 函数拟合能力：上面的 MIN-MAX 函数理论上可以近似任意的函数（详情见：Monotone and partially monotone neural networks）

计费规则

计费逻辑如下：
$$ p_i = \max_{z\in[Z]}\min_{q\in[Q]} e^{-w_{qz}}(r_{i+1} -\alpha_{qz} - w_{qz}^\prime \times \mathbf{x}_i^\prime) $$
问题：这里的反函数是错的，理论上应该是下面的表达才对(TODO：待确认)：
$$ p_i = \min_{z\in[Z]}\max_{q\in[Q]} e^{-w_{qz}}(r_{i+1} -\alpha_{qz} - w_{qz}^\prime \times \mathbf{x}_i^\prime) $$
- 可以举例并画出函数图像说明： $f(x) = \max(2x, x+1)$ 的反函数是 $f^{-1}(y) = \min(\frac{1}{2}y, y-1)$

Differentiable Sorting Engine

输入 Rank Score 分数，进行可微分排序，并执行计费操作，包含 Differentialble Sorting Operator 和 Allocation & Pricing 两部分
设未排序的 Rank Score 分数集合为 $\mathbf{r} = [r_1, r_2, \cdots, r_N]^T$，令 $\text{argsort}(\mathbf{r})$ 为 $\mathbf{r}$ 降序排列的序号，则可以定义排列矩阵 $M_r \in \{0,1\}^{N\times N}$：
$$M_r[k,i]=
\begin{cases}
1& \text{if}\ i=\text{argsort}(\mathbf{r})[k]\\
0& \text{otherwise}
\end{cases}$$
进一步地，可以用下面的等价形式表示：
$$M_r[k,i]=
\begin{cases}
1& \text{if}\ i=\text{argmax}(c_k)\\
0& \text{otherwise}
\end{cases}$$
- 其中 $c_k = (N+1-2k)\mathbf{r} - A_r\mathbb{I}$, $A_r[i,j] = |r_i - r_j|$ 表示两个元素对之间的 Rank Score 差的绝对值， $\mathbb{I}$ 表示值全为1的列向量 $\mathbb{I}=[1,1,\cdots,1]^T$
- 这一步表述来自论文：Stochastic Optimization of Sorting Networks via Continuous Relaxations, Stanford University, ICLR 2019 的 Corollary 3 和附录 B.1 B.2，详细验证代码见附录
于是，对 $\text{argmax}$ 进一步做放松（放松为 $\text{softmax}$ ），则有
$$\hat{M}_r[k,:] = \text{softmax}(\frac{c_k}{\tau})$$
- $\tau > 0$ 表示温度系数，当 $\tau \to 0$ 时，$\hat{M}_r \to M_r$
- 理解：用 $\text{softmax}$ 来替换 $\text{argmax}$ 做放松可以理解为将 100% 的确定性选择概率变成了带随机性的选择概率
- $\hat{M}_r$ 也被作者称为行随机的排列矩阵（ row-stochastic permutation matrix ）
此时，如果将按照 Rank Score 降序排列后，按照反函数计费规则计费的结果表达为 $\mathbf{p} = [p_1, p_2, \cdots, p_N]^T$ ，则有 Top-K 广告的付费金额为：
$$ f_{\text{pay}} = \hat{M}_r[1:K,:]\cdot \mathbf{p} $$
- 理解：这里 $f_{\text{pay}}$ 是一个 K 行的向量，分别代表 Top-K 的支付值

端到端训练实现

主要损失函数

前K个位置拍卖的性能指标可以表达为：
$$
\begin{align}
\text{整体性能指标} &= \hat{M}_r[1:k,:] \cdot F_{\text{all}} \\
F_{\text{all}} &= [\sum_{l=1}^L\lambda_l\times f_l^1,\sum_{l=1}^L\lambda_l\times f_l^2,\cdots,\sum_{l=1}^L\lambda_l\times f_l^N]^T
\end{align}
$$
- 其中 $F_{\text{all}}$ 表示所有广告的性能指标向量
- 理解：$\hat{M}_r[1:k,:]$ 表示前 K 个位置展示 $N$ 个广告的概率，$\hat{M}_r[1:k,:] \cdot F_{\text{all}}$ 是一个 K 维向量，表示前 K 个位置的性能指标
因此，训练时最小化前K个位置的负目标性能指标和，即下面整体目标损失函数即可：
$$\mathcal{L}_{\text{tgt}} = \sum_{i=1}^K \hat{M}_r[i,:] \cdot F_{\text{all}}$$
- 注：由于排序改变会影响计费（论文中也称计费为 Revenue），作者使用 $f_{\text{pay}} = \hat{M}_r[1:K,:]\cdot \mathbf{p}$ 来近似代替前 K 个位置的计费（问题：这个计费的 Top-K 排序也是按照 Rank Score 降序排列得到的吧，一旦 Rank Score 发生了变化， Top-K 广告也要变化的，计费不用变化吗？）
- 无论如何都会出现不稳定问题(计费 Revenue 的值依赖着 Rank Score 的求逆)，以下是来自阿里官方账号的讲解 KDD 2021 | Neural Auction: 电商广告中的端到端机制优化方法的内容：
  
  仔细观察这两个 loss 的形式不难发现，$\mathcal{L}_{\text{tgt}}$ 的优化其实就是使网络产生的 rankscore 与在用户真实行为上计算出的多目标最优排序一致，但由于 revenue 的计算还是依赖于网络 rankscore 的求逆，导致 rankscore 之间的 distance 又会被显式优化，这给模型训练带来了一些不稳定的因素（离线实验中我们也确实观察到了）；而 $\mathcal{L}_{\text{ce}}$ 由于只纠正序的准确性，不涉及广告 rankscore 之间 distance 的学习，它的训练过程较为稳定。我们的经验是：如果优化目标仅有 revenue，那么 $\mathcal{L}_{\text{tgt}}$ 任务可以独立训练，最终会收敛（尽管其 learning curve 存在一些毛刺）；如果优化多个目标之间权衡，那么 $\mathcal{L}_{\text{tgt}}$ 的权重要和 $\mathcal{L}_{\text{ce}}$ 在同一水平，或者先全局优化 $\mathcal{L}_{\text{ce}}$ 学好 allocation，再引入 $\mathcal{L}_{\text{tgt}}$ 精细化优化 revenue
  值得注意的是，工业界广告系统的真实反馈通常是稀疏的，算法日志中有用户行为的数据占比可能较低。为了使训练信号更加稠密、提高模型学习的效率，我们将用户反馈与预估值进行了融合，在有用户行为的数据上使用后验校准技术来纠正预估值，再进一步构造两个 loss，提高了训练的稳定性

辅助损失函数

借助用户真实反馈来构建辅助损失，让出现最优排序的概率越大越好，辅助损失函数的形式如下：
$$ \mathcal{L}_{\text{ce}} = -\frac{1}{N} \sum_{k=1}^N \sum_{i=1}^N \mathbb{I}{(M_y[k,i]=1)} \log \hat{M}_r[k,i] $$
- 其中 $\mathbb{I}(\cdot) $ 是指示函数
- 注：$M_y[k,i]$ 表示按照真实反馈算出来的 ground-truth 排序矩阵（问题：无法观察到同一个请求不同排列的反馈吧，使用如何确定这个是最优的排列？除非用预估值或模拟器，如果用预估值的话，和普通GSP分配方式有何区别？）

附录：可微分排序argsort到argmax转换证明

证明

参考论文 Stochastic Optimization of Sorting Networks via Continuous Relaxations, Stanford University, ICLR 2019 的 Corollary 3 和附录 B.1 B.2

代码验证

验证代码如下：

import numpy as np

def generate_rank_matrix_original(r):
    """
    通过 argsort 生成排列矩阵 M_r^{(1)}
    """
    N = len(r)
    # argsort 返回的是从小到大排序的索引，我们需要降序排序
    sorted_indices = np.argsort(-r)
    Mr = np.zeros((N, N), dtype=int)
    for k in range(N):
        i = sorted_indices[k]
        Mr[k, i] = 1
    return Mr

def generate_rank_matrix_equiv(r):
    """
    通过等价定义生成排列矩阵 M_r^{(2)}
    """
    N = len(r)
    # 计算 A_r 矩阵: |r_i - r_j|
    A_r = np.abs(r.reshape(-1, 1) - r.reshape(1, -1))  # Shape: (N, N)
    # print(A_r)
    # 生成全1向量 I
    I = np.ones(N)

    Mr = np.zeros((N, N), dtype=int)

    for k in range(1, N + 1):
        # 计算 (N +1 - 2k)*r
        term1 = (N + 1 - 2 * k) * r
        # 计算 A_r @ I
        term2 = A_r @ I
        # 计算 c_k
        c_k = term1 - term2
        # 找到 argmax(c_k)
        # 如果有多个最大值，argmax 返回第一个
        i_max = np.argmax(c_k)
        Mr[k - 1, i_max] = 1
    return Mr

def verify_equivalence(r):
    Mr_original = generate_rank_matrix_original(r)
    Mr_equiv = generate_rank_matrix_equiv(r)
    print("Rank Score Vector r:")
    print(r)
    print("\n排列矩阵 M_r^{(1)} (原始定义):")
    print(Mr_original)
    print("\n排列矩阵 M_r^{(2)} (等价定义):")
    print(Mr_equiv)
    print("\n是否相同:", np.array_equal(Mr_original, Mr_equiv))
    print("-" * 50)

def main():
    np.random.seed(42)  # 为了结果可重复

    # # 测试案例1: 简单的已排序向量
    # r1 = np.array([5, 4, 3, 2, 1])
    # verify_equivalence(r1)

    # 测试案例2: 随机向量
    # r2 = np.random.rand(10)
    # verify_equivalence(r2)
    #
    # # 测试案例4: 含有负数的向量
    # r4 = np.array([3, -1, 4, -5, 2])
    # verify_equivalence(r4)

if __name__ == "__main__":
    main()

测试结果

Rank Score Vector r:
[ 3 -1  4 -5  2]

排列矩阵 M_r^{(1)} (原始定义):
[[0 0 1 0 0]
[1 0 0 0 0]
[0 0 0 0 1]
[0 1 0 0 0]
[0 0 0 1 0]]

排列矩阵 M_r^{(2)} (等价定义):
[[0 0 1 0 0]
[1 0 0 0 0]
[0 0 0 0 1]
[0 1 0 0 0]
[0 0 0 1 0]]

是否相同: True

说明两者确实等价

CA——DeepGSP

参考链接：
- 原始论文：Optimizing Multiple Performance Metrics with Deep GSP Auctions for E-commerce Advertising, Alibaba, WSDM 2021
- 博客：Deep GSP ：面向多目标优化的工业界广告智能拍卖机制

核心贡献

端到端拍卖机制
能保证单广告位下的激励兼容（Incentive Compatibility, IC）和多广告位下的对称纳什均衡（Symmetric Nash equilibrium, SNE）
离线+在线验证

问题建模

定义拍卖问题为多目标优化问题：
$$ \mathop{\text{maximize}}_{\mathbf{\mathcal{M}}} \mathbb{E}_{\mathbf{b} \sim \mathcal{D}}\Big[\sum_{j=1}^L w_j\times f_j(\mathbf{b};\mathbf{\mathcal{M}})\Big]$$
- $\mathbf{b}$：广告主出价向量
- $L$：优化目标数
- $\mathcal{D}$：广告主出价分布, $\mathbf{b}$ 是从分布 $\mathcal{D}$ 中采样得到的
- $w_j$：目标权重，是用于控制目标之间重要性的权重因子，可调整目标重要性
- 注：实际上，还应该加上激励兼容和个体理性的约束才完整

一些重要的理论

Theorem 1：IC，激励兼容

单位置拍卖机制 $\mathcal{M}<\mathcal{R},\mathcal{R}>$ 是激励兼容（Incentive-Compatible）的，当且仅当满足两个规则：
- 分配规则（Allocation Scheme） $\mathcal{R}$ 是单调的（即出价越高，竞拍获胜的概率越大，改规则也称为Monotone Allocation）；
- 计费规则（Pricing Rule） $\mathcal{P}$ 是竞胜者支付其需要保持竞胜状态所需要的最低报价（该价格也称为Critical Bid，该规则也称为Critical Bid based Pricing）：
  $$
  \begin{align}
  \mathcal{R}_i(z, \mathbf{b}_{-i}) &> \mathcal{R}_i(b_i, \mathbf{b}_{-i}) \ \text{if} \ z > b_i \text{(Monotone Allocation)} \\
  \mathcal{P}_i &= \text{inf}_{z \vert \mathcal{R}_i(z, \mathbf{b}_{-i}) = \mathcal{R}_i(b_i, \mathbf{b}_{-i})} \ \text{(Critical Bid based Pricing)}
  \end{align}
  $$
注意：Theorem 1 仅针对单位置（single slot）拍卖场景

Theorem 2: SNE，对称纳什均衡

拍卖机制 $\mathcal{M}<\mathcal{R},\mathcal{R}>$ 满足对称纳什均衡（Symmetric Nash equilibrium，SNE），当且仅当：
- 竞拍者在均衡状态下更喜欢他当前的分配到位置（相对其他位置而言，更喜欢当前位置）
  $$ \beta_i(v_i - p_i) \ge \beta_j(v_j - p_j) $$
  - 其中 $\beta_i$ 表示当前位置固有的CTR预估值（理解：$\beta_i(v_i - p_i)$ 表示当前位置点击的概率乘以点击价值和付出点击成本的差值
  - 个人理解：这里仅针对CPC计费场景，广告主针对点击来估计流量的点击价值，付费也在点击上，此时不同位置之间的最大价值差异在CTR上
注意：Theorem 2 可扩展到针对多位置（multi-slot）拍卖场景

Deep GSP Auction

分配规则和计费规则设计

分配规则 $\mathcal{R}$ ：按照 Rank Score 排序(Rank Score 是关于出价 bid 非递减的函数)，$r_i = R_\theta(b_i, \mathbf{x}_i)$，排序中最靠前的 Top-K 个广告主赢得 K 个广告位
- 这里参照了经典的GSP拍卖机制实现，选择了一个非单调递减的排序分数
计费规则 $\mathcal{P}$ ： $p_i = R_\theta^{-1}(r_{i+1},\mathbf{x}_i)$
- 用后一位广告主的分数，通过逆运算计算当前广告主的价格

Point-wise Monotonicity Loss

用于引导分配规则的单调性，思路是在损失函数中增加惩罚非单调的部分
单调损失部分呢定义如下：
$$ \mathcal{L}_{\text{mono}} = \sum_{i=1}^N \max(0, -\nabla_b R_\theta(b_i, \mathbf{x}_i)) $$
- 理解：非单调则说明梯度小于0，惩罚梯度小于0的部分即可引导 Rank Score 分数 $R_\theta(b_i, \mathbf{x}_i)$ 关于出价 $b_i$ 的梯度 $\nabla_b R_\theta(b_i, \mathbf{x}_i) \ge 0$，这种单调是不严格的，智能引导，不能强保障

Approximate Inverse Operation

用于近似计算计费规则中的逆运算操作
第一步：将 Rank Score 分数 $R_\theta(b_i, \mathbf{x}_i)$ 拆解为：
$$ r_i = R_\theta(b_i, \mathbf{x}_i) = b_i \times \pi_\theta(b_i, \mathbf{x}_i) $$
- 理解：$\pi_\theta(b_i, \mathbf{x}_i)$ 是关于 $b_i$ 的非线性函数
第二步：单调损失函数对应变为：
$$ \mathcal{L}_{\text{mono}} = \sum_{i=1}^N \max(0, -(\pi_\theta(b_i, \mathbf{x}_i) + b_i\nabla_b \pi_\theta(b_i, \mathbf{x}_i))) $$
- 复合函数求导展开
第三步：近似逆运算操作
$$ p_i = \frac{r_{i+1}}{\pi_\theta(b_i, \mathbf{x}_i)} $$
- 这里假定了 $\pi_\theta(b_i, \mathbf{x}_i)$ 是关于 $b_i$ 的一个函数，这样的好处是逆运算会变得非常简单，准确求解逆运算是需要推理神经网络（神经网络函数难以定义明确的反函数吧？）
- 论文中提到，通过观察看到了 $\pi_\theta(b_i, \mathbf{x}_i)$ 关于 bid 的变化是不敏感的
  
  We have observed from an industrial data set that the non-linear function $\pi_\theta(b_i, \mathbf{x}_i)$ is not so sensitive to the bid (please refer to the experiment results in Section 4.2.3 for more details). Thus, in payment calculation, we regard $\pi_\theta(b_i, \mathbf{x}_i)$ as a constant w.r.t. $b_i$

Deep GSP的一些讨论

Theorem 3：Deep GSP的纳什均衡

Deep GSP Auction存在对称纳什均衡状态的非空集合

Theorem 3. There exists a non-empty set of Symmetric Nash Equilibrium (SNE) states in the Deep GSP auction.
理解：Deep GSP Auction拍卖下，至少存在一个状态是满足对称纳什均衡的

Deep GSP 实现

思考：考虑到一些指标是难以通过精确数学公式定义的，所以考虑使用反馈来学习

As introduced in Section 2.2, some performance metrics are not feasible to have rigorous mathematical analyses, and we can only evaluate these metrics via actual feedback from the system after deploying the auction mechanism.

强化学习建模

状态：
- 广告信息
- 广告主信息
- 用户特征等
动作：
- 深度 Rank Score 模型的输出就是动作（连续动作），策略就是深度 Rank Score 模型本身，即策略就是 $R_\theta$
奖励：
$$ re_i = F(\mathbf{b};\mathcal{M}) - \eta \times \max(0, (1-\epsilon)\mu_i(\mathcal{M_0}) - \mu_i(\mathcal{M})) $$
- 理解：
  - $F(\mathbf{b};\mathcal{M})$ 部分是原始目标；
  - $- \eta \times \max(0, (1-\epsilon)\mu_i(\mathcal{M_0}) - \mu_i(\mathcal{M}))$ 部分表示希望引导 $\mu_i(\mathcal{M}) \ge (1-\epsilon)\mu_i(\mathcal{M_0})$ 成立
状态转移 ：
- 模型训练是单步的是单步决策问题，无需要考虑状态转移

强化学习实现更多细节

强化学习的目标是：
$$ R_\theta^* = \mathop{\arg\max}_{R_\theta} \mathbb{E}_{\mathbf{b}\sim \mathcal{D}}[re_i|R_\theta] $$
使用DDPG来训练，Critic 网络和 Policy 网络损失函数如下：
$$
\begin{align}
\text{Critic Net:} \quad \mathcal{L}(Q_\theta) &= \frac{1}{N}\sum_i(y_i - Q_\theta(s_i, a_i))^2 \\
\text{Policy Net:} \quad \mathcal{L}(R_\theta) &= \frac{1}{N}\sum_i(-Q_\theta(s_i, R_\theta(s_i)) + \gamma \times \mathcal{L}_{\text{mono}})
\end{align}
$$
- 其中 $y_i = re_i$
实现时，与原始的DDPG有两点不同：
- Deep GSP 是一个单步决策问题
DeepGSP强化框架(Figure 2)：

实验指标设置

一般业务指标

Revenue Per Mille (RPM), Add-to-Cart Rate (ACR), CTR, CVR, GMV Per Mille (GPM)等等

单调性指标

计算出价和其对应的 Deep Rank 模型输出之间的单调性关系，该指标定义为：
$$ \mathcal{T}_m = \frac{1}{n}\sum \rho_{rank_{bids}},\rho_{rank_{outputs}} $$
- 其中斯皮尔曼秩相关系数（Spearman’s rank correlation coefficient）系数的定义为：
  $$ \rho = 1 - \frac{6 \sum d_i^2}{n(n^2-1)} $$
  - $d_i$ 表示每一对样本之间的等级差异。当排序一致时，等级差异为0，此时 $\rho$ 取得最大值 1；当排序相反时，可以证明，$\rho$ 取得最小值 -1

计费错误率

计费错误率（Payment Error Rate，PER），近似计费可能引入误差，作者首先使用二分查找去搜索精确的计费 $p_i^*$，使用 $\frac{p_i}{p_i^*}$ 来表示PER

激励兼容性

作者使用 Individual Stage-IC (i-SIC) 指标来量化激励兼容性(该指标参考自A Data-Driven Metric of Incentive Compatibility)，其定义为：假设广告主的效用是 $\hat{u}(b) = b \times x(b) - p(b)$ （其中 $x(\cdot)$ 是分配概率），同时广告主的价值分布满足 $F$。则 i-SIC 可以定义为：
$$ \text{i-SIC} = \lim_{\alpha \to 0} \frac{\mathbb{E}_{v\sim F}[\hat{u}((1+\alpha)v)] - \mathbb{E}_{v\sim F}[\hat{u}((1-\alpha)v)] }{2\alpha \times \mathbb{E}_{v \sim F}[v \times x(v)]} $$
- i-SIC 通过对出价进行微小扰动并评估给竞拍者带来的效用以量化激励兼容性，可通过在拍卖日志上的黑盒模拟直接计算
- i-SIC 取值为0到1（一价拍卖对应0，二价拍卖对应1），值越大，说明激励兼容性越好
  
  We now utilize the i-SIC metric [7] to evaluate incentive compatibility (IC) of Deep GSP. The i-SIC metric is between 0 and 1, and the larger value means the better IC property
  - 可以证明：一价计费下，i-SIC的值为0；二价计费下，i-SIC 的值为1
    - 一价计费时，由于竞拍者的出价等于商户的计费，在 $\lim_{\alpha \to 0}$ 时
      - 分配概率为 $x((1+\alpha)v) = x((1-\alpha)v) = x(v)$
      - 计费为 $p((1+\alpha)v) = (1+\alpha)v \times x(v) $ 和 $ p((1-\alpha)v) = (1-\alpha)v \times x(v)$，故而有
        $$
        \begin{align}
        \mathbb{E}_{v\sim F}[&\hat{u}((1+\alpha)v)] - \mathbb{E}_{v\sim F}[\hat{u}((1-\alpha)v)] \\
        &= \mathbb{E}_{v\sim F}[(1+\alpha)v \times x(v) - (1+\alpha)v \times x(v) - ((1-\alpha)v \times x(v)-(1-\alpha)v\times x(v))] \\
        &= \mathbb{E}_{v\sim F}[0] \\
        &= 0
        \end{align}
        $$
    - 二价计费时，若竞拍者赢得拍卖，在 $\lim_{\alpha \to 0}$ 时
      - 分配概率为 $x((1+\alpha)v) = x((1-\alpha)v) = x(v)$
      - 计费为 $p((1+\alpha)v) = p((1-\alpha)v) = p(v)$，故而有:
        $$
        \begin{align}
        \mathbb{E}_{v\sim F}[\hat{u}((1+\alpha)v)] - \mathbb{E}_{v\sim F}[\hat{u}((1-\alpha)v)] &= \mathbb{E}_{v\sim F}[(1+\alpha)v \times x(v) - (1-\alpha)v \times x(v)] \\
        &= \mathbb{E}_{v\sim F}[2\alpha v \times x(v) ] \\
        &= 2\alpha \mathbb{E}_{v\sim F}[ v \times x(v) ]
        \end{align}
        $$

对照基线

GSP

Generalized Second Price auction (GSP). 排序规则是通过 expected Cost Per Milles (eCPM) 排序，支付规则时使用下一位的排序分反算计费

uGSP

Utility-based Generalized Second Price auction (uGSP)，最早提出于论文 Optimising trade-offs among stakeholders in ad auctions, Microsoft Research, 2014. 是对GSP的一种扩展，其分配规则中的排序公式为：
$$ r_i(b_i) = \lambda_1 \times b_i \times pCTR_i + o_i $$
- 其中 $o_i$ 表示其他效用指标，比如作者使用了 $o_i = \lambda_2 \times pCTR_i + \lambda_3 \times pCVR_i$
支付规则与GSP相同，都是通过下一位的排序分反算计费

附录：Smooth Transition是什么？

以下内容参考自：基于深度学习的广告拍卖机制论文阅读笔记（1）

平滑切换（Smooth Transition），即多目标优化中的各指标权重发生变化时，广告主侧的优化目标不会有明显的波动；
理解：不是“广告主的优化目标”不会有明显波动，应该是“广告主效果指标”不会有明显波动
原始论文内容：

As the importance of different performance metrics can vary over time due to business needs, we further introduce the smooth transition constraint to ensure the advertiser performance metrics not fluctuate too much when the auction mechanism switches among candidate mechanisms to achieve different optimization objectives

Another desirable property we want to achieve is Smooth Transition (ST). As discussed in Section 1, the performance objectives of the ad platform may vary due to the change of the business logic. If the new optimization objective is quite different from the previous one, the resulting auction mechanism would significantly affect the advertisers’ utilities [2]. This introduces the chaos of the auction environment. To stabilize advertisers’ utility change under different mechanisms, we choose a benchmark mechanism $\mathcal{M}_0$, and require advertisers’ utility under the new mechanism should not be less than $1-\epsilon$ of that under $\mathcal{M}_0$. The benchmark mechanism $\mathcal{M}_0$ could be the currently deployed mechanism.
$$ \mu_i(\mathcal{M}) \ge (1-\epsilon)\mu_i(\mathcal{M_0}) $$
where we set a lower bound for advertiser $i$’s utility $\mu_i$ when selecting a new auction mechanism $\mathcal{M}$. The lower bound $\bar{\mu}(\mathcal{M}_0)$ could be set as the average utility over a certain period under the benchmark mechanism $\mathcal{M}_0$. The parameter $\epsilon$ is a tolerant utility loss ratio for advertisers (0 ≤ $\epsilon$ ≤ 1). By choosing an appropriate $\epsilon$, the advertiser’s utility would not fluctuate too much when the auction mechanism is switched towards optimizing another objective.
个人理解：在切换不同候选拍卖机制去实现不同的优化目标时，广告主效果波动不大(相对之前的基线不能负向太多)，相当于能比较平滑的迁移拍卖机制

CA——GAVE

参考链接：
- 原始论文：Generative Auto-Bidding with Value-Guided Explorations, SIGIR 2025, Kuaishou

整体思路

现有自动出价方法 ：通常采用 rule-based strategies 或 RL 技术，这些方法存在一些问题：
- rule-based strategies ：缺乏适应时变市场条件的灵活性
- RL-based methods ：在 MDP 框架中难以捕捉重要的历史依赖关系和观测结果
- 通用问题 ：
  - 目前切换的适应性问题 ：在 ensuring strategy adaptability across diverse advertising objectives 方面常常面临挑战
  - Offline问题 ：随着越来越多地采用离线训练方法来促进稳定在线策略的部署和维护，在固定离线数据集上进行训练所导致的行为模式记录和行为崩溃问题变得日益突出
为解决这些局限性，论文提出了基于价值引导探索的离线生成式自动出价框架（offline Generative Auto-bidding framework with Value-Guided Explorations，GAVE）
- 通过 Score-based未来回报（Return-To-Go, RTG）模块适应各种广告目标
- 将动作探索机制与基于 RTG 的评估方法相结合，在探索新动作的同时确保保持稳定性的更新
- 设计了一个可学习的价值函数来指导动作探索的方向，并减轻 OOD（Out-of-Distribution）问题
实验：离线+在线
- 注：论文方法在 NeurIPS 2024 竞赛 “AIGB赛道 ：使用生成模型学习自动出价智能体” 中荣获第一名
其他：实现代码已开源 Applied-Machine-Learning-Lab/GAVE

一些讨论

自动出价的重要性 ：自动出价凭借其在动态竞争的在线环境中优化出价决策的强大能力，已成为广告平台的关键策略，有助于企业触达目标受众并提高销售额
出价需求 ：现代广告系统非常复杂（市场条件的波动、用户行为的多样性），这要求出价策略能够适应这些变化并与广告商的多样化目标保持一致。此外，大量需要实时处理的广告竞价进一步加剧了这一需求，在这种情况下，人为干预既不切实际，也往往无法实现最佳广告效果
现有解决方案主要发展为两类：
- rule-based strategies ：计算量小且易于部署，但其静态特性导致其不适合动态市场，也无法满足广告商的多样化需求
- RL-based methods ：虽然采用 MDP 来适应环境变化并获得更好的性能，但面临一个关键的结构性制约：
  - MDP 状态独立性假设本质上忽略了出价序列中的时间依赖关系和观测结果。这一限制阻碍了对不断变化的行为模式和市场波动的识别，大大削弱了RL在高度波动的实时出价环境中的实际适用性
  - 个人理解：这里对 RL 无法建模波动主要体现在无法预知快速变化的流量趋势（特别是与历史趋势不一致时）；特别地，出价场景可能是 POMDP 问题，常规 RL 方法将难以解决问题，将历史序列都作为输入才能缓解
DT 在出价上的前景 ：Decision Transformer（DT）作为一个强大的框架，能够有效捕捉时间依赖关系和历史上下文（temporal dependencies and historical context），因此，将 DT 应用于离线出价建模为改进策略提供了一个有前景的方向，其优点有：
- 适配Offline RL场景 ：通过采用离线训练范式，DT 规避了在线训练的风险和实施挑战，确保了在各种场景中的更广泛适用性
- 时间依赖和上下文建模 ： DT 的生成式建模基础进一步使其能够明确捕捉时间依赖关系和历史出价上下文，实现与现实世界广告环境的动态特性相匹配的自适应决策
DT 的面临问题 ：
- 首先，实际部署需要适应复杂的广告目标 ：其评估指标不仅限于总点击量或转化率等基本指标，这些目标通常涉及许多复杂函数（包含相互依赖的参数，如 CPA 或 CPC 约束等），这要求 DT 建模具有自适应优化目标 ，以符合多样化的运营标准
- 其次，在离线环境中直接训练 DT 模型可能会局限于已记录的行为模式 ，并遭受行为崩溃问题，这需要在稳定更新的同时加强动作探索
论文提出了一个统一框架 GAVE，用于增强 DT 在离线生成式自动出价中的应用
- 首先，为适应复杂的广告目标，论文设计了一个 Score-based RTG 模块，其分数函数可定制，通过可微编程实现对各种目标要求（如CPA约束）的自适应建模
- 其次，提出了一种动作探索机制以及基于 RTG 的评估方法，用于在固定数据集之外探索和评估动作，同时确保探索动作与原始动作之间的稳定更新
  - 在如此敏感的出价环境中，动作空间大，通过随机探索学习有益策略并避免分布外（OOD）风险颇具挑战。因此，论文引入了一个可学习的价值函数来指导动作探索过程，将探索导向潜在的最优动作。该机制将探索锚定在合理区域内，同时实现可控的外推（extrapolation），从而促进策略改进并进一步减轻OOD问题
论文的贡献：
- 引入了创新框架 GAVE ，利用 DT 优化自动出价策略，旨在无缝适应各种现实场景，提出了三项技术创新：
  - （1）一个 Score-based RTG 模块，通过可微编程实现针对各种广告目标的可定制函数；
  - （2）一种动作探索机制，结合基于 RTG 的评估，确保稳定更新；
  - （3）一个可学习的价值函数，将探索锚定在合理区域，从而减轻OOD风险，并实现可控外推以改进策略
- 实验：离线+在线，AIGB 出价赛道第一名

一些基础知识

自动出价问题

考虑在离散时间段 $i = 1, \cdots, I$ 内到达的一系列 $I$ 个曝光机会。广告商通过为这些曝光提交出价 $\{b_{i}\}_{i = 1}^{I}$ 参与实时竞争
拍卖机制遵循以下规则：
- 如果广告商的出价 $b_{i}$ 超过其他参与者的最高竞争出价 $b_{i}^{-}$，则该广告商赢得曝光 $i$
- 获胜的广告商随后会产生成本 $c_{i}$，该成本由拍卖机制确定，按照行业标准做法，论文采用 GSP 拍卖机制
广告商的目标 ：在指定时间段内通过赢得的曝光最大化总获取价值。这个优化问题可以正式表示为：
$$\max \sum_{i = 1}^{I} x_{i} v_{i}$$
- 其中 $v_{i} \in \mathbb{R}^{+}$ 表示广告商对曝光 $i$ 的私人估值（例如转化率或点击率），$x_{i} \in \{0, 1\}$ 表示指示拍卖结果的二元决策变量：
  $$x_{i}= \begin{cases}1 & \text{If } b_{i}>b_{i}^{-} \\ 0 & \text{Otherwise} \end{cases}$$
同时，广告商必须满足多个约束条件以确保有效的广告计划（campaign）管理。基本约束是总预算限制：
$$\sum_{i = 1}^{I} x_{i} c_{i} \leq B$$
- 其中 $B \in \mathbb{R}^{+}$ 表示广告商的总预算。其他关键绩效指标（KPI）约束，以每次获取成本（CPA）为例，可以表示如下：
  $$\frac{\sum_{i = 1}^{I} x_{i} c_{i} }{\sum_{i = 1}^{I} x_{i} v_{i} } \leq C \tag{4}$$
  - 其中 $C \in \mathbb{R}^{+}$ 表示最大允许的CPA。这个比率量化了广告支出相对于价值创造的效率。由于大多数其他KPI约束可以类似地建模，为简单起见，论文仅考虑CPA约束。然而，与由拍卖平台直接管理的预算约束不同，这些KPI约束在实际场景中通常并不严格。这是因为计算这些约束需要广告商对所有出价曝光的 $v_{i}$，因此只有在整个出价过程结束后才能确定真正的CPA。尽管如此，论文仍然希望在建模中将它们作为软约束使用
因此，整个出价过程可以表示为：
$$\begin{aligned} \max_{b_{1}, \cdots, b_{I} } & \sum_{i} x_{i} v_{i} \\ \text{s.t.} & \sum_{i} x_{i} c_{i} \leq B \\ & \frac{\sum_{i} x_{i} c_{i} }{\sum_{i} x_{i} v_{i} } \leq C \end{aligned} \tag{5}$$
解决这个优化问题存在固有的挑战，这源于曝光的高基数以及对未来拍卖表现的基本不确定性。先前的研究将这个问题重新表述为一个线性规划问题，以得出简化的最优出价策略：
$$b_{i}^{*}=\lambda_{0}^{*} v_{i}-\sum_{j} \lambda_{j}^{*}\left(q_{i j}\left(1-\mathbb{1}_{C R_{j} }\right)-\mathbb{k}_{j} \mathbb{p}_{i j}\right) \tag{6}$$
- 其中 $b_{i}^{*}$ 表示曝光 $i$ 的理论最优出价，$q_{ij}$ 可以是任何性能指标或常数，$\mathbb{1}_{C R_{1} }$ 是指示约束 $j$ 是否与成本相关的指标函数。$P_{i j}$ 和 $k_{j}$ 可以视为在多个KPI条件下公式（5）中 $v_{i}$ 和 $c$ 的扩展表达式。这种重新表述将自动出价问题转化为确定满足所有约束的最优 $\lambda_{0}^{*}$ 和 $\lambda_{j}^{*}$。通过将公式（6）代入公式（5），令 $j = 1$，$\mathbb{1}_{C R_{j} } = 1$，$\mathbb{P}_{i j} = v_{i}$，$k_{j} = C$ 且 $q_{i j}$ 为任何性能指标或常数，我们可以得到：
  $$b_{i}^{*}=\left(\lambda_{0}^{*}+\lambda_{1}^{*} C\right) v_{i}=\lambda^{*} v_{i} \tag{7}$$
  - 其中 $\lambda^{*}=\lambda_{0}^{*}+\lambda_{1}^{*} C$ 作为统一的出价参数。因此，许多近期研究试图通过在出价过程中迭代确定最优的 $\lambda^{*}$ 来解决出价问题。此外，值得注意的是，当根据公式（7）解决出价问题时，第一个条件，即 $\sum_{i} x_{i} c_{i} \leq B$ 总是满足的。这是因为当广告商的预算不足时，拍卖平台会自动控制 $x_{1}$，以确保广告商不欠款。然而，第二个条件并不总是满足，因为论文预测的 $\lambda$ 与最优的 $\lambda^{*}$ 之间存在差距。解决这个问题的一个简单方法是在评估阶段为模型选择在公式（7）的目标函数中添加一个关于CPA条件的惩罚项，这将在3.2节中进一步讨论

基于 DT 的自动出价

为解决自动出价问题，现有方法采用基于规则的策略或RL方法进行优化。然而，基于规则的策略通常无法适应现实出价环境的高度动态性，而RL方法依赖于由 $s_{t + 1} = f(s_{t}, a_{t})$ 定义的状态转换，这使得对拍卖生态系统中固有的重要时间依赖关系和历史观测进行建模变得复杂
Transformer架构的最新进展催生了 DT，使其成为顺序决策的最先进方法。DT 在捕捉长程依赖关系方面表现出色，使其非常适合拍卖结果显示出显著时间相关性的出价环境。基于这个框架，论文将自动出价视为 DT 设置下的序列建模任务。出价期被划分为离散的时间步，每个时间步在特定的环境设置下进行配置：
- 状态 $s_{t}$ ：状态向量 $s_{t}$ 包含一系列特征，用于描述时间步 $t$ 的出价条件。对于广告场景，这些特征可以是剩余时间、未使用的预算、历史出价统计信息等
- 动作 $a_{t}$ ：动作 $a_{t}$ 表示在整个出价期内可以迭代调整的出价变量。在论文中，根据公式（7），最优动作是 $a = \lambda^{*}$。因此，论文将时间步 $t$ 的实际动作表示为： $a_{t}=\lambda_{t}$
- 奖励 $rw_{t}$ ：假设有 $N_{t}$ 个候选曝光在时间步 $t$ 到 $t + 1$ 之间到达。奖励 $rw_{t}$ 可以定义为： $rw_{t}=\sum_{n = 0}^{N_{t} } x_{n_{t} } v_{n_{t} }$，其中 $x_{n_{t} }$ 和 $v_{n_{t} }$ 是时间步 $t$ 第 $n$ 个曝光的二元指示符和价值
- 未来回报（Return-To-Go, RTG） $r_{s}$ ： RTG 值表示在未来时间步中要获得的总奖励： $r_{t}=\sum_{t’ = t}^{T} rw_{t’}$，其中 $T$ 是最后一个时间步
这些设置导致了以下轨迹表示，非常适合自回归训练和推理：
$$\tau=\left(r_{1}, s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, \cdots, r_{T}, s_{T}, a_{T}\right)$$

GAVE 整体框架介绍

GAVE概述

GAVE整体架构：
如图1所示，GAVE采用 DT 架构，其中 RTG、状态和动作对构成输入序列，即时间戳 $t$ 处的 $(r_{t}, s_{t}, a_{t})$。与传统 DT 不同，GAVE引入了几个关键创新，以实现自适应优化、增强稳定性并促进策略改进，这些创新包括
- 自适应的 RTG ：用于与多样化广告目标对齐的 Score-based RTG （图1（a.1））
- 配备基于 RTG 评估机制的动作探索模块（图1（a.2）），用于发现和评估新动作并稳定更新
- 一个可学习的价值函数（图1（a.3）），用于引导探索以改进策略 ，同时减轻分布外（OOD）风险。GAVE的训练遵循离线范式（图1（b）），使用序列样本作为输入生成预测标签
- 为进行评估，采用模拟出价环境（图1（c）），其中测试模型与固定策略智能体进行交互
GAVE的预测过程如下所示：
$$\left\{\begin{array}{l} \left(\hat{\beta}_{t}, \hat{a}_{t}, \hat{V}_{t+1}\right)=GAVE(r_{t-M},s_{t-M},a_{t-M},\cdots ,r_{t},s_{t})\\ \hat {r}_{t+1}=GAVE(r_{t-M},s_{t-M},a_{t-M},\cdots ,r_{t},s_{t},a_{t})\\ \tilde {a}_{t}=\hat {\beta }_{t}a_{t}\end{array} \right.$$
- 其中 $M$ 是一个超参数，表示具有 $M + 1$ 个输入时间步的序列
GAVE采用自适应的 Score-based RTG 函数 ，可以使优化目标与不同的广告目标保持一致：在时间步 $t$ 的动作探索过程中，除了预测动作 $\hat{a}_{t}$ 之外，GAVE还预测以下内容：
- 一个系数 $\hat{\beta}_{t}$
  - 问题：$\hat{\beta}_{t}$ 的训练依赖 $\tilde {a}_{t}$，继而依赖 $\tilde {r}_{t}$，损失函数见文章后面的公式（22）？是否在图1（a.2）中还需要接一个网络预估 $\tilde{r}_{t}$ 才能反传损失函数吗？
  - 回答：从源码看，是的，且使用的是和主网络相同的同一个 transformer 网络
    - transformer 网络过程见：CAVE/…/dt.py：$\tilde {a}_{t}\rightarrow \tilde {r}_{t}$ 定义
    - 损失函数见：CAVE/…/dt.py：$L_v$ 定义
- 一个用于估计可学习价值函数 $V_{t + 1}$ 的 $\hat{V}_{t + 1}$（注：文章后面会介绍，损失函数是分位点回归）
- 一个 RTG 值 $\hat{r}_{t + 1}$ （注：文章后面会介绍，拟合目标是真实的 RTG $r_{t+1}$）
以下创新共同使GAVE能够实现更好的性能和鲁棒性：
- 通过使用基于 RTG 的评估方法评估探索动作 $\tilde{a}_{t}$ 和动作标签 $a_{t}$，GAVE应用平衡更新策略来协调 $\tilde{a}_{t}$ 和 $a_{t}$。这确保了一个保持稳定性的更新过程
- 引入可学习的价值函数 $V_{t + 1}$ 来引导模型朝着潜在的最优策略改进，同时进一步降低OOD风险

Score-based RTG

如2.1节所述，直接优化赢得曝光的累积价值可能会导致每次行动成本（CPA）约束显著超出其限制范围。为解决这个问题，可以构建包含惩罚项的目标函数作为评估指标，从而能够依据特定的广告目标调整对CPA限制的重视程度
- 这种方式有助于对最优模型进行评估和筛选。例如，先前的研究工作[44]提出在测试阶段使用分数 $S$ 来评估模型的实际性能，进而能够挑选出性能更优的模型。该分数整合了针对CPA约束的惩罚项，用于评估整个出价周期内出价模型的整体表现，公式如下：
  $$\begin{cases}
  CPA = \frac{\sum_{i} x_{i} c_{i} }{\sum_{i} x_{i} v_{i} } \\
  \mathbb{P}(CPA; C) = \min\left\{\left(\frac{C}{CPA}\right)^{\gamma}, 1\right\} \\
  S = \mathbb{P}(CPA; C) \cdot \sum_{i} x_{i} v_{i}
  \end{cases} \tag{13}$$
- 注：前文已经定义过，$C$ 是允许的最大 $CPA$
- 理解： $CPA > C$ 时，$\mathbb{P}(CPA; C) < 1$ 成立，此时原始收益会变小
在论文中，论文将约束条件直接融入训练阶段，不再仅仅依赖于预训练模型的选择来提升评估分数（如何理解？）
- 为了使训练与各种广告目标的评估指标保持一致，论文提出在 GAVE 中采用带约束的分数函数（而非无约束的 $\sum_{i = 1}^{I} x_{i} v_{i}$）来进行 RTG 建模，如图1（a.1）所示。例如，基于公式（13）所定义的评估指标，可以利用以下 Score-based RTG 函数来使训练与评估同步：
  $$\begin{cases}
  CPA_{t} = \frac{\sum_{i}^{I_{t} } x_{i} c_{i} }{\sum_{i}^{I_{t} } x_{i} v_{i} } \\
  \mathbb{P}(CPA_{t}; C) = \min\left\{\left(\frac{C}{CPA_{t} }\right)^{\gamma}, 1\right\} \\
  S_{t} = \mathbb{P}(CPA_{t}; C) \cdot \sum_{i}^{I_{t} } x_{i} v_{i} \\
  r_{t} = S_{T} - S_{t - 1}
  \end{cases} \tag{14}$$
- $I_{t}$ 表示从时间步0到时间步 $t$ 的曝光数量
- $S_{t}$ 代表时间步 $t$ 的广义分数函数
- $T$ 表示出价周期中的最后一个时间步
- 通过将分数计算推广到每个时间步，推导出 RTG $r_{t}$，以表示尚未获得的未来分数，进而引导GAVE的优化方向
此外，在实际应用中，不同的广告目标对CPA约束的依赖程度可能有所不同，从而产生不同的评估指标。尽管如此，通过以类似的方式将分数推广到每个时间步（即 $S_{t}$），训练和评估仍可保持一致，公式如下：
$$r_{t} = S_{T} - S_{t - 1} \tag{15}$$
这种 Score-based RTG 函数增强了 GAVE 的灵活性，确保其能够适用于各种不同的广告目标
问题：在推理阶段，广告曝光次数等是未知的，如何设计对应的 RTG？

Action Explorations

本节的主要目标是在训练过程中探索新的动作，以发现离线数据集中可能缺失的策略，从而实现更好的模型优化，但离线环境动作探索面临以下问题：
- 不探索面临的问题 ：在离线环境中，由于无法与环境进行交互，仅从固定的数据集中学习可能会导致模型局限于已记录的行为模式
- 探索面临的问题 ：但在数据集之外探索动作可能会引入固有的分布转移，进而可能导致行为崩溃[6, 21]（与实际动作标签相比，探索出的动作对模型性能的影响可能是有益的，也可能是有害的，这给开发保持稳定性的更新过程带来了巨大挑战）
为应对这些挑战，GAVE 引入了一种全新的动作探索机制，并结合基于 RTG 的评估方法，如图1（a.2）所示。这使得GAVE能够通过识别动作的重要性，自适应地调整动作的探索和更新方向，从而实现保持稳定性的更新
- 具体而言，在时间步 $t$，GAVE预测一个与 $a_{t}$ 维度相同的系数 $\hat{\beta}_{t}$，以生成一个新的动作 $\tilde{a}_{t}$。该过程的正式表达式为：
  $$\begin{cases}
  \hat{\beta}_{t} = \sigma(FC_{\beta}( DT (r_{t - M}, s_{t - M}, a_{t - M}, \cdots, r_{t}, s_{t}))) \\
  \tilde{a}_{t} = \hat{\beta}_{t}a_{t}
  \end{cases}$$
  - 如前文所述，$M$ 是一个超参数，表示具有 $M + 1$ 个输入时间步的序列
其中，$ DT (\cdot)$ 表示 DT backbone（主干网络），$FC_{\beta}(\cdot)$ 表示全连接层，$\sigma$ 是缩放函数。为减轻分布外（OOD）问题，缩放函数定义为：
$$\sigma(x) = Sigmoid(x) + 0.5$$
- 该公式将 $\hat{\beta}_{i}$ 限制在区间 $[0.5, 1.5]$ 内，确保探索出的动作 $\tilde{a}_{t}$ 与动作标签 $a_{t}$ 保持接近
为了在训练过程中最小化分布转移并实现保持稳定性的更新，论文并未直接使用 $\tilde{a}_{t}$ 来生成新样本，而是将其作为额外标签，与原始标签 $a_{t}$ 共同平衡动作更新
- 这种方法需要估计 $\tilde{a}_{t}$ 和 $a_{t}$ 的相对重要性，以确定预测动作 $\hat{a}_{t}$ 的最优更新方向
- 根据强化学习的惯例[21, 39, 41]，论文将 $a_{t}$ 的动作价值定义为 $r_{t + 1}$ （时间步 $t + 1$ 的 RTG），因为它 代表了执行动作 $a_{t}$ 后 未来的累积回报
论文设计了如图1（b.1）所示的 $w_{t}$，以平衡更新方向：
$$\begin{cases}
\tilde{r}_{t + 1} = GAVE(r_{t - M}, s_{t - M}, a_{t - M}, \cdots, r_{t}, s_{t}, \tilde{a}_{t}) \\
\hat{r}_{t + 1} = GAVE(r_{t - M}, s_{t - M}, a_{t - M}, \cdots, r_{t}, s_{t}, a_{t}) \\
w_{t} = Sigmoid(\alpha_{r} \cdot (\tilde{r}_{t + 1} - \hat{r}_{t + 1}))
\end{cases} \tag{18}$$
- 其中，$\tilde{r}_{t + 1}$ 和 $\hat{r}_{t + 1}$ 分别表示 $\tilde{a}_{t}$ 和 $a_{t}$ 的估计 RTG
- 问题：$\alpha_{r}$ 是超参数吗？如何设置？
- 相应的动作探索损失函数定义为：
  $$\begin{cases}
  L_{r} = \frac{1}{M + 1} \sum_{t - M}^{t}(\hat{r}_{t + 1} - r_{t + 1})^{2} \\
  L_{a} = \frac{1}{M + 1} \sum_{t - M}^{t}((1 - w_{t}’) \cdot (\hat{a}_{t} - a_{t})^{2} + w_{t}’ \cdot (\hat{a}_{t} - \tilde{a}_{t}’)^{2})
  \end{cases} \tag{19}$$
  - $w’$ 和 $\tilde{a}_{t}’$ 表示梯度冻结后的 $w$ 和 $\tilde{a}_{t}$
  - $\hat{a}_t$ 是预测动作，也是 $L_{a}$ 的学习目标
  - 通过 $L_{r}$，GAVE 确保了 RTG 预测的准确性，能够可靠地估计 $\tilde{a}_{t}$ 和 $a_{t}$ 的 RTG
  - 通过 $L_{a}$，GAVE 在 $\tilde{a}_{t}$ 和 $a_{t}$ 之间维持了平衡且保持稳定性的更新过程，当 $w_{t} > 0.5$ 时，更新方向朝着 $\tilde{a}_{t}$ ；否则，朝着 $a_{t}$，以此减轻OOD问题以及探索可能带来的负面影响
    - 理解：当 $w_{t} > 0.5$ 时，说明探索动作 $\tilde{a}_{t}$ 预估的 RTG $\tilde{r}_{t + 1}$ 比真实动作 $a_{t}$ 预估的 RTG $\hat{r}_{t + 1}$ 好的比较多，值得让 $\hat{a}_t$ 朝探索动作 $\tilde{a}_{t}$ 更新一些

Learnable Value Function

虽然动作探索机制确保了在数据集之外进行探索并实现保持稳定性的更新过程，但随机生成的 $\tilde{a}_{t}$ 并不能保证提升模型性能。为解决这一局限性，论文提出了一种可学习价值函数，如图1（a.3）所示，该函数有助于发现更优的动作以改进策略。具体而言，受强化学习惯例[21, 39, 41]的启发，论文提出了一个序列价值函数 $V_{t + 1}$，类似于强化学习中的最优状态价值函数，它表示 $r_{t + 1}$ 的上限，公式如下：
$$V_{t + 1} = \underset{a_{t} \in \mathbb{A} }{\arg \max} \ r_{t + 1} \tag{20}$$
- $\mathbb{A}$ 表示可用动作空间
- 由于动作空间广泛，且离线数据集中的实际动作有限，直接对 $V_{t + 1}$ 进行统计计算并不可行。论文使用 $r_{t + 1}$ 的期望分位数回归过程来学习这个值：
  $$\begin{align}
  L_{e} &= \frac{1}{M + 1} \sum_{t - M}^{t}(L_{2}^{\tau}(r_{t + 1} - \hat{V}_{t + 1})) \\
  &= \frac{1}{M + 1} \sum_{t - M}^{t}(\left|\tau - \mathbb{1}((r_{t + 1} - \hat{V}_{t + 1}) < 0)\right|(r_{t + 1} - \hat{V}_{t + 1})^{2})
  \end{align} \tag{21}$$
  - $\hat{V}_{t + 1}$ 表示 $V_{t + 1}$ 的预测值
  - $L_{2}^{\tau}(y - m(x))$ 表示使用模型 $m(x)$ 预测标签 $y$ 的期望分位数 $\tau \in (0, 1)$ 时的损失函数[21]。根据公式（20），论文将 $\tau = 0.99$，以学习 $r_{t + 1}$ 的上限，从而有效地估计 $V_{t + 1}$
通过使用 $\hat{V}_{t + 1}$ 估计 $V_{t + 1}$，并利用它来指导 $\tilde{r}_{t + 1}$ 的更新方向，GAVE隐式地将探索出的 $\tilde{a}_{t}$ 的更新方向引导向潜在的最优动作。这一过程如图1（b.2）所示，可正式表示为：
$$L_{v} = \frac{1}{M + 1} \sum_{t - M}^{t}(\tilde{r}_{t + 1} - \hat{V}_{t + 1}’)^{2} \tag{22}$$
- 其中，$\hat{V}_{t + 1}’$ 表示梯度冻结后的 $\hat{V}_{t + 1}$。通过应用 $L_{v}$，GAVE将 $\tilde{a}_{t}$ 的 RTG 锚定在 $\hat{V}_{t + 1}$ 附近，从而隐式地将 $\tilde{a}_{t}$ 的更新方向引导向最优动作。这种方法减轻了OOD风险，并实现了可控的外推以改进策略

Optimization Algorithm

通过上述机制，GAVE实现了一个离线生成式自动出价框架，该框架结合了价值引导的探索，以增强策略学习能力。综合损失函数由公式（19）、（21）和（22）中定义的各个组件加权组合而成：
$$L_{o} = \alpha_{1} \cdot L_{r} + \alpha_{2} \cdot L_{a} + \alpha_{3} \cdot L_{e} + \alpha_{4} \cdot L_{v} \tag{23}$$
- 其中，${\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4} }$ 是超参数，用于控制每个损失组件的相对贡献
GAVE的完整优化过程在算法1中详细列出，训练过程如图1（b）所示
在推理过程中，如图1（c）所示，GAVE处理每个输入序列以预测 $\hat{a}_{t} = \lambda_{t}$，它作为时间步 $t$ 的出价参数。然后，根据公式（7），时间步 $t$ 第 $n$ 个曝光的出价计算为 $b_{t n} = \lambda_{t} v_{t n}$，从而实现实时出价模拟

离线实验

在本节中，论文在两个公共数据集上进行实验，以研究以下问题：
- RQ1 ：与 SOTA 自动出价基线方法相比，GAVE 的性能如何？
- RQ2 ：GAVE 能否适应多样化的广告目标？
- RQ3 ：可学习价值函数在促进动作探索方面的效果如何？
- RQ4 ：GAVE 中所提出的组件对最终出价性能有何贡献？

Experiment Setup

数据集 ：先前的自动出价研究主要依赖于专有出价日志进行评估，问题的表述往往针对特定场景。这种评估方法的异质性阻碍了不同方法之间进行公平、系统的比较。最近，阿里巴巴妈妈推出了AuctionNet，这是行业内首个标准化的大规模模拟出价基准，能够在一致的条件下对模型进行全面评估。在本研究中，论文使用AuctionNet框架中的两个数据集：
- （i）AuctionNet：主要数据集，包含全面的出价轨迹；
- （ii）AuctionNet-Sparse：AuctionNet的稀疏变体，具有较低的转化率
- 以上这两个数据集都包含约 50 万个出价轨迹，收集自 1 万个不同的投放期，每个投放期由 48 个时间步组成，并且包含来自数百万个曝光机会的交互数据。详细统计信息见表1
评估协议 ：论文的评估方法遵循AuctionNet基准，并采用模拟环境来模拟现实世界的广告系统，如图1（c）所示
- 评估涵盖一个 24 小时的投放期，离散化为 48 个均匀的时间步，在此期间，预测动作用于出价（$(\hat{a}_{t} = a_{t})$）
- 在这个模拟环境中，48个具有不同策略的出价智能体竞争即将到来的（incoming）曝光机会，性能使用公式（13）（$\gamma = 2$）进行衡量。为确保全面评估，论文采用循环测试策略：测试模型依次替换48个智能体中的每一个，在每一轮中与其余智能体竞争。最终性能计算为所有评估的平均得分，从而提供了对模型有效性的可靠衡量
基线方法 ：为评估GAVE的有效性，论文将其与多种基线方法进行全面比较：
- DiffBid：应用扩散框架来模拟出价轨迹并对出价序列进行建模
- USCB：在在线RL出价环境中动态调整出价参数以实现最优出价性能
- CQL：学习一个保守的价值函数，以减轻 Offline RL 中的高估问题
- IQL：应用期望分位数回归方法，在不评估超出范围动作的情况下实现策略改进
- BCQ：在典型的 Offline RL 学习过程中对动作空间施加限制
- DT：采用transformer架构进行顺序决策建模，并使用行为克隆方法从数据集中学习平均策略
- CDT：尝试在离线设置中训练一个约束满足策略，以平衡安全性和任务性能
- GAS：尝试通过在建模中应用蒙特卡洛树搜索（MCTS）来构建一个基于 DT 的离线出价框架，并进行训练后搜索
实现细节 ：根据先前的研究，论文使用原始数据集中不同的预算比率进行评估。性能使用以下评分指标衡量：
$$S = \mathbb{P}(CPA; C) \cdot \sum_{i} x_{i} v_{i}$$
该指标如公式（13）所定义，其中 $Y = 2$。所有实验均在NVIDIA H100 GPU上进行，使用固定的批量大小128，最大训练步数为40万步。GAVE的实现采用具有8层和16个注意力头的因果transformer架构。模型参数使用AdamW优化器进行优化，学习率为 $1e^{-5}$。其他超参数通过全面的网格搜索确定，以最大化性能。为确保统计显著性，论文使用最优参数配置进行10次独立运行，并报告平均性能指标

整体性能（RQ1）

论文在不同预算设置下对GAVE和各种基线方法进行了全面比较，结果汇总在表2中
实验分析揭示了几个关键发现：
- GAVE在所有预算和数据集配置下均表现出色，始终优于现有方法。这种优越性可归因于论文新颖的动作探索方法，该方法在价值函数的指导下，能够在离线数据集之外发现新颖的、潜在的最优动作，同时通过平衡探索收益和风险的稳定更新过程保持稳健的训练
- 在所有基线方法中，基于 DT 的方法（GAS、 DT 和 CDT）表现较为突出，这凸显了 DT 结构在捕捉时间依赖关系和促进出价场景中的顺序决策方面的有效性。值得注意的是，GAS比 DT 和 CDT 取得了更好的结果，验证了其MCTS实现对策略优化的有效性。DiffBid在数据集上的表现不佳，可能是由于长序列和高度动态的环境给DiffBid准确预测轨迹和从反向过程中学习带来了额外挑战

一致性分析（RQ2）

如3.2节所述，广告目标可能需要不同的评估指标。为解决这一问题，GAVE采用了 Score-based自适应 RTG 建模方法，该方法能够适应各种优化目标，从而使训练目标与评估指标保持一致，如公式（15）所示。在本节中，论文探究GAVE在不同 RTG 和评估指标配置下的性能，以回答RQ2。具体而言，论文考虑以下三种评估指标：
$$\begin{cases}
S_{1}=\sum_{i} x_{i} v_{i} \\
S_{2}=\min\left\{\left(\frac{C}{CPA}\right)^{2}, 1\right\} \cdot \sum_{i} x_{i} v_{i} \\
S_{3}=\min\left\{\left(\frac{C}{CPA}\right)^{5}, 1\right\} \cdot \sum_{i} x_{i} v_{i}
\end{cases}$$
- 其中，$S_{1}$ 仅考虑获得的总曝光价值，代表对CPA条件限制较为宽松的业务场景。$S_{2}$ 是论文的优化目标和评估分数，它对CPA约束添加了惩罚项。$S_{3}$ 进一步提高了CPA的惩罚系数，代表对CPA条件限制严格的业务场景。这些指标既可以在训练期间用于 RTG 建模，也可以在测试期间用作评估标准。结果如表3所示
从表3中可以观察到，当训练 RTG 与用作评估指标的函数一致时，GAVE始终能取得最高性能。这一发现强调了通过论文 Score-based RTG 方法使训练目标与特定评估指标保持一致的重要性
注：表3体现不出来自适应能力吧，毕竟没有对照，靠衰减不多来说明目标变化时的有效性吗？

参数分析（RQ3）

为回答RQ3，论文对权重 $w_{t}$ 进行参数分析，如图1（b.1）所示，以阐明训练过程中 $\tilde{a}_{t}$ 和 $a_{t}$ 之间的差异。具体而言，图2曝光了训练步骤中平均总损失 $L_{o}$ 和权重 $w_{t}$ 的变化情况，使论文能够监测 $\tilde{r}_{t + 1}$ 和 $\hat{r}_{t + 1}$ 之间的差异。$w_{t}$ 越大，表明 $\tilde{r}_{t + 1}$ 对 $\hat{r}_{t + 1}$ 的影响越大，进而证明 $\tilde{a}_{t}$ 优于 $a_{t}$。这一结果凸显了价值函数在指导动作探索方面的有效性
从图2中明显可以看出，随着训练的进行，参数 $w_{t}$ 从约0.5增加到稳定高于0.5的位置。该稳定位置受数据集分布和模型超参数的共同影响。这一趋势证实了可学习价值函数在指导动作探索方面的有效性。在价值函数的引导下，模型持续探索具有更高 RTG 值 $\tilde{r}_{t + 1}$ 且接近估计最优值 $\hat{V}_{t + 1}$ 的动作 $\tilde{a}_{t}$。这种方法有助于学习潜在的最优策略，同时减轻OOD问题

消融研究（RQ4）

为进一步阐明GAVE中每个模块的贡献以回答RQ4，论文进行了消融研究，评估以下修改版本的GAVE：
GAVE-V ：不包含3.4节中描述的可学习价值函数。在此配置下，损失函数 $L_{v}$ 和 $L_{e}$ 被以下更新规则取代，以确保探索出的动作通过提高其 RTG 值 $\tilde{r}_{t + 1}$ 总体上优于原始标签：
$$L_{w}=1 - Sigmoid\left(\alpha_{r} \cdot \left(\tilde{r}_{t + 1}-\hat{r}_{t + 1}’\right)\right)$$
- 其中，$\hat{r}_{t + 1}’$ 是 $\hat{r}_{t + 1}$ 的梯度冻结版本。然而，由于没有价值函数，$\tilde{r}_{t + 1}$ 的更新方向变得无界，导致OOD问题和次优性能
GAVE-VA ：既不包含3.4节中的价值函数，也不包含3.3节中详细介绍的动作探索机制
DT ：移除所有与GAVE相关的设计模块，包括3.4节、3.3节和3.2节中描述的模块。因此，此配置与纯 DT 框架一致，使用 $S=\sum_{i} x_{i} v_{i}$ 进行 RTG 建模
图3曝光了评估结果。结果表明：
- （i）使用 Score-based RTG 建模使优化目标与评估指标保持一致，这使得GAVE-VA的性能优于 DT，证明了训练中目标一致性的重要性；
- （ii）GAVE-V中融入动作探索机制和基于 RTG 的评估，使模型能够发现离线数据集之外的潜在策略，并评估其重要性以实现稳定更新过程，从而比GAVE-VA取得更好的性能；
- （iii）GAVE中完全集成价值函数以指导动作探索，利用了潜在的最优策略，进一步缓解了OOD问题并提高了整体性能

在线部署

论文通过在两个工业实时出价场景（Nobid 和 Costcap）中的A/B测试来评估GAVE的有效性。Nobid 旨在在每日预算内最大化转化次数，Costcap 旨在在CPA/ROI限制下最大化转化次数。实验设置如下：
- 状态：20步的序列，特征包括预算、CPA限制、预测值、流量/成本速度、时间分段预算、剩余时间和窗口平均出价系数
- 动作：为稳定出价结果，出价系数 $\lambda$ 基于前两小时包含 $E$ 个时间步的窗口平均值确定，$\lambda_{t}=a_{t}+\frac{1}{|E|} \sum_{t’=t-E}^{t-1} \lambda_{t’}$，其中 $a_{t}$ 是GAVE在时间步 $t$ 的输出动作
- 未来回报（RTG） ：鉴于实际转化的稀疏性，论文在训练期间使用预期总转化次数 $\sum_{i} pcvr_{i}$，其中 $pcvr_{i}$ 是赢得流量 $i$ 的预测转化率。在推理时，整个序列的 RTG 设置为前一天广告计划的总预期转化次数
论文将GAVE与目前正在实际应用中的离线强化学习算法IQL进行比较
- 评估指标包括成本、转化次数、目标成本和CPA有效率，出价策略侧重于在预算和CPA约束下最大化转化次数
- 为考虑不同的广告计划目标，目标成本作为一种价值加权的转化度量，对于 Costcap 广告计划，转化价值等于CPA限制；对于 Nobid 广告计划，使用总流量的平均实际 CPA
- 如果 Costcap 广告计划的 CPA 保持在限制以下，则认为其 CPA 有效，该指标仅针对 Costcap 广告计划进行评估。论文进行了为期五天的在线A/B测试，将每个广告计划25%的预算和流量分配给基线出价模型和GAVE，结果汇总在表4中
对于 Nobid 和 Costcap 广告计划，GAVE均改善了成本和转化次数指标。在 Nobid 广告计划中，GAVE使成本增加了0.8%，转化次数增加了8.0%，目标成本增加了3.2%。在 Costcap 广告计划中，广告收入和广告商价值有所提升，同时CPA有效性显著改善，成本增加2.0%，转化次数增加3.6%，目标成本增加2.2%，有效CPA率增加1.9%

结论

论文提出了GAVE，通过价值引导探索来增强 DT 在离线生成式自动出价中的应用
- 为适应复杂的广告目标，论文设计了一种可定制的 Score-based RTG 机制，能够对各种优化目标进行自适应建模，以匹配不同的评估指标
- 论文将动作探索机制与基于 RTG 的评估方法相结合，在离线数据集之外探索动作的同时，确保稳定的更新过程
- 为进一步引导探索并减轻 OOD 风险，论文采用了可学习价值函数，将 RTG 更新锚定在分布合理的区域，同时允许可控的外推以改进策略
大量实验、在线部署和 NeurIPS 竞赛结果表明，论文的 GAVE 框架在增强自动出价策略的适应性和性能方面是有效的，为在动态环境中优化数字广告计划提供了一种通用解决方案

Joe Zhou

Stay Hungry. Stay Foolish.

GitHub E-Mail

AMA是什么？

分配规则

计费规则

AMA 和 VCG的比较

前置：对文章的整体评价

整体说明

讨论

模型与预备知识

经典拍卖机制

修正的VCG机制

联合仿射最大化拍卖

仿射最大化拍卖概述

JAMA架构

整体说明

更多讨论

论文主要贡献

机制相关工作讨论

联合拍卖设计

联合拍卖

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

JRegNet 方案

JRegNet 架构

问题: 实际场景位置分配

JRegNet 的训练

Experiments

基线方法

评估指标

合成数据

真实数据集

未来规划

整体思路说明（摘要）

Introduction and Discussion

Preliminary

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

问题公式化

自动化机制设计

MIAA拍卖机制

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

自动化拍卖模块（AAM）

可微分排序模块（DSM）

训练与在线服务

Experiments

Experiment Setup

数据集

评估指标

基线

离线实验

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

机制的性能比较（Q2）

在线结果

整体概述

论文设计思路

论文的贡献

论文中的一些讨论

Auction Design as a Learning Problem

拍卖设计基础及符号说明

表述为 Learning Problem

个体理性

泛化边界（TODO）

神经网络架构

加性估值下的网络架构

单位需求估值下的网络架构

组合估值下的网络架构

覆盖数边界

优化与训练

实验结果

Experiment Setup

评估指标

单个竞拍者

多个竞拍者

扩展性测试

与线性规划（LP）的比较

附录：双随机矩阵（doubly stochastic matrix）

核心思路

当前存在的问题

BCB介绍

问题定义

解法一

解法二

关于两种解法的结果分析