Method, apparatus, and embodied data structures for optimal anytime winner determination in combinatorial auction-type problems
First Claim
1. 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.
18 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5)
-
-
6. 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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14)
carrying out a depth first search of the bidtree using the stopmask array for bids to add to a main search tree; and
(1) determining if an existing bid structure of the main search tree is the best allocation price;
(a) if so, updating the best allocation price and terminating the search; and
(b) if not, terminating the search;
or(2) entering a bid in the storage.
-
-
13. The method of claim 12 comprising alter entering a bid in the storage, resetting the stopmask in the storage in accordance with the bid and doing one of:
-
(a) searching the bidtree for a next node;
(b) backtracking and searching the bidtree for a sibling node;
or(c) exiting.
-
-
14. The method of claim 12 comprising the steps of:
-
(a) initializing the first element of the stopmask data structure to “
MUST”
;
(b) initializing the remaining elements of the stopmask data structure to “
ANY”
; and
(c) conducting a depth first search of the bidtree.
-
-
15. 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. - View Dependent Claims (16, 17, 18, 19, 20)
carrying out a depth first search of the bidtree using the stopmask array for bids to add to a main search tree; and
(1) determining if an existing bid structure of the main search tree is the best allocation price;
(a) if so, updating the best allocation price and terminating the search; and
(b) if not, terminating the search;
or(2) entering the bid.
-
-
19. The system of claim 18 wherein, after entering the bid, the system is controlled to reset the stopmask in accordance with the bid, and is further controlled to:
-
(a) search the bidtree for a next node;
(b) backtrack and searching the bidtree for a sibling node;
or(c) exit.
-
-
20. The system of claim 18 wherein the system is controlled to:
-
(a) initialize the first clement of the stopmask array to “
MUST”
;
(b) initialize the remaining elements of the stopmask array to “
ANY”
; and
(c) conduct a depth search of the bidtree.
-
-
21. 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.
-
Specification