Matrix Bidding in Combinatorial Auctions
Matrix Bidding in Combinatorial Auctions
复制标题
DOI：
10.1287/opre.1080.0637
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
Robert W. Day;S. Raghavan
中科院分区：
文献类型：
--
作者：
Robert W. Day;S. Raghavan
在组合拍卖中，竞标者可以对任何商品组合出价，出价数据可能呈指数级增长。我们描述了一种创新的组合拍卖格式，竞标者提交“矩阵投标”。这种方法的优点是，它为竞标者提供了一种机制，可以对每个可能的捆绑包紧凑地表示竞标者。我们描述了许多不同类型的偏好，可以使用矩阵出价来建模，这是非常灵活的，同时支持加性、次加性和超加性偏好。为了在更一般的偏好环境中利用矩阵出价格式的紧凑性，我们将矩阵出价的逻辑语言描述为“原子”，并表明矩阵出价紧凑地表达偏好，在其他出价语言中需要指数数量的原子，并且与文献中最复杂的语言一样具有表现力。我们将NP-hard赢家确定问题建模为一个多项式大小的整数规划，特别是一个带有侧约束的赋值问题。我们展示了这个公式的强度，用它我们快速解决了72个独特项目的赢家确定问题，表明这个模型可能非常适合实际实施。
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.