GPU-Accelerated Algorithms for the Winner Determination Problem in Combinatorial Auctions
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2023-12-11
Department
Major/Subject
Data Science
Mcode
SCI3115
Degree programme
Master's Programme in ICT Innovation
Language
en
Pages
45 + 21
Series
Abstract
This thesis explores the use of GPUs to improve the efficiency of solving the Winner Determination Problem (WDP) in Combinatorial Auctions, which involve selling multiple goods whose value depends on being sold together. Combinatorial Auctions are complex due to the lack of fixed prices for items, making the WDP a computationally challenging NP-complete problem. This thesis investigates the potential of GPUs, known for parallel processing, to accelerate WDP solutions. It provides an interdisciplinary overview of auctions, examining economic and computational perspectives. It also evaluates specific GPU-accelerated algorithms, focusing on a stochastic local search. Results show substantial speedup, although commercial solvers still outperform in solution quality and efficiency.Description
Supervisor
Korpi-Lagg, MaaritThesis advisor
Haruvi, YotamKeywords
GPGPU, combinatorial auction, stochastic optimization, winner determination problem