Sealed Bid Auctions with Non-Additive Bid Functions

A traditional sealed bid auction of a single item sells the item at the high bid price to a bidder with the highest bid. Such an auction may be used to auction several items; each bidder submits a bid on each item and each item is sold to a high bidder on that item. Implicit in this traditional scheme is the assumption that the bid for a set of items is the sum of the bids on the individual items: there are instances where this restriction appears unreasonable.

This paper considers a more general sealed bid auction in which bids are submitted on all possible subsets of the items. The items are partitioned among the bidders to maximize revenue, where each bidder are partitioned among the bidders to maximize revenue, where each bidder pays what was bid on the set of items actually received. In general, the set partitioning problem is an extremely difficult integer programming problem, and there are two alternatives. The “greedy” and “sequential auction” heuristics are shown to result, at least for some examples, in very sub-optimal solutions. However, a class of slightly less general auction problems is presented for which optimal solutions may be calculated relatively easily; suggesting that some form of general sealed bid auctions may be appropriate in some situations.