Abstract:
The present invention relates to a method of real-time on-line auction processing implemented by a bid server, comprising the following steps: reception of bid orders relating to at least one good or service put up for sale by auction, each bid order being associated with an amount; selection of a bid order, from among the bid orders received whose amount is equal to the highest amount of all the bid orders received. Furthermore, in this method a timeout is triggered whenever the server receives a bid order of an amount strictly greater than the highest amount of all the bid orders received previously and relating to the said good or service; and during the selection step, a bid order is selected randomly from among those received during the timeout period. The invention applies also to two other types of auction methods in which the price of the good or service put up for sale is fixed by the server.

Description:
[0001]     The present invention relates to a method of real-time on-line auction processing.  
         [0002]     More precisely, the invention relates to a method of real-time on-line auction processing implemented by a bid server, of the type comprising the following steps: 
        reception of bid orders relating to a good or service put up for sale by auction, each bid order being associated with an amount;     selection of a bid order, from among the bid orders received whose amount is equal to the highest amount of all the bid orders received.        
 
         [0005]     Such a method is described in document WO 99/27476. It concerns a method of real-time on-line auction processing implemented by a server receiving bid orders relating to a good or service put up for sale by auction. As soon as the server receives a bid order whose amount is strictly greater than the amount of the previous bid selected, the server selects this bid order.  
         [0006]     In this method, when a user bids, the bid order that he sends to the bid server travels via a data transmission network of the Internet type. Now, the Internet network guarantees neither the duration of transmission (variable depending on the users&#39; connection bit rate), nor the proper receipt of the bid order.  
         [0007]     It may therefore happen that the order of receipt of two bid orders by the bid server is the reverse of the order of issue by two different terminals, if the bid orders were issued at very closely spaced instants.  
         [0008]     Now, in the current state of the art, it is impossible to determine which of the two bid orders was issued first since it is very difficult to synchronize the clocks of the terminals used by the users.  
         [0009]     Document WO 99/27476 pinpoints this problem, but simply specifies that the loss of a message and the variable period of transmission of this message are random items that have to be taken into consideration by the users before participating in the bidding.  
         [0010]     This method may therefore create unfairness by favouring the users who have a high bit rate connection.  
         [0011]     An aim of the invention is to remedy this drawback by providing a method of auction processing allowing the bid orders to be processed more equitably, that is to say without systematically disadvantaging the users who benefit from a low bit rate connection only.  
         [0012]     To this end, the subject of the invention is a method of real-time on-line auction processing implemented by a bid server of the aforesaid type, characterized in that: 
        a timeout is triggered whenever the server receives a bid order of an amount strictly greater than the highest amount of all the bid orders received previously and relating to the said good or service; and     during the selection step, a bid order is selected randomly from among those received during the timeout period.        
 
         [0015]     A method of auction processing according to the invention allows equal processing of the bid orders received, regardless of the user and his connection. If two bid orders of the same amount have been received during the timeout period, each bid order has a chance of being selected by the server. Thus, all the users whose bid orders are received by the server during the timeout period are processed on an equal footing, regardless of their type of connection.  
         [0016]     A method of auction processing according to the invention can furthermore comprise one or more of the following characteristics: 
        the putting of the said good or service up for sale is closed at the end of a predetermined sale period, this period being measured from the receipt of the first bid order, the good or service put up for sale then being allotted to the last bid order randomly selected;     the putting of the said good or service up for sale is closed at the end of a predetermined sale period, this period being measured from the receipt of the last bid order, the good or service put up for sale then being allotted to the issuer of the last bid order randomly selected; and     the validity of the bid orders is ensured by a procedure for signing the bid orders using a message authentication code.        
 
         [0020]     The invention also relates, according to a first variant, to a method of real-time on-line auction processing implemented by a bid server, comprising the following steps: 
        (a) fixing by the server of an amount associated with a good or service put up for sale by auction;     (b) reception of bid orders relating to this good or service in respect of an amount corresponding to the amount fixed by the server;     (c) selection of a bid order from among the bid orders received and then return to step (a) for the fixing of a higher amount associated with the good or service put up for sale.        
 
         [0024]     This method is characterized in that 
        a timeout is triggered whenever the server receives a first bid order associated with the amount fixed by the server; and     during the selection step, a bid order is selected randomly from among those received during the timeout period.        
 
         [0027]     According to a particular characteristic of this method, the putting of the said good or service up for sale is closed when no bid order is received by the server following the fixing of a new higher amount, the good or service put up for sale then being allotted to the issuer of the last bid order randomly selected.  
         [0028]     The invention also relates, according to a second variant, to a method of real-time on-line auction processing implemented by a bid server, comprising the following steps: 
        (a) fixing by the server of an amount associated with a good or service put up for sale by auction;     (b) awaiting by the server of reception of a bid order relating to this good or service in respect of an amount corresponding to the amount fixed by the server, and 
            if no bid order is received during a predetermined period, then return to step (a) for the fixing of a lower amount associated with the good or service put up for sale,     otherwise, selection of a bid order from among the bid orders received.    
               
 
         [0033]     This method is characterized in that: 
        a timeout is triggered whenever the server receives a first bid order associated with the amount fixed by the server; and     during the selection step, a bid order is selected randomly from among those received during the timeout period.       
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0036]     The invention will be better understood on reading the description which follows, given merely by way of example and while referring to the appended drawings in which:  
         [0037]      FIG. 1  diagrammatically represents a system adapted for the implementation of a method according to the invention;  
         [0038]      FIG. 2  is a flowchart representing the various steps of a method according to the invention;  
         [0039]      FIG. 3  is a time chart symbolizing a sale by auction using a method according to the invention;  
         [0040]      FIG. 4  is a diagram detailing a method of secure exchanges implemented by the system of  FIG. 1 . 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0041]     The system represented in  FIG. 1  comprises r terminals  100   1 ,  100   2 , . . . ,  100   r , for example personal computers.  
         [0042]     These terminals  100   1 ,  100   2 , . . . ,  100   r  are used by r bidders  102   1 ,  102   2 , . . . ,  102   r  to ascertain the information of the auction in progress and to issue bid orders. To do this, the terminals  100   1 ,  100   2 , . . . ,  100   r  have means for displaying the bid information.  
         [0043]     These terminals  100   1 ,  100   2 , . . . ,  100   r  are linked to a data transmission network  104 , for example the Internet network.  
         [0044]     A bid server  106  is used to manage auction sales, that is to say to send the terminals  100   1 ,  100   2 , . . . ,  100   r  the information relating to the auction in progress (designation of the good, name of the seller, amount of the last bid order selected relating to this good, period remaining, etc.), and to process the bid orders placed by the bidders  102   1 ,  102   2 , . . . ,  102   r . To be recognized by the server  106 , each bidder must register before the start of an auction sale with a trusted third party (or TTP) which manages the server  106 . An individual identifier Id 1 , Id 2 , . . . , Id r , is generated during this registration phase for each terminal by the trusted third party and is then transmitted by the server  106  in a secure manner to each terminal which stores it in a memory area  108   1 ,  108   2 , . . . ,  108   r .  
         [0045]     The method of auction processing represented in  FIG. 2  is implemented by the bid server  106 .  
         [0046]     This method uses two timeouts. A first timeout, individual to the invention, of period D of the order of a few seconds, resolves cases of conflicts between bid orders received at very closely spaced instants. The role of this timeout will be specified later. The second timeout of period D E , which varies from a few minutes to a few tens of minutes, characterizes the limit period after which the server  106  closes the bid if it has not received any new bid order since the previous one.  
         [0047]     During a step  200 , the server  106  initializes the amount of an object put up for sale at a value M 0 . In what follows, the current amount of the bid will be denoted M. The server  106  also fixes the period D E  and the period D of the two timeouts.  
         [0048]     During a step  202 , the server  106  continuously tests whether one of the two timeouts has elapsed and whether it receives a new bid order.  
         [0049]     If a new bid order has been received during step  202 , the server  106  tests the validity of this bid order during a step  204 . The validity of the bid orders is ensured by a procedure for signing the bid orders using a message authentication code. This procedure will be described later with reference to  FIG. 4 .  
         [0050]     If the bid order has been validated during step  204 , the server S triggers the timeout of period D E  and compares the value of the amount of the new bid order with the value M of the current bid during a step  206 .  
         [0051]     Otherwise, we go to step  202 .  
         [0052]     If during step  206 , the server  106  notes that the amount of the new bid order is strictly greater than the current bid M, then the server triggers the timeout of period D during a step  208  and fixes the value of the current amount M of the bid at the amount of the new bid order. It then also initializes a variable Datum_bid. This variable Datum_bid keeps in memory the identifiers of all the bidders who have placed a bid order whose amount is equal to M, that is to say to the largest amount of all the bid orders received.  
         [0053]     During a step  210  following step  208 , the server  106  issues the updated information relating to the bid to all the terminals  100   1 , . . . ,  100   r . This information includes among other things the current amount M of the bid, and possibly the identifier of the user whose bid order is temporarily selected.  
         [0054]     After step  210 , we return to step  202 .  
         [0055]     During step  206 , if the server  106  notes that the amount of the new bid order is equal to the current bid M, it then updates the variable Datum_bid in a step  212  by adding the identifier of the user who has just placed the new bid order. We then go to step  210 .  
         [0056]     If during step  206 , the server  106  notes that the amount of the new bid order is strictly lower than the amount M of the current bid, we return to step  202 .  
         [0057]     If the bid order has not been validated during step  204 , we return to step  202 .  
         [0058]     If during step  202  the timeout of the server  106  corresponding to the period D has elapsed, it then chooses randomly in the course of a step  214 , one of the users whose identifier is stored in the variable Datum_bid, that is to say one of the users who has issued a bid order of amount M, received during the timeout period D. In practice, this random selection is implemented by virtue of conventional pseudo-random means of selection. We then go to step  210 .  
         [0059]     If during step  202 , the server  106  detects that the timeout relating to the variable D E  has elapsed, it then issues, during a step  216 , the final information relating to the bid to all the terminals and closes the auction sale. This information includes among other things the identifier of the winner as well as the amount of the final bid.  
         [0060]      FIG. 3  represents an example of an auction sale using the method described above and in the course of which two bidders  102   i  and  102   j  issue bid orders with regard to the same object.  
         [0061]     The two bidders  102   i  et  102   j  follow the auction in real time with the aid of the two terminals  100   i  and  100   j .  
         [0062]     The terminals  100   i  and  100   j  being remote from the server  106 , there is a variable duration of transmission of the information to the server  106  and in particular of the bid orders. The instant at which a user places his bid order is therefore separate from the instant at which the server  106  receives this bid order. The duration between these two instants may vary over time as a function of the congestion of the network and also varies as a function of each user&#39;s connection bit rate.  
         [0063]     Let M i   1  be the amount of a first bid order issued by the user  102   i  at an instant T 1 . The bid server  106  receives this bid order at the instant t′ 1 . According to the method described above, the server  106  then triggers the timeout of period D at the instant t′ 1 . When the timeout has elapsed, and in the absence of other bid orders received by the bid server  106  in the course of this period D, the server  106  selects, at the instant t″ 1 , the bid order from the bidder  102   i  for an amount M i   1 . The instant t″ 1 , is equal to t′ 1 +D.  
         [0064]     The server  106  thereafter receives at the instant t′ 2  a bid order of amount M j   1  issued at the instant t 2  by the user  102   j , M j   1  being strictly greater than M i   1 . Thereafter, the server  106  allots the bid to the user  102   j  at the instant t″ 2 =t′ 2 +D.  
         [0065]     At the instant t 3 , the bidder  102   i  issues a bid order of amount M i   2 . This bid order will be received by the server  106  at the instant t′ 3    
         [0066]     The bidder  102   j  thereafter issues a bid order of amount M j   2  equal to M i   2  at the instant t 4  greater than t 3 . This bid order is received by the server  106  at the instant t′ 4  less than the instant t′ 3 , thereby triggering the timeout of period D. The typical case then transpires in which two bid orders of identical amounts have been placed by two bidders, and in which the order of receipt by the server S of the two bid orders is the reverse order to the actual order of issue by the two users  102   i  and  102   j .  
         [0067]     According to the method described above, on completion of the timeout of period D, that is to say at the instant t″ 4 , the server  106  determines in a random manner which of the two users  102   i  and  102   j  will be allotted the bid at the amount M j   2 =M i   2 .  
         [0068]      FIG. 4  describes the way in which the exchanges between the bid server  106  and the terminals  100   1 , . . . ,  100   r  of the users are made secure.  
         [0069]     The server is managed by a trusted third party and possesses a pair of asymmetric keys PK and SK in which PK is a public key and SK is a private key which it keeps secret and which allows it to decrypt the messages encrypted with PK. All the terminals  100   1 , . . . ,  100   r  participating in a sale by auction therefore have knowledge of the key PK.  
         [0070]     The server also possesses a master key MK that it keeps secret.  
         [0071]     During a step  400 , the trusted third party generates for each user the identifiers Id 1 , Id 2 , . . . , Id r  as well as a secret key K 1 , K 2 , . . . , K r . The secret keys K 1 , K 2 , . . . , K r  derive from the master key MK and from the identifiers Id 1 , Id 2 , . . . , Id r  with the aid of a function F (for example the function SHA): K i =F(MK, Id i ).  
         [0072]     These identifiers Id 1 , Id 2 , . . . , Id r  as well as these keys K 1 , K 2 , . . . , K r  are thereafter sent by the server  106  to each terminal  100   1 , . . . , 100   r  concerned.  
         [0073]     During a step  402 , the terminals receive and store the identifiers Id 1 , Id 2 , . . . , Id r  as well as the keys K 1 , K 2 , . . . , K r  in the memory areas  108   1 ,  108   2 , . . . ,  108   r .  
         [0074]     The auction sale begins with a step  404  during which the server generates a message containing the current amount M of the object put up for sale by auction as well as its identifier O Id . This message is signed electronically by the bid server with the aid of its private key SK.  
         [0075]     This message is thereafter issued to all the terminals of the users participating in the auction relating to the object put up for sale.  
         [0076]     After receipt of this message, each terminal verifies the signature in a step  406 , using the public key PK.  
         [0077]     If a user  102   i  wishes to bid, he creates, during a step  408 , a message containing among other things an amount M′ of his new bid order, his own identifier Id i , as well as the identifier O Id  of the object put up for sale. A message authentication code is generated with the aid of these three items of information and of the secret key K i  that he possesses: MAC Ki (O id ,M′,Id i ). This message authentication code is an electronic seal produced by an algorithm using the derived secret key K i  and making it possible to guarantee the integrity of the message on arrival. All these items of information are thereafter sent to the server  106 .  
         [0078]     During a step  410 , the server  106 , with the aid of the identifier Id i  of the user who has bid, generates the secret key K i  of the user as well as the message authentication code.  
         [0079]     The comparison of the authentication code thus obtained with the authentication code received allows it to validate or otherwise the bid order of the user  102   i .  
         [0080]     During a step  412 , the bid server  106  updates the information relating to the current bid, by following the method of the invention.  
         [0081]     Thereafter, we go to step  404  again.  
         [0082]     It is clearly apparent that the method described above allows equal processing of the bid orders received, regardless of the type of connection of the users.  
         [0083]     It will be noted that the invention is not limited to the bidding system example which has been described, in particular in conjunction with  FIG. 3 , and in which the bidders raise the price of the object put up for sale.  
         [0084]     The invention applies equally to a system in which it is the server that raises the price of the object put up for sale. The server fixes a price at the start as in the previous example. The bidders who accept the price then respond and a timeout is triggered when the server receives the first acceptance of the price from a bidder. The server thereafter randomly selects a bidder who has accepted the price from among the responses received during the timeout period, then fixes a new higher price, doing so until it no longer receives any response accepting the new price in which case it allots the good put up for sale to the last bidder randomly selected.  
         [0085]     The invention applies also to another bidding system in which the server initially proposes a high reserve price and waits a predetermined period for at least one bidder to accept this offer. When it receives an acceptance from a bidder, the server triggers a timeout and it then randomly selects a bidder who has accepted the price from among those that responded during the timeout period. If the server receives no response during the predetermined period, it lowers the price, doing so until one bidder at least accepts the price or until the end of the auction if nobody accepts the lowest price proposed by the server.