KM Lochner and MP Wellman

First Conference on Auctions, Market Mechanisms, and their Applications, May 2009.
Copyright (c) 2009, Lochner & Wellman.


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 implications of this restriction in environments where bidders’ preferences lie within a strictly larger class, that of complement-free valuations. Using valuations derived from a supply chain scenario, we show that an iterative bidding protocol can 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 metric.

Includes material previously presented at the AAAI-08 Workshop on Trading Agent Design and Analysis, July 2008.