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.
Claims15
A method of generating a directed graph representing an auction problem having I items and S counterparties, each item being subdivided into Q units, with a plurality of bids, each bid being a bid Bis (qs) representing the cost of qs units of item i with counterparty s where i may be any element of {1, 2, . . . l}, and s may be any element of {1, 2, . . . S};
- the method comprising:
- generating a source vertex and a sink vertex;
- generating a plurality of intermediate vertices (i, s, q) for each item i where i =1, 2, . . . l, for each counterparty s where s =1, 2, . . . S, and for each possible quantity q where q =0,1, . . . Q, wherein when s =S q=Q;
- generating, by executing a module stored on a non-transitory computer readable medium, edges representing each bid, each edge being an ordered edge from the source vertex or one of the intermediate vertices towards the vertex (i, s, q) of length Bis (qs) representing the cost of a quantity qs of item i by counterparty s where q is the total quantity of units of item i supplied by counterparties from counterparty 1 up to and including counterparty s so that there are a plurality of paths along the ordered edges from the source vertex to the sink vertex via intermediate vertices;
- and
- storing the directed graph as a model of the auction problem for solving the auction problem.
Auction apparatus for carrying out an auction having I items and S counterparties, each item being subdivided into Q units, the apparatus comprising:
- a formulation module for generating a directed graph representing an auction problem having l items and S counterparties, each item being subdivided into Q units, with a plurality of bids, each bid being a bid Bis (qs) representing the cost of qs units of item i with counterparty s;
- and
- a solutions determination module arranged to carry out a k-shortest path algorithm to identify the k- shortest paths from source to sink representing the k best solutions to accepting bids to obtain each item;
- wherein the formulation module includes
- a vertex generator for generating the source vertex and a plurality of intermediate vertices (i,s,q) for each item i where i =1,2, . . . l, for each counterparty s where s =1,2, . . . S, and for each possible quantity q where q=0, 1, . . . Q, wherein when s=S q=Q;
- and
- an edge generator for generating edges representing each bid, each edge being an ordered edge from a vertex towards the vertex (i, s, q) of length Bis (qs)s representing the cost of a quantity qs of item i by counterparty s and where
- q
- =
- ∑
- 1
- s
-
- q
- s
- .
Dependencies are inferred from the claim text.