System and method for an efficient dynamic multi-unit auction

Abstract

A method and apparatus allow the computer based implementation of an auction of heterogeneous types of items wherein one or more types of the items may include plural items. At any point in the bidding process, the set of feasible assignments of the items, given the bidding state is the set of all possible allocations of the available quantity of the types of items to the bidders, subject to satisfying all the constraints on the assignment of the goods, the constraints on the bidding process and the constraints posed by the bidding state. Depending on the particulars of the bids, there may be one or more items (of one or more types) which are only included in the bid of a single bidder. The bidding is constrained such that once an item is uniquely spoken for, that bidder is guaranteed to receive the item. The item is said to be desired by only one bidder and such item is assigned to that bidder at the time. The auction continues until all items are assigned.