Matrix Bidding in Combinatorial Auctions
成果类型：
Article
署名作者：
Day, Robert W.; Raghavan, S.
署名单位：
University of Connecticut; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0637
发表日期：
2009
页码：
916-933
关键词：
摘要：
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 NP-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.