Method, apparatus, and embodied data structures for optimal anytime winner determination in combinatorial auction-type problems

• US 6,272,473 B1
• Filed: 10/27/1998
• Issued: 08/07/2001
• Est. Priority Date: 10/27/1998
• Status: Expired due to Term

• Current Assignee: SciQuest Incorporated
• Original Assignee: Tuomas Sandholm
• Inventors: Sandholm, Tuomas
• Primary Examiner(s): Downs, Robert W.
• Assistant Examiner(s): Patel, Jagdish
• Application Number:
  US09/179,659
• Time in Patent Office: 1,015 Days
• Field of Search: 705/35, 705/37, 705/26
• US Class Current: 705/37
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

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.

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.

2. The computer-implemented method according to claim 1 further comprising removing one or more of said sets of items and associated bids stored in said data structure wherein said one or more sets of items and associated bids are selected for removal based on their associated bids being dominated by a combination of bids of other sets of items stored in said data structure and wherein items in said other sets of items are disjoint subsets of items in said removed sets of items.

3. The computer-implemented method according to claim 1 wherein said data structure is repeatedly searched using an iterative-deepening A* search.

4. The method of claim 3 wherein a heuristic used is based on a maximum bid contribution of items determined by (a) computing for each bid each item'"'"'s contribution to said bid by dividing the value of said bid by the number of items in the bid, and (b) associating each item with the maximum value computed therefor in step (a).

5. The method of claim 4 wherein said maximum bid contribution is recomputed every time a set is added to a candidate allocation.

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.

7. The method of claim 6 further comprising pruning bids that are dominated in the sense that there is some set of other bids, each of which other bids only contains items included in the pruned bid, the other bids do not share items, and the sum of the prices of those other bids is higher or equal to the bid price of the pruned bid.

8. The method of claim 7 further comprising using only items included in the bid to be pruned wherein if the tally of prices on a search path is greater or equal to the price of the bid to be pruned, the bid intended to be pruned is deleted.

9. The method of claim 6 comprising setting one or more variables in the stopmask array to “

ANY”

for items included in the bid intended to be pruned, and to “

NOT”

for items that are not included in the bid intended to be pruned.

10. The method of claim 6 wherein the array of remaining bids in storage is a binary tree with one level for each item in the auction, and bids are represented as leaves of the binary tree, where the inclusion of an item in a bid corresponds to a first direction of branching at the level of the tree corresponding to that item, and the exclusion of an item corresponds to a second direction of branching at the level of the tree corresponding to that item, wherein the method comprises following inclusion branches at levels corresponding to items in the bid and exclusion branches at levels corresponding to items not in the bid.

11. The method of claim 10 wherein each of the variables of the stopmask array takes a value of “

NOT”

, “

MUST” and

“

ANY”

, where “

NOT”

indicates that a search of the bidtree should not follow branches including the item, “

MUST”

indicates that a search of the bidtree should follow all branches that include the item, and “

ANY”

means no restrictions are placed on the search with respect to the item.

12. The method of claim 11 comprising conducting a main search by carrying out the steps of:

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.

16. The system of claim 15 wherein the bidtree of remaining bids is a binary tree with one level for each item in the auction and bids are represented as leaves of the binary tree, where the inclusion of an item in a bid corresponds to a first direction of branching at the level of the tree corresponding to that item, and the exclusion of an item corresponds to a second direction of branching at the level of the tree corresponding to that item, wherein the system is controlled to follow inclusion branches at levels corresponding to items in the bid and exclusion branches at levels corresponding to items not in the bid.

17. The system of claim 16 wherein the stopmask array is associated with a stopmask data structure, said stopmask data structure having one variable for each item in the auction, each of the variables taking a value of “

NOT”

, “

MUST” and

“

ANY”

, where “

NOT”

indicates that a search of the bidtree should not follow branches including the item, “

MUST”

indicates that a search of the bidtree should follow all branches that include the item, and “

ANY”

means no restrictions are placed on the search with respect to the item.

18. The system of claim 17 wherein the system is controlled to conduct a main search by carrying out the steps of:

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.