Auction method and apparatus
AssigneeHewlett-Packard Development Company, L.P.
InventorAndrew Robert Byde
Life of this patent
Estimating the term…
Abstract
An automatic system for determining outcomes to an auction process represents the auction by a directed graph and uses a K best solutions algorithm to determine the K best solutions. The system uses a particular graphical representation. Constraints may be included directly into the graph.
Claims18
A method for evaluating auction bids in an auction with I items and S counterparties, where each item i is subdivided into Q units, the method comprising:
- accepting a plurality of bids, each bid being a bid Bis (qs) representing a cost of a quantity qs of item i from counterparty s;
- generating, by executing a module stored on a non-transitory computer readable medium, a directed graph from a source vertex to a sink vertex representing the plurality of bids;
- identifying k shortest paths from the source vertex to the sink vertex, the bids making up each shortest path representing a corresponding solution to the auction-and the k-shortest paths representing the k best solutions, where k is an integer ≧2;
- and
- outputting the k best solutions;
- wherein the directed graph is defined by a single set of rules for all I items, and includes a plurality of intermediate vertices (i, s, q), wherein:
- i represents an item, i=1, 2, . . . I;
- s represents a counterparty, s=1, 2, . . . S;
- and
- q represents a number of units already supplied by counterparties from counterparty 1 up to and including counterparty s of item i, where q=0, 1, . . . Q.
A computer program product stored on a non-transitory computer readable medium for evaluating auction bids in an auction with I items and S counterparties, where each item i is subdivided into Q units, the computer program product comprising:
- code to accept a plurality of bids, each bid being a bid Bis (qs) representing the cost of a quantity qs of item i from counterparty s;
- code to generate a directed graph from a source vertex to a sink vertex representing the plurality of bids, the graph defined by a single set of rules for all I items;
- and
- code to identify the k-shortest paths from the source vertex to the sink vertex representing the k best solutions to accepting bids to obtain each item, where k is an integer ≦2;
- wherein the code to generate a directed graph comprises:
- code to generate the source vertex and the sink vertex;
- code to generate a plurality of intermediate vertices (i, s, q) for each item i where i=1, 2, . . . . I, for each counterparty s where s=1, 2, . . . S, and for each possible quantity q, where q is the total quantity of units of item i supplied by counterparties from counterparty 1 up to and including counterparty s and where q=0, 1, . . . Q.
An auction apparatus to auction I items among S counterparties, each item i being subdivided into Q units, the apparatus to accept a plurality of bids, each bid being a bid Bis (qs) representing a cost of a quantity qs of item i from counterparty s, the apparatus comprising:
- a formulation module stored in memory and executed by a processor to generate a directed graph from a source vertex to a sink vertex representing the plurality of bids;
- and
- a solutions determination module to identify, based on the generated directed graph, k bids that correspond to k shortest paths from the source vertex to the sink vertex, where k is an integer ≧2;
- wherein the directed graph is defined by a single set of rules for all I items and includes a plurality of intermediate vertices (i, s, q), wherein:
- i represents an item, i=1, 2, . . . I;
- s represents a counterparty, s=1, 2, . . . S;
- and
- q represents a number of units already supplied by counterparties from counterparty 1 up to and including counterparty s where q=0,1, . . . Q.
Dependencies are inferred from the claim text.