Characterizing false-name-proof allocation rules in combinatorial auctions
Characterizing false-name-proof allocation rules in combinatorial auctions
复制标题
DOI：
10.1145/1558013.1558049
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Taiki Todo;Atsushi Iwasaki;M. Yokoo;Y. Sakurai
中科院分区：
文献类型：
--
作者：
Taiki Todo;Atsushi Iwasaki;M. Yokoo;Y. Sakurai
组合拍卖机制由一个分配规则和一个支付规则组成，分配规则定义了每个代理人的货物分配，支付规则定义了每个赢家的支付。有几个研究特征的防策略分配规则。特别是，一个条件称为弱单调性已被确定为一个完整的特征的防策略分配规则。更具体地说，对于一个分配规则，存在一个适当的支付规则，使得该机制成为防策略的当且仅当它满足弱单调性。在本文中，我们确定了一个条件，称为次可加性的特点，假名称证明分配规则。虚假名称的防范性通过假设投标人可以在虚构的标识符下提交多个投标来推广策略防范性。据作者所知，这是第一次尝试描述假名证明分配规则。我们可以利用这个特征来开发一个新的防假名机制，因为我们可以集中精力设计一个分配规则。只要分配规则满足弱单调性和次可加性，总存在一个合适的支付规则。此外，通过利用次可加性条件，我们可以很容易地验证一个机制是否是假名证明。令我们惊讶的是，我们发现，两个机制，这被认为是假名称证明，不满足次可加性，他们不是假名称证明。正如这些例子所示，我们的表征对于机制验证是非常有用的。
A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategy-proof allocation rules. In particular, a condition called weak-monotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity. In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. False-name-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-name-proof, do not satisfy sub-additivity; they are not false-name-proof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.