本文是 NeurIPS 2023 入选的 spotlight 论文 A Scalable Neural Network for DSIC Affine Maximizer Auction Design 的解读。该论文由北京大学邓小铁算法博弈论实验室完成，作者包括北京大学计算机学院博士生段志健、元培学院本科生孙皓然和计算机学院博士生陈昱蓉。

　　本文使用深度学习的方法寻找最大化卖家利润的仿射最大化拍卖（Affine Maximizer Auction，简称 AMA）机制，在保障占优策略激励相容与个体理性的同时，使该方法具备更强的可拓展性。

　　论文链接：https://arxiv.org/abs/2305.12162

01 问题背景与相关工作

　　拍卖设计的一个核心问题是设计一个既满足占优策略激励相容（dominant strategy incentive compatible，简称 DSIC）、个体理性（individually rational，简称 IR），又能为拍卖者带来高利润的拍卖机制。其中 DSIC 指的是无论其他人如何出价，每个买家真实报价一定能获得最好的效用；IR 指的是买家真实报价得到的效用不会为负。

　　由于利润最大化拍卖的理论研究陷入了瓶颈，因此研究人员开始尝试使用基于机器学习的方法，从经验角度搜索寻找高利润的拍卖机制。这类工作大致可以分为两类：一类是基于 RegretNet 的方法，一类是基于仿射最大化拍卖（Affine Maximizer Auction）的方法。

　　第一类方法 [2][3] 通过计算后验后悔值来衡量拍卖机制违反 DSIC 的程度，并将其作为惩罚项，加上平均利润的相反数作为损失函数，让机制在尽可能满足 DSIC 的同时寻找高利润的拍卖。然而这样做并不能保障机制的激励相容性，而且后悔值的计算开销巨大。

　　第二类方法 [1][4] 优化 AMA 拍卖机制，并借助 AMA 拍卖的 DSIC 性质，直接以平均利润作为目标函数。这类方法的优点是可以保障激励相容性，但现有的工作往往面临可拓展性问题，这是因为它们考虑了所有确定型分配方案，总共有 (n+1)^{m}种，是买家数量n与商品数量m的指数级别。

　　本文所提出的方法也是基于 AMA 拍卖的方法，在利用 AMA 拍卖良好的 DSIC 性质的同时，具备更好的可拓展性。

02 问题描述

　　我们考虑n个买家和m个商品的密封拍卖，其中买家对商品的估值服从先验分布，该先验分布由买家和商品的表示共同决定。我们考虑可加估值（additive valuation）场景，也即买家对商品集合的估值为该买家对集合内所有商品估值之和。

　　我们的目标是设计一个最大化卖家利润的仿射最大化拍卖（Affine Maximizer Auction，简称AMA）。AMA 拍卖是 VCG 拍卖的泛化形式，天生满足 DSIC 和 IR 条件。一个 AMA 的参数包含每个买家的权重w_{i} ∈\mathbb{R}_{+}、分配方案菜单\mathcal{A}（即所有考虑的分配方案集合）以及对每个分配方案A∈\mathcal{A}的增强变量λ(A)。类似 VCG 拍卖，给定买家出价B、买家的表示X、商品的表示Y，AMA 在分配方案菜单中寻找最大化仿射福利的分配机制：

　　并且对买家k，向其收取她对其他买家带来的仿射外部性

　　其中，

　　是去除买家k之后最大化其他人仿射福利的分配方案。

03 方 法

　　我们整体的方法论是将利润最大化的 AMA 拍卖设计建模成一个优化问题，以期望利润作为优化目标；我们利用一个神经网络，以买家和商品的表示作为输入，计算 AMA 的三组参数：买家权重、分配菜单和增强变量，并将该神经网络的权重作为优化问题的自变量。随后，我们采用标准的机器学习方法，在训练集上训练模型，在测试集上测试。

　　前人工作中通常将所有(n+1)^{m}种决定性分配方案作为固定的分配菜单，但是这样做面临可拓展性问题。为此，我们预定义分配菜单的大小s，然后利用神经网络去计算这s个可能有用的分配。这样一来，我们缩小了分配菜单的规模。

　　除此之外，我们在模型设计中引入了 transformer 等与输入序列规模大小无关的网络模块，使得我们的整个模型权重规模与买家数量和商品数量无关。这样做控制了模型参数量，进一步提升了可拓展性。我们的模型命名为 AMenuNet，整体结构如下图所示，具体细节详见我们的论文。

04 实 验

　　在利润实验中，我们观察到的现象有：

1. 相比于 VCG 拍卖，我们的方法 AMenuNet 通过引入额外的参数，提高了卖家利润。
2. 在所有保障 DSIC 的方法（VCG、Item-Myerson、Lottery AMA）中，AMenuNet 能够达到最好的卖家利润。
3. 相比于基于 RegretNet 的方法（CITransNet、RegretNet），AMenuNet 的利润偏低。但是 AMenuNet 相比于它们的优势在于能够保障 DSIC。

　　而在剥离试验中，我们可以看到，利用一个大小为s的菜单提高了模型的可拓展性。相比以\mathcal{A}_{dtm} （所有确定型分配）作为分配菜单，我们的做法可以适用于更大的拍卖规模。

　　我们进一步观察了分配菜单最后学到的分配结果。我们发现常用的分配结果只占了菜单的一小部分。此外，如上图所示，我们注意到在观测到的胜率最高的10个分配方案中，所有均为确定性分配方案；我们还观察到了一个高胜率的方案，即不分配任何物品，并且该方案具有相对较大的增强变量。这一现象可以被视为设定了一组保留价。

参考文献：

[1] Likhodedov et al. Approximating revenue-maximizing combinatorial auctions. AAAI 2005.

[2] Paul Dütting et al. Optimal auctions through deep learning. ICML 2019.

[3] Zhijian Duan et al. A context-integrated transformer-based neural network for auction design. ICML 2022.

[4] Michael Curry, et al. Differentiable economics for randomized affine maximizer auctions. IJCAI 2023.