A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions
- 1 December 2021
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Information Systems Research
- Vol. 32 (4) , 1099-1114
Abstract
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.Keywords
This publication has 37 references indexed in Scilit:
- A Differential Evolution Algorithm for the Winner Determination Problem in Combinatorial AuctionsElectronic Notes in Discrete Mathematics, 2010
- Local Search Methods for the Optimal Winner Determination Problem in Combinatorial AuctionsJournal of Mathematical Modelling and Algorithms, 2010
- Block order restrictions in combinatorial electric energy auctionsEuropean Journal of Operational Research, 2009
- Heuristics for a bidding problemComputers & Operations Research, 2006
- BOB: Improved winner determination in combinatorial auctions and generalizationsArtificial Intelligence, 2003
- A short convergence proof for a class of ant colony optimization algorithmsIEEE Transactions on Evolutionary Computation, 2002
- eMediator: A Next Generation Electronic Commerce ServerComputational Intelligence, 2002
- Algorithm for optimal winner determination in combinatorial auctionsArtificial Intelligence, 2002
- A Graph-based Ant System and its convergenceFuture Generation Computer Systems, 2000
- Ant algorithms and stigmergyFuture Generation Computer Systems, 2000