Exact algorithms for the matrix bid auction

D.R. Goossens, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

In a combinatorial auction, multiple items are for sale simultaneously to a set of buyers. These buyers are allowed to place bids on subsets of the available items. A special kind of combinatorial auction is the so-called matrix bid auction, which was developed by Day (2004). The matrix bid auction imposes restrictions on what a bidder can bid for a subsets of the items. This paper focusses on the winner determination problem, i.e. deciding which bidders should get what items. The winner determination problem of a general combinatorial auction is NP-hard and inapproximable. We discuss the computational complexity of the winner determination problem for a special case of the matrix bid auction. We compare two mathematical programming formulations for the general matrix bid auction winner determination problem. Based on one of these formulations, we develop two branch-and-price algorithms to solve the winner determination problem. Finally, we present computational results for these algorithms and compare them with results from a branch-and-cut approach based on Day and Raghavan (2006).
Original languageEnglish
Title of host publicationExperimental algorithms : 6th international workshop, WEA 2007, Rome, Italy, June 6-8, 2007 : proceedings
EditorsC. Demetrescu
Place of PublicationBerlin
PublisherSpringer
Pages433-445
ISBN (Print)978-3-540-72844-3
DOIs
Publication statusPublished - 2007
Externally publishedYes
EventWEA 2007, Rome, Italy; 2007-06-06; 2007-06-08 -
Duration: 6 Jun 20078 Jun 2007

Publication series

NameLecture Notes in Computer Science
Volume4525

Conference

ConferenceWEA 2007, Rome, Italy; 2007-06-06; 2007-06-08
Period6/06/078/06/07
OtherWEA 2007, Rome, Italy

Cite this