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

500次阅读
没有评论

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

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

导  读

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

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

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

论文链接:

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 性质,直接以平均利润作为目标函数。这类方法的优点是可以保障激励相容性,但现有的工作往往面临可拓展性问题,这是因为它们考虑了所有确定型分配方案,总共有  种,是买家数量  与商品数量  的指数级别。

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

02

问题描述

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

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

并且对买家  ,向其收取她对其他买家带来的仿射外部性其中,  是去除买家  之后最大化其他人仿射福利的分配方案。

03

方   法

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

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

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

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

04

实   验

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

在利润实验中,我们观察到的现象有:

  1. 相比于 VCG 拍卖,我们的方法 AMenuNet 通过引入额外的参数,提高了卖家利润。

  2. 在所有保障 DSIC 的方法(VCG、Item-Myerson、Lottery AMA)中,AMenuNet 能够达到最好的卖家利润。

  3. 相比于基于 RegretNet 的方法(CITransNet、RegretNet),AMenuNet 的利润偏低。但是 AMenuNet 相比于它们的优势在于能够保障 DSIC。

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

而在剥离试验中,我们可以看到,利用一个大小为  的菜单提高了模型的可拓展性。相比以  (所有确定型分配)作为分配菜单,我们的做法可以适用于更大的拍卖规模。

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

我们进一步观察了分配菜单最后学到的分配结果。我们发现常用的分配结果只占了菜单的一小部分。此外,如上图所示,我们注意到在观测到的胜率最高的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.

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

图文 | 段志健

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

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

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

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

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

实验室相关新闻#PKU daGAME

daGAME近期动态

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

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

—   版权声明  —

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

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

阅读原文转论文链接

 

Read More 

正文完
可以使用微信扫码关注公众号(ID:xzluomor)
post-qrcode
 
评论(没有评论)
Generated by Feedzy