Designing and learning optimal finite support auctions
Designing and learning optimal finite support auctions
复制标题
设计和学习最佳有限支持拍卖
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Edith Elkind
中科院分区：
文献类型：
--
作者：
Edith Elkind
Myerson [18]的一篇经典论文展示了如何在一个模型中构建一个最优（收入最大化）拍卖，其中投标人的价值来自已知的连续分布。在本文中，我们将展示如何使这种方法适应可能部分未知的有限支持度分布。我们证明了一个迈尔逊式拍卖可以在时间多项式的投标人的数量和支持集的大小。接下来，我们考虑机制设计者知道支持集，但不知道每个值的概率的情况。在这种情况下，我们表明，最优拍卖可以学习在多项式时间内使用一个弱预言，给定两个候选拍卖，返回一个具有较高的预期收入。为了研究这个问题，我们引入了一类新的真实机制，我们称之为基于订单的拍卖。我们证明了最优机制是基于订单的拍卖，并使用该类的内部结构来证明我们的学习算法的正确性以及限制其运行时间。
A classical paper of Myerson [18] shows how to construct an optimal (revenue-maximizing) auction in a model where bidders' values are drawn from known continuous distributions. In this paper we show how to adapt this approach to finite support distributions that may be partially unknown. We demonstrate that a Myerson-style auction can be constructed in time polynomial in the number of bidders and the size of the support sets. Next, we consider the scenario where the mechanism designer knows the support sets, but not the probability of each value. In this situation, we show that the optimal auction may be learned in polynomial time using a weak oracle that, given two candidate auctions, returns one with a higher expected revenue. To study this problem, we introduce a new class of truthful mechanisms which we call order-based auctions. We show that the optimal mechanism is an order-based auction and use the internal structure of this class to prove the correctness of our learning algorithm as well as to bound its running time.