Methods for Performing Large Scale Auctions and Online Negotiations

1. Field of the Invention

The present invention relates generally to auctions and, more particularly, auctions over the Internet. The invention is directed to repeated auctions of commodities over a continuous time period.

2. Description of Prior Art

An auction is a method of selling goods through the process of competition. At an auction, buyers, who are referred to as bidders, make competitive bids for goods, and sellers designate goods, which are up for sale to the highest bidder. Sellers who conduct the process of bidding are referred to as auctioneers.

The important principle in auctioning is to allow buyers the initiative of determining the market price through mutual competition, rather than having the price set by the seller. When a seller determines the market price, he is quoting his opinion on the value of goods, and then possibly negotiating with the individual buyer. This is one of the reasons why the auction method has often been used traditionally for auctioning of scarce valuable items, whose exact market prices are difficult to determine. In recent years the techniques of auctioning have begun to become increasingly favorable for commodities transactions on the Internet.

Examples of traditional auctions, performed for centuries, are described below.

1. The Ascending Order or an English Auction: the bidders quote successively higher prices in order to determine the best price for the goods. The goods are sold to the highest bidder. Thus, the order of the bids are ascending in terms of the price level.

The starting bid may be decided either by the auctioneer or by one of the potential buyers. Many variations are possible on the English auction, e.g., providing fixed price advances for each bid, or providing minimums on each advance.

An example of an ascending auction is the Interval Auction. Here, the bidding must be conducted in a certain time interval. This time interval gives bidders reasonable time to consider their bids. For example, it may be pre decided that the auction will start at 3 p.m., and the final decision on the auction will be made at 3:30 p.m. This gives the buyers 30 minutes to ponder and to raise their bids before a final decision is made. The following are the tradeoffs in adjusting the time interval for an auction:

A. If the time-interval is too long, the auction is too slow and the rate of sales will slow down.

If the time-interval is too short, the bidders will not have sufficient time to bid against each other and sufficiently raise the price.

2. The Descending Auction or a Dutch Auction: the auctioneer starts by quoting a high price and successively recites lower bids at regular intervals, until one of the bidders accepts that price. It is important to understand that quoting a good initial price is critical to the success of the descending auction. If the initial price which is quoted is too high, then the auctioneer may spend too much time reciting bids which are not useful. If the initial bid price is too low, then the auctioneer may be unable to obtain the best price for the goods.

3. The Simultaneous Bidding or a Japanese Auction: all bids are made by prospective buyers at the same time. The highest bid is taken to be the price at which the goods are finally sold. This technique is often utilized for the sale of fish in Tokyo.

In simultaneous bidding, it is possible for one buyer to make multiple bids for a given item. For example, a bidder may provide the following three bids for a given item: $50, $20, and $10. If it turns out that the highest bid that any other buyer in the system has made is $18, then the bid for $20 may be awarded to the buyer. This kind of technique reduces the chances that a bidder may overpay because of the lack of knowledge about the bids made by other bidders.

Similarly, in a Haphazard Bidding system, the bidders are unaware of the exact nature of the bids made by others. An example of such a scheme is the written tender scheme in which bids are made in writing and posted to an auction official. The best bid is picked from among these. In a haphazard bidding systems, sometimes considerable temptation may exist for the seller to move the auction to its advantage, since the buyers are not aware of each other's bids.

All the auction methods described above are techniques which are more suited for "one-time" transactions as opposed to repeated transactions of commodities over a continuous time period. Today, typical auction methods proceed by doing auctions at specified times. There exists a need to run continuous auctions over long periods of time on Internet in order to set prices and to sell large scale commodities.

The present invention discloses a technique for conducting auctions at dynamically adjusting time intervals. The time intervals for the auctions are adjusted in such a way that auctions are not so slow, that buyer's timed bids are excluded. At the same time, the auctions are adjusted not to be so fast that bidders do not have time to bid against each other sufficiently. This creates a dynamic adjustment in the trade-offs of the time intervals to perform the bidding.

A method of the present invention performs continuous auctions over a computer network system consisting of multiple clients/buyers which are computer systems connected via a network to a server/seller which is a computer system comprising a CPU, a disk and memory. The seller makes information about the type of sale items, the number of sale items, minimum bid price, and time limits for bids to be submitted. Each buyer responds by entering a bid and such bid's duration within the time limits set by the seller into the auction system through buyers' computer terminals. Additionally, a buyer's bid entry time is saved by the auction system.

To schedule the next auction, the estimated time interval to the next auction decision is determined by selecting premium buyers whose bids are above a certain predefined market premium and calculating a maximum time before which a certain percentage of bids of these premium buyers will not expire. The target queue length is then calculated by using average bid response intervals for the premium bidders and the target queue length. The current queue length is compared to the target queue length in order to readjust the target time at which the next auction winner will be selected.

At least one auction winner, whose bid is within the bid duration is selected through a dynamically adjusted customer selection method. This dynamically adjusted customer selection method finds all buyers whose bids are higher than a predetermined amount set by a seller. The method then computes arrival and defection times of these selected buyers, based on each buyer's bid entry time and the buyer' bid duration, in order to determine these buyers who have the lowest value of the sum of the arrival and defection times. Based on these computations and the buyer's intended purchase volume the winners are declared.

In the present invention, a bid made by a given buyer may be valid across multiple auctions. A bidder not only specifies the price that he is willing to pay, but also the maximum time for which such a bid is valid. For example, assuming that a bid made by a buyer is valid for a period of one hour and that decisions on auctions are made at the rate of one every 15 minutes, then if a buyer's bid expires before that bid is declared as the winner, then this is said to be a defection or an expiry. A bidder is allowed to renew the defection bid. Whenever the bidder renews the defection bid, the new maximum time for which that bid is valid must also be specified.

The method of the present invention improves on the prior art by defining automated time-interval auctions, in which the times at which the auctions are conducted are specific to the information provided by the buyers who make the bids. The information provided by the bidders is as follows:

1. The amount of the bid.

2. The time at which the bid is entered. This information need not be explicitly provided by the bidder. When a bid is submitted, the system clock automatically records the time at which the bid was made.

3. The time duration for which the bid is valid. A bid can be valid across multiple auction sessions.

The time-interval of the auction is determined by the nature of the times at which the bids of the buyers and the sellers in the system are registered. If there are many bidders in the system whose bids are valid for long periods of time, then the time intervals between auctions are kept large. On the other hand, when there are many bidders in the system whose bids are valid for short periods of time, then the time-intervals of the auctions are kept short. This is done in order to reduce the rate of expiring of bids from high bidders. The time interval between successive auctions takes into account both the bids of the buyers as well as that of the sellers.

The process of the present invention includes:

1. determining time intervals between auctions, using the information provided by bidders about the amount of each bid,

2. determining the time at which a buyer entered the system, and

3. determining the time for which each bid is valid.

The automated system of the present invention optimizes the auctioneers' objective function of keeping the buyers bidding against each other, while making sure that the premium bidders do not defect. Thus, the speeds of the auction decisions are dynamically adjusted in correspondence with the times that bidders are willing to wait in the system. Therefore, when there is a large number of bidders in the system who are bidding high, then the rate at which each auction decision is made will be increased by the automated system, otherwise the rate of bidding will be reduced.

FIG. 1 is a graphical depiction of the architecture of the present invention.

FIG. 2 is a graphical depiction of the user interface for the auctioning algorithm of the present invention.

FIG. 3 is a flowchart diagram of the computer implementation of a part of the present invention which allows the auctioneer at the server end and customers at the client end to interact.

FIG. 4 is a flowchart diagram of the computer implementation of a part of the present invention describing the calculation of the intervals for auctioning decisions.

FIG. 5 is a flowchart diagram of the computer implementation of a part of the present invention describing how the actual bids are decided and which sellers are accepted as successful bidders.

The present invention conducts repeated, continuous interval auctions over the Internet. Running repeated, continuous interval auctions is necessary for continuous sale of identical commodity items. For example, it may be desirable to sell a commodity at 3:00 p.m., 3:30 p.m., 4:00 p.m., 4:30 p.m. and so on in 30 minute intervals. In order to sell the commodity at a given time, say 3:30 p.m., bids made by buyers between 3:00 p.m. and 3:30 p.m. will be considered. The buyer making the highest bid between 3:00 and 3:30 p.m. is declared to be the winner.

FIG. 1 shows the hardware architecture of the present invention, which consists of multiple clients 40 communicating with the server 5 over a network 35. The clients 40 are the bidders, and the server 5 is the auctioneer. The server 5 consists of a CPU 10, a disk 15, and the main memory 30. The task of deciding how to adjudicate the received bids is performed by the CPU 10, and the data 20 e.g., bids, resides in the main memory 30. The disk 15 contains the data corresponding to the bids.

FIG. 2 shows, the user interface 200 between each client 40 (FIG. 1) and the server 5 (FIG. 1). The user interface 200 contains six informational components provided to each bidder, who is present at the client end.

1. Best current bids 210 which are in the system, may be specified either exactly or approximately. The auctioneer has the flexibility of choosing any number of best bids to show to the bidders. Approximate specification refers to the fact that only ranges for current bids may be specified. If desired, this feature may even be excluded from the user interface. In the preferred embodiment, bidders are making blind bids, because they do not know what bids other buyers have specified.

2. Buyer's bid 220, specified by the bidder, and equal to the number of dollars which bidder is willing to pay for the item.

3. Response interval for the buyer's bid, indicates the time that the client is willing to wait for his/her bid to remain valid. Thus, this feature is specified by the client in that client's user interface.

4. Estimated interval between the auction decisions 240, specified by the auctioneer or the server, which states the current rate at which the auctions are taking place. This number may change dynamically as the auction progresses. The number is provided to the client since it is useful for the client to decide the nature of his/her response interval depending upon the rate at which the auctions are taking place.

5. Number of items, of a given type, to be bought 250 which a bidder may wish to buy. For example, a bidder may provide an order for a bundle of commodities of a given kind.

6. Minimum bid 260, provided by the auctioneer.

FIG. 3 shows a flowchart of the automated auction software at the server end. The program starts at step 300 and proceeds to the initializing of the variable "Sales", which indicates the total number of sales made so far, to 0 in step 305. In step 310, the seller, the auctioneer at the server end, provides information related to the starting bid price, and a response window relative to the time that the bid is submitted. The starting bid price may be newly entered into the system or calculated from results of previous auctions. Additionally, the seller indicates the estimated time interval to the next auction decision. The auctioneer may provide supplemental information, e.g., the best set of bids which have been submitted so far 210 (FIG. 2).

A potential buyer may enter a bid at any time with an optional desired response interval in step 320. This response interval can be valid across bids. At any given time there may be multiple possible buyers in the system. Thus, the automated computer driven auction software is aware of multiple bids which have been provided to the system. From each bid, the auction software holds three selections of information:

1. the price of the bid,

2. the response interval,

3. the time at which a buyer entered the bid.

The auctioneer uses the information regarding the bids in order to determine the response time for the various buyers in the system, in order to determine when to schedule the next auction, step 330. once it has been determined that an auction should be executed, the auctioneer, in step 340, determines the winning buyer. In making that determination, the auctioneer uses information such as the time of arrival of a bidder into the system, the bidder's estimated response time, and the price of his bid.

FIG. 4 shows steps of a technique for calculating correct time intervals. This recalculation is done at the beginning of each auction interval. However, the present invention does not exclude the possibility of this recalculation being done at periodic time intervals which are larger or smaller than the auction interval. After being started in step 400, the program for calculating correct time intervals determines, in step 420, the number of buyers whose bids are above a certain predefined market premium p*. The buyers who made such bids will be referred to as premium bidders. It is one of the objectives of the present invention to manage the time intervals of the auction in such a way that the bids of as many premium bidders as possible are accepted.

In step 430, the maximum time before which a predefined percentage of the premium bidders will not expire is calculated. Thus, it is preferable to keep the auction fast enough so that most premium bidders are retained, while keeping the auction slow enough so that buyers bid against each other for a sufficient number of times. The arrival rate of the premium bidders in the system is defined by the rate at which bids were made by these people entering into the system. In step 440 the target queue length is calculated by using the average bid response intervals for the premium bidders and the target queue length. Step 450 determines if the true queue length differs from the expected queue length by more than a certain threshold. If it is not, then the program terminates in step 470. Otherwise, the target time at which the next auction decision will be made is readjusted in step 460. The rate at which the readjustment is accomplished, i.e., the speeding up or the slowing down of the target time, is based on the predefined seller interval. Step 470 terminates the program.

FIG. 5 shows the flow of a program for finding the best decisions for auctions. The simple technique of always awarding the highest bidder(s) is one possibility. It may sometimes be desirable to pick a bidder based on the time of that bidder's arrival, the length of that bidder's bids, and the value of that bidder's bid. This ensures that high priced bidders who are about to defect are not lost unnecessarily. After starting the program in step 500, the bid found by the k.sup.th highest bidder is evaluated in step 510. In step 520, this bid is relaxed by a predetermined amount "A".

All the bidders whose bids are higher than "A" are ascertained in step 530. There will be m>=k buyers whose bids are higher than A. The value of m is chosen by the auctioneer, i.e., the server 5 (FIG. 1), and accepted as a system configurable parameter. The arrival and defection times of these m bidders will be used in order to determine whom to declare as the successful bidder(s). In step 540 the sum of the arrival and defection times of each of these m>=k bidders is computed. In step 550 k bidders who have the lowest value of the sum of the arrival and defection times are determined and declared as successful bidders. Priority may also be given to bidders who have bid above a certain predefined volume. The program then terminates in step 560.

The present invention provides an ability of using a combination of several factors, which may be used to determine the winning bidder. Another flexibility provided by this invention is the fact that if a buyer bids above a certain default value, then that buyer's bid is accepted. In the event that the buyer's response window is less than the seller response window, then a way is provided to set a target price for this buyer. In other words, a fixed price is set. If a buyer has a response window which is less than the time at which the next auction decision will be made, then a check is made to determine if the value of the bid was above this fixed price. If such is indeed the case, then the bidder is awarded the commodity.

While the invention has been particularly shown and described with respect to illustrative and preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention which should be limited only by the scope of the appended claims.