System and method for an efficient dynamic multi-unit auction

• US 7,343,342 B2
• Filed: 02/08/2006
• Issued: 03/11/2008
• Est. Priority Date: 05/18/2000
• Status: Expired due to Term

• Current Assignee: Efficient Auctions, LLC
• Original Assignee: Efficient Auctions, LLC
• Inventors: Ausubel, Lawrence M.
• Primary Examiner(s): Kramer; James
• Assistant Examiner(s): Tran; Hai
• Application Number:
  US11/293,190
• Publication Number:
  US 20060167787A1
• Time in Patent Office: 762 Days
• Field of Search: 705/37, 705/35
• 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 goods, the constraints on the bidding process and the constraints posed by the bidding state. Depending on the particulars of the bids, there may be one or more items (of one or more types) which are only included in the bid of a single bidder. The bidding is constrained such that once an item is uniquely spoken for, that bidder is guaranteed to receive the item. The item is said to be desired by only one bidder and such item is assigned to that bidder at the time. The auction continues until all items are assigned.

Claims

1. A method for implementing an auction of heterogeneous objects of at least two types, 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) accepting bids from participating bidders,

b) determining, 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 comprises;

b1) selecting a bidder,

b2) selecting an object type,

b3) 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 an object type;

d2) determining whether a sum of bids by bidders for objects of said selected type is less than a number of available objects of said type,

d3) in the event the determination of step d2) is positive, adjusting a particular bid for said object type by a particular bidder, the particular bid selected such that the particular bid is smaller than an earlier bid for said object type by said particular bidder, and

d4) repeating steps d1)-d3) for another bidder.

4. A computer-implemented method for conducting an auction of heterogeneous objects of at least two types, 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) accepting bids from participating bidders,

b) determining, at a computer, based on the bids for each different object type, 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 of a given type bid for by the other bidders,

b3) identifying a quantity of all unassigned objects of the given type 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 of the given type 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 computer-implemented method for conducting an auction of heterogeneous objects, of at least two types, 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) accepting bids from participating bidders,

b) determining, at a computer, based on the bids, whether there is at least one object of a given type which is desired by only one bidder and, if so, assigning the determined object or objects of the given type 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 an object type;

d2) determining whether a sum of bids by bidders for objects of said selected type is less than a number of available objects of said type,

d3) in the event the determination of step d2) is positive adjusting a particular bid for said object type by a particular bidder, the particular bid selected such that the particular bid is smaller than an earlier bid for said object type by said particular bidder, and

d4) repeating steps d1)-d3) for another bidder.

6. A computer system implementing an auction of heterogeneous objects of at least two types, 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:

a) receiving bids from participating bidders,

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

c) 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 includes;

b1) selecting a bidder,

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

b3) identifying a quantity of all unassigned objects of the given type and determining if the quantity is strictly greater than the first sum, and wherein the assigning includes;

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

7. The computer system of claim 6 in which the computer system

d1) selects a bidder,

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

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

d4) adjusts 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 of at least two types, 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:

a) accepting bids from participating bidders,

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

c) assigning, in the event there is at least one object of the given type which is desired by only one bidder, the determined object or objects to the determined bidder, wherein the determining includes;

b1) selecting a bidder,

b2) selecting an object type,

b3) determining if bids of other bidders for this object type total less than available objects of this type, and wherein the assigning comprises;

c1) in the event the bids of other bidders for this object type totals less than the number of available objects of this type, 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 identifies each object which is desired by only one bidder and the assigning assigns each such object identified by the determining means.

10. The computer system as recited in claim 8 which further includes 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 in excess of an earlier bid, and

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

11. A computer-implemented method for conducting 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) providing auction information including at least an indicator of a current price for each of the types of items;

b) accepting 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 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 least one additional opportunity for accepting 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 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 computer system 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 computer system:

a) 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 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 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 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 least one additional opportunity for bidders to submit bids at an updated price following a determination that the auction should continue.

18. The computer system of claim 17 for further 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 computer system of claim 18 for assigning clinched units of a given type at a price related to the current price for the given type.

20. The computer system of claim 18 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 computer system of claim 17 for further assigning units of a given type of item at a price related to the current price for the given type of item.

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

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

24. A computer-implemented method for conducting 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) providing 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 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) determining, at a computer, from the received bids 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) further determining whether the auction should continue, based on the 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 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. The method of claim 24 which further includes adjusting a bid in the event that the constraint is not satisfied.

32. The method of claim 31 wherein the adjusting comprises replacing said bid with a bid placed by the bidder i at an earlier time.

33. The method of claim 32 wherein said bid placed by the bidder i at an earlier time is a bid placed at the most recent time.

34. A computer system 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 computer system:

a) providing 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 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) 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; and

d) further determining whether the auction should continue based on the bids.

35. The computer system of claim 34 further 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.

36. The computer system of claim 35 implementing the assigning so that clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

37. The computer system of claim 35 implementing the assigning so that clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

38. The computer system of claim 34 further assigning units of a given type k of item at time t at a price related to P_k^t.

39. The computer system of claim 34 further assigning units of a given type k of item at time t at a price equaling P_k^t.

40. The computer system of claim 39 implementing the assigning so that all units that are assigned are assigned at the end of the auction.

41. The computer system of claim 34 wherein the computer system adjusts a bid in the event that the constraint is not satisfied.

42. The computer system of claim 41 wherein the adjusting comprises replacing said bid with a bid placed by the bidder i at an earlier time.

43. The computer system of claim 42 wherein said bid placed by the bidder i at an earlier time is a bid placed at the most recent time.

44. A computer-implemented method for conducting 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) providing 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 bids 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) determining, at a computer, whether a bid by the bidder i at time t indicating 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 Q_k;

d) further determining whether the auction should continue, based on the bids; and

e) repeating a)-d) if the auction is determined to continue.

45. The method of claim 44 further including the step of 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.

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

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

48. The method of claim 44 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.

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

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

51. The method of claim 44 wherein the determining also determines 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.

52. The method of claim 51 further including the step of 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.

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

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

55. The method of claim 51 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.

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

57. The method of claim 56 wherein all units that are assigned are assigned at the end of the auction.

58. The method of claim 44 which further includes adjusting a bid in the event that the constraint is not satisfied.

59. The method of claim 58 wherein the adjusting of a bid includes replacing the bid with a bid placed by the bidder i at an earlier time.

60. The method of claim 59 wherein said bid placed by the bidder i at an earlier time is a bid placed at the most recent time.

61. The method of claim 58 wherein the adjusting of a bid includes replacing the bid of bidder i with a bid indicating a quantity equal to Q_k−

Σ

<sub>j≠

i</sub>Q_k^j for the type k of item.

62. A computer system 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 computer system:

a) providing 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 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) determining whether a bid by the bidder i at time t indicatingjhe 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 ty pe 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 Q_k; and

d) further determining whether the auction should continue based on the bids.

63. The computer system of claim 62 further 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.

64. The computer system of claim 63 wherein the assigning is implemented so that clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

65. The computer system of claim 63 wherein the assigning is implemented so that clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

66. The computer system of claim 62 further assigning units of a given type k of item at time t at a price related to P_k^t.

67. The computer system of claim 62 further assigning units of a given type k of item at time t at a price equaling P_k^t.

68. The computer system of claim 67 wherein assigning is implemented so that all units that are assigned are assigned at the end of the auction.

69. The computer system of claim 62 wherein the determining also determines 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.

70. The computer system of claim 69 further 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.

71. The computer system of claim 70 wherein the assigning is implemented so that clinched units of a given type k of item are assigned at time t at a price related to P_k^t.

72. The computer system of claim 70 wherein the assigning is implemented so that clinched units of a given type k of item are assigned at time t at a price equaling P_k^t.

73. The computer system of claim 69 further assigning units of a given type k of item at time t at a price related to P_k^t.

74. The computer system of claim 69 further assigning units of a given type k of item at time t at a price equaling P_k^t.

75. The computer system of claim 69 wherein the assigning is implemented so that all units that are assigned are assigned at the end of the auction.

76. A computer system as recited in claim 62 wherein the computer system adjusts a bid in the event that the constraint is not satisfied.

77. A computer system as recited in claim 76 wherein the computer system adjusts a bid by replacing the bid with a bid placed by the bidder i at an earlier time.

78. A computer system as recited in claim 77 wherein said bid placed by the bidder i at an earlier time is a bid placed at the most recent time.

79. A computer system as recited in claim 76 wherein the computer system adjusts a bid by replacing the bid of bidder i with a bid indicating a quantity equal to Q_k−

Σ

<sub>j≠

i</sub>Q_k^j for the type k of item.