A Permutation-Equivariant Neural Network Architecture For Auction Design
A Permutation-Equivariant Neural Network Architecture For Auction Design
复制标题
DOI：
10.1609/aaai.v35i6.16711
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Jad Rahme;Samy Jelassi;Joan Bruna;S. Weinberg
中科院分区：
文献类型：
--
作者：
Jad Rahme;Samy Jelassi;Joan Bruna;S. Weinberg
设计一个激励相容的拍卖，使期望收益最大化是拍卖设计中的一个核心问题。在过去的几十年里，解决这个问题的理论方法已经达到了一些极限，只有少数几个简单的设置的分析解决方案是已知的。通过使用LP来解决问题的计算方法有其自身的局限性。在深度学习成功的基础上，Duetting等人（2019）最近提出了一种新方法，其中拍卖由前馈神经网络建模，设计问题被视为学习问题。在这项工作中使用的神经架构是通用的，并且没有利用问题可能存在的任何对称性，例如置换等变性。在这项工作中，我们考虑具有置换等变对称性的拍卖设计问题，并构建一个能够完美恢复置换等变最佳机制的神经架构，我们表明这在以前的架构中是不可能的。我们证明，置换等变架构不仅能够恢复以前的结果，他们也有更好的推广性能。
Designing an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. Theoretical approaches to the problem have hit some limits in the past decades and analytical solutions are known for only a few simple settings. Computational approaches to the problem through the use of LPs have their own set of limitations. Building on the success of deep learning, a new approach was recently proposed by Duetting et al. (2019) in which the auction is modeled by a feed-forward neural network and the design problem is framed as a learning problem. The neural architectures used in that work are general purpose and do not take advantage of any of the symmetries the problem could present, such as permutation equivariance. In this work, we consider auction design problems that have permutation-equivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutation-equivariant optimal mechanism, which we show is not possible with the previous architecture. We demonstrate that permutation-equivariant architectures are not only capable of recovering previous results, they also have better generalization properties.