GPU-Accelerated Algorithms for the Winner Determination Problem in Combinatorial Auctions

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis

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, Maarit

Thesis advisor

Haruvi, Yotam

Keywords

GPGPU, combinatorial auction, stochastic optimization, winner determination problem

Other note

Citation