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.

Description:
RELATED APPLICATIONS 
       [0001]    Prior US Applications: 
         [0002]    U.S. application Ser. No. 11/232,518 filed 22 Sep. 2005 “Computing A Set of K-Best Solutions to an Auction Winner-Determination Problem” (HP Ref: 200502482) and U.S. application Ser. No. 11/546,042 filed 11 Oct. 2006 “Constraint Satisfaction for Solutions to an Auction Winner-determination Problem” (HP Ref: 200600318). 
     
    
     FIELD OF INVENTION 
       [0003]    The invention relates to apparatus for solving certain problems, including for example auction problems, and related methods. 
       BACKGROUND 
       [0004]    A particular example of a winner determination problem is the winner determination problem for auctions. For example, consider a reverse auction in which a number of sellers provide bids for supplying quantities of a variety of goods and/or services. It would be desirable to have an automatic system capable of providing the best set of bids to accept. 
         [0005]    A difficulty may arise in that often there will be some form of constraint on the process so that the winner determination problem is not simply a question of selecting the set of bids which generate the lowest cost. For example, there may be a desire to have at least two suppliers, to avoid over-reliance on a single supplier, but not too many suppliers, to avoid excessive costs in procurement and delivery. It may be very hard to mathematically represent such constraints. For example, it may be very difficult to represent the desire not to have “too many suppliers” since it may not be clear at the start of the auction how many suppliers represents “too many”. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0006]    Embodiments will now be described, purely by way of example, with reference to the accompanying drawings, in which: 
           [0007]      FIG. 1  is a schematic diagram of an auction system according to an embodiment; 
           [0008]      FIG. 2  is a more detailed schematic diagram of the auction system of  FIG. 1 ; 
           [0009]      FIG. 3  is a schematic diagram of a graph representation of an auction system according to a comparative example; 
           [0010]      FIG. 4  is a schematic diagram of a graph representation according to an embodiment; 
           [0011]      FIG. 5  is a schematic diagram of an alternative graph representation according to another embodiment; and 
           [0012]      FIG. 6  is a schematic diagram of an alternative graph representation according to another embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0013]    The invention will now be described with reference to a particular example. The particular example is to an auction system, and the example presented relates to a reverse auction, also known as a procurement auction, where a purchaser invites bids to supply a number of different goods or services, which will be referred to as items. In general, there will be S sellers and I such items. 
         [0014]    The system operates schematically as shown in  FIG. 1 . A number of bids  120 A,  120 B, . . .  120 N are submitted to the auction system  130 , and a number of solutions (greater than one) are output as the k best solutions  180 . Each bid indicates a quantity of an item and a cost of the item. 
         [0015]    This is illustrated in more detail in  FIG. 2 , which illustrates the solutions module  210  within the auction system  130 . This contains a formulation module  220  for representing the bids as a graph  140 , stored on a computer-readable medium and a solutions determination module  230  for determining the solutions  180 . A preprocessing module  231  is in the embodiment provided for preprocessing the graph  140  represented by the formulations module. The computer readable medium may be, for example, a memory or a readable disk. 
         [0016]    The output may be a number k of solutions  180 . The system may also generate subsets of these, such as the subset of feasible solutions  282  that comply with certain constraints. These will be discussed in more detail below. 
         [0017]    The output may be displayed on a display  182 , output to a computer readable medium  184 , or both. 
         [0018]    One of the solutions is then selected, and the corresponding set of bids in the path of that solution are accepted and the remaining bids rejected. The suppliers then supply the quantities of the accepted bids and are paid the amounts of the accepted bids. 
         [0019]    The auction system  130  also allows the inputs of objective functions  240 , for determining the goal of the solutions determination module (for example, lowest cost) and side constraints  250 . 
         [0020]    There is no obligation that each supplier supplies all of any given item. For example, one supplier may supply half the required number of a particular kind of item, and another the rest. Thus, each item may be subdivided into a number of shares. The number of shares will be denoted Q (for quantiles), and each item may therefore be divided into Q quantiles. For example, if Q=4, there are four quantiles, and each supplier may supply 0, 1, 2, 3 or 4 quantiles of each of the items, representing 0%, 25%, 50%, 75% and 100% of the total requirement for that item. 
         [0021]    In this example, each seller provides a number of bids for each possible number of quantiles for each of the items. The bid from the s-th seller for supplying qs quantiles of the i-th item will be denoted B is  (q s ). 
         [0022]    It will be appreciated that I, S and Q are integers. Since there are I items, i may take the values 1, 2, 3 . . . I, and likewise s may take the values 1, 2, 3 . . . S and q may take the values 0, 1, 2, 3 . . . Q, since it is possible to supply 0 items. 
         [0023]    Given this significant number of bids, the problem is for the buyer to determine the best solution. 
         [0024]    The approach adopted in the present invention is to represent this problem as a directed graph. 
         [0025]    One version of such an approach has previously been considered within Hewlett Packard. In this approach the problem is broken down into sub-auctions for each of the items, a comparative example, illustrated in  FIG. 3 . There are two sellers (A and B) and the number of quantiles Q is 2, so that for each item there are two lots. Thus, for each item, the possibilities are that seller A sells both lots, represented as AA, that seller B sells both lots, represented as BB, and that each seller sells one lot, represented as AB. 
         [0026]    The formulation module  220  constructs a graph as illustrated in  FIG. 3 , with a source node  310 , a destination node  340  and a number of intermediate nodes  320 ,  330 . In this case, there are two intermediate nodes, a first intermediate node  320  and a second intermediate node  330 . 
         [0027]    Each item is represented by a set of edges (the lines in  FIG. 3 ) between two nodes, corresponding to the possible combinations to deliver each item. Thus, graph of  FIG. 3  represents three items. The first item is represented by the edges between the source node  310  and first intermediate node  320 , and each edge represents one of the three possible ways the two suppliers can supply the product. Similarly, the second item is represented by the edges between first and second intermediate nodes  320 ,  330 , and the third item is represented by the edges between the second intermediate node  330  and the destination node  340 . 
         [0028]    The length of each edge is then given as the sum of the bids for that edge. For example, the length of the edge AB between source node  310  and the first intermediate node  320  is the sum of the bid of seller A for supplying one unit and the bid of seller B for supplying one unit. 
         [0029]    The problem of finding the best combination of bids to accept then becomes the problem of finding the shortest path from the source node  310  to the destination node  340 . 
         [0030]    In this approach the number of edges between each pair of adjacent nodes, corresponding to each item, can be large. In particular, the number of edges for Q quantiles and S sellers is given by 
         [0000]    
       
         
           
             
               
                 
                   N 
                   = 
                   
                     
                       
                         ( 
                         
                           Q 
                           + 
                           S 
                           - 
                           1 
                         
                         ) 
                       
                       ! 
                     
                     
                       
                         Q 
                         ! 
                       
                        
                       
                         
                           ( 
                           
                             S 
                             - 
                             1 
                           
                           ) 
                         
                         ! 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0031]    For significant numbers of sellers and quantiles, this number can be very large. Accordingly, the inventor has realised that an improved graph can significantly reduce the number of edges. 
         [0032]    For each item, instead of a series of parallel edges between adjacent nodes as in  FIG. 3 , a more complex pattern of edges is adopted between source node s i    400  and sink node t i    410 , via intermediate vertices  420  labelled (s,q) for s=1, 2, 3 . . . S and q=1, 2, 3 . . . Q. The source and sink nodes correspond to adjacent vertices  310 ,  320  in the comparative example of  FIG. 3 . 
         [0033]    Consider first the specific example as illustrated in  FIG. 4 , which is for the case of a single item with three sellers and three quantiles (S=3, Q=3). The edges are directed left to right, and are labelled with their lengths. 
         [0034]    Each vertex (s,q) represents a situation where the sellers from 1 up to s have supplied their bids and supplied a total of q quantiles. Thus, where each seller s supplies q s  units 
         [0000]    
       
         
           
             q 
             = 
             
               
                 ∑ 
                 1 
                 s 
               
                
               
                 
                   q 
                   s 
                 
                 . 
               
             
           
         
       
     
       Thus, the vertex (2,1) represents a situation where the first two sellers have in total supplied one unit. 
       [0035]    The rows in  FIG. 4  are labelled with the values of q and the columns with the seller. 
         [0036]    The four edges from starting vertex si which may be represented as (0,0) represent the supply from the first seller of 0, 1, 2 or 3 quantiles respectively, and the lengths are the bids for supplying the respective number of quantiles. These edges terminate in the vertices (1,0), (1,1), (1,2) and (1,3) where the second number represents the total number of quantiles supplied. 
         [0037]    From each of these four vertices, the edges represent the supply by the second seller of 0, 1, 2, or 3 quantiles respectively. However, it should be noted that if the first seller has already supplied 2 quantiles, the second seller can only supply 0 or 1 since in this example the total number of quantiles supplied is 3. Therefore, there are only two paths from the (s,q)=(1,2) vertex corresponding to the supply of zero and 1 quantile respectively by the second seller. 
         [0038]    The set of paths leading to sink t i  (3,3) corresponds to the third seller supplying the remainder of the quantiles required at the corresponding price. 
         [0039]    Thus, the different paths from source  400  to sink  410  represent the different ways that the three sellers can supply the three quantiles of the item in question concerned. 
         [0040]    Of course, this approach may be used for other numbers of sellers and quantiles. 
         [0041]    Expressed more generally and mathematically, the following algorithm may be used to generate the graph for S sellers and Q quantiles for each item. 
         [0042]    The source node is s i    400  and the sink node t i    410 , and intermediate vertices  420  are labelled (s, q) for s=1, 2, 3 . . . S and q=1, 2, 3 . . . Q. 
         [0043]    For the first seller, s=1, for each quantile q 1  from 0 to q 1 , an edge is added from the node s i  to vertex (1,q 1 ) labelled q 1  and with length B i1 (q 1 ). 
         [0044]    For each of the sellers from s=2 to S−1, for quantiles q≦Q and q s ≦Q−q, connect the vertices (s−1, q) to (s, q+q s ) via an edge of label q s  and length B is (q s ). 
         [0045]    For the last seller s=S, connect each vertex (S−1,q) to the node t i  via an edge with label Q−q and length B iS (Q−1). 
         [0046]    At first sight, this graph may seem more complex than those of  FIG. 3 . However, the number of vertices is Q(S−1)+2 for each subgraph (i.e. for each item) and the number of edges is (S−2)((Q+1)(Q+2)/2)+2Q. 
         [0047]    Since there are I items, in general, the total number of vertices V is given by 
         [0000]        V=I ( Q ( S− 1)+2)   (2) 
         [0000]    and the total number of edges E is given by 
         [0000]        E =(( S− 2)(( Q+ 1)( Q+ 2)/2)+2Q)   (3) 
         [0048]    The total number of vertices is O(ISQ)—that is to say of order (ISQ), and the total number of edges O(ISQ 2 ). 
         [0049]    By comparison with equation (1), it may be seen that this polynomial order is much better than the number in the  FIG. 3  case, for large Q and S. 
         [0050]    The particular graphical representation used can cope efficiently with significant numbers of sellers and of a significant number of quantiles, i.e. wherein the amount of each item can be subdivided into a large number of different pieces. Thus, the use of the representation as recited allows faster and more computationally efficient processing than alternative formulations in these cases. 
         [0051]    The above description and  FIG. 4  relate to a sub-graph for a single item  500  which is chained together with graphs for other items  510 ,  520  to provide the complete graph as illustrated in  FIG. 5 . 
         [0052]    In an alternative approach the graph may be defined by a single set of rules for all items, rather than for each item separately. 
         [0053]    In this approach, there is a vertex for each triple (i,s,q) where i represents an item, s the seller and q the number of quantiles already supplied of by sellers up to and including the s-th seller of the i-the item. For s=S q=Q. There is an extra source node s=(0,0,0) and sink t=(I+1,S,Q). 
         [0054]    The graph is defined with edges as follows. 
         [0055]    1. Each vertex (i,s,q) is connected to (i, s+1q+q s ) for each s&lt;S−1 and q s ≦Q≦q. These are the majority of edges and correspond to the assignment of q s  quantiles of item i to seller s. These edges are labelled q s  and have length B is (q s ). 
         [0056]    2. Each vertex in the form (i,S−1q) is connected to (i,S,Q) for 0&lt;i≦I. These edges correspond to allowing the last seller to supply all remaining quantiles of item i. These edges are labelled (Q−q) and have length B iS (Q−q) 
         [0057]    3. (i,S,Q) is connected to (i+1,1,q 1 ) or each 0≦i&lt;I and q 1 ≦Q. These correspond to the assignment of q 1 items of the (i+1)—the item to the first seller, and thus represent the linking of the sub-graphs together. These edges have label q 1  and length B (i+1)1 (q 1 ) 
         [0058]    4. (i,S,Q) is connected to t with a single edge of length 0. 
         [0059]    The graphs may be represented in the auction system  130  in any convenient way. 
         [0060]    After the formulation module  220  has specified the graph, the solutions determination module  230  then determines a plurality (k) shortest paths. 
         [0061]    The skilled person is aware of a number of “k-shortest path” (KSP) algorithms which may be used for finding the k shortest paths, and any of these may be used to identify the k best solutions  180  ( FIG. 2 ) 
         [0062]    The use of a k-shortest path algorithm instead of just finding the single shortest path has certain benefits. It has been appreciated that the best path according to the algorithm is not always the best path in the real world, since there may be additional constraints or considerations that are difficult to incorporate into the model. For this reason, the provision of a plurality (k) shortest paths allows the user to select from the suitable shortest paths to deal with other constraints, such as a general desire to use no more than a particular number of suppliers, or the desire to take at least some items from one or more preferred suppliers if this can be done without excessively increasing costs. 
         [0063]    Such constraints can be very hard for users to capture mathematically. For example, the desire to use a preferred supplier if this can be done without excessively increasing costs requires knowledge in advance of what “excessively” means in this context, which may be hard to know in advance but which is easy for a procurement professional to identify presented with a list of options and their costs. 
         [0064]    Referring back to  FIG. 2 , the solutions determination module can be arranged not just to provide the k best solutions  180  but also subsets of these solutions according to additional criteria determined by side constraints. 
         [0065]    These can include features such as the requirement to use or not to use particular combinations of suppliers. The k best solutions  180  are searched to provide the feasible solutions that meet these side constraints, which will be a subset of the K best solutions. 
         [0066]    The above embodiments do not code constraints into the model or into the solutions determined by the solutions determination model. The user simply selects suitable solutions from the k best solutions. 
         [0067]    However, in other embodiments, which will now be described, some or all of the constraints are incorporated into the graphs so that they are automatically considered by the solutions determination module  230 . 
         [0068]    In general terms, the same approach is used as in  FIG. 5  as described above with a single graph. Each vertex is additionally labelled with an additional index x that can take any of a set of values that will be denoted as the set X which is {*, 1, 2, . . . N} where * is a special element of the set, representing the initial state. 
         [0069]    Thus, assuming that the set X has a certain number of possible values, each vertex (i, s q) for possible values of i, s and q in the graph of  FIG. 5  may be replaced by that number of vertices, labelled (i,s,q,x) for each possible value of x. 
         [0070]    The concept is to use the variable x to capture additional details to allow constraints to be modeled within the graph. 
         [0071]    For example consider a case where only certain subsets of sellers may be used, for example no more than two sellers. For simplicity, there may be three sellers, 1, 2 and 3 of which no more than two may be selected to supply all items. Each vertex may be labelled with the set of sellers that have already supplied. 
         [0072]    In this case the set X may be represented as {*, 1, 2, 3, 12, 13, 23}. * is the situation where no sellers have supplied any units, and each other element represents the sellers that have already supplied. Note that there is no element  123 , since this is not permitted by the constraint that there be no more than two sellers. Further, note that the values of X are in this case non-numeric—they represent elements of a set. There is in general no requirement that x is a numeric value. 
         [0073]    The source point  400  is labelled with x=*, and each edge as defined above connects (i,s,q,x) to (i′,s′,q′, x′) where the variable x′ keeps track of how many sellers have supplied. Thus, each edge from the source point (which represent the quantity of the first item sold by the first seller) is to x′={1} except for the case where q′=0, which mean that no items are sold from the first seller, which is to x′={*}. 
         [0074]    More generally, an edge from x={1} which represents a sale by the second seller is to the vertex labelled x′={12} since “after” this additional sale both sellers  1  and  2  have supplied. 
         [0075]    There are no edges defined from points labelled x={12} which involve supply by the third seller since this is not permitted. Such edges are omitted from the graph. 
         [0076]    These omitted edges from the graph mean that there are “hanging” edges which do not form part of any path from source to sink in this embodiment. However, the KSP algorithms can readily cope with this, so alternative embodiments may not have this property. 
         [0077]      FIG. 6  illustrates part of such a graph. It corresponds to the part starting from a value 1=0 and s=1 representing the supply of either zero or one unit by seller s=2. Each vertex of  FIG. 4  is replaced by seven vertices in  FIG. 6 , corresponding to the seven possible different values of x: *, 1, 2, 3, 12, 13, 23. 
         [0078]    The horizontal edges represent the supply of no units by seller  2 . The value of x is accordingly unchanged. 
         [0079]    The diagonal lines to q=1 represent the supply of one unit by seller  2 . Thus, where x={1} at the start, indicating that only seller  1  has supplied any units, x′={12} at the end indicating that sellers  1  and  2  have each supplied at least one unit. 
         [0080]    Note that there is no edge from x={13} since this would need to go to the element {123} which is not an element of X. Accordingly, this edge is omitted. 
         [0081]    Note that the value x={*} is only relevant for the first sub-graph  500  (as shown in  FIG. 5 ). The subsequent sub-graphs  510 ,  520  do not require this, since the paths through the first sub-graph  500  always represent supply by at least one of the sellers. 
         [0082]    In more general terms, the graph is defined with edges as follows. For completeness, the whole set of rules is given. 
         [0083]    The variable x can take values in the set X where X={x:x ⊂ σ′ and σ′∈S} where S is a collection of allowed sets of sellers and σ′ is an element of this collection S. 
         [0084]    1. Each vertex (i,s,q,x) is connected to (i, s+1, q+q s , x′) for each s&lt;S−1 and q s ≦Q−q for a particular value of x′ except where the edge is omitted as defined below. These are the majority of edges and correspond to the assignment of q s  quantiles of item i to seller s. 
         [0085]    x′=x if the edge is labelled 0, x′=x∪{s+1} otherwise. If the edge is not labelled 0 and x′ as defined is not an element of X, the edge is omitted. 
         [0086]    2. Each vertex in the form (i,S−1,q,x) is connected to (i,S,Q,x′) for 0&lt;i≦I and a particular value of x unless the edge is omitted. These edges correspond to allowing the last seller to supply all remaining quantiles of item i. These edges are labelled (Q−q) and have length B iS (Q−q) 
         [0087]    Again, x′=x if the edge is labelled 0, x′=x∪{S} otherwise. If the edge is not labelled 0 and x′ as defined is not an element of X, the edge is omitted. 
         [0088]    3. (i,S,Q,x) is connected to (i+1,1,q 1 ,x′) or each 0≦i&lt;I and q 1 ≦Q. These correspond to the assignment of q 1  items of the (i+1)-th item to the first seller, and thus represent the linking of the sub-graphs together. These edges have label q 1  and length B (i+1)1 (q 1 ) 
         [0089]    Again, x′=x if the edge is labelled 0, x′=x∪{1} otherwise. If the edge is not labelled 0 and x′ as defined is not an element of X, the edge is omitted. 
         [0090]    4. (i,S,Q,x) is connected to t with a single edge of length 0 for those values of x in S. If x is not in S, the vertex is not connected to t. 
         [0091]    Note that although in the simple example above for which X={*, 1, 2, 3, 12, 13, 23} all allowed values for x (except *) are in S, this is not necessarily the case. For example, if the constraint was that exactly two sellers need to be suppliers, S would be {12, 13, 23} whereas x can take on any of {*, 1, 2, 3, 12, 13, 23}. 
         [0092]    Only paths corresponding to suitable sets for which the sellers comply with the requirement connect the source  400  to the sink  410 . 
         [0093]    A similar formulation can be used to include quantile thresholds in the graph, i.e. thresholds where there are constraints on the number of quantiles supplied by the sellers. 
         [0094]    In this case X is a product of sets of the form {0, 1, 2 . . . T s } for each seller s where T s  is a threshold, for example a maximum or minimum value for that seller. x can then be represented by (x 1 , x 2 , . . . x S ) where x s  for each of s=1, 2 . . . S counts the number of quantiles so far assigned to seller s. 
         [0095]    To implement a minimum, x s ′=min (T s ,x s +q s ) on a path labelled q s , i.e. a path corresponding to supplier s supplying q s  quantiles. x s  then counts up to the minimum requirement. Any seller already meeting this requirement has x s =T s . Then, only those penultimate vertices (I,S,Q,x) are connected to the sink for which x S =T S  for all suppliers. (Note that T s  can take the value 0 for some suppliers). 
         [0096]    To implement a maximum, x s ′=x s +q s . Where x′ S  is greater than T S  the edge is simply omitted. In this case, all vertices (I,S,Q,x) are connected to the sink. 
         [0097]    Thus, by using the above approaches involving the additional vertex label X, some constraints may be incorporated in the graph 
         [0098]    In the examples above that deliver a plurality of solutions, i.e. the k-best solutions, it is possible for a human user of the system to determine a solution that meets constraints even if the constraints are not mathematically formulated. 
         [0099]    It should be noted that the above embodiments are presented purely by way of example. 
         [0100]    Please note that the above description is based on the same number Q for all items. However, in alternative embodiments the number of quantiles Q may vary for each item, in which case it may be represented as Q i  for each i from 1 to I. 
         [0101]    Further, although the above description describes a reverse auction, exactly the same approach can be used for a normal auction for which the goal is to maximise revenue, by simply representing each bid by either by a negative number or by a constant less the cost of each bid. Thus, instead of the sellers in the embodiments described above, the participants may in fact be buyers. 
         [0102]    The representation of the elements may vary. For example, the variable q may represent the percentage of the total supplied, not the number of quantiles. 
         [0103]    Further, the bids may not be bids from external suppliers, but they may instead represent the cost of supply of a resource from an internal source. For example, instead of suppliers, each counterparty in the auction may be a computer server that supplies a particular amount of processing of a particular job and the bids represent the cost of that server supplying that amount of processing power. The auction outcome in this case represents the least expensive use of resources to achieve a particular processing goal. 
         [0104]    For this reason, the term “counterparty” is used to refer to the participants in the auction—these counterparties may be buyers, sellers or even inanimate objects such as computer servers.