Patent ID: 7716110
Filing Date: 2010-05-11
Classification: G06Q

Abstract:
1. A computer-implemented method for determining winning bid(s) in a combinatorial auction or exchange comprising: (a) receiving 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) choosing one of the bids received in the memory; (c) selecting bids from the bids received in the memory as a function of the chosen bid, wherein the selected bids include the chosen bid; (d) a processor of the computer forming in the memory of the computer from the selected bids at least part of a search tree that includes both bid inclusion branches and bid exclusion branches, said search tree defining for each selected bid at least one node on one level of the search tree that is connected to one other node on another level of the search tree by one of the bid inclusion branches or one of the bid exclusion branches; (e) the processor searching a plurality of unique paths of the search tree formed in the memory of the computer 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 a price of a candidate allocation is better than a current price of a best allocation, the processor updating the best allocation and its price as a function of the candidate allocation and its price.