Kevin M. Lochner, Michael P. Wellman
Studies of bidding languages for combinatorial auctions have highlighted tradeoffs between expressiveness and complexity of representation and computation of standard auction functions. When goods are multiattribute, the cost of supporting multi-unit offers is especially acute, since the underlying good space is itself exponential in the number of attribute dimensions. We investigate tradeoffs among expressiveness, operational cost, and economic efficiency for a class of multiattribute double-auction markets. To enable polynomial-time clearing and information feedback operations, we restrict the bidding language to a form of multiattribute OR-of-XOR expressions. We then consider the implications for this language restriction in environments where bidders' preferences lie within a strictly larger class, that of complement-free valuations. Using a family of multi-unit multiattribute valuations derived from a supply chain manufacturing scenario, we show that an iterative bidding protocol can often overcome the limitations of this language restriction. We further introduce a metric characterizing the degree to which valuations violate the substitutes condition, theoretically known to guarantee efficiency, and present experimental evidence that the actual efficiency loss is proportional to this degree of substitutes violation.
Subjects: 7.1 Multi-Agent Systems; 15.8 Simulation
Submitted: May 5, 2008