Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
复制标题
DOI：
10.1613/jair.1.11525
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Vitor Bosshard;Benedikt Bünz;Benjamin Lubin;Sven Seuken
中科院分区：
文献类型：
--
作者：
Vitor Bosshard;Benedikt Bünz;Benjamin Lubin;Sven Seuken
我们提出了一种新算法，用于计算组合拍卖中的纯策略 ε-贝叶斯-纳什均衡 (ε-BNE)。我们算法的主要创新是将算法的搜索阶段（用于查找 ε-BNE）与验证阶段（用于计算 ε）分开。使用这种方法，我们获得了一种算法，该算法不仅速度非常快，而且为其找到的 ε 提供了理论保证。我们的主要贡献是一种验证方法，令人惊讶的是，它允许我们在整个连续值空间中设定 ε 的上限，而无需对机制做出假设。使用我们的算法，我们现在可以计算多思维领域中的 ε-BNE，这些领域比以前可以解决的问题要复杂得多。我们根据开源许可证发布代码，使研究人员能够对拍卖进行算法分析，使投标人能够分析不同的策略以及许多其他应用程序。
We present a new algorithm for computing pure-strategy ε-Bayes-Nash equilibria (ε-BNEs) in combinatorial auctions. The main innovation of our algorithm is to separate the algorithm’s search phase (for finding the ε-BNE) from the verification phase (for computing the ε). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the ε it finds. Our main contribution is a verification method which, surprisingly, allows us to upper bound the ε across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute ε-BNEs in multi-minded domains that are significantly more complex than what was previously possible to solve. We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and many other applications.