Granted Patent B2

US 7,353,191 · App. 11/065,333 · Granted Apr 1, 2008

Abstract

Claims (33)

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.

Assignments (21)