Title: Exact algorithms for the matrix bid auction
Authors: Goossens, Dries ×
Spieksma, Frederik #
Issue Date: Apr-2009
Series Title: Computers & operations research vol:36 pages:1090-1109
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 [Expressing preferences with price-vector agents in combinatorial auctions. PhD thesis, University of Maryland; 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. We discuss the computational complexity of the winner determination problem for a special case of the matrix bid auction. We present 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 [Matrix bidding in combinatorial auctions. Manuscript; 2006].
ISSN: 0305-0548
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
ExactAlgorithms.pdf Published 246KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science