A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions
提出一种基于蚁群元启发式的随时算法，能在指定时间内给出组合拍卖胜者确定问题的最优或近优解，在94个测试实例上优于20种现有启发式和两种精确算法。
Iterative combinatorial auctions are known to resolve bidder preference elicitation problems. However, winner determination is a known key bottleneck that has prevented widespread adoption of such auctions, and adding a time-bound to winner determination further complicates the mechanism. As a result, heuristic-based methods have enjoyed an increase in applicability. We add to the growing body of work in heuristic-based winner determination by proposing an ant colony metaheuristic–based anytime algorithm that produces optimal or near-optimal winner determination results within specified time. Our proposed algorithm resolves the speed versus accuracy problem and displays superior performance compared with 20 past state-of-the-art heuristics and two exact algorithms, for 94 open test auction instances that display a wide variety in bid-bundle composition. Furthermore, we contribute to the literature in two predominant ways: first, we represent the winner determination problem as one of finding the maximum weighted path on a directed cyclic graph; second, we improve upon existing ant colony heuristic–based exploration methods by implementing randomized pheromone updating and randomized graph pruning. Finally, to aid auction designers, we implement the anytime property of the algorithm, which allows auctioneers to stop the algorithm and return a valid solution to the winner determination problem even if it is interrupted before computation ends.