System and method for an efficient dynamic multi-unit auction

• US 7,062,461 B1
• Filed: 05/18/2000
• Issued: 06/13/2006
• Est. Priority Date: 05/18/1999
• Status: Expired due to Term

• Current Assignee: Efficient Auctions, LLC
• Original Assignee: Efficient Auctions, LLC
• Inventors: Ausubel, Lawrence M.
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US09/573,007
• Time in Patent Office: 2,217 Days
• Field of Search: 705 25- 42
• US Class Current: 705/37
• 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

A method and apparatus allow the computer based implementation of an auction of heterogeneous types of items wherein one or more types of the items may include plural items. At any point in the bidding process, the set of feasible assignments of the items, given the bidding state, is the set of all possible allocations of the available quantity of the types of items to the bidders, subject to satisfying all the constraints on the assignment of the items, the constraints on the bidding process and the constraints posed by the bidding state. There may be a time in the auction when, based on the bidding state, one or more items (of one or more types) can only be assigned to one particular bidder in any feasible assignment, i.e., the particular bidder is guaranteed to be assigned the item. Such item is assigned to such bidder at such time.

Claims

1. A method for using a computer to implement an auction of heterogeneous objects, two or more bidders participating in the auction, the auction allowing assignment of objects of the same type to one or more of the bidders at different prices, the method comprising:

a) inputting, into the computer, bids from participating bidders,

b) determining at the computer, based on the bids, whether there is at least one object which is desired by only one bidder and,

c) in the event there is at least one object which is desired by only one bidder, assigning the determined object or objects to the determined bidder,

and wherein the determining further comprises;

b11) selecting a bidder,

b12) selecting an object type,

b13) determining if bids of other bidders for this object type total less than available objects of this type, and in that event the assigning comprises assigning to the selected bidder the smaller of;

the difference between number of available objects of this selected type and sum of bids by other bidders for this object type; and

the selected bidder'"'"'s bid for objects of this selected type.

2. A method as recited in claim 1 in which inputting and determining steps are repetitively performed until all objects are assigned, wherein any bidder is constrained in bidding based on prior bids.

3. A method as recited in claim 1 which includes the further steps of:

d) validating bids by

d1) selecting a bidder,

d2) comparing a most recent bid by the bidder to an earlier bid of the same bidder, and

d3) determining for each object type if a most recent bid carries a quantity less than an earlier bid,

d4) in the event the determination of step d3) is positive, determining the sum of all bids for objects of a type that in the event the sum is less than the number available, adjusting the most recent bid, or

d5) repeating steps d1)–

d4) for another bidder.

4. A method for using a computer to implement an auction of hetergeneous objects, two or more bidders participating in the auction, the auction allowing assignment of objects of the same type to one or more of the bidders at different prices, the method comprising:

a) inputting, into the computer, bids from participating bidders,

b) determining at the computer, based on the bids, whether there is at least one object which is desired by only one bidder and, if so, assigning the determined object or objects to the determined bidder, and

c) repeating steps a) and b) until no objects remain unassigned,

wherein said determining includes;

b1) selecting a bidder,

b2) summing, for all other bidders, a first sum representing a quantity of all objects bid for by the other bidders,

b3) identifying a quantity of all unassigned objects and determining if the quantity is strictly greater than the first sum,

b4) in the event the quantity is strictly greater than the first sum, then assigning objects either based on the selected bidder'"'"'s bid or using a most preferred assignment rule, and

b5) repeating steps b2) to b4) for each other bidder.

5. A method for using a computer to implement an auction of heterogeneous objects, two or more bidders participating in the auction, the auction allowing assignment of objects of the same type to one or more of the bidders at different prices, the method comprising:

a) inputting, into the computer, bids from participating bidders,

b) determining at the computer, based on the bids, whether there is at least one object which is desired by only one bidder and, if so, assigning the determined object or objects to the determined bidder, and

c) repeating steps a) and b) until no objects remain unassigned,

which includes the further steps of;

d) validating bids by

d1) selecting a bidder,

d2) comparing a most recent bid by the bidder to an earlier bid of the same bidder, and

d3) determining for each object type if a most recent bid carries a quantity less than an earlier bid,

d4) in the event the determination of step d3) is positive, determining the sum of all bids for objects of a type that in the event the sum is less than the number available, adjusting the most recent bid, or

d5) repeating steps d1)–

d4) for another bidder.

6. A computer system implementing an auction of heterogeneous objects, two or more bidders participating in the auction, the auction allowing assignment of objects of the same type to one or more of the bidders at different prices, the computer system including:

a) means for inputting to the computer, bids from participating bidders,

b) determining means for determining, based on the bids, whether there is at least one object which is desired by only one bidder and,

c) assigning means for assigning the determined object or objects to the determined bidder in the event there is at least one object which is desired by only one bidder,

wherein the determining means includes;

b1) means for selecting a bidder,

b2) means for summing, for all other bidders, a first sum representing a quantity of all objects bid for by the other bidders,

b3) means for identifying a quantity of all unassigned objects and determining if the quantity is strictly greater than the first sum,

and wherein the assigning means includes;

c1) responsive means, in the event the quantity is strictly greater than the first sum, for assigning objects either based on the selected bidder'"'"'s bid or using a most preferred assignment rule.

7. The system of claim 6 which further includes means for validating bids comprising

d1) means for selecting a bidder,

d2) means for comparing a most recent bid by the bidder to an earlier bid of the same bidder, and

d3) means for determining, for each object type if a most recent bid carries a quantity in excess of an earlier bid, and

d4) adjusting means for adjusting the most recent bid in the event the most recent bid carries a quantity in excess of an earlier bid.

8. A computer system implementing an auction of heterogeneous objects, two or more bidders participating in the auction, the auction allowing assignment of objects of the same type to one or more of the bidders at different prices, the computer system including:

a) input means for inputting bids from participating bidders,

b) determining means for determining, based on the bids, whether there is at least one object which is desired by only one bidder and,

c) assigning means for assigning, in the event there is at least one object which is desired by only one bidder, the determined object or objects to the determined bidder,

wherein the determining means includes;

b1) means for selecting a bidder,

b2) means for selecting an object type,

b3) summing means for determining if bids of other bidders for this object type total less than available objects of this type,

and wherein the assigning means comprises;

c1) responsive means, in the event the bids of other bidders for this object type totals less than the number of available objects of this type, for assigning to the selected bidder the smaller of;

the difference between number of available objects of this selected type and the total of bids by other bidders for this object type; and

the selected bidder'"'"'s bid for objects of this selected type.

9. The computer system of claim 8 wherein the determining means identifies each object which is desired by only one bidder and in which the assigning means assigns each such object identified by the determining means.

10. The computer system as recited in claim 8 which further includes means for validating bids comprising:

d1) means for selecting a bidder,

d2) means for comparing a most recent bid by the bidder to an earlier bid of the same bidder, and

d3) means for determining, for each object type if a most recent bid carries a quantity in excess of an earlier bid, and

d4) adjusting means for adjusting the most recent bid in the event the most recent bid carries a quantity in excess of an earlier bid.

11. A method for using at least one computer to implement an auction of at least two types of items, each of the types of items including plural items, the auction allowing submission of bids on the types of items at a plurality of times, the method comprising:

a) transmitting from a computer a signal representing auction information, said auction information including at least an indicator of a current price for each of the types of items;

b) receiving bids submitted by a plurality of bidders, each bid indicating at least a quantity of one of the types of items that a bidder wishes to transact at the current price;

c) constraining bids at a computer to satisfy a condition that a sum of quantities bid by a bidder for all of the types of items at their current prices is no greater than a sum of quantities previously bid by the bidder for all of the types of items;

d) determining at a computer whether the auction should end or continue, based on a comparison of a sum of quantities that bidders wish to transact at the current price and an available quantity of items;

e) establishing updated auction information, said auction information including an updated price for at least one of the types of items; and

f) initiating at a computer at least one additional opportunity for bidders to submit bids at an updated price following a determination that the auction should continue.

12. The method of claim 11 further including the step of determining, at a computer, whether any units of any of the types of items have been clinched by any bidders and, if so, assigning the units determined to be clinched to the determined bidders.

13. The method of claim 12 wherein clinched units of a given type of item are assigned at a price related to the current price for the given type of item.

14. The method of claim 12 wherein clinched units of a given type of item are assigned at the current price for the given type of item.

15. The method of claim 11 further including the step of assigning units of a given type of item at a price related to the current price for the given type of item.

16. The method of claim 11 further including the step of assigning units of a given type of item at the current price for the given type of item.

17. A system comprising at least one computer for implementing an auction of at least two types of items, each of the types of items including plural items, the auction allowing submission of bids on the types of items at a plurality of times, the system comprising:

a) transmitting means for transmitting a signal representing auction information, said auction information including at least an indicator of a current price for each of the types of items;

b) receiving means for receiving bids submitted by a plurality of bidders, each bid indicating at least a quantity of one of the types of items that a bidder wishes to transact at the current price;

c) constraining means for constraining bids to satisfy a condition that a sum of quantities bid by a bidder for all of the types of items at their current prices is no greater than a sum of quantities previously bid by the bidder for all of the types of items;

d) first determining means for determining whether the auction should end or continue, based on a comparison of a sum of quantities that bidders wish to transact at the current price and an available quantity of items;

e) establishing means for establishing updated auction information, said auction information including an updated price for at least one of the types of items; and

f) initiating means for initiating at least one additional opportunity for bidders to submit bids at an updated price following a determination that the auction should continue.

18. The system of claim 17 which further includes second determining means for determining whether any units of any of the types of items have been clinched by any bidders and, if so, assigning the units determined to be clinched to the determined bidders.

19. The system of claim 18 wherein clinched units of a given type of item are assigned at a price related to the current price for the given type of item.

20. The system of claim 18 which further includes assigning means for assigning quantities that bidders wish to transact, at prices related to the current price, to the respective bidders following a determination that the auction should end.

21. The system of claim 17 which further includes assigning means for assigning units of a given type of item at a price related to the current price for the given type of item.

22. The system of claim 17 which further includes assigning means for assigning units of a given type of item at the current price for the given type of item.

23. The system of claim 17 wherein clinched units of a given type of item are assigned at the current price for the given type of item.

24. A method for using one or more computers to implement an auction of heterogeneous items, said heterogeneous items including m types of items, m equaling an integer of at least two, a bidder submitting bids in the auction at a plurality of times, the method comprising:

a) outputting, from a computer of said one or more computers, prices (P₁^t, . . . , P_m^t), each price P_k^t indicating the price of items of a given type k at time t;

b) receiving, into a computer of said one or more computers, bids indicating quantities (Q₁^i,t, . . . , Q_m^i,t), each quantity Q_k^i,t indicating a quantity of items of a given type k that a bidder i wishes to transact at time t;

c) processing, at a computer of said one or more computers, the received bids, said processing including determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t) satisfy a constraint that a sum of the quantities Q_k^i,t, summed over all k from 1 to m, is no greater than a sum of the quantities Q_k^i,s, summed over all k from 1 to m, where time s is a time preceding time t;

d) determining, at a computer of said one or more computers, whether the auction should continue, based on the processed bids; and

e) repeating a)–

d) if the auction is determined to continue.

25. The method of claim 24 further including the step of determining, at a computer, whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bidder.

26. The method of claim 25 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

27. The method of claim 25 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

28. The method of claim 24 further including the step of assigning units of a given type k of item at time t at a price related to P_k^t.

29. The method of claim 24 further including the step of assigning units of a given type k of item at time t at a price equaling P_k^t.

30. The method of claim 29 wherein all units that are assigned are assigned at the end of the auction.

31. A system comprising at least one computer for implementing an auction of heterogeneous items, said heterogeneous items including m types of items, m equaling an integer of at least two, a bidder submitting bids in the auction at a plurality of times, the system comprising:

a) means for outputting prices (P₁^t, . . . , P_m^t), each price P_k^t indicating the price of items of a given type k at time t;

b) means for receiving a bid indicating quantities (Q₁^i,t, . . . , Q_m^i,t), each quantity Q_k^i,t indicating a quantity of items of a given type k that a bidder i wishes to transact at time t;

c) means for processing the received bid, said processing including determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t) satisfy a constraint that a sum of the quantities Q_k^i,t, summed over all k from 1 to m, is no greater than a sum of the quantities Q_k^i,s, summed over all k over 1 to m, where time s is a time preceding time t; and

d) means for determining whether the auction should continue, based on the processed bids.

32. The system of claim 31 further including second determining means for determining whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bidder.

33. The system of claim 32 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

34. The system of claim 32 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

35. The system of claim 31 further including assigning means for assigning units of a given type k of item at time t at a price related to P_k^t.

36. The system of claim 31 further including assigning means for assigning units of a given type k of item at time t at a price equaling P_k^t.

37. The system of claim 36 wherein all units that are assigned are assigned at the end of the auction.

38. A method for using at least one computer to implement an auction of heterogeneous items, said heterogeneous items including m types of items, m equaling an integer of at least two, n bidders submitting bids in the auction, n equaling an integer of at least two, a bidder submitting bids in the auction at a plurality of times, the method comprising:

a) outputting, from a computer, prices (P₁^t, . . . , P_m^t), each price P_k^t indicating the price of items of a given type k at time t;

b) receiving, into a computer, a bid indicating quantities (Q₁^i,t, . . . , Q_m^i,t), each quantity Q_k^i,t indicating the quantity of items of a given type k that a bidder i wishes to transact at time t;

c) processing, at a computer, the received bid, said processing including determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t), together with the quantities (Q₁^j,t, . . . , Q_m^j,t) of all other bidders j, satisfy a constraint for every type k of item that a sum of the quantities Q_k^j,t, summed over all bidders j from 1 to n, is no less than an available quantity;

d) determining, at a computer, whether the auction should continue, based on the processed bids; and

e) repeating a)–

d) if the auction is determined to continue.

39. The method of claim 38 further including the step of determining, at a computer, whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bidder.

40. The method of claim 39 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

41. The method of claim 39 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

42. The method of claim 38 further including the step of assigning units of a given type k of item at time t at a price related to P_k^t.

43. The method of claim 38 further including the step of assigning units of a given type k of item at time t at a price equaling P_k^t.

44. The method of claim 43 wherein all units that are assigned are assigned at the end of the auction.

45. The method of claim 38 wherein the processing step further includes determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t) satisfy a constraint that a sum of the quantities Q_k^i,t, summed over all k from 1 to m, is no greater than a sum of the quantities Q_k^i,s, summed over all k from 1 to m, where time s is a time preceding time t.

46. The method of claim 45 further including the step of determining, at a computer, whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bladder.

47. The method of claim 46 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

48. The method of claim 46 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

49. The method of claim 45 further including the step of assigning units of a given type k of item at time t at a price related to P_k^t.

50. The method of claim 45 further including the step of assigning units of a given type k of item at time t at a price equaling P_k^t.

51. The method of claim 50 wherein all units that are assigned are assigned at the end of the auction.

52. A system comprising at least one computer for implementing an auction of heterogeneous items, said heterogeneous items including m types of items, m equaling an integer of at least two, n bidders submitting bids in the auction, n equaling an integer of at least two, a bidder submitting bids in the auction at a plurality of times, the system comprising:

a) means for outputting prices (P₁^t, . . . , P_m^t), each price P_k^t indicating the price of items of a given type k at time t;

b) means for receiving a bid indicating quantities (Q₁^i,t, . . . , Q_m^i,t), each quantity Q_k^i,t indicating a quantity of items of a given type k that a bidder i wishes to transact at time t;

c) means for processing the received bid, said processing including determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t) together with the quantities (Q₁^j,t, . . . , Q_m^j,t) of all other bidders j, satisfy a constraint for every type k of item that a sum of the quantities Q_k^j,t, summed over all bidders j from 1 to n, is no less than an available quantity; and

d) means for determining whether the auction should continue, based on the processed bids.

53. The system of claim 52 further including second determining means for determining whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bidder.

54. The system of claim 53 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

55. The system of claim 53 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

56. The system of claim 52 further including assigning means for assigning units of a given type k of item at time t at a price related to P_k^t.

57. The system of claim 52 further including assigning means for assigning units of a given type k of item at time t at a price equaling P_k^t.

58. The system of claim 57 wherein all units that are assigned are assigned at the end of the auction.

59. The system of claim 52 wherein the processing means further includes means for determining whether the quantities (Q₁^i,t, . . . , Q_m^i,t) satisfy a constraint that a sum of the quantities Q_k^i,t, summed over all k from 1 to m, is no greater than a sum of the quantities Q_k^i,s, summed over all k from 1 to m, where time s is a time preceding time t.

60. The system of claim 59 further including second determining means for determining whether any units of any of the types of items have been clinched by any bidder and, if so, assigning the units determined to be clinched to the determined bidder.

61. The system of claim 60 wherein clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

62. The system of claim 60 wherein clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

63. The system of claim 59 further including assigning means for assigning units of a given type k of item at time t at a price related to P_k^t.

64. The system of claim 59 further including assigning means for assigning units of a given type k of item at time t at a price equaling P_k^t.

65. The system of claim 64 wherein all units that are assigned are assigned at the end of the auction.