前置：对文章的整体评价
- 提出了新颖的供应商与零售商联合拍卖场景
- 文章中部分内部不是很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更高的收入
Joint-Bidding-in-Ad-Auctions/JAMA-Figure1.png)
- 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输出的分配可以实现最优社会福利
Joint-Bidding-in-Ad-Auctions/JAMA-Algorithm1.png)
- 现在，论文详细阐述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的基本结构
Joint-Bidding-in-Ad-Auctions/JAMA-Figure2.png)
- 论文将零售商和供应商的出价及其权重作为输入。然后根据零售商和供应商之间的合作关系计算联合出价。通过训练分配方案和相应的 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运算符