Bidding and allocation in combinatorial auctions

When an auction of multiple items is performed, it is often desirable to allow bids on combinations of items, as opposed to only on single items. Such an auction is often called combinatorial, and the exponential number of possible combinations results in computational intractability ofmanyaspects regarding such an auction. This paper considers two of these aspects: the bidding language and the allocation algorithm. First we consider which kinds of bids on combinations are allowed and how, i. e. in what language, they are speci ed. The basic tradeo is the expressibility of the language versus its simplicity. Weconsider and formalize several bidding languages and compare their strengths. We proveexponential separations between the expressive power of di erent languages, and show that one language, \-bids with phantom items, can polynomially simulate the others. We then consider the problem of determining the best allocation { a problem known to be computationally intractable. We suggest an approach based on Linear Programming (LP) and motivate it. We provethat the LP approach nds an optimal allocation if and only if prices can be attached to single items in the auction. We pinpoint several classes of auctions where this is the case, and suggest greedy and branch-and-bound heuristics based on LP for other cases.