PR Wurman and MP Wellman

Second ACM Conference on Electronic Commerce, pages 21-29, Minneapolis, October 2000.
Copyright © 2000 ACM.


The allocation of discrete, complementary resources is a fundamental problem in economics and of direct interest to e-commerce applications. Combinatorial auctions account for complementarities by optimizing over offers expressed in terms of bundles. Progressive versions of combinatorial auctions alleviate the burden on bidders of expressing offers for all bundles of interest by providing interim feedback based on partial sets of bids. Feedback in terms of hypothetical prices is particularly useful, as it directs bidders toward those bundles potentially yielding the greatest surplus. For a general class of discrete resource allocation problems with free disposal, we establish by construction the existence of competitive equilibrium prices on bundles that support the efficient allocation. We introduce AkBA, a family of progressive auctions that use these equilibrium bundle prices. We examine a particular instance of the family, called A1BA, and present some empirical data on its performance.