NeurIPS 2023 Spotlight | 仿射最大化拍卖机制设计的可拓展神经网络方法

关键词：拍卖设计、深度学习

导读

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

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

论文链接：

https://arxiv.org/abs/2305.12162

问题背景与相关工作

拍卖设计的一个核心问题是设计一个既满足占优策略激励相容（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 性质的同时，具备更好的可拓展性。

问题描述

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

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

$g(B, X, Y)=A^{*}:=\arg \max _{A \in \mathcal{A}} \sum_{i=1}^{n} w_{i} b_{i}(A)+\lambda(A),$ 并且对买家 $k$ ，向其收取她对其他买家带来的仿射外部性 $p_k(B,X,Y) = \frac{1}{w_k}\left(\sum_{i \neq k} w_i b_i(A^*_{-k}) + \lambda(A^*_{-k})\right) - \frac{1}{w_k}\left(\sum_{i \neq k} w_i b_i(A^*) + \lambda(A^*)\right).$ 其中， $A^*_{-k} := \arg\max_{A \in \mathcal{A}} \sum_{i \neq k} w_i b_i(A) + \lambda(A)$ 是去除买家 $k$ 之后最大化其他人仿射福利的分配方案。

方法

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

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

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

实验

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

相比于 VCG 拍卖，我们的方法 AMenuNet 通过引入额外的参数，提高了卖家利润。
在所有保障 DSIC 的方法（VCG、Item-Myerson、Lottery AMA）中，AMenuNet 能够达到最好的卖家利润。
相比于基于 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.

图文 | 段志健

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

↑↑扫码转实验室主页↑↑

实验室 PI 简介：邓小铁讲席教授

实验室相关新闻：#PKU daGAME

daGAME近期动态

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转论文链接

NeurIPS 2023 Spotlight | 仿射最大化拍卖机制设计的可拓展神经网络方法

评论