Abstract O.R. Applications Auctions with bidder-determined allowable combinations

Combinatorial auctions are desirable as they enable bidders to express the synergistic values of a group of assets and thus may lead to better allocations. Compared to other types of auctions, they keep bidders from being exposed to risks (of receiving only parts of combinations that would be valuable to them) or from being overly cautious (in order to minimize such risks). However, computation time needed to determine the set of optimal winning combinations in a general combinatorial auction may grow exponentially as the auction size increases, and this is sometimes given as a reason for not using combinatorial auctions. To determine the winning allocation in a reasonable time, a bid taker might try to limit the kinds of allowable combinations, but bidders may disagree on what combinations should be allowed, and this may make limiting the allowable combinations politically infeasible. This paper proposes and tests successfully a new approach to managing the computational complexity of determining the set of winning combinations. The main idea is to let bidders themselves determine and prioritize the allowable combinations. Using bidder-determined combinations has two nice properties. First, by delegating the decision on what is biddable to the bidders who know what combinations are important to them, the bid taker is able to be (and appear) fair. Second, since bidders know their economics and have the incentive to get important combinations included, bidder prioritization of combinations will tend to assure that the most economically-important combinations are included in determining the winning set of bids if the bid taker is not able to consider all of the combination