Preference elicitation in combinatorial auctions

• US 20040039682A1
• Filed: 04/10/2003
• Published: 02/26/2004
• Est. Priority Date: 04/10/2002
• Status: Active Grant

• Current Assignee: SciQuest Incorporated
• Original Assignee: Combinenet Incorporated (Jaggaer LLC)
• Inventors: Conen, Wolfram, Sandholm, Tuomas
• Granted Patent: US 7,742,971 B2
• Time in Patent Office: Days
• US Class Current: 705/37
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

In determining a winning allocation in a forward auction, reverse auction or an exchange, a plurality of allocations are defined wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers. At least one potential buyer is queried regarding at least one preference of the buyer about at least one allocation or a bundle associated therewith. The buyer'"'"'s reply or intimation to the query is received and, based on the reply or intimation, each allocation that is either not feasible or not optimal is eliminated from consideration as the winning allocation. This process is repeated until a predetermined criteria is met whereupon one of the remaining allocations is selected as the winning allocation.

Claims

1. A method of determining an winning allocation in a forward auction, reverse auction or exchange comprising:

(a) defining a plurality of allocations, wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers;

(b) querying at least one potential buyer regarding at least one preference of said buyer about at least one allocation or a bundle associated therewith;

(c) receiving said buyer'"'"'s reply or intimation to the query;

(d) based on said reply or intimation, eliminating from consideration as a winning allocation each allocation that is at least one of (1) not feasible and (2) not optimal; and

(e) based on a predetermined criteria, selecting one of the remaining allocations as the winning allocation.

2. The method of claim 1, further including, before step (e), repeating steps (b)-(d) a plurality of times.

3. The method of claim 2, wherein, for each repetition of step (b), a different buyer is queried from the previous repetition of step (b).

4. The method of claim 1, wherein the reply in step (c) is at least one of (1) responsive to the query and (2) unsolicited information regarding said at least one preference of said buyer.

5. The method of claim 1, wherein the intimation in step (c) is the absence of a response by said buyer to the query.

6. The method of claim 1, wherein the criteria includes one of:

one remaining allocation;

all remaining allocations are equally optimal;

the remaining allocation'"'"'s values are all within a measure of each other; and

all remaining allocations have values that are within a predetermined range of values.

7. The method of claim 6, wherein the measure includes a bound or a factor.

8. The method of claim 1, wherein the query includes at least one of:

the bidder'"'"'s desired price for a bundle;

the bidder'"'"'s desired ranking of a bundle;

the bidder'"'"'s desired order of at least two bundles in the sense the buyer prefers one bundle over another;

the bidder'"'"'s desired bundle when a hypothetical bid price is proposed for two or more bundles;

the bidder'"'"'s desired attribute(s) associated with a bundle or at least one item thereof, and

how the bidder assimilates attribute(s) in the sense of how his utility is affected by the attribute values.

9. The method of claim 8, wherein the attribute(s) include at least 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, bidder flexibility, 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 drop-off time, latest drop-off time, production facility, packaging and flexibility.

10. The method of claim 8, wherein the bidder'"'"'s desired price includes one of an exact price, an upper bound and a lower bound.

11. The method of claim 1, wherein the query includes at least one of:

the bidder being asked if a valuation for a bundle is an exact price; and

the bidder being asked to supply an exact price for the bundle.

12. The method of claim 1, wherein the query includes at least one:

the bidder being asked to supply a ranking of at least two bundles;

the bidder being asked to supply a bundle that the bidder desires at a specific ranking;

the bidder being asked to supply a desired ranking to a bundle X; and

the bidder being asked to supply a next desired bundle after a bundle X.

13. The method of claim 1, wherein each bundle includes a least one item, a quantity of said one item and a price for the bundle.

14. The method of claim 1, further including:

summing the values of the bundles forming the winning allocation absent the value of each bundle of one bidder to obtain a first value;

determining another winning allocation absent the one bidder;

summing the values of the bundles in the other winning allocation to obtain a second value;

determining a difference between the first and second values; and

assigning said difference as the value of each bundle of the bidder in the winning allocation regardless of the price assigned to each bundle of the bidder.

16. The method of claim 1, wherein the query elicits from the buyer information known only by the buyer.

17. The method of claim 1, wherein the query includes at least one of:

the bidder being asked the effect on at least one offer if the allocations are restricted; and

the bidder being asked what restriction can be applied to the allocations to produce a specific change in at least one offer.

18. The method of claim 1, wherein the query includes at least one of:

the bidder being asked how much of a discount will an offer receive for a minimum value commitment; and

the bidder being asked how much business will the bidder have to be given in order to get from the bidder a predetermined percentage discount.

15. The method of claim 15, wherein the difference assigned is the value the bidder pays or the value the bidder receives.

19. A computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of:

(a) define a plurality of allocations, wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers;

(b) query at least one potential buyer regarding at least one preference of said buyer about at least one allocation or a bundle associated therewith;

(c) receive said buyer'"'"'s reply or intimation to the query;

(d) based on said reply or intimation, eliminate from consideration as a winning allocation each allocation that is at least one of (1) not feasible and (2) not optimal; and

(e) based on a predetermined criteria, select one of the remaining allocations as the winning allocation.

20. The computer readable medium of claim 19, wherein, before step (e), the instructions cause the processor to repeat steps (b)-(d) a plurality of times.

21. The computer readable medium of claim 20, wherein, for each repetition of step (b), the instructions cause the processor to, query a different buyer from the previous repetition thereof.

22. The computer readable medium of claim 19, wherein the reply in step (c) is at least one of (1) responsive to the query and (2) unsolicited information regarding said at least one preference of said buyer.

23. The computer readable medium of claim 19, wherein the intimation in step (c) is the absence of a response by said buyer to the query.

24. The computer readable medium of claim 19, wherein the criteria includes one of:

one remaining allocation;

all remaining allocations are equally optimal;

the remaining allocation'"'"'s values are all within a measure of each other; and

all remaining allocations have values that are within a predetermined range of values.

25. The computer readable medium of claim 24, wherein the measure includes a bound or factor.

26. The computer readable medium of claim 19, wherein the query includes at least one of:

the bidder'"'"'s desired price for a bundle;

the bidder'"'"'s desired ranking of a bundle;

the bidder'"'"'s desired order of at least two bundles in the sense the buyer prefers one bundle over another;

the bidder'"'"'s desired bundle when a hypothetical bid price is proposed for two or more bundles;

the bidder'"'"'s desired attribute(s) associated with a bundle or at least one item thereof; and

how the bidder assimilates attribute(s) in the sense of how his utility is affected by the attribute values;

27. The computer readable medium of claim 26, wherein the attribute(s) include at least 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, bidder flexibility, 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 drop-off time, latest drop-off time, production facility, packaging and flexibility.

28. The computer readable medium of claim 26, wherein the bidder'"'"'s desired price includes one of an exact price, an upper bound and a lower bound.

29. The computer readable medium of claim 19, wherein the query includes at least one of:

the bidder being asked if a valuation for a bundle is an exact price; and

the bidder being asked to supply an exact price for the bundle.

30. The computer readable medium of claim 19, wherein the query includes at least one:

the bidder being asked to supply a ranking of at least two bundles;

the bidder being asked to supply a bundle that the bidder desires at a specific ranking;

the bidder being asked to supply a desired ranking to a bundle X; and

the bidder being asked to supply a next desired bundle after a bundle X.

31. The computer readable medium of claim 19, wherein each bundle includes a least one item, a quantity of said one item and a price for the bundle.

32. The computer readable medium of claim 19, further including:

summing the values of the bundles forming the winning allocation absent the value of each bundle of one bidder to obtain a first value;

determining another winning allocation absent the one bidder;

summing the values of the bundles in the other winning allocation to obtain a second value;

determining a difference between the first and second values; and

assigning said difference as the value of each bundle of the bidder in the winning allocation regardless of the price assigned to each bundle of the bidder.

33. The computer readable medium of claim 32, wherein the difference assigned is the value the bidder pays or the value the bidder receives.

34. The computer readable medium of claim 19, wherein the query elicits from the buyer information known only by the buyer.

35. The computer readable medium of claim 19, wherein the query includes at least one of:

the bidder being asked the effect on at least one offer if the allocations are restricted; and

the bidder being asked what restriction can be applied to the allocations to produce a specific change in at least one offer.

36. The computer readable medium of claim 19, wherein the query includes at least one of:

the bidder being asked how much of a discount will an offer receive for a minimum value commitment; and

the bidder being asked how much business will the bidder have to be given in order to get from the bidder a predetermined percentage discount.