Towards a characterization of truthful combinatorial auctions
Towards a characterization of truthful combinatorial auctions
复制标题
真实组合拍卖的表征
DOI：
10.1109/sfcs.2003.1238230
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. Nisan
中科院分区：
文献类型：
--
作者：
R. Lavi;Ahuva Mu'alem;N. Nisan
本文分析了有限偏好领域内的激励兼容（真实）机制，最典型的例子是组合拍卖。我们的工作概括了 Roberts（1979）的特征，他表明在不受限制的领域上具有至少 3 种可能结果的真实机制必须是“仿射最大化器”。我们证明，如果组合拍卖（以及相关限制域）的真实机制还满足“不相关替代方案的独立性”的附加要求，则它们必须是“几乎仿射最大化器”。对于不受限制的域以及必须分配所有商品的两个玩家之间的拍卖，此要求不失一般性。这意味着这些情况的无条件结果，包括罗伯茨定理的新证明。这种特征的计算影响是严重的，因为合理的“几乎仿射最大化器”被证明与精确优化一样计算困难。这意味着在精确优化在计算上难以处理的所有情况下，这种真实的多项式时间拍卖几乎是无助的。
This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of Roberts (1979) who showed that truthful mechanisms over unrestricted domains with at least 3 possible outcomes must be "affine maximizers". We show that truthful mechanisms for combinatorial auctions (and related restricted domains) must be "almost affine maximizers" if they also satisfy an additional requirement of "independence of irrelevant alternatives". This requirement is without loss of generality for unrestricted domains as well as for auctions between two players where all goods must be allocated. This implies unconditional results for these cases, including a new proof of Roberts' theorem. The computational implications of this characterization are severe, as reasonable "almost affine maximizers" are shown to be as computationally hard as exact optimization. This implies the near-helplessness of such truthful polynomial-time auctions in all cases where exact optimization is computationally intractable.