Method, apparatus, and embodied data structures for optimal anytime winner determination in combinatorial auction-type problems
OwnerTuomas Sandholminventor
Life of this patent
Estimating the term…
Abstract
Disclosed is a method and data structures for solution of problems of the class equivalent to optimal allocation determination in a combinatorial auction. The method stores bids in a binary tree which is searched in conjunction with a stopmask data structure which allows, in effect, parts of the binary tree to be instantly pruned during search and in place. Depth-first search in this tree can be done in place without an open list or recursive calls. The main search method operates via recursive call and generates each allocation of positive value once but does not generate others.
Claims21
A computer-implemented method for optimally selecting sets of items and associated bids in a combinatorial auction, said computer-implemented method comprising the steps of:
- receiving a plurality of sets of items having associated bids, wherein each set has no restrictions regarding the items forming said set,
- storing said plurality of sets and associated bids in a data structure configured for searching based on the inclusion/exclusion of items,
- creating candidate allocations of said sets and associated bids, said candidate allocations created by repeatedly searching said data structure for a set wherein successive searches exclude sets having items already present in said candidate allocation, and
- selecting a candidate allocation comprising disjoint sets having an optimal combination of associated bids.
A computer-implemented method for maximizing the aggregate value of sets of individual items and individual values therefor in a combinatorial auction, said method comprising the steps of:
- (a) receiving as input to the computer a plurality of bids, wherein each bid is a set of one or more items with associated prices and each bid has no restrictions regarding the items forming the set;
- (b) pruning the bids in the computer to remove dominated bids;
- (c) generating in a storage of the computer from the remaining bids a bidtree of the remaining bids, and a stopmask array, wherein the stopmask array is a vector with one variable for each item;
- (d) inserting dummy bids into the array of bids in storage for all single items for which there are not already bids, and assigning these dummy bids a price of 0;
- (e) examining the bids individually in the computer to determine whether there are combinations of disjoint subsets of the items in the bid, the sum of whose bid prices is greater than, or equal to, the bid, and pruning those bids;
- and
- (f) conducting a main search to determine a maximum aggregate value allocation to maximize revenue from the auction.
A system comprising one or more computers controlled to maximize the aggregate bid value of sets of individual items and individual values therefor in a combinatorial auction, said system controlled to:
- (a) receive a plurality of bids, wherein a bid is a set of one or more items with associated prices and said set has no restrictions regarding the items forming it;
- (b) prune the bids to remove dominated bids;
- (c) generate a bidtree of bids, and a stopmask array of remaining bids;
- (d) insert dummy bids into the bidtree for all single items for which there are not already bids, and assigning these dummy bids a price of 0;
- (e) examine the bids individually to determine whether there are combinations of disjoint subsets of the items in the bid, the sum of whose bid prices is greater than, or equal to, the bid, and pruning those bids from the array;
- and
- (f) conduct a main search to determine a maximum aggregate value allocation.
A computer implemented method for determining a winning bid or a winning combination of bids in a combinatorial auction, said method comprising the steps of:
- (a) receiving a plurality of bids, wherein each bid is a set of one or more items with an associated value and each bid has no restrictions regarding the items forming the set;
- (b) creating candidate allocations of said sets, each candidate allocation comprised of a unique set or a unique union of disjoint sets and a combination of the associated values of each set of the candidate allocation;
- and
- (c) selecting the candidate allocation comprising the unique set or the unique union of disjoint sets having an optimal combination of associated values.
Dependencies are inferred from the claim text.