Method and apparatus for selecting a desirable allocation of bids in a combinatorial exchange setting

• US 7,353,191 B2
• Filed: 02/24/2005
• Issued: 04/01/2008
• Est. Priority Date: 02/24/2004
• Status: Active Grant

• Current Assignee: SciQuest Incorporated
• Original Assignee: Combinenet Incorporated (Jaggaer LLC)
• Inventors: Shields, Robert L. Jr., Sandholm, Tuomas, Boutilier, Craig E.
• Primary Examiner(s): Smith; Jeffrey A.
• Assistant Examiner(s): MISIASZEK, MICHAEL
• Application Number:
  US11/065,333
• Publication Number:
  US 20050192865A1
• Time in Patent Office: 1,132 Days
• Field of Search: 705/26, 705/27, 705/37, 705/1
• US Class Current: 705/26.4
• CPC Class Codes: G06Q 30/0275 Auctions
• CPC Class Codes: G06Q 30/0611 Request for offers or quotes
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A desirable allocation of bids in a combinatorial exchange can be selected by determining a first candidate allocation of the bids and a first value of a minimax regret, related to the difference in utility between the adversarial allocation and the candidate allocation, as a function of a first adversarial allocation of the bids. Based on the first candidate allocation, a second adversarial allocation of the bids and a first value of a maximum regret related to the difference in utility between the new adversarial allocation and the utility of the candidate allocation can be determined. When the value of the maximum regret is greater than the value of the minimax regret, the candidate allocation can be designated as the desirable allocation.

Claims

1. A method of selecting a desirable allocation of bids in a combinatorial exchange setting comprising:

(a) providing a plurality of bids, each of which includes at least one item, a quantity for each item and price for all of the item(s) and their quantities;

(b) selecting an adversarial allocation of the bids;

(c) determining as a function of the adversarial allocation of the bids (1) a candidate allocation of the bids and (2) a value of a minimax regret related to a utility associated with the adversarial allocation minus a utility associated with the candidate allocation;

(d) determining as a function of the candidate allocation (1) a new adversarial allocation of the bids and (2) a value of a maximum regret related to a utility associated with the new adversarial allocation minus a utility associated with the candidate allocation;

(e) if the current value of the maximum regret is greater than the current value of the minimax regret, determining as a function of the adversarial allocation(s) (1) a new candidate allocation of the bids and (2) a new value of minimax regret related to a utility associated with the adversarial allocations minus a utility associated with the new candidate allocation;

(f) determining as a function of the new candidate allocation (1) a new adversarial allocation of the bids and (2) a new value of maximum regret related to a utility associated with the new adversarial allocation minus a utility associated with the candidate allocations; and

(g) repeating steps (e) and (f) until the current value of maximum regret is not greater than the current value of minimax regret.

2. The method of claim 1, wherein step (a) further includes associating initial bounds to at least one feature of the exchange.

3. The method of claim 1, wherein each utility is a measure of the usefulness of the corresponding allocation(s) to a buyer.

4. The method of claim 3, wherein each utility is comprised of a value associated with at least one feature of the allocations over which the buyer has some preference.

5. The method of claim 4, wherein each utility is comprised of a sum of a plurality of values associated with a like plurality of features of the corresponding allocation(s) over which the buyer has some preference.

6. The method of claim 1, further including:

(h) determining at least one constraint for at least one pair of allocations; and

(i) repeating steps (b)-(g) subject to the one constraint.

7. The method of claim 6, wherein each pair of allocations includes (1) a candidate allocation and an adversarial allocation, (2) a pair of candidate allocations or (3) a pair of adversarial allocations.

8. The method of claim 5, further including:

(h) amending at least one value associated with at least one feature; and

(i) repeating steps (b)-(g).

9. An apparatus for selecting a desirable allocation of bids in a combinatorial exchange comprising:

means for receiving a plurality of bids, each of which includes at least one item, a quantity for each item and price for all of the item(s) and their quantities;

means for forming a first adversarial allocation of the bids;

means for determining as a function of the first adversarial allocation of the bids (1) a first candidate allocation of the bids and (2) a first value of a minimax regret related to a difference between a utility associated with the adversarial allocation and a utility associated with the candidate allocation;

means for determining as a function of the first candidate allocation (1) a second adversarial allocation of the bids and (2) a first value of a maximum regret related to a difference between a utility associated with the new adversarial allocation and a utility associated with the candidate allocation; and

means for producing a visual display of the first candidate allocation as the desirable allocation when the first value of the maximum regret is not greater than the first value of the minimax regret.

10. The apparatus of claim 9, further including means for associating initial bounds to at least one feature of the exchange.

11. The apparatus of claim 9, wherein, when the first value of the maximum regret is not greater than the first value of the minimax regret, further including:

means for determining as a function of the first adversarial allocation and the second adversarial allocation (1) a second candidate allocation of the bids and (2) a second value of minimax regret related to a difference between a utility associated with the first and second adversarial allocations, and a utility associated with the second candidate allocation;

means for determining as a function of the second candidate allocation (1) a third adversarial allocation of the bids and (2) a second value of maximum regret related to a difference between a utility associated with the third adversarial allocation and a utility associated with the second candidate allocation; and

means for designating the second candidate allocation as the desirable allocation when the second value of the maximum regret is not greater than the second value of the minimax regret.

12. The apparatus of claim 11, further including means for determining at least one constraint based on the selection of at least one pair of allocations, wherein (1) the third adversarial allocation of the bids and (2) the second value of the maximum regret are determined subject to the one constraint.

13. The apparatus of claim 11, further including means for determining as a function of at least one adversarial allocation a plurality of feasible allocations and means for determining at least one constraint based on at least one pair of allocations, wherein (1) at least one of the adversarial allocations of the bids and (2) one of the values of maximum regret are determined subject to the one constraint.

14. The apparatus of claim 9, wherein the visual display is produced by one of a video monitor and a printer.