Efficiency of (revenue-)optimal mechanisms

Efficiency of (revenue-)optimal mechanisms
复制标题

（收入）最优机制的效率

DOI：
10.1145/1566374.1566408
复制
发表时间：
2009
期刊：
ArXiv
影响因子：
--
通讯作者：
Aranyak Mehta
Aranyak Mehta
中科院分区：
--
文献类型：
--
作者：
Gagan Aggarwal;G. Goel;Aranyak Mehta

文献摘要

被引文献

相似文献

我们比较的预期效率的收入最大化（或最佳）的机制与效率最大化的。我们表明，销售一个单一的项目与（k + logeovere-1 k + 1）投标人的收入最大化机制的效率至少是一样多的效率最大化机制与k投标人，投标人的估值时，i.i.d.单调风险率分布令人惊讶的是，我们还表明，这个界限是紧在一个小的附加常数为4.7。换句话说，Θ（log k）个额外投标者足以使收入最大化机制匹配效率最大化机制的效率，而o（log k）个额外投标者不足以匹配效率最大化机制的效率。这与Bulow和Klemperer比较两种机制的收入的结果相反，其中只有一个额外的投标人就足够了。更准确地说，他们表明，与k + 1投标人的效率最大化机制的收入不低于收入最大化机制与k投标人的收入。 我们扩展了我们的结果的情况下，销售t相同的项目，并表明，Θ（log k）+ t Θ（log log k）额外的投标人足够的收入最大化机制，以匹配效率最大化机制的效率。 为了证明我们的结果，我们对单调危险率（MHR）分布进行了分类，并确定了一个MHR分布族，使得对于我们分类中的每个类，这个族中有一个成员逐点低于该类中的每个分布。这让我们证明了关于单调风险率分布的有趣的结构定理。
We compare the expected efficiency of revenue maximizing (or optimal) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with (k + logeovere-1 k + 1) bidders is at least as much as the efficiency of the efficiency-maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 4.7. In other words, Θ(log k) extra bidders suffice for the revenue-maximizing mechanism to match the efficiency of the efficiency-maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency-maximizing mechanism with k + 1 bidders is no less than the revenue of the revenue-maximizing mechanism with k bidders. We extend our result for the case of selling t identical items and show that Θ(log k) + t Θ(log log k) extra bidders suffice for the revenue-maximizing mechanism to match the efficiency of the efficiency-maximizing mechanism. In order to prove our results, we do a classification of Monotone Hazard Rate (MHR) distributions and identify a family of MHR distributions, such that for each class in our classification, there is a member of this family that is pointwise lower than every distribution in that class. This lets us prove interesting structural theorems about distributions with Monotone Hazard Rate.