System and method for an efficient dynamic multi-unit auction
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
79 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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (7)
-
-
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. - View Dependent Claims (9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
-
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 (P1t, . . . , Pmt), each price Pkt indicating the price of items of a given type k at time t; b) receiving bids indicating quantities (Q1i,t, . . . , Qmi,t), each quantity Qki,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 (Q1i,t, . . . , Qmi,t) satisfy a constraint that a sum of the quantities Qki,t, summed over all k from 1 to m, is no greater than a sum of the quantities Qki,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. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
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 (P1t, . . . , Pmt), each price Pkt indicating the price of items of a given type k at time t; b) receiving bids indicating quantities (Q1i,t, . . . , Qmi,t), each quantity Qki,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 (Q1i,t, . . . , Qmi,t) satisfy a constraint that a sum of the quantities Qki,t, summed over all k from 1 to m, is no greater than a sum of the quantities Qki,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. - View Dependent Claims (35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
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 (P1t, . . . , Pmt), each price Pkt indicating the price of items of a given type k at time t; b) receiving bids indicating quantities (Q1i,t, . . . , Qmi,t) each quantity Qki,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 Q1i,t, . . . , Qmi,t), together with the quantities (Q1j,t, . . . , Qmj,t) of all other bidders j, satisfy a constraint for every type k of item that a sum of the quantities Qkj,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. - View Dependent Claims (45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61)
-
-
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 (P1t, . . . , Pmt), each price Pkt indicating the price of items of a given type k at time t; b) receiving bids indicating quantities (Q1i,t, . . . , Qmi,t), each quantity Qki,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 (Q1i,t, . . . , Qmi,t), together with the quantities (Q1j,t, . . . , Qmj,t) of all other bidders j, satisfy a constraint for every ty pe k of item that a sum of the quantities Qkj,t, summed over all bidders j from 1 to n, is no less than an available quantity Q k; andd) further determining whether the auction should continue based on the bids. - View Dependent Claims (63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79)
-
Specification