A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions

Abhishek Ray (), Mario Ventresca () and Karthik Kannan ()
Additional contact information
Abhishek Ray: School of Business, George Mason University, Fairfax, Virginia 22030
Mario Ventresca: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47906
Karthik Kannan: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907

Information Systems Research, 2021, vol. 32, issue 4, 1099-1114

Abstract: Combinatorial auctions (CAs) are used to allocate bundles of items among interested bidders. However, to resolve bidder preference elicitation problems, CAs are conducted iteratively. Winner determination is a key bottleneck that restricted the widespread adoption of such iterative CAs. Time bounded winner determination is further complicated by the increased variety and velocity of bids each round, and so regular solvers such as IBM CPLEX and A Mathematical Programming Language have been demonstrably ineffective in determining winners within a short duration. In response, 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–based anytime algorithm ( tr aveling a nts for c ombinatorial a uctions, or TrACA) that produces optimal or near-optimal winner determination results within specified time. Experiments are performed on 94 open test instances that display a variety in bid-bundle composition. We show and compare the performance of TrACA to 20 most recent state-of-the-art heuristics and two of the best exact algorithms (CPLEX and Max W Clique). Compared with 12 of 20 heuristics that employ classic search (e.g., stochastic local search, tabu search) or genetic or memetic algorithms, TrACA does significantly better on all instances. On the other eight heuristics that employ advanced hybrid search methodologies (e.g., hyperheuristics, biased random keys), TrACA performs significantly better on the harder test instances. Additionally, we show that TrACA resolves the trade-off between time and accuracy by achieving optimal solutions on 76 out of 94 instances, in at most one-sixth the time taken by exact algorithms. Finally, we analyze the TrACA search process and highlight factors that make TrACA suitable for solving hard auction instances within a prespecified (short) duration.

Keywords: design science; iterative combinatorial auctions; algorithms; metaheuristics; ant colony (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/isre.2021.1031 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orisre:v:32:y:2021:i:4:p:1099-1114

Access Statistics for this article

More articles in Information Systems Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().