Information Feedback and Efficiency in Multiattribute Double Auctions

Studies of bidding languages for combinatorial auctions have highlighted tradeoffs between expressiveness and complexity of representation and computation of standard auction func-tions. When goods are multiattribute, the cost of support-ing multi-unit offers is especially acute, since the underly-ing 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 multi-attribute 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 ex-pressions. We then consider the implications for this lan-guage restriction in environments where bidders ’ preferences lie within a strictly larger class, that of complement-free valu-ations. 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 lim-itations of this language restriction. We further introduce a metric characterizing the degree to which valuations violate the substitutes condition, theoretically known to guarantee ef-ficiency, and present experimental evidence that the actual ef-ficiency loss is proportional to this degree of substitutes vio-lation