A Genetic Algorithm for the Winner Determination Problem in Combinatorial Auctions

Abstract

Auctions are a very popular way of allocating multiple items. There are three different auction types, such as sequential auctions, parallel auctions, and combinatorial auctions. This study focuses on combinatorial auctions. Combinatorial auctions allow bidders to bid on a collection of items rather than a single item. This results in more efficient allocations than traditional auctions. The problem is determining the winners of all bids in a way that maximizes the auctioneer's profit. Some instances of the problem may be solvable in polynomial time with a few items and bidders. However, with excessive numbers of items and bidders, the problem becomes NP-complete. In this paper, a genetic algorithm is proposed and compared with a random search algorithm on various sized datasets. The results for experiments indicate that the proposed genetic algorithm performs better than random search as the size of the problem increases. © 2018 IEEE.