Abstract:
A set of auctions is divided into groups of auctions such that the chances of finding interesting auctions across the groups of auctions by a bidder are minimized. These groups of auctions can scheduled such that the chances of auctions of interest to bidders (and prospective bidders) held in the same time slot or are either minimised or maximized.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to auctions and relates particularly, though not exclusively, to auctions conducted online using the Internet, and the scheduling of such auctions.  
         BACKGROUND  
         [0002]    An auction is a public sale at which property or goods are sold to the highest bidder. In this respect, an auction can be thought of as a market mechanism for determining the price of an item. Usually, the item is sold to the highest bidder. Auctions are effectively defined by a predetermined set of rules governing the auction mechanism, the product or service that is being auctioned, and by other various parameters of the auction such as reserve prices, and duration etc.  
           [0003]    In case of Internet auctions, the auctioneer communicates or publicises the progress of the auction (the current leading bids, anticipated closing time, etc) via the Internet, typically from a particular Web site.  
           [0004]    One of the issues facing online auctioneers is the ability to effectively schedule when auctions are conducted. Wellman et al (Michael P Wellman and Peter R Wurman,  Real Time Issues in Internet Auctions , First IEEE Workshop on Dependable and Real-time E-commerce Systems (DARE-98), Denver, Colo., United States, June 1988) have studied auction scheduling techniques that balance the load on multiple servers.  
           [0005]    In the case of Internet auctions, an auctioneer typically conducts a large number of auctions during a given period of time. Scheduling a large number of auctions at once causes the following problems: (i) high levels of network traffic to the auction server; and (ii) reduced participation as users&#39; responsiveness is limited by the need to browse and/or search through a large number of auctions at a time.  
           [0006]    In view of the above, a need clearly exists for an improved manner of scheduling auctions that at least attempts to address one or more limitations of the prior art.  
         SUMMARY  
         [0007]    Clear and apparent advantages are available by appropriately scheduling auctions. In particular, it is recognised that auctions are advantageously scheduled in a manner that increases the average chances of auctions of interest to a bidder (and prospective bidder) being scheduled at the same time (or same time slot). In other words, it is desirable that the chances of finding interesting auctions across the groups of auctions by a bidder are minimized.  
           [0008]    Appropriate grouping of auctions allows auctions to be scheduled during non-overlapping or at most partially overlapping periods of time. Appropriate scheduling reduces the participation cost of bidders. That is, once appropriate groups are determined, the resulting groups are used to suitably schedule the auctions based on these identified groups.  
           [0009]    It is recognised that auctions can be desirably clustered or grouped into groups for scheduling by representing auctions as data that can be interpreted by cluster analysis techniques to form non-hierarchical groups of auctions. Division of auctions into groups is performed based on data that represents bidders&#39; respective interests in various auctions. A predetermined number of auction groups can be specified. Alternatively, a lower bound on the fraction of bidders interested in multiple auctions from a particular group of auctions can be specified. A hybrid approach, for determining the number of auction groups, can also be adopted. 
       
    
    
     DESCRIPTION OF DRAWINGS  
       [0010]    [0010]FIG. 1 is a schematic representation of a system, involving two modules (a data preparation module and a cluster module), used for grouping auctions in accordance with the techniques described herein.  
         [0011]    [0011]FIG. 2 is a schematic representation of the data preparation module used in the system of FIG. 1.  
         [0012]    [0012]FIG. 3 is a schematic representation of a relationship computation module that is part of the data preparation module of the system of FIG. 1.  
         [0013]    [0013]FIG. 4 is a flowchart that represents the steps performed by the cluster module of the system of FIG. 1.  
         [0014]    [0014]FIG. 5 is a schematic representation of a computer system suitable for performing the described techniques provided by the system of FIG. 1. 
     
    
     DETAILED DESCRIPTION  
       [0015]    A method, computer system and computer software are described for scheduling auctions using an approach that involves appropriately grouping the auctions to be scheduled.  
         [0016]    In essence, determining an appropriate grouping of auctions involves finding clusters in a data set with respect to a given relation. Each of the auctions is considered as a data point (for example, in the set {a 1 , a 2 , . . . a n }), and auction a i  is related to auction a j . This relationship defined between auction pairs (a i , a j ) depends on the objective of the proposed auction grouping: it may be a symmetric or asymmetric relationship. The objective is to group auctions such that for any given bidder, the chances of finding interesting auctions in two or more different groups of auctions are minimized. To this end, a relation that reflects the average interest that a bidder interested in auction a i  has in auction a j  is considered. However, note that this relation is asymmetric (that is, R(a i , a j ) g R(a j , a i )). Techniques for estimating this relation are described in the section entitled “Relation computation module”.  
         [0017]    A technique for solving the data clustering problem noted above is addressed in two steps. In a first step, data points (corresponding with auctions) are evaluated for their ability to form a cluster. This evaluation is referred to as the “lead value” of the data point. One way of computing the lead value of an auction involves determining the number of users interested in the auction. A second step consists of actually determining proposed auction grouping, given the lead values of the data points and the relations between them.  
         [0018]    The two-step process referred to the above is implemented by respective modules. The first module, referred to as the data preparation module, converts data relating to auctions and users (that is, profiles and bidding history) into data used in clustering analysis. The second module, referred to as the clustering module, uses this data to cluster the auctions.  
         [0019]    [0019]FIG. 1 schematically represents these two modules, and the process associated with these modules. In overview, auction data  110  and user profile/history data  120  are both input to the data preparation module  130 . The data preparation module  130  outputs cluster data  140 , which is then input to the cluster module  150 . Based on the cluster data  140 , the cluster module  150  provides a group of auctions  160  that can be used for scheduling purposes.  
         [0020]    These two modules are described in detail below under respective sections entitled “data preparation module” and “clustering module”.  
         [0021]    Data Preparation Module  
         [0022]    The first module uses the following three sub-modules (namely an interest prediction module, a relationship computation module and a lead value computation module):  
         [0023]    1. Interest prediction module: The interest prediction module maps an auction a i  to an interest vector a i  of dimension equal to the number of m bidders. Each element of the interest vector as represents the degree of interest of the corresponding bidder in the respective auction a i . Accordingly, the interest prediction module produces a set of interest vectors {a 1 , a 2 , . . . a N }, members of which correspond with respective members of the set of auctions {a 1 , a 2 , . . . a N }.  
         [0024]    This interest prediction module outputs a binary interest vector a i  where the i-th element (corresponding with a respective bidder) is: (i) 1 if the i-th bidder has bid at least once for the item to be auctioned in auction a i  (that is, it is inferred that the bidder is interested in this auction a i : the bidder has not cast a dummy bid); and is (ii) 0 otherwise. A more sophisticated version of this interest prediction module outputs an interest vector a i  containing numbers in the range [ 0 , 1 ] that reflect the extent of bidders&#39; interests in auction items.  
         [0025]    2. Relationship computation module: The relationship computation module computes the relationship between respective pair of auctions a i  and a j  and returns a relationship matrix R that specifies the average correlation in interest between all pairs of auctions a i  and a j . That is, the ij-th element r ij  of the relationship matrix R represents the average interest of a bidder interested in auction a i  towards auction a j .  
         [0026]    Assuming that the auctions {a 1 , a 2 , . . . a N } are represented by binary interest vectors {a 1 , a 2 , . . . a N } generated in the interest prediction module, the relationship computation module computes r ij  as |a i ·a j |/|a i |, where |a| is the sum of elements of the vector a. This expression for r ij  can also be used to compute the relationship matrix R for non-binary interest vectors {a 1 , a 2 , . . . a N } (for example, vectors having elements that are numbers in the range [ 0 , 1 ]). More sophisticated computations can also be used. For example, r ij  could be |a i ·a j |/|a i | where the intersection is a fuzzy intersection.  
         [0027]    3. Lead value computation module: Each auction a i  is evaluated for its ability to lead a cluster. Various measures that reflect an auction&#39;s ability to lead a cluster can be used. For example, the lead value of an auction can be the number of users interested in the item that is being auctioned. That is, the lead value of auction a i  is |a i |. Alternatively, other indicators or measures can be used. For example, the lead value of an auction could be the profit earned by selling the item at the reserved price of the item. This lead value is used in the clustering module described below.  
         [0028]    [0028]FIG. 2 schematically represents the operation of the data preparation module  130  as described above with reference to FIG. 1. In summary, the auction  210  and user profile/history data  220  are input to the interest prediction module  230  to produce auction interest vector data  240 . This auction interest vector data  240  is supplied both to the relationship computation module  250  and the lead value computation module  260 . The lead value computation module  250  computes lead values  280  from the auction interest vector data  240 , with input from the relationship computation module  250 . The relationship computation module  250  computes auction relationship matrix data  270  from the auction interest vector data  240 .  
         [0029]    [0029]FIG. 3 schematically represents the operation of the relationship computation module  250  as described above with reference to FIG. 2. Values as a i    310  and a j    320  are supplied for respective auctions associated with indices i and j. These values are used to calculate the expression |a i ·a j |/|a i |  330 , which is used in determining the auction relationship matrix r ij    340 .  
         [0030]    Clustering Module  
         [0031]    The clustering problem under consideration is first defined before describing the clustering method per se.  
         [0032]    The set of auctions A={a 1 , a 2 , . . . a N } represents the auctions to be scheduled.  
         [0033]    The set of interest vectors D={a 1 , a 2 , . . . a N } is formed with respect to m bidders That is, each interest vector a i  is an m-dimensional vector in which elements of interest vector a i , represent the extent of interest of bidders in the i-th auction a i .  
         [0034]    The relationship matrix R represents the relation between any two auctions.  
         [0035]    Partition P={C i } is a set of non-empty disjoint sets C i , of the set of auctions A that represents a way in which the set of auctions A can be clustered.  
         [0036]    The set of lead values L:D→R (R is the set of all real numbers). That is, L maps each auction to a real number that represents its lead value.  
         [0037]    The number η is a threshold value specified by the user.  
         [0038]    The objective is to find a partition {C i } (that is, a set of non-empty disjoint sets) of the set of auctions A satisfying the following conditions:  
         [0039]    1. For all pairs of auctions a i , a m  that are members of a cluster C i  of partition {C i }, all corresponding elements r lm  of R is greater than η; and  
         [0040]    2. The cardinality of {C i } (that is, the number of member sets of {C i }) is as small as possible.  
         [0041]    In other words, the task is to find as few clusters as possible such that for every pair (a i , a m ) of auctions in each of the clusters, the average interest of a bidder interested in action a l towards a m  is greater than η.  
         [0042]    The described techniques provide a heuristic algorithm that results in a relatively close approximation to the problem described above.  
         [0043]    Proposed Algorithm  
         [0044]    [0044]FIG. 4 schematically represents the process involved in forming clusters C i  and a partition of the set of auctions A. Relationship and lead value data is first determined in step  405 . The auctions are sorted in step  410  according to their lead values, to provide sorted indices {n 1 , n 2 , . . . n N } in descending order of their lead values. In step  415 , the set S of cluster representatives and the array B of vectors containing the indices of auctions in the clusters are initialized to {a n1 } and [(n 1 )] respectively, and, i and K are initialized to 2 and 1 respectively.  
         [0045]    At step  420 , it is checked whether i is less than or equal to N. If the value of i is less than N, the value x j  is computed for each value of j from 1 to K in step  425  as follows: 
         if (| a   ni   ·s   j   |&gt;h   j ·η)  x   j   =R ( a   ni   , s   j ); 
         else  x   j =infinity; 
         [0046]    In the above computation:  
         [0047]    s j  represents the j-th cluster representative in the set S,  
         [0048]    h j  represents the maximum number of bidders interested in any of the auctions in the j-th cluster, and  
         [0049]    the relation R between any two auction R(a,b) is given by |a·b|/|a|.  
         [0050]    It is then determined, in step  430 , if the minimum value of x j  is greater than a predetermined minimum threshold value η.  
         [0051]    If the minimum value of x j  exceeds this predetermined minimum η in step  430 , then b m  (b m  is the m-th vector in array B) and S m  are updated in step  440  as below, where m is the value of the index that corresponds to the minimum value of x j : 
           b   m =( b   m   , n   i ), and 
           s   m =∩ l   a   ml   
         [0052]    where, a ml  is the l-th auction in the m-th cluster. That is, s m  is the intersection of all auctions in the j-th cluster.  
         [0053]    If the minimum value of x j  does not exceed this predetermined minimum η, then sets S and B are updated, in step  435 , with new values according to the relation S={S, a ni } and B={B, (ni)}. Also, K is incremented to K+1.  
         [0054]    Irrespective of the minimum value of x j , the index i is incremented to i+1, in step  445 , and the process repeats from step  420 .  
         [0055]    Steps  425  to  445  are repeatedly performed for incrementing values of i, until i is greater than N. In this case, the process of steps  425  to  445  is stopped, and the end results for sets B and S obtained in step  450 .  
         [0056]    In summary, the auction with the highest lead value is made a member of the first cluster. Then, each of the remaining auctions, taken in the descending order of their lead values, is assigned to either an existing cluster or a new cluster. An auction is assigned to the cluster corresponding to the nearest among the representatives of the clusters if the auction&#39;s relationship with the nearest representative is greater than a predetermined threshold. An auction is made a representative of a new cluster if the auction&#39;s relationship with members of each of the existing clusters is less than the given threshold value.  
         [0057]    A cluster representative can be considered to be the centroid of the cluster and is found by taking the commonality of all the auctions in the cluster. If auctions are represented by binary vectors, then the cluster representative is the vector representing the set of users who are interested in all the auctions in the cluster. A similar fuzzy intersection can be used in the case in which the auctions are represented by non-binary vectors.  
         [0058]    The following observations show that all clusters obtained using the described techniques satisfy the first condition above (that is, for a l , a m εC i , R(a l , a m )&gt;η).  
         [0059]    Let C={c 1 , c 2 , . . . c m }, in which c is a set of binary vectors, and let c represent the vector resulting from a bit-wise AND operation on all the vectors in C. Then, for any binary vector a, |a·c|/|a|&lt;|a·c i |/|a|, for i=1, . . . m.  
         [0060]    As a consequence, if |a·c|/|a|&gt;η, then |a·c i |/|a|&gt;η, for i=1, . . . m.  
         [0061]    Let the set C be such that R(c i , c j )=|c i ·c j |/|ci|&gt;η for all i, j. Then, the set C′={c 1 , c 2 , . . . c m , a} retains the above property (that is R(c i , c j )=|c i ·c j |/|c i |&gt;η for all c i , c j εC′.), if |a·c|≧max |c i |·η. This is so, because R(c i , a)=|a·c i |/|c i |≧η for all i.  
         [0062]    Pseudo-Code  
         [0063]    A pseudo-code representation of described technique is given directly below. In the pseudo-code, text following double slash marks (that is, “//”) denotes comments that are not part of the pseudo-code, but serve to provide explanatory explanation to the pseudo-code.  
         [0064]    1. Sort auctions in decreasing order of their lead values. Let the sorted index set be I={n 1 , n 2 , . . . n N }.  
         [0065]    2. Initialize S, the set of cluster representatives. Let B be an array of vectors of variable length whose elements represent the indices of auctions in C i . Denote the i-th element (vector) of B by b i  and the j-th element of S by s j . Let B=[(n 1 )], S={s 1 }={a n1 }, and i=2.  
         [0066]    3. Build S.  
                                                                                                                                                 while i &lt; N, {           for j = 1 to |S|, // |S| − cardinality of S                if (|a ni  · s j | &gt; h j  · η)           // h j  represents the maximum number of bidders interested           // in any of the auctions in j th  cluster                x j  = R(a ni , s j );                else x j  = infinity,                if (min x j  &gt; η) {                m = arg min x j ;           b m  = (b m , n i );           isNewMember = false;           s m  = representative(a m ); // finds a new representative of a m                  }                else   {                A = [A , (n i )];           S = S ∪ {a ni };           }                i = i + 1;           }                      
 
         [0067]    Computer Hardware and Software  
         [0068]    [0068]FIG. 5 is a schematic representation of a computer system  500  that can be used to perform steps in a process which implements the techniques described herein. The computer system  500  is provided for executing computer software that is programmed to assist in performing the described techniques. This computer software executes under a suitable operating system installed on the computer system  500 .  
         [0069]    The computer software involves a set of programmed logic instructions that are able to be interpreted by the computer system  500  for instructing the computer system  500  to perform predetermined functions specified by those instructions. The computer software can be an expression recorded in any language, code or notation, comprising a set of instructions intended to cause a compatible information processing system to perform particular functions, either directly or after conversion to another language, code or notation.  
         [0070]    The computer software is programmed by a computer program comprising statements in an appropriate computer language. The computer program is processed using a compiler into computer software that has a binary format suitable for execution by the operating system. The computer software is programmed in a manner that involves various software components, or code means, that perform particular steps in the process of the described techniques.  
         [0071]    The components of the computer system  500  include: a computer  520 , input devices  510 ,  515  and video display  570 . The computer  520  includes: processor  540 , memory module  550 , input/output (I/O) interfaces  560 ,  565 , video interface  545 , and storage device  555 .  
         [0072]    The processor  540  is a central processing unit (CPU) that executes the operating system and the computer software executing under the operating system. The memory module  550  includes random access memory (RAM) and read-only memory (ROM), and is used under direction of the processor  540 .  
         [0073]    The video interface  545  is connected to video display  590  and provides video signals for display on the video display  570 . User input to operate the computer  530  is provided from input devices  510 ,  515  consisting of keyboard  510  and mouse  515 . The storage device  555  can include a disk drive or any other suitable non-volatile storage medium. Each of the components of the computer  520  is connected to a bus  530  that includes data, address, and control buses, to allow these components to communicate with each other via the bus  530 .  
         [0074]    The computer system  500  can be connected to one or more other similar computers via a input/output (I/O) interface  565  using a communication channel  585  to a network  580 , represented as the Internet.  
         [0075]    The computer software program may be provided as a computer program product, and recorded on a portable storage medium. In this case the computer software program is accessed by the computer system  500  from the storage device  562 . Alternatively, the computer software can be accessed directly from the network  580  by the computer  520 . In either case, a user can interact with the computer system  500  using the keyboard  510  and mouse  515  to operate the programmed computer software executing on the computer  520 .  
         [0076]    The computer system  500  is described for illustrative purposes: other configurations or types of computer systems can be equally well used to implement the described techniques. The foregoing is only an example of a particular type of computer system suitable for implementing the described techniques.  
       CONCLUSION  
       [0077]    A method, system and computer software are each described above for grouping auctions for the purposes of appropriately scheduling the grouped auctions.  
         [0078]    In the above described example, auction data is assumed to relate only to auctioned items, and user data is assumed to relate only to items for which the user has bid in the past. However, more complex application of the described techniques is possible, with appropriate modification to the various described processes involved in the two modules.  
         [0079]    For example, in the case of user data, greater weight can be attached to items that have been actually bought by a user, compared to items for which only bids have been received from a user.  
         [0080]    It is understood that various alterations and modifications can be made to the techniques and arrangements described herein, as would be apparent to one skilled in the relevant art.