Randomized methods for solving the winner determination problem in combinatorial auctions

Combinatorial auctions, where buyers can bid on bundles of items rather than bidding them sequentially, often lead to more economically efficient allocations of financial resources. However, the problem of determining the winners once the bids are submitted, the so-called Winner Determination Problem (WDP), is known to be NP hard. We present two randomized algorithms to solve this combinatorial optimization problem. The first is based on the Cross-Entropy (CE) method, a versatile adaptive algorithm that has been successfully applied to solve various well-known difficult combinatorial optimization problems. The other is a new adaptive simulation approach by Botev and Kroese, which evolved from the CE method and combines the adaptiveness and level-crossing ideas of CE with Markov Chain Monte Carlo techniques. The performance of the proposed algorithms are illustrated by various examples.