This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Goossens, D. R. Articles by Spieksma, F. C. R.

Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions

Operations Research and Business Statistics, Faculty of Business and Economics, Katholieke Universiteit Leuven, 3000 Leuven, Belgium
Quantitative Economics, Maastricht University, 6200 MD Maastricht, The Netherlands
Operations Research and Business Statistics, Faculty of Business and Economics, Katholieke Universiteit Leuven, 3000 Leuven, Belgium
dries.goossens{at}econ.kuleuven.be
r.muller{at}maastrichtuniversity.nl
frits.spieksma{at}econ.kuleuven.be

A combinatorial auction is an auction where multiple items are for sale simultaneously to a set of buyers. Furthermore, buyers are allowed to place bids on subsets of the available items. This paper focuses on a combinatorial auction where a bidder can express his preferences by means of a so-called ordered matrix bid. Ordered matrix bids are a bidding language that allows a compact representation of a bidder's preferences and was developed by Day [Day, R. W. 2004. Expressing preferences with price-vector agents in combinatorial auctions. Ph.D. thesis, University of Maryland, College Park]. We give an overview of how a combinatorial auction with matrix bids works. We discuss the relevance of recognizing whether a given matrix bid has properties related to elements of economic theory such as free disposal, subadditivity, submodularity, and the gross substitutes property. We show that verifying whether a matrix bid has these properties can be done in polynomial time by solving one or more shortest-path problems. Finally, we investigate to what extent randomly generated matrix bids satisfy these properties.

Key words: combinatorial auction; matrix bids; free disposal; subadditivity; submodularity; gross substitutes; expressiveness
History: received May 2007; revised January 2009; accepted February 2009.