Patent ID: 7640189
Filing Date: 2009-12-29
Classification: G06Q

Abstract:
1. A computer-implemented method for determining winning bid(s) in a combinatorial auction or exchange comprising: (a) storing bids in a memory of a computer, wherein each bid includes one or more items and a bid price associated with said one or more items; (b) directing a processor of the computer to choose one of the received bids; (c) directing the processor to select bids from the received bids as a function of the bid chosen in step (b), wherein the selected bids include the chosen bid; (d) directing the processor to form in the memory from said selected bids at least part of a search tree that includes inclusion branches and exclusion branches and which defines for each selected bid at least one node on one level of the search tree that is connected to at least one other node on another level of the search tree by either an inclusion branch or an exclusion branch; (e) directing the processor to search a plurality of unique paths of the search tree to determine for each path a candidate allocation of the selected bids, wherein each candidate allocation includes a combination of the selected bids that lie along the corresponding search path and a price that is the sum of the bid prices of the combination of the selected bids; and (f) when the processor determines that a price of a candidate allocation is better than a current price of a best allocation stored in a memory location, updating the memory location storing the best allocation and its price with the candidate allocation and its price.