Preference elicitation in combinatorial auctions
AssigneeCombineNet, Inc.
InventorsTuomas Sandholm, Wolfram Conen
Life of this patent
Estimating the term…
Abstract
In determining a winning allocation in a forward auction, reverse auction or an exchange, a plurality of allocations are defined wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers. At least one potential buyer is queried regarding at least one preference of the buyer about at least one allocation or a bundle associated therewith. The buyer's reply or intimation to the query is received and, based on the reply or intimation, each allocation that is either not feasible or not optimal is eliminated from consideration as the winning allocation. This process is repeated until a predetermined criteria is met whereupon one of the remaining allocations is selected as the winning allocation.
Claims30
A computer implemented method of determining a winning allocation in a forward auction, reverse auction or exchange comprising the following steps implemented by a computer processor operating under the control of a software program tangibly stored on a computer readable medium:
- (a) the computer processor defining a plurality of allocations, wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers;
- (b) the computer processor querying a bidder regarding at least one preference of said bidder about at least one allocation defined in step (a), a bundle associated with the one allocation defined in step (a), or an item associated with the one allocation defined in step (a), wherein the bidder is either a buyer or a seller;
- (c) the computer processor receiving said bidder's reply or intimation to the query of step (b);
- (d) based on said reply or intimation received in step (c), the computer processor permanently eliminating from consideration as a winning allocation each allocation defined in step (a) that is either (1) not feasible or (2) not optimal;
- (e) repeating steps (b)-(d) at least one time, wherein:
- for each repetition of step (b) the same bidder or a different bidder is queried from the previous repetition of step (b);
- and
- at least one iteration of step (b) includes either (1) a query of at least the bidder's preferred bundle or item that is not in response to a hypothetical bid price being proposed for at least one bundle or item, or (2) a query of at least the bidder's preferred bundle or item that is in response to a hypothetical bid price being proposed for at least two bundles or items, wherein the hypothetical bid price includes a price of at least one of said items or bundles that decreases from a prior query of said bidder's preferred bundle or item in response to a different hypothetical bid price being proposed for at least two bundles or items in a prior iteration of step (b);
- and
- (f) based on a predetermined criteria, the computer processor selecting one of the remaining plurality of allocations as the winning allocation.
A computer readable medium having tangibly stored thereon software which, when executed by a computer processor, cause the computer processor to perform the steps of:
- (a) define a plurality of allocations, wherein each allocation defines a trade between one or more potential buyers and one or more potential sellers;
- (b) query a bidder regarding at least one preference of said bidder about at least one allocation defined in step (a), a bundle associated with the one allocation defined in step (a), or an item associated with the one allocation defined in step (a), wherein the bidder is either a buyer or a seller;
- (c) receive said bidder's reply or intimation to the query of step (b);
- (d) based on said reply or intimation received in step (c), permanently eliminating from consideration as a winning allocation each allocation defined in step (a) that is either (1) not feasible or (2) not optimal;
- (e) repeat steps (b)-(d) at least one time, wherein:
- for each repetition of step (b) the same bidder or a different bidder is queried from the previous repetition of step (b);
- and
- at least one iteration of step (b) includes either (1) a query of at least the bidder's preferred bundle or item that is not in response to a hypothetical bid price being proposed for at least one bundle or item, or (2) a query of at least the bidder's preferred bundle or item that is in response to a hypothetical bid price being proposed for at least two bundles or items, wherein the hypothetical bid price includes a price of at least one of said items or bundles that decreases from a prior query of said bidder's preferred bundle or item in response to a different hypothetical bid price being proposed for at least two bundles or items in a prior iteration of step (b);
- and
- (f) based on a predetermined criteria, select one of the remaining allocations as the winning allocation.
Dependencies are inferred from the claim text.