Exact Algorithms For The Matrix Bid Auction

摘要

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].