ACM通信
研究突出了
技术视角:寻求最优的多物品拍卖
来源:盖蒂图片社
销售一个或多个不可分割的物品以实现收益最大化的最佳方法是什么?它们是应该单独定价、捆绑定价，还是使用更复杂的销售机制进行销售?尽管这些问题具有重要的现实意义、悠久的历史和数个世纪的科学研究，但它们仍然没有得到答案。卖家和科学家面临的挑战是，有无数的销售机制。虽然我们已经习惯了商店里商品的价格标签，但还有许多其他的销售机制。编写包含所有可能机制的模型已经很麻烦了，更不用说对它们进行优化了。
因此，在20世纪80年代，当经济学家开发出一种数学方法，可以精确地指出销售商品的最佳方式时，人们感到很惊讶单一个或多个战略买家，根据他们对该项目的价值分配信息。当这些价值是独立的和同分布的，最优可以描述为熟悉的带保留价的上升价格拍卖，如eBay所使用的，当价值不是同分布时，最优拍卖就变成了一种更奇特的拍卖。迈尔森极具影响力的诺贝尔奖获奖作品明确规定了如何建立这种关系。
唉，把这个程序推到多产品设定一直困扰着经济学家和计算机科学家。我们应该认识到，组织多个道具的同时销售既不是一个无害的问题，也不是一个深奥的问题。当政府出售无线电频谱时，他们会在一次大型拍卖中同时出售多个许可证。当广告交换出售横幅广告，比如说纽约时报Frontpage，他们同时出售每个印象的所有横幅。当网上零售商向相互竞争的买家出售各种商品时，他们应该巧妙地组织销售。尽管多项目设置很重要，但最佳解决方案仍然难以捉摸。
事实上，大量的研究表明，最优的多商品机制，即使是向一个买家出售两件商品，也要比单商品机制复杂得多。捆绑和随机分配是必要的，正如我在最近的一项调查中所描述的，最佳机制可能表现出各种违反直觉的特性。2在撰写本文时，只存在表征最优多项目的结果single-buyer机制。3.这些结果利用最优输运理论，从买方价值分布所满足的随机支配条件来表征最优机制的结构，表明不存在一刀切的最优多项目机制。
在优化机制中缺少一个简单的、普遍的结构，就有两种自然的方法，它们都是CS美学的好兆头，并得到了广泛的追求。一种是用最优性来换取简单性，正如越来越多的工作所追求的那样，这些工作已经确定了越来越简单、近似最优的机制，用于越来越复杂的多项目多买家设置。
另一种方法是开发框架计算在给定买方价值分布的情况下，基于实例的最优机制。这样的框架对于它们的最终产品(即它们所计算的机制)都很有用，同时也作为探索性工具，用于研究在一系列感兴趣的设置下最优机制中结构的存在性。在这个主题上有大量的工作，通过凸规划计算在相当复杂的设置下的最优机制。2
以下由Dütting等人撰写的论文对这一计算挑战提出了非常有趣和前瞻性的新看法，开创了在机制设计中使用深度学习的新方法。
他们的框架不是将值分布作为输入，而是从该分布中接收样本，并训练一个代表机制的神经网络，以获得良好的经验收益。对最优多项目机构的样本复杂度已经进行了一定的研究，因此我们对什么样的设置可以从多项式多的样本中识别出接近最优的机构有了合理的理解;特别是，众所周知，为了统计效率，项目值之间需要一些条件独立性。1
他们没有为他们的机制追求最优保证，而是通过追求最佳努力的保证，即梯度下降可能提供的最佳收益，再次偏离了之前的工作，即使没有赋予他们的神经网络关于最优机制结构的很多归纳偏差。此外，他们寻求的不是精确的真实，而是通过神经网络的最小-最大训练公式来实现的近似真实。
通过这些设计选择，作者提供了一个灵活的计算框架，它很容易适应连续分布，并且在问题的某些维度上具有更强的可伸缩性。尽管缺乏强烈的归纳偏差和基于梯度的优化，经验测试表明，由他们的框架识别的机制在简单设置中获得了接近最优的收益，而在其他设置中，最优的机制没有识别，它计算的机制是接近最优的。这些发现在更广泛的背景下有多可靠?而且，如果是的话，最优多项目机制的难以捉摸的特性是什么，它使相对不可知论的体系结构能够表示它们，并使梯度下降能够识别它们?
参考文献
1.蔡勇，吕剑杰，蔡勇。无项目独立性的多项目机制:基于鲁棒性的学习性。在廿一年会议记录圣ACM会议经济学与计算, 2020, 715 - 761。
2.多品拍卖违背直觉?SIGecom交流1， 14(2015)， 41-75。
3.C. Daskalakis, A. Deckelbaum, C. Tzamos, C.多重商品垄断者的强对偶性。费雪3， 85(2017)， 735-767。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有发现记录