CABOB: A fast, optimal algorithm for winner determination in combinatorial auctions

• 成果类型: Article
• 署名作者: Sandholm, T; Suri, S; Gilpin, A; Levine, D
• 署名单位: Carnegie Mellon University; University of California System; University of California Santa Barbara
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1040.0336
• 发表日期: 2005
• 页码: 374-390
• 关键词: auction; Combinatorial auction; winner determination; winner-determination algorithm; search; branch and bound; MIP; anytime algorithm; branching heuristics; dynamically chosen heuristic; bounding across components; random restart

摘要

Combinatorial auctions where bidders can bid on bundles of items' can lead to more economically efficient allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower, bounding (also across components), elaborate and dynamically chosen bid-ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance. without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster-especially in cases with structure. CABOB's search runs in linear space and has significantly better anytime performance than CPLEX We also uncover interesting aspects of the problem itself. First, problems with short bids, which were hard for the first generation of specialized algorithms, are easy. Second, almost all of the CATS distributions are easy, and the run time is virtually unaffected by the number of goods. Third, we test several random restart strategies, showing that they do not help on this problem-the run-time distribution does not have a heavy tail.