Branch on bid searching method and apparatus
AssigneeCombineNet, Inc.
InventorsTuomas Sandholm, Subhash Suri
Life of this patent
Estimating the term…
Abstract
In a multi-unit combinatorial auction, reverse auction, or exchange, a number of bids can be received, with each bid including one or more items and for each item a desired quantity thereof. Each bid also includes a price. A number of unique combinations of bids can be formed from the received bids, and the one combination of bids which represents the best value in terms of an auction setting, a reverse auction setting and/or an exchange setting can be determined. Thereafter, the bids forming this combination can be declared the winning bids of the auction, reverse auction or exchange.
Claims44
A computer-implemented method for determining winning bid(s) in a combinatorial auction or exchange comprising:
- (a) receiving bids, wherein each bid includes one or more items and a bid price associated with said one or more items;
- (b) choosing one of the received bids;
- (c) selecting bids from the received bids as a function of the chosen bid, wherein the selected bids include the chosen bid;
- (d) forming from the selected bids at least part of a search tree that 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 at least one of an inclusion branch and an exclusion branch;
- (e) searching 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 a price of a candidate allocation is better than a current price of a best allocation, updating the best allocation and its price with the candidate allocation and its price.
A computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of:
- (a) receive bids, wherein each bid includes one or more items and a bid price associated with said one or more items;
- (b) choose one of the received bids;
- (c) select bids from the received bids as a function of the chosen bid, wherein the selected bids include the chosen bid;
- (d) form from the selected bids at least part of a search tree that defines for each selected bid at least one node that is connected to at least one other node by at least one of an inclusion branch and an exclusion branch;
- (e) 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 a price of a candidate allocation is better than a current price of a best allocation, update the best allocation and its price with the candidate allocations and its price.
A method for determining a winning allocation of bids in a combinatorial exchange, combinatorial forward auction or combinatorial reverse auction comprising:
- (a) receiving a plurality of bids, wherein each bid includes one or more items and an associated bid price for said one or more items;
- (b) utilizing a branch on bid tree search technique to create from the received bids a plurality of disjoint candidate allocations of bids;
- (c) determining a price for each candidate allocation by combining the bid prices of the bids forming the candidate allocation;
- and
- (d) selecting the candidate allocation having an optimal price.
Dependencies are inferred from the claim text.