System and method for an efficient dynamic multi-unit auction

• US 20060167787A1
• Filed: 02/08/2006
• Published: 07/27/2006
• Est. Priority Date: 05/18/2000
• Status: Active Grant

• Current Assignee: Efficient Auctions, LLC
• Original Assignee: Efficient Auctions, LLC
• Inventors: Ausubel, Lawrence M.
• Granted Patent: US 7,343,342 B2
• Time in Patent Office: Days
• 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. (canceled)

3. A method for 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 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;

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 3 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.

4. A method as recited in claim 3 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.

5. (canceled)

6. A method for 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 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, 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.

7. A method for 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 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, 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.

8-9. -9. (canceled)

10. 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:

a) receiving 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) 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 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, and wherein the assigning includes;

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

11. The computer system of claim 10 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.

12. (canceled)

14. 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:

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) 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,

d) 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.

13. The computer system of claim 14 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.

15. The computer system as recited in claim 14 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.

16. A method 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 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 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.

17. The method of claim 16 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.

18. The method of claim 16 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.

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

20. The method of claim 17 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.

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

22. 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.

23. The computer system of claim 22 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.

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

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

26. The computer system of claim 23 for assigning clinched units of a given type at a price related to the current price for the given type.

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

28. The computer system of claim 23 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.

29. A method 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 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) accepting 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 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 which were included in the bids taking part in the determining; and

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

30. The method of claim 29 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.

31. The method of claim 29 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.

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

33. The method of claim 32 wherein all units that are assigned are assigned at the end of the auction.

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

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

36. 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) accepting 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 included in the determining.

37. The computer system of claim 36 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.

38. The computer system of claim 36 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 36 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 37 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.

42. The computer system of claim 37 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.

43. A method 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 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) accepting 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 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) further determining whether the auction should continue, based on the bids taken into account in the determining; and

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

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

45. The method of claim 43 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.

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

47. The method of claim 46 wherein all units that are assigned are assigned at the end of the auction.

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

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

50. The method of claim 43 wherein the determining 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.

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

52. The method of claim 50 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.

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

54. The method of claim 53 wherein all units that are assigned are assigned at the end of the auction.

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

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

57. 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) accepting 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), 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) further determining whether the auction should continue, based on the bids taken into account in the determining.

58. The computer system of claim 57 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.

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

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

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

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

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

64. The computer system of claim 57 wherein the determining 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.

65. The computer system of claim 64 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.

66. The computer system of claim 64 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 64 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 the assigning is implemented so that all units that are assigned are assigned at the end of the auction.

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

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

71. A computer implemented method useful in applying a constraint in a clock auction, comprising the steps of:

conveying information, including prices for two or more types of items, to at least one bidder,

receiving from said bidder, information for a bid comprising quantities for said types of items, and

applying a constraint to the bid information to require that the sum of the quantities over a group of item types is no larger than the sum of quantities over a group of item types contained in a prior bid.

72. A method as recited in claim 71 wherein the group of item types is less than all the item types subject to the auction.

73. A method as recited in claim 71 wherein the group of item types includes a single item type.

74. A method as recited in claim 72 wherein the bid information is limited so that, for each different type of item, the number of items in a bid is no larger than the number of items contained in a prior bid.