This Article Full Text (PDF) e-companion References 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 Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Day, R. W. Articles by Raghavan, S. Search for Related Content

Matrix Bidding in Combinatorial Auctions

Operations and Information Management, School of Business, University of Connecticut, Storrs, Connecticut 06269
Robert H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, Maryland 20742
bob.day{at}business.uconn.edu
raghavan{at}umd.edu

In a combinational auction in which bidders can bid on any combination of goods, bid data can be of exponential size. We describe an innovative new combinatorial auction format in which bidders submit "matrix bids." The advantage of this approach is that it provides bidders a mechanism to compactly express bids on every possible bundle. We describe many different types of preferences that can be modeled using a matrix bid, which is quite flexible, supporting additive, subadditive, and superadditive preferences simultaneously. To utilize the compactness of the matrix bid format in a more general preference environment, we describe a logical language with matrix bids as "atoms" and show that matrix bids compactly express preferences that require an exponential number of atoms in other bidding languages and are as expressive as the most sophisticated languages in the literature. We model the -hard winner-determination problem as a polynomially sized integer program, specifically an assignment problem with side constraints. We show the strength of this formulation with which we rapidly solve winner-determination problems with 72 unique items, indicating that this model may be well suited for practical implementation.

Subject classifications: games/group decisions; bidding/auctions; information systems; decision support systems; integer programming; algorithms.
History: Received March 2006; revision received May 2008; accepted June 2008.

This article has been cited by other articles:

				D. R. Goossens, R. Muller, and F. C. R. Spieksma Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions INFORMS Journal on Computing, July 1, 2010; 22(3): 339 - 352. [Abstract] [PDF]