Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms
Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms
复制标题
DOI：
10.1145/1838206.1838289
复制
发表时间：
2010-05
影响因子：
--
通讯作者：
Atsushi Iwasaki;Vincent Conitzer;Yoshifusa Omori;Y. Sakurai;Taiki Todo;M. Guo;M. Yokoo
中科院分区：
文献类型：
--
作者：
Atsushi Iwasaki;Vincent Conitzer;Yoshifusa Omori;Y. Sakurai;Taiki Todo;M. Guo;M. Yokoo
分析了防假名组合拍卖机制的最坏情况效率比。防假名通过假设投标人可以在虚构的标识下提交多个投标来推广防策略。即使是众所周知的Vickrey-Clarke-Groves机制也不是防假名的。以前已经证明，不存在总是实现帕累托有效分配的防假名机制。因此，如果冒名投标是可能的，我们需要在一定程度上牺牲效率。这就留下了一个自然的问题：必须牺牲多少盈余。为了回答这个问题，本文着重于最坏情况分析。具体地说，我们考虑了我们所获得的帕累托有效盈余的分数，并试图在最坏的情况下，在防假名的约束下最大化这个分数。据我们所知，这是第一次尝试研究防假名机制的最坏情况下的效率。我们证明了对于具有m种不同商品的拍卖，只要满足一些明显较小的假设，任何防伪机制的最坏情况效率比至多为2/(m+1)。我们还观察到，现有的防假名机制的最坏情况下的效率比一般为1/m或0。最后，我们提出了一种新的机制，称为自适应保留价机制，当所有竞标者都是单一的时，该机制是防伪的。最坏情况下的效率比为2/(m+1)，即最优。
This paper analyzes the worst-case efficiency ratio of false-name-proof combinatorial auction mechanisms. False-name-proofness generalizes strategy-proofness by assuming that a bidder can submit multiple bids under fictitious identifiers. Even the well-known Vickrey-Clarke-Groves mechanism is not false-name-proof. It has previously been shown that there is no false-name-proof mechanism that always achieves a Pareto efficient allocation. Consequently, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplus must be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider the fraction of the Pareto efficient surplus that we obtain and try to maximize this fraction in the worst-case, under the constraint of false-name-proofness. As far as we are aware, this is the first attempt to examine the worst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proof mechanism that satisfies some apparently minor assumptions is at most 2/(m + 1) for auctions with m different goods. We also observe that the worst-case efficiency ratio of existing false-name-proof mechanisms is generally 1/m or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism that is false-name-proof when all bidders are single-minded. The worst-case efficiency ratio is 2/(m + 1), i.e., optimal.