Randomized methods for solving the Winner Determination Problem in combinatorial auctions

Chan, J. C. C. and Kroese, D. P. (2008). Randomized methods for solving the Winner Determination Problem in combinatorial auctions. In: S. Mason, R. Hill, O. Rose and L. Mounch, Simulation Conference, 2008. WSC 2008. Winter. Winter Simulation Conference 2008 (WSC 2008), Miami, United States, (1344-1349). 7-10 December, 2008. doi:10.1109/WSC.2008.4736208

Author Chan, J. C. C.
Kroese, D. P.
Title of paper Randomized methods for solving the Winner Determination Problem in combinatorial auctions
Conference name Winter Simulation Conference 2008 (WSC 2008)
Conference location Miami, United States
Conference dates 7-10 December, 2008
Proceedings title Simulation Conference, 2008. WSC 2008. Winter   Check publisher's open access policy
Journal name 2008 Winter Simulation Conference, Vols 1-5   Check publisher's open access policy
Place of Publication Piscataway, NJ, U.S.A.
Publisher IEEE
Publication Year 2008
Sub-type Fully published paper
DOI 10.1109/WSC.2008.4736208
ISBN 9781424427279
ISSN 0891-7736
Editor S. Mason
R. Hill
O. Rose
L. Mounch
Start page 1344
End page 1349
Total pages 6
Collection year 2009
Language eng
Abstract/Summary 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.
Subjects E1
970101 Expanding Knowledge in the Mathematical Sciences
010405 Statistical Theory
010406 Stochastic Analysis and Modelling
Keyword Winner Determination Problem (WDP)
Markov processes
Monte Carlo methods
Combinatorial mathematics
Computational complexity
Financial management
Randomised algorithms
Q-Index Code E1
Q-Index Status Confirmed Code

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 2 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 19 Feb 2009, 11:50:44 EST by Marie Grove on behalf of School of Mathematics & Physics