Method and apparatus for forming expressive combinatorial auctions and exchanges
View Patent ↗A method of processing an exchange includes providing a solver/analyzer for determining a solution that includes at least one of a winning allocation and feasible allocations. At least one bid is received at the solver/analyzer, with each bid including at least one item and an associated price. Exchange description data (EDD) is associated with the at least one bid. The EDD is also received at the solver/analyzer. The processing of the at least one bid is modified in accordance with the at least one feature included in the EDD.
1. A computer-implemented method of conducting a combinatorial exchange comprising:
(a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price;
(b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: a non-price attribute of a bid; a non-price attribute of an item; an item adjustment; a bid adjustment; a cost constraint; a unit constraint; a cost requirement; a unit requirement; a counting constraint; a counting requirement; a homogeneity constraint; a mixture constraint; cost conditional pricing; or unit conditional pricing;
(c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with at least one of the following: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself;
(d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation; and
(e) electronically outputting the allocation and the value determined in step (d).
2. The method as set forth in claim 1 , wherein:
the non-price attribute of a bid is one of credit history, shipping cost, bidder credit worthiness, bidder business location, bidder business size, bidder zip code, bidder reliability, bidder reputation, bidder timeliness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility; and
the non-price attribute of an item is one of size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging and flexibility.
3. The method as set forth in claim 1 , wherein:
the item adjustment includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied, wherein the item adjustment is based on an item attribute of at least one item of the associated bid; and
the bid adjustment includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied, wherein the bid adjustment is based on a bid attribute of the at least one bid.
4. The method as set forth in claim 3 , wherein:
the item attribute is one of the following: size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging and flexibility; and
the bid attribute is one of the following: a size of one or more items of the bid, a color of one or more items of the bid, a weight of one or more items of the bid, delivery date, bidder credit history, shipping costs, bidder credit worthiness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility.
5. The method as set forth in claim 1 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following objectives: a surplus, a traded ask volume, a traded bid volume, a traded average volume, a number of winning bidders, or a number of losing bidders.
6. The method as set forth in claim 1 , wherein:
the cost constraint causes an amount of an exchange value that is allocated to a bid group to be limited to no more than a predetermined percent or cost of the exchange value, where the bid group includes at least one bid;
the unit constraint causes a quantity of an item that is awarded to a bid group to be limited to no more than a predetermined maximum quantity or percentage, where the bid group includes at least one bid;
the cost requirement causes a bid group to be allocated at least a predetermined percent or cost of an allocation value, or nothing, where the bid group includes at least one bid;
the unit requirement causes a bid group to be allocated at least a predetermined quantity or percentage of an allocation, or nothing, where the bid group includes at least one bid;
the counting constraint causes an allocation to be generated that includes a number of winning bid groups within a specified range, where each bid group includes at least one bid;
the counting requirement causes an allocation to be generated that includes at least one of the following: no winning bid groups or a number of winning bid groups within a specified range, where each bid group includes at least one bid;
the homogeneity constraint causes an allocation to be generated that includes a uniformity of items or bids as a function of an item attribute description associated with the items or bids; and
the mixture constraint causes an allocation to be generated that includes a specified average limit of an item or bid attribute of a bid group.
7. The method as set forth in claim 1 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a constraint relaxer that causes at least one soft constraint placed on an exchange to be relaxed.
8. The method as set forth in claim 7 , wherein the exchange includes at least one hard constraint that the solver/analyzer cannot relax.
9. The method as set forth in claim 7 , wherein a value is associated with the relaxation of the at least one relaxed soft constraint.
10. The method as set forth in claim 9 , wherein the value is aggregated across at least two relaxed soft constraints.
11. The method as set forth in claim 10 , wherein the aggregate constraint relaxation value is a function of how much each soft constraint is relaxed.
12. The method as set forth in claim 11 , wherein:
each soft constraint is assigned a weight;
the aggregate constraint relaxation value is a sum of the relaxation values of the relaxed soft constraints; and
the relaxation value of each relaxed soft constraint is one of the following: (i) a weight associated with the constraint, (ii) the weight of the constraint multiplied by a percentage amount that said constraint is relaxed, or (iii) the weight of the constraint multiplied by the absolute amount that said constraint is relaxed.
13. The method as set forth in claim 10 , wherein the allocation (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) maximizes or minimizes a value of the exchange minus or plus, respectively, the aggregate constraint relaxation value.
14. The method as set forth in claim 10 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a feasibility obtainer that causes an allocation to be output that (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) minimizes the aggregate constraint relaxation value.
15. The method as set forth in claim 1 , wherein:
the cost conditional pricing causes a value of an allocation to be modified based on a difference between (i) a total currency volume awarded to a first bid group, or a total currency volume awarded to a subset of the items of the first bid group and (ii) a total currency volume awarded to a second bid group, or a total currency volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid; and
the unit conditional pricing causes a value of an allocation to be modified based on a difference between (i) a unit volume awarded to a first bid group, or a unit volume awarded to a subset of the items of the first bid group and (ii) a unit volume awarded to a second bid group, or a unit volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid.
16. The method as set forth in claim 1 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of whether there is free disposal of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate less than an offered quantity of the item for sale without affecting the price of the bid that includes the item or (ii) allocate more than an offered quantity of the item for purchase without affecting the price of the bid that includes the item.
17. The method as set forth in claim 1 , further comprising at least one of the steps of:
(i) modifying at least one feature of the EDD associated with the at least one bid and processing the at least one bid in accordance with said modified feature;
(ii) including another feature with the EDD associated with the at least one bid and processing the at least one bid in accordance with said other feature; and
(iii) associating with the bid another EDD that includes another feature and processing the at least one bid in accordance with said other feature.
18. The method as set forth in claim 1 , further comprising terminating processing of the model in step (d) in response to at least one of the following: (i) elapse of predetermined time interval, (ii) a current best solution being within a predetermined numerical distance of an optimal solution, or (iii) a manual abort command.
19. The method as set forth in claim 1 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation of a quote request that causes, for a bid associated with the quote request, a price to be determined that would result in the bid being included in an allocation.
20. The method of claim 1 , wherein the representation of step (b) is a computer language.
21. The method of claim 20 , wherein the computer language is XML.
22. The method as set forth in claim 1 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of the free disposal quantity of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate as little as an offered quantity of the item for sale, minus the free disposal quantity, without affecting the price of the bid that includes the item or (ii) allocate as much as an offered quantity of the item for purchase, plus the free disposal quantity, without affecting the price of the bid that includes the item.
23. A computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of:
(a) electronically store a plurality of bids of a combinatorial exchange in a computer storage, with each bid including at least one item and an associated bid price;
(b) cause exchange description data (EDD) stored in the computer storage to be electronically associated with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features: a non-price attribute of a bid; a non-price attribute of an item; an item adjustment; a bid adjustment; a cost constraint; a unit constraint; a cost requirement; a unit requirement; a counting constraint; a counting requirement; a homogeneity constraint; a mixture constraint; cost conditional pricing; or unit conditional pricing;
(c) cause a model builder to electronically build a model of the received plurality of bids and the EDD associated with each bid of the subset of the plurality of bids;
(d) cause a solver/analyzer to electronically process said model to determine an infeasible allocation, a winning allocation or a feasible allocation and an allocation value for said exchange; and
(e) electronically output the allocation determined in step (d).
24. A computer-implemented method of conducting a combinatorial exchange comprising:
(a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price;
(b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features:
a non-price attribute of an item,
an item adjustment,
a cost requirement,
a unit requirement,
a counting requirement,
a mixture constraint,
a homogeneity constraint,
cost conditional pricing, or
unit conditional pricing;
(c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself;
(d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and
(e) electronically outputting the allocation and the value determined in step (d).
25. The method of claim 24 , wherein the non-price attribute of an item includes one of the following: size, color, weight, delivery date, width, height, purity, concentration, pH, brand, hue, intensity, saturation, shade, reflectance, origin, destination, volume, earliest pickup time, latest pickup time, earliest dropoff time, latest dropoff time, production facility, packaging, and flexibility.
26. The method of claim 24 , wherein:
the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and
the condition is based on a non-price attribute on an item of the associated bid.
27. The method of claim 24 , wherein the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing.
28. The method of claim 24 , wherein the unit requirement causes a bid group that includes at least one bid to be allocated either a predetermined quantity of an allocation, a predetermined percentage of an allocation, or nothing.
29. The method of claim 24 , wherein the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid.
30. The method of claim 24 , wherein the mixture constraint causes an allocation to be generated that includes a specified average limit of either an item attribute of a bid group or a bid attribute of a bid group.
31. The method of claim 24 , wherein the homogeneity constraint causes an allocation to be generated that includes a uniformity of items or bids based on a non-price attribute of the items or bids, respectively.
32. The method of claim 24 , wherein the cost conditional pricing causes a value of an allocation to be modified based on a difference between the total awarded currency volume of a first bid group and the total awarded currency volume of a second bid group, where the first bid group includes at least one bid.
33. The method of claim 24 , wherein the unit conditional pricing causes a value of an allocation to be modified based on a difference between an awarded unit volume of a first bid group and an awarded unit volume of a second bid group, where the first bid group includes at least one bid.
34. The method of claim 24 , wherein, in addition to the at least one feature of step (b), the EDD stored in the computer storage further comprises a representation, for each item, of whether there is free disposal of the item, wherein free disposal of the item enables the solver/analyzer to either (i) allocate less than an offered quantity of the item for sale without affecting the price of the bid that includes the item or (ii) allocate more than an offered quantity of the item for purchase without affecting the price of the bid that includes the item.
35. The method of claim 24 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following non-price attributes on a bid: credit history, shipping cost, bidder credit worthiness, bidder business location, bidder business size, bidder zip code, bidder reliability, bidder reputation, bidder timeliness, freight terms and conditions, insurance terms and conditions, bidder distance and bidder flexibility.
36. The method of claim 24 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of a bid adjustment that includes a condition and a value that is utilized to modify the bid price of the associated bid when the condition is satisfied.
37. The method of claim 24 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following constraints:
a cost constraint that causes an amount of an exchange value that is allocated to a bid group to be limited to no more than a predetermined percent or cost of the exchange value, where the bid group includes at least one bid;
a unit constraint that causes a quantity of an item that is awarded to a bid group to be limited to no more than a predetermined maximum quantity or percentage, where the bid group includes at least one bid; or
a counting constraint that causes an allocation to be generated that includes a number of winning bid groups within a specified range, where each bid group includes at least one bid.
38. The method of claim 24 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following:
a feasibility obtainer that causes an allocation to be output that (i) satisfies each hard constraint of the exchange that the solver/analyzer cannot relax and (ii) minimizes a value associated with said relaxation;
a constraint relaxer that causes at least one constraint placed on an exchange to be relaxed and to determine a value associated with said relaxation, or
a quote request that causes, for a bid associated with the quote request, a price to be determined that would result in the bid being included in an allocation.
39. The method of claim 24 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following objectives: a surplus, a traded ask volume, a traded bid volume, a traded average volume, a number of winning bidders, or a number of losing bidders.
40. The method of claim 24 , further comprising at least one of the steps of:
(i) modifying at least one feature of the EDD associated with the at least one bid and processing the at least one bid in accordance with said modified feature;
(ii) including another feature with the EDD associated with the at least one bid and processing the at least one bid in accordance with said other feature; and
(iii) associating with the bid another EDD that includes another feature and processing the at least one bid in accordance with said other feature.
41. The method of claim 24 , further comprising terminating processing of the model in step (d) in response to at least one of the following: (i) elapse of predetermined time interval, (ii) a current best solution being within a predetermined numerical distance of an optimal solution, or (iii) a manual abort command.
42. The method of claim 24 , wherein the representation of step (b) is a computer language.
43. A computer-implemented method of conducting a combinatorial exchange comprising:
(a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price;
(b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features:
an item adjustment,
a cost requirement,
a unit requirement,
a counting requirement,
cost conditional pricing, or
unit conditional pricing;
(c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself;
(d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and
(e) electronically outputting the allocation and the value determined in step (d).
44. The method of claim 43 , wherein:
the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and
the condition is based on a non-price attribute on an item of the associated bid.
45. The method of claim 43 , wherein:
the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing;
the unit requirement causes a bid group that includes at least one bid to be allocated either a predetermined quantity of an allocation, a predetermined percentage of an allocation, or nothing; and
the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid.
46. The method of claim 43 , wherein:
the cost conditional pricing causes a value of an allocation to be modified based on a difference between (i) a total currency volume awarded to a first bid group, or a total currency volume awarded to a subset of the items of the first bid group and (ii) a total currency volume awarded to a second bid group, or a total currency volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid; and
the unit conditional pricing causes a value of an allocation to be modified based on a difference between (i) a unit volume awarded to a first bid group, or a unit volume awarded to a subset of the items of the first bid group and (ii) a unit volume awarded to a second bid group, or a unit volume awarded to a subset of the items of the second bid group, wherein the first bid group includes at least one bid.
47. The method of claim 43 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following features: free disposal, a non-price attribute on a bid, a non-price attribute on an item, a bid adjustment, an objective, a cost constraint, a unit constraint, a counting constraint, a homogeneity constraint, a mixture constraint, a feasibility obtainer, a constraint relaxer, and a quote request.
48. The method of claim 43 , wherein the representation of step (b) is a computer language.
49. A computer-implemented method of conducting a combinatorial exchange comprising:
(a) electronically storing in a computer storage a plurality of bids of a combinatorial exchange, wherein each bid includes at least one item and an associated bid price;
(b) electronically associating exchange description data (EDD) stored in the computer storage with at least one of the following: a subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself, wherein the EDD stored in the computer storage comprises a representation of at least one of the following features:
an item adjustment,
a cost requirement,
a counting requirement, or
cost conditional pricing;
(c) a model builder electronically constructing a model of (1) the bids received in step (a) and (2) the EDD electronically associated in step (b) with: the subset of the received bids, each bid of the subset of the received bids, and/or the combinatorial exchange itself;
(d) a solver/analyzer electronically processing the model constructed in step (c) to determine for the combinatorial exchange an infeasible allocation, a winning allocation or a feasible allocation of received bids and a value for said allocation, subject to the EDD electronically associated in step (b); and
(e) electronically outputting the allocation and the value determined in step (d).
50. The method of claim 49 , wherein:
the item adjustment includes a condition and a value that is utilized to modify the bid price of an associated bid when the condition is satisfied; and
the condition is based on a non-price attribute on an item of the associated bid.
51. The method of claim 49 , wherein:
the cost requirement causes a bid group that includes at least one bid to be allocated either a predetermined percent of an allocation value, a predetermined cost of the allocation value, or nothing; and
the counting requirement causes an allocation to be generated that includes either no winning bid groups or a number of winning bid groups within a specified range, wherein each bid group includes at least one bid.
52. The method of claim 49 , wherein the cost conditional pricing causes a value of an allocation to be modified based on a difference between the total awarded currency volume of a first bid group and the total awarded currency volume of a second bid group, where the first bid group includes at least one bid.
53. The method of claim 49 , wherein, in addition to including at least one of the features in step (b), the EDD stored in the computer storage further comprises a representation of at least one of the following features: free disposal, a non-price attribute on a bid, a non-price attribute on an item, a bid adjustment, an objective, a cost constraint, a unit constraint, a counting constraint, a homogeneity constraint, unit conditional pricing, a mixture constraint, a feasibility obtainer, a constraint relaxer, and a quote request.
54. The method of claim 49 , wherein the representation of step (b) is a computer language.