An Algorithm for Optimal Winner Determination in Combinatorial Auctions
An Algorithm for Optimal Winner Determination in Combinatorial Auctions
复制标题
DOI：
10.7936/k74j0cb1
复制
发表时间：
1999-07
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
T. Sandholm
组合拍卖，即投标人可以对物品组合进行投标的拍卖，往往比传统的多物品拍卖中的代理人对物品的估价不是相加的拍卖更有效地分配。然而，确定获胜者以使收入最大化是NP完全的。我们提出了一个搜索算法的最佳赢家确定。几个投标分布的实验。该算法允许组合拍卖的规模显着更大的项目和出价的数量比以前的方法，以最佳的赢家确定利用的事实，即出价的空间，在实践中必然是稀疏的。我们这样做，通过可证明足够的选择性生成的孩子在搜索中，并通过使用一种方法，快速的孩子生成，精确和优化的速度，和四种方法预处理的搜索空间。
Combinatorial auctions, i.e. auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auctions in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP complete. We present a search algorithm for optimal winner determination. Experiments are shown on several bid distributions. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is necessarily sparsely populated in practice. We do this via provably sufficient selective generation of children in the search and by using a method for fast child generation, heuristics that are accurate and optimized for speed, and four methods for preprocessing the search space.