System and method for an auction of multiple types of items

• US 7,899,734 B2
• Filed: 05/31/2002
• Issued: 03/01/2011
• Est. Priority Date: 05/18/2000
• Status: Active Grant

• Current Assignee: Efficient Auctions, LLC
• Original Assignee: Efficient Auctions, LLC
• Inventors: Jones, Wynne P., Ausubel, Lawrence M., Cramton, Peter C.
• Primary Examiner(s): DUNHAM, JASON B
• Application Number:
  US10/467,868
• Publication Number:
  US 20050102215A1
• Time in Patent Office: 3,196 Days
• Field of Search: 705/26, 705/27, 705/35
• US Class Current: 705/37
• CPC Class Codes: G06Q 20/10 specially adapted for electronic funds transfer [EFT] systems; specially adapted for home banking systems
• CPC Class Codes: G06Q 20/20 Point-of-sale [POS] network systems
• CPC Class Codes: G06Q 30/0212 Chance discounts or incentives
• CPC Class Codes: G06Q 30/0235 constrained by time limit or expiration date
• CPC Class Codes: G06Q 30/0239 Online discounts or incentives
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• 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/03 Credit; Loans; Processing thereof
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• CPC Class Codes: G06Q 50/188 Electronic negotiation

Abstract

An improved system and method for a computer-implemented auction in which multiple types of items are auctioned together without imposing a particular division of supply or demand among the individual types of items. In some embodiments the auction of the present invention provides a means or method for establishing prices for the types of items, wherein the prices maintain a relationship. In other embodiments, the present invention provides a means or method for implying prices from price parameters in the bids received form bidders, based on a relation among the prices for the types of items. Market clearing may be defined by the condition that the aggregate quantity bid for all types of items is less than or equal to the available quantity of all types of items. The division among the types of items within is thus determined flexibly, based on the bids at the associated prices. In other embodiments, market clearing is defined by the condition that the quantity bid for one selected type of item is less than or equal to the available quantity of the selected type of item. The quantities of the other types of items are thus determined flexibly, based on the bids at the associated prices.

Claims

1. A computer system for conducting an auction of at least one type of item among a plurality of bidders in a plurality of rounds, wherein bids are received and processed by the computer system, said system comprising:

establishing means for establishing a starting price, an ending price and a price range, said ending price different from said starting price, and said price range comprising prices between said starting and ending prices, for at least one type of item in a given round of the plurality of rounds,

receiving means for receiving bids in the given round, wherein a bid comprises a quantity parameter indicating a quantity of at least one type of item and a price parameter indicating a price within the established price range, said price parameter dividing the established price range into a first interval comprising prices between the indicated price and the established starting price and a second interval comprising prices between the indicated price and the established ending price,

processing means for processing the received bids, said processing means treating a bid with said quantity parameter and said price parameter from a given bidder as a proposal to transact the indicated quantity at a price within the second interval and as a proposal to transact another quantity at a price within the first interval, said another quantity based on at least one other bid in the auction by the given bidder,

determining means for determining whether the auction should continue or end, based on the received bids, and

initiating means for initiating an additional round, following a determination that the auction should continue.

2. A system as recited in claim 1 which further comprises means for constraining the changes in a bid from a given bidder in an additional round by considering, in the processing means, only bids which satisfy a constraint enforced by the means for constraining.

3. The computer system as recited in claim 1 wherein the quantity parameter of a bid is capable of indicating a quantity other than a quantity of zero and a quantity of unity.

4. The computer system as recited in claim 3 for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed by the computer system, wherein:

said establishing means establishes starting prices, ending prices and price ranges for a plurality of types of items in a plurality of rounds.

5. A system as recited in claim 4 which further comprises means for constraining the changes in a bid from a given bidder in an additional round by considering, in the processing means, only bids which satisfy a constraint enforced by the means for constraining.

6. A system as recited in claim 5 wherein the constraining means includes summation means for calculating a sum of quantities bid for a group of types of items.

7. A system as recited in claim 6 wherein the constraining means includes comparing means for comparing the calculated sum with a previous calculated sum for the same group of types of items.

8. A system as recited in claim 4 which further comprises:

constraining means for constraining bids for a set of types of items received from the given bidder within the given round, said constraining means limiting a sum of the indicated quantities of second bids to be no greater than a sum of the indicated quantities of first bids, in the event that the indicated prices of the second bids are between the indicated prices of the first bids and the established ending prices of the given round.

9. A computer system as recited in claim 1 which allocates at least some items among the bidders based on the bids, said computer system further comprising:

second determining means for determining an allocation of the items among the bidders based on the processed bids, following a determination that the auction should end.

10. A computer system as recited in claim 1 which further comprises:

second determining means for determining at least one final price based on the processed bids, following a determination that the auction should end.

11. The computer system as recited in claim 1 wherein the establishing means establishes a price range applicable to an additional round in response to the initiation of the additional round, said price range applicable to the additional round different from the price range established for the given round.

12. The computer system as recited in claim 1 wherein said processing means for processing the received bids treats the bid of the given bidder as a proposal to transact the indicated quantity at all prices within the second interval and as a proposal to transact another quantity at all prices within the first interval, said another quantity based on at least one other bid in the auction by the given bidder, in the event that only a single bid for the at least one type of item is received from the given bidder in the given round.

13. The computer system as recited in claim 1 wherein said processing means for processing the received bids treats a first bid and a second bid of the given bidder in the given round for a given type of item as a proposal to transact the second bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the established ending price, as a proposal to transact the first bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the first bid'"'"'s indicated price, and as a proposal to transact another quantity at a price between the first bid'"'"'s indicated price and the established starting price, said another quantity based on at least one other bid in the auction by the given bidder, where the indicated price of the second bid is between the indicated price of the first bid and the established ending price.

14. A system as recited in claim 13 which further comprises:

constraining means for constraining bids for a given type of item received from the given bidder within the given round, said constraining means limiting the indicated quantity of the second bid to be no greater than the indicated quantity of the first bid.

15. A system as recited in claim 1 which further comprises:

constraining means for constraining bids received from the given bidder in the given round, said constraining means limiting said indicated quantity of a given type of item to be no greater than the quantity of the given type of item indicated at a previous round'"'"'s ending price.

16. A system as recited in claim 1 which further comprises:

constraining means for constraining bids for a given type of item received from the given bidder within the given round, said constraining means limiting the indicated quantity of a second bid to be no greater than the indicated quantity of a first bid, in the event that the indicated price of the second bid is between the indicated price of the first bid and the established ending price of the given round.

35. A system as recited in claim 4 which further comprises:

constraining means for constraining bids received from the given bidder in the given round, said constraining means limiting a sum of the indicated quantities of a set of types of items to be no greater than a sum of quantities of the set of types of items indicated at a previous round'"'"'s ending prices.

17. A computer system for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed by the computer system, said system comprising:

establishing means for establishing a starting price and an ending price for each of a plurality of types of items in a plurality of rounds, said establishing means establishing both a starting price and an ending price prior to the computer system receiving bids within a round, wherein the establishing means includes means to maintain a predetermined relation among the established prices,

receiving means for receiving bids, wherein a bid comprises a quantity parameter for at least one type of item and a price parameter signifying a percentage of the distance from the established starting price to the established ending price, and

processing means for processing the received bids to determine an allocation of the items among the bidders consistent with the bids in the event that an allocation consistent with the bids is possible, otherwise

enabling the establishing means to alter the prices established for at least one type of item.

18. A system as recited in claim 17 wherein the means to maintain a relation among the established prices employs a schedule of prices.

19. A system as recited in claim 17 wherein the means to maintain a relation among the established prices employs an algorithm.

20. A method implemented in a system comprising a plurality of computers, at least one of which is located remotely from at least one other of said computers and interconnected by a communication system, for conducting an auction of at least one type of item among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, said method comprising:

establishing a starting price, an ending price and a price range, said ending price different from said starting price, and said price range comprising prices between said starting and ending prices, for at least one type of item in a given round of the plurality of rounds,

receiving bids in the given round on at least one computer of said system and communicating at least some of said bids to at least one remotely-located computer via the communication system, wherein a bid comprises a quantity parameter indicating a quantity of at least one type of item and a price parameter indicating a price within the established price range, said price parameter dividing the established price range into a first interval comprising prices between the indicated price and the established starting price and a second interval comprising prices between the indicated price and the established ending price,

processing the received bids on the at least one remotely-located computer, said processing treating a bid with said quantity parameter and said price parameter from a given bidder as a proposal to transact the indicated quantity at a price within the second interval and as a proposal to transact another quantity at a price within the first interval, said another quantity based on at least one other bid in the auction by the given bidder,

determining whether the auction should continue or end, based on the received bids, and

initiating an additional round, following a determination that the auction should continue.

21. A method as recited in claim 20 which further comprises constraining the changes in a bid from a given bidder in an additional round by considering, in the processing, only bids which satisfy a constraint.

22. A method as recited in claim 20 wherein the quantity parameter of a bid is capable of indicating a quantity other than a quantity of zero and a quantity of unity.

23. A method as recited in claim 22 for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, wherein:

said establishing establishes starting prices, ending prices and price ranges for a plurality of types of items in a plurality of rounds.

24. A method as recited in claim 23 which further comprises constraining the changes in a bid from a given bidder in an additional round by considering, in the processing, only bids which satisfy a constraint.

25. A method as recited in claim 24 wherein the constraining includes calculating a sum of quantities bid for a group of types of items.

26. A method as recited in claim 25 wherein the constraining includes comparing the calculated sum with a previous calculated sum for the same group of types of items.

27. A method as recited in claim 23 which further comprises:

constraining bids received from the given bidder in the given round by limiting a sum of the indicated quantities of a set of types of items to be no greater than a sum of quantities of the set of types of items indicated at a previous round'"'"'s ending prices.

28. A method as recited in claim 23 which further comprises:

constraining bids for a set of types of items received from the given bidder within the given round by limiting a sum of the indicated quantities of second bids to be no greater than a sum of the indicated quantities of first bids, in the event that the indicated prices of the second bids are between the indicated prices of the first bids and the established ending prices of the given round.

29. A method as recited in claim 20 which also allocates at least some items among the bidders based on the bids, said method further comprising:

further determining an allocation of the items among the bidders based on the processed bids, following a determination that the auction should end.

30. A method as recited in claim 20 which further comprises:

further determining at least one final price based on the processed bids, following a determination that the auction should end.

31. A method as recited in claim 20 wherein the establishing includes establishing a price range applicable to an additional round in response to the initiation of the additional round, said price range applicable to the additional round different from the price range established for the given round.

32. A method as recited in claim 20 wherein said processing the received bids treats the bid of the given bidder as a proposal to transact the indicated quantity at all prices within the second interval and as a proposal to transact another quantity at all prices within the first interval, said another quantity based on at least one other bid in the auction by the given bidder, in the event that only a single bid for the at least one type of item is received from the given bidder in the given round.

33. A method as recited in claim 20 wherein said processing the received bids treats a first bid and a second bid of the given bidder in the given round for a given type of item as a proposal to transact the second bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the established ending price, as a proposal to transact the first bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the first bid'"'"'s indicated price, and as a proposal to transact another quantity at a price between the first bid'"'"'s indicated price and the established starting price, said another quantity based on at least one other bid in the auction by the given bidder, where the indicated price of the second bid is between the indicated price of the first bid and the established ending price.

34. A method as recited in claim 33 which further comprises:

constraining bids for a given type of item received from the given bidder within the given round by limiting the indicated quantity of the second bid to be no greater than the indicated quantity of the first bid.

36. A method as recited in claim 20 which further comprises:

constraining bids received from the given bidder in the given round by limiting said indicated quantity of a given type of item to be no greater than the quantity of the given type of item indicated at a previous round'"'"'s ending price.

37. A method as recited in claim 20 which further comprises:

constraining bids for a given type of item received from the given bidder within the given round by limiting the indicated quantity of a second bid to be no greater than the indicated quantity of a first bid, in the event that the indicated price of the second bid is between the indicated price of the first bid and the established ending price of the given round.

38. A method implemented in a system comprising a plurality of computers, at least one of which is located remotely from at least one other of said computers and interconnected by a communication system, for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, said method comprising:

establishing a starting price and an ending price for each of a plurality of types of items in a plurality of rounds, said establishing including establishing both a starting price and an ending price prior to said system receiving bids within a round, wherein the establishing includes maintaining a predetermined relation among the established prices,

receiving bids on at least one computer of said system and communicating at least some of said bids to at least one remotely-located computer via the communication system, wherein a bid comprises a quantity parameter for at least one type of item and a price parameter signifying a percentage of the distance from the established starting price to the established ending price, and

processing the received bids on the at least one remotely-located computer to determine an allocation of the items among the bidders consistent with the bids in the event that an allocation consistent with the bids is possible, otherwise altering the established prices for at least one type of item.

39. A method as recited in claim 38 wherein the relation among the established prices is determined by a schedule.

40. A method as recited in claim 38 wherein the relation among the established prices is determined by an algorithm.

41. A non-transitory computer readable medium storing a sequence of instructions which, when executed on a system comprising a plurality of computers, at least one of which is located remotely from at least one other of said computers and interconnected by a communication system, implements a method for conducting an auction of at least one type of item among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, said method comprising:

establishing a starting price, an ending price and a price range, said ending price different from said starting price, and said price range comprising prices between said starting and ending prices for at least one type of item in a given round of the plurality of rounds,

receiving bids in the given round on at least one computer of said system and communicating at least some of said bids to at least one remotely-located computer via the communication system, wherein a bid comprises a quantity parameter indicating a quantity of at least one type of item and a price parameter indicating a price within the established price range, said price parameter dividing the established price range into a first interval comprising prices between the indicated price and the established starting price and a second interval comprising prices between the indicated price and the established ending price,

processing the received bids on the at least one remotely-located computer, said processing treating a bid with said quantity parameter and said price parameter from a given bidder as a proposal to transact the indicated quantity at a price within the second interval and as a proposal to transact another quantity at a price within the first interval, said another quantity based on at least one other bid in the auction by the given bidder,

determining whether the auction should continue or end, based on the received bids, and

initiating an additional round, following a determination that the auction should continue.

42. A computer readable medium as recited in claim 41 wherein the quantity parameter of a bid is capable of indicating a quantity other than a quantity of zero and a quantity of unity.

43. A computer readable medium as recited in claim 42 storing a sequence of instructions which, when executed, implements a method for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, wherein:

said establishing establishes starting prices, and ending prices and price ranges for a plurality of types of items.

44. A computer readable medium as recited in claim 43 wherein the method further comprises constraining the changes in a bid from a given bidder in an additional round by considering, in the processing, only bids which satisfy a constraint.

45. A computer readable medium as recited in claim 44 wherein the constraining includes calculating a sum of quantities bid for a group of types of items.

46. A computer readable medium as recited in claim 45 wherein the constraining includes comparing the calculated sum with a previous calculated sum for the same group of types of items.

47. A computer readable medium as recited in claim 43 wherein said processing the received bids further comprises constraining bids received from the given bidder in the given round by limiting a sum of the indicated quantities of a set of types of items to be no greater than a sum of quantities of the set of types of items indicated at a previous round'"'"'s ending prices.

48. A computer readable medium as recited in claim 43 wherein said processing the received bids further comprises constraining bids for a set of types of items received from the given bidder within the given round by limiting a sum of the indicated quantities of second bids to be no greater than a sum of the indicated quantities of first bids, in the event that the indicated prices of the second bids are between the indicated prices of the first bids and the established ending prices of the given round.

49. A computer readable medium as recited in claim 41 wherein the method further comprises constraining the changes in a bid from a given bidder in an additional round by considering, in the processing, only bids which satisfy a constraint.

50. A computer readable medium as recited in claim 41, said method further comprising:

further determining an allocation of the items among the bidders based on the processed bids, following a determination that the auction should end.

51. A computer readable medium as recited in claim 41, said method further comprising:

further determining at least one final price based on the processed bids, following a determination that the auction should end.

52. A computer readable medium as recited in claim 41 wherein the establishing includes establishing a price range applicable to an additional round in response to the initiation of the additional round, said price range applicable to the additional round different from the price range established for the given round.

53. A computer readable medium as recited in claim 41 wherein said processing the received bids treats the bid of the given bidder as a proposal to transact the indicated quantity at all prices within the second interval and as a proposal to transact another quantity at all prices within the first interval, said another quantity based on at least one other bid in the auction by the given bidder, in the event that only a single bid for the at least one type of item is received from the given bidder in the given round.

54. A computer readable medium as recited in claim 41 wherein said processing the received bids treats a first bid and a second bid of the given bidder for a given type of item in the given round as a proposal to transact the second bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the established ending price, as a proposal to transact the first bid'"'"'s indicated quantity at a price between the second bid'"'"'s indicated price and the first bid'"'"'s indicated price, and as a proposal to transact another quantity at a price between the first bid'"'"'s indicated price and the established starting price, said another quantity based on at least one other bid in the auction by the given bidder, where the indicated price of the second bid is between the indicated price of the first bid and the established ending price.

55. A computer readable medium as recited in claim 54 wherein said processing the received bids further comprises constraining bids for a given type of item received from the given bidder within the given round by limiting the indicated quantity of the second bid to be no greater than the indicated quantity of the first bid.

56. A computer readable medium as recited in claim 41 wherein said processing the received bids further comprises constraining bids received from the given bidder in the given round by limiting said indicated quantity of a given type of item to be no greater than the quantity of the given type of item indicated at a previous round'"'"'s ending price.

57. A computer readable medium as recited in claim 41 wherein said processing the received bids further comprises constraining bids for a given type of item received from the given bidder within the given round by limiting the indicated quantity of a second bid to be no greater than the indicated quantity of a first bid, in the event that the indicated price of the second bid is between the indicated price of the first bid and the established ending price of the given round.

58. A non-transitory computer readable medium storing a sequence of instructions which, when executed on a system comprising a plurality of computers and a communication system, implements a method for conducting an auction of a plurality of types of items among a plurality of bidders in a plurality of rounds, wherein bids are received and processed, said method comprising:

establishing a starting price and an ending price for a plurality of types of item in a plurality of rounds, said establishing including establishing both a starting price and an ending price prior to said computer system receiving bids within a round, wherein the establishing includes maintaining a relation among the established prices,

receiving bids on at least one computer of said system and communicating at least some of said bids to at least one-remotely located computer via the communication system, wherein a bid comprises a quantity parameter for at least one type of item and a price parameter signifying a percentage of the distance from the established starting price to the established ending price for said type of item, and

processing the received bids on the at least one remotely-located computer to determine an allocation of the items among the bidders consistent with the bids in the event that an allocation consistent with the bids is possible, otherwise

altering the established prices for at least one type of item.

59. A computer readable medium as recited in claim 58 wherein the relation among the established prices is determined by a schedule.

60. A computer readable medium as recited recited in claim 58 wherein the relation among the established prices is determined by an algorithm.