HK1082065A - Displaying paid search listings in proportion to advertiser spending - Google Patents

Description

Displaying paid search listings in proportion to advertiser spending

This patent application is filed as required by U.S. 35 u.s.c § 119(e) on the filing date of U.S. provisional patent application No.60/369,460, filed on 1/4/2002, the contents of which are incorporated herein by reference in their entirety.

Background

The pay for location (pay-for-placement) search engine operates just like the online version of the Phoneyellow Page: the user conducts a search and the system displays a paid advertiser listing (listing) that matches the user's query. Because of the limited space available on the screen, users typically see only a small portion of the catalog that matches their query. Thus, in order to build a viable system, the search engine provider needs to decide how often each catalog is displayed, how much is charged, and the order in which the various catalogs should appear.

The current state of the art is the search engine for Overture, which can be selected fromwww.overture.comAnd (4) obtaining. Overture uses a scheme called bid-for-rank in which it charges the individual advertisers on click-through and subscription lists based on how much each advertiser is willing to pay per click. The advertiser may place his desired price with a minimum bid of 5 cents per click. Many web sites display Overture search results and there is a strong incentive to get near the top since each web site displays a different number of search results from the top of the list. The highest bidding advertiser always occurs, and as its bid decreases, the advertiser occurs less frequently. Ideally, the advertiser offering the highest quality of service bids the highest and appears at the top of the list. In practice, however, the system is almost impossible to operate as well. The above solution is simple in principle, but it has many problems that hinder both the user and the advertiser.

From the user's perspective, the problem is that the bid ranking scheme may result in irrelevant, unwanted search listings near the top. Advertisers have full control over the order in which their catalogs appear, and smart advertisers can take advantage of this freedom to allow users to spend money and display themselves free of charge. For example, suppose there is an advertiser selling pet ferrets. The advertiser will appear in the case of very specific search words like "ferret" and "pet ferret" as well as in the case of more common words like "pet". When a user searches for "pet ferrets," it is reasonable for the ferret advertiser to appear at the top of the list, because the user is almost certainly looking for what the advertiser sells. But for more common words like "pet" the ferret advertiser should not appear near the top. The user entering "pet" is more likely to be looking for a dog or cat, rather than a ferret.

Unfortunately, if the ferret advertiser is clever, he will create such a catalog as "special stick pet ferret! Ultra-cheap! ". He may be willing to give this catalog a very high price-a price that takes him to the top of the list-because he knows that when the user clicks on the catalog, this user sees this clearly about ferrets. There is enough information in the catalog that the advertiser is likely to make a deal. In a bid ranking system, advertisers do not pay for being at the top of a listing; the advertiser only pays if the user actually clicks on his catalog. This catalog is so specific that it is clicked only when the user is interested in ferrets, so there is little risk to the advertiser even if the catalog appears in the context of words such as "pets". Thus, the first search result for "pets" is a catalog related to only a few users. For others, this catalog is not useful and the overall search experience is poor. The ferret phenomenon is common in place paid search engines. Yellow pages are not plagued by this problem because advertisers are forced to pay based on the size of the page they occupy.

A problem with the bid ranking system from the advertiser's perspective is that it is complex and it is difficult for the advertiser to know what he obtained. When an advertiser bids for a particular rank, he cannot calculate in advance how many clicks he is likely to get, or how much money he is likely to spend, or whether it is likely to receive a higher revenue on some other rank. He cannot even determine whether he can get the rank he wants because another advertiser might give a higher price behind him. If the advertiser budget is fixed, he must constantly monitor his spending to ensure that the budget is not exceeded, while still keeping his bid high enough to obtain the maximum possible number of clicks. Typically, he must deal with all of these uncertainties for 50 or 100 different search terms, each of which has its own bid.

For example, assume that an advertiser now bids $ 1.00 for the search term "fresh fish" to obtain the rank 2 position. He can keep his position, either increase his bid to $ 1.20 to advance to position 1, or decrease his bid to $ 0.80 to lower to position 3. In order to make the above decision, he needs to know how many clicks he is likely to get at each of the above three ranks. He is almost impossible to get this information. Indeed, under the current state of the art, search engine providers cannot even certainly say: he will get more clicks at rank 1 than rank 3. Even if an advertiser determines that it is necessary to bid on position 1, there is no guarantee that one of the other advertisers will not bid more than he after a few hours. Or, it is also possible that the advertiser might bid to position 1, finding that he paid too much after a few days, because the advertiser has abandoned behind him. The advertiser must constantly monitor his bids and positions to ensure that he obtains what he wants without paying too much. The current state of the art is to use electronic bidding agents to track bids. Examples are as follows:www.gotoast.com、 www.did-it.comandwww.pay-per-click-bid-managers.com. However, none of these examples perform well enough because they only run periodically, and they often do not get the required information from the search engine provider, such as how many clicks the advertiser might get at different rankings.

If the advertiser's budget is fixed, he must also constantly monitor his spending to ensure that he will be able to meet his budget in the future. Assume, for example, that the advertiser has $ 1000 available for payment in the next month. If he sets his bid to $ 1.00 and 50 users click on his catalog the first day, he must depress his bid because his payout rate is too high. At $ 50/day he will spend all his budget before the end of the month. Conversely, if only 10 users click on his catalog the first day, he must raise his bid because his payout rate is too low. The interaction between bids and budgets is complex and difficult to fit without constant adjustment. This will also lead to poor search results because the user sees not the best most relevant advertisers, but only those that are not currently beyond budget.

All of these problems become more complicated when advertisers bid on multiple search terms. Each word gets a different number of searches and clicks and requires a different bid. The advertiser must allocate his funds among the various search terms in some manner that optimizes his overall revenue. There is currently no good tool to help advertisers do this, nor is even the best bidding agent attempting to raise or lower bids among multiple words to match a fixed budget.

Many advertisers prefer to use an alternative to such a system. This elaborate bidding structure requires very much micro-management and it involves only two issues of practical interest to the advertiser: how much he pays and what rewards he can get. The advertiser wants the search engine provider to tell him: spending $ 1000, he can buy 1000 clicks in the next month; or he spends twice as much money to get twice as many clicks, or half as much money to get half as many clicks. This model is more consistent with other advertising methods, like yellow pages and internet banner advertisements. When the information is refined into spending and hits, it is clear that the concept of whole bids and rankings is no longer necessary. The advertiser is not really concerned about his ranking in the search result list. He is concerned about how many clicks he can get after paying money and how many of these clicks will translate into sales. Ideally, he could make a purchasing decision based solely on such information-how much money to pay, and how many clicks to get in return-leaving all other detailed questions to the search engine provider as to when and where his catalog occurred. Systems based on this idea provide the search engine provider with sufficient freedom to decide which catalogs should be displayed in response to the user's query, thus solving the ferret problem while being much simpler for advertisers.

Disclosure of Invention

The invention maintains the optimal characteristics of the bidding ranking scheme, and simultaneously eliminates the bidding and ranking: auctions are used to automatically set prices and allow advertisers to pick up the search terms they should appear. In addition, these embodiments automatically optimize the payout of each advertiser between the search terms he presents, thus eliminating the need for a bidding agent.

The idea behind these embodiments is simple. Each advertiser decides how much he wants to spend on a search term and the search provider displays the list of advertisers in proportion to the amount of money spent by the respective advertiser. Suppose there are N advertisers competing for space on a search results page displaying M catalogs. If there are T searches, the search provider has TM total impressions (impressions) distributed among the advertisers. One impression is the display of a search listing among the search results presented to the searcher. If the advertiser is willing to spend a_iHe then gets the number of impressions as:

he can expect the number of hits to be:

CLICK_i＝t_ir_i(≡c_i) (2)

r_ithe term is the advertiser's click-through rate, i.e., the probability that a user clicks on his catalog when the advertiser appears in the search.

In order to assign the correct number of impressions to each individual, the provider keeps a running total s of the number of impressions made by each advertiser_i. When the user conducts a search, the provider calculates the difference between this number and the number of impressions that the advertiser should have obtained. This difference is:

s is the total number of searches that have occurred. The provider orders the advertisers by the variance and returns the top M listings. The order of return entries may be random or according to the click-through rate r_iOrdered, or ordered according to the perceived quality of the catalog, or ordered according to some other criteria. This algorithm ensures that each advertiser gets the correct number of impressions after a total of T searches, while distributing impressions evenly over time.

There is a limit to the number of impressions an advertiser can purchase. Since, in one embodiment, no one advertiser may appear more than once in any search result, he may not have more than T impressions in total. Let A equal the total money spent by all advertisers, the money that would make an advertiser reach this limit is:

we refer to this limit as the flow limit. If an advertiser exceeds this traffic limit, the search engine provider blanks the excess impressions. If N ≦ M, there is always at least one advertiser at the traffic limit and the market collapses. In this case, the search engine provider may reduce the number of catalogs it returns, so that M < N, and advertisers have an incentive to compete. Alternatively, the provider may always set the number of catalogs to a fraction of the number of advertisers, e.g., M ═ 0.5N.

In a preferred embodiment, the advertiser pays for a click or click through rather than a print pass, and the price is fixed at the time of sale. A click or click through is an action by a searcher to browse the advertiser's search listings and click on their associated hyperlink, or to select to browse the search listings. The searcher's web browser is then redirected to a Uniform Resource Locator (URL) associated with the search catalog. When an advertiser wants to purchase clicks, the search engine provider gives a cost-per-click (cost-per-click) that depends on how often he expects the user to click on the advertiser's inventory, and how many ads he expects to sell in total. The cost per click reported by the provider is:

in the context of this equation, the equation,is an estimate by the search engine provider of the total number a of ads he expects to sell in T searches,is his estimate of the click-through rate of the advertiser. The price per click for an advertiser increases as his expected click-through rate decreases. If everyone has the same click-through rate, then everyone pays the same CPC. The search engine provider expresses the number of clicks he expects to deliver as:

to complete the sale, the advertiser decides the amount a he wants to spend at the indicated price per click, a_i. The provider delivers the clicks at this price until the advertiser reaches his spending limit or the user ends a total of T searches.

By adjusting its valuation, search engine providersTo control the price. When his estimate is as accurate as possible, i.e. whenHe earned the most. If the evaluation is madeIf too small, the click valuation is too large and the advertiser is used if the respective limit has not been reachedLight out ofIn this case, the provider should increase the number of providersTo increase the price. Advertisers will tend to spend less, but the total amount obtained by the providerWill rise. If the evaluation is madeToo large, the click valuation is too small and the advertiser reaches the total limit A before the T searches end. In this case, the provider should decrease the rate by decreasingTo reduce the price. Advertisers will tend to spend more and the total a earned by the provider will rise again. If the evaluation is madeJust as appropriate, each advertiser pays its respective spending limit a_iWhile there are no unsold clicks. Likewise, the search engine provider will do the best when all estimated click-through rates are as accurate as possible.

One way to make a good estimate of the total expense and click through rate is to use historical data. Assume, for example, that the historical click-through rate for the entire market is the CTR. The provider can estimate the individual catalog click-through rates using the following formula:

u_ithe item is the number of clicks, s, that a catalog has obtained_iIs the number of prints. For theFor a new catalog, these numbers are all 0 and the estimates default to the total click-through rate CTR. For a catalog that has many clicks and impressions, the estimate is close to the observation frequency. The constant k acts as a scaling factor to determine how fast the estimate changes between the two values. When the advertiser decides to purchase more clicks for their catalog, the provider bases r on_iThe price per click is reported as the latest estimate. Providers may also estimate click-through rates in other ways, such as by comparing new catalogs to other catalogs having historical data.

There are many other ways for the provider to complete the process of contracting with the advertiser. For example, he may run an auction once a week or a month to determine the quantity a_iOr he may allow the advertiser to continually adjust them. The present invention is not limited to any particular scheme.

Each web site displaying the search results is different. Under the current state of the art, the number of catalogs ranges from 1 to 20, with some web sites displaying the complete catalog and others displaying only the title. Because of these differences, the preferred embodiment treats each combination of search terms and web sites as a separate marketplace. An alternative is to treat all impressions of a search term from anywhere as a single market. In this case, the flow limit formula is different from equation 3, but the other equations and algorithms remain the same. A person skilled in the art can derive new flow limit equations suitable for this alternative without difficulty.

Advertisers typically spend money on many different search terms. One advantage of the present invention is that the provider can recommend the best amount the advertiser should spend between different markets and automatically distribute his money between them. If the advertiser follows the provider's recommendations, he can be guaranteed to maximize the expected revenue. The remainder of this section will describe the formulas and algorithms necessary to start with a single advertiser in a single market, up to the full range of problems for multiple advertisers in multiple markets.

To optimize the advertiser's expense, the provider needs to know three things: advertiser's total budget b_iHis profit per click p_iAnd an external rate of return R (which is available to all advertisers if they spend money elsewhere). Thus, the expected revenue for an advertiser to purchase paid listings in a single marketplace is:

PROFIT_i＝(p_ic_i-a_i)+R(b_i-a_i)(≡f_i) (4)

the first item is the revenue the advertiser gets from its paid catalog; the second term is the revenue he gets by investing elsewhere. If the external rate of return R is high, the advertiser should spend less budget on clicks. Maximizing its profit_iThe values are:

quantity d_iIs the total amount of money spent by other advertisers in the marketplace; v. of_i＝r_ip_iIs the market value of the advertiser. The amount an advertiser should spend decreases as its click-through rate or revenue per click decreases. If a is_iLess than 0, or less than the provider's minimum cost, or greater than the traffic limit, or greater than the advertiser's budget, it is limited to an appropriate value.

When there are multiple markets, the optimal solution will process them separately. Optimal placement of advertisersThe support is given by equation 5 for one special case of each market. Quantity T, v_iAnd d_iAll may be different in each market. The only interactive factor between markets is the advertiser's budget limit,

this is a summation over all markets. To achieve this limit, the advertiser's market value includes a budget scaling factor, v_ij＝λ_jr_ijp_ij. Note that with a single λ_iValue scales advertiser values uniformly in each market. If the advertiser is not budget limited, λ_i1. If he is budget limited, λ_iIs set to the value that exactly spends its budget. Any good numerical equation solver can find this value. Examples include online guided reading of the Nonlinear equation solver on www.ece.nwu.edu/OTC, and Numerical Methods for Uncistronic optimization and Nonlinear Equations, Dennis and Schnabel, ISBN 0898713641.

The problem is further compounded when there are multiple advertisers in a single market. If any advertiser changes the amount he is willing to pay, the optimal solutions for the other advertisers change. One possible algorithm is to iteratively solve for each advertiser and hope that the iterative process converges. If the iterative processes do converge, the final answer will be a fixed point where none of the advertisers can increase their revenue unless another advertiser changes the amount he is willing to pay. Using equation 4 for f_iThis fixed point satisfies the following system of equations:

this fixed point is not a global maximum for any advertiser, since if one advertiser changes the amount of his spending, there is a possibility that the revenue of other advertisers will rise. In addition, it is a correct solution to the problem, since the revenue for each advertiser is maximized with respect to an amount that he can control, his own expenses.

The system of equation 6 can be solved in a closed form. The solutions for each advertiser are:

the total amount of money A spent by all advertisers added together is:

quantity v_LIs the lowest market value an advertiser may have before equation 7 becomes negative and the advertiser should not spend any money. Its value and its positionThere is a harmonic mean of the advertiser's value,

wherein the harmonic mean v is a value of,

another quantity of interest is v_UI.e., the maximum value an advertiser may have before being subject to traffic restrictions. The value of which is such that,

equations 7-11 are the basic formulas for these embodiments.

When calculating the optimal amount of spending using equation 7, it may happen that some advertisers have an optimal amount that is less than 0 or greater than the traffic limit. These solutions are not possible in the real world. The algorithm for finding the effective solution is just beyond the boundaryOne of the actors is picked, he is constrained to the appropriate bounds, he is removed from the question, and the solution is recalculated for all others. This process is repeated until the algorithm solves for a valid solution. The recalculated value pair v in each iteration_LA slightly different formula is used and,

in this equation, m is the number of white spaces on the search result page that are not occupied by advertisers at the traffic limit, and n is the number of free advertisers that are neither at the zero limit nor at the traffic limit. A harmonic mean v is calculated for the free advertiser. If all advertisers are free, then M is M, N is N, and the solution equals the previous formula of equation 9.

The algorithm for choosing which advertiser to remove is to consider a total signed over-run that is either negative or above the traffic limit:

if E < 0, then an advertiser below the zero limit has a dominant over-run, the algorithm removes the advertiser with the lowest market value. If E ≧ 0, the excess of advertisers above the traffic limit dominates, the algorithm limits the advertiser with the highest market value to the traffic limit. The flow limit tends to be increased to decide that the boundary case E is 0 to ensure that the market never collapses if the advertiser has less space than on the search results page.

Optimal solution singleton when there are multiple markets and multiple advertisersThey are processed individually. For a single advertiser, each advertiser's market value contains a budget scaling factor that limits its spending across all markets. If the advertiser is not budget limited, his budget factor λ_i1. If the advertiser has a budget constraint, λ_iIs less than 1. By renumbering advertisers so that the first k advertisers are budget constrained, algorithms meeting budget constraints will solve a simultaneous system of nonlinear equations,

the free variables are λ of those advertisers at budget limits_i. A is given by equations 7 and 12_ijIs constrained to the limits 0 and A_j/M_j. Any good equation solver can solve this system numerically.

There are some practical problems. First, because the advertiser's market value changes as its budget scale factor changes, his optimal expense may cross a zero or traffic limit when we solve the system of equation 14. It is therefore important to always use equations 7 and 12 to calculate a_ijEven if the advertiser is initially constrained in a certain market. By using the equation all the time, the advertiser's overall optimal spending varies smoothly between 0 and its maximum.

Second, because the market constraint is solving for λ_iMay change, so the algorithm must iterate until a stable solution is obtained. The algorithm is as follows: solving all zero constraints and flow constraints in each market to obtain values of m and n, and then solving budget constraints to keep the values of m and n unchanged. If atWhen the budget constraint is solved, any advertiser crosses the zero or flow limit, and the process is repeated.

Third, the algorithm must determine which advertisers are included in equation 14 when solving the budget constraint. The algorithm includes any advertiser above budget, and any lambda_i< 1 advertiser. This combination gives the working set of advertisers at their budget limits. This working set may be wrong, with some advertisers even at λ_iIt is also actually below the budget when 1. In this case, equation 14 has no solution under the current working set. A good equation solver will solve as many budget constraints as possible. In the next iteration, the algorithm will remove advertisers that do not belong to the working set and solve equation 14.

Finally, there are areas where the advertiser's overall optimal spending does not change as his budget scale changes. This occurs when the advertiser is constrained in each market. Fig. 21 illustrates this problem. This figure depicts how the overall optimal spending for an advertiser varies as a function of its budget scale. The graph is flat on the left because the advertiser's optimal spending is below the zero limit in each market, and it is also flat on the right because his optimal spending is above the traffic limit in each market. These flat areas can cause problems for the numerical equation solver.

The solution is to provide two points, min λ_iAnd max λ_iAs equation solver pair λ_iIs determined. These boundaries replace the usual bounds 0 and 1. In a single market, min λ_iIs the point at which the advertiser reaches the zero bound, and max λ_iIs the point at which the advertiser reaches the traffic limits. These values are:

the values of β are:

the desired boundary constraints are the minimum and maximum of these values among all markets. It is possible that even with these limitations, the equation solver will encounter a flat region in the middle of the expense graph. These flat areas hardly occur when advertisers are below the zero limit in some markets and above the traffic limit in the remaining markets. In this case, the algorithm will operate with a λ that falls outside the flat region_iThe value restarts the equation solver so that it can proceed.

An advertiser may forego automatic optimization and adjust his spending personally. Except that v_LAll of the above equations continue to hold for other advertisers, except for changes in the formula(s). If C is the total amount contributed by an advertiser who paid a fixed amount, then

Quantity v₀Is the old zero limit value derived from equation 12,

note that when C is 0, v_LIs formed as v₀. Another test of interest is n-1 and M-M. In this case, v₀0 and equation 16 returns to the original advertiser result of equation 5.

In one embodiment, an ordering method is implemented for a pay for location database search system. The method includes a search provider that provides advertisers with a large number of searcher engagements (engagments) at a specified price. The seeker engagement may be a print, click or click through, click through action, or other type of engagement. In this manner, the advertiser may select the amount or number of clicks that he is willing to pay and order accordingly. The subscription may be for a fixed period of time, such as a month, or may be arranged in any two-party negotiated manner. The search provider may provide different rates for different advertisers, or depending on the number of search listings or markets in which the advertisers participate.

The method also includes establishing a subscription account with the subscription advertiser. The fee paid by the advertiser may be charged to the predetermined account and then automatically deducted from the account when the seeker engagement occurs.

The pay for location database search system will next receive a search request from the searcher. In response to these search requests, the database search system will provide search results. Some search results may be listings of the subscribing advertiser if the search query matches the search listing. If the subscription advertiser search listings are provided in the search listings page, the subscription account is adjusted accordingly. This may be done by crediting the account with the number of impressions or click-throughs paid by the subscribing advertiser and subtracting 1 for each search listing provided to the searcher. Other kinds of subscription management may also be used.

Drawings

1-20 are flow charts illustrating specific algorithms for finding the optimal spending for each advertiser;

FIG. 21 is a graph illustrating the variation of an advertiser's total optimal spending as a function of the advertiser's budget proportion; and

FIG. 22 is a block diagram illustrating one embodiment of a network including a computer database search system.

Detailed Description

Referring now to the drawings, the flow charts formed in FIGS. 1-20 present specific algorithms for finding the optimal spending for each advertiser. The inputs to the algorithm are:

search number of SEARCHES [ M ] in one market M

Number of SPACES on SPACES [ M ] search results Page

ROI [ M ] external rate of return

Revenue PER CLICK for PROFIT _ PER _ CLICK [ A, M ] advertisers

CLICK-through RATE for CLICK _ RATE [ A, M ] advertisers

BUDGET for BUDGET [ A ] advertisers.

The output of the algorithm is:

speed A, M advertiser's best spending

CONSTRAINT [ A, M ] advertiser's CONSTRAINT status

LAMBDA [ A ] advertiser's budget scale factor.

Throughout the detailed description, variable A represents an advertiser and variable M represents a market. Since each quantity other than BUDGET [ A ] and LAMBDA [ A ] depends on the current market M, M is generally omitted from the figures to improve readability. Also, error conditions, floating point boundary conditions, or opportunities for caching and optimization are not shown in the figures. Those skilled in the art will readily understand the pseudo code and write an efficient computer program that will implement it.

The embodiments described herein may be implemented as computer readable program code for executing one or more processing devices and associated data storage devices. In one embodiment, the disclosed methods and apparatus may be implemented as C + + program code for controlling a database management system or search engine. In another embodiment, the methods and apparatus may be implemented as a data storage medium having computer-readable program code stored therein, a data processing apparatus performing the functions described herein, or any other suitable device.

FIG. 1 illustrates one embodiment of a top-most approach. The method in this embodiment is a cyclic process: the zero and traffic constraints in each market are solved first, and then the budget constraints are solved. The loop process ends when the function IS _ cooled indicates that the current solution satisfies all constraints. In the final step, the algorithm records the optimal spending for each advertiser in the output variable speed [ a, M ].

The top-most method is a process labeled Solve, which begins at block 100. At block 102, the INITIALIZE _ bud-SCALES procedure is invoked. This process initializes the advertiser's budget scale factor, lambda. One embodiment of this process is shown in fig. 9. The loop process begins at block 104. At block 106, a loop variable is initialized. At block 108, the SOLVE _ MARKET procedure is invoked. One embodiment of this process is shown in fig. 2. This process satisfies the zero constraint and the traffic constraint in a certain market. The loop continues at block 110 until all markets M have been processed. At block 112, the loop process is exited and the SOLVE _ BUDGETS process is invoked. One embodiment of this process is shown in fig. 10. This process satisfies the budget constraints of each advertiser. The loop process, including blocks 104, 106, 108, 110, 112, and 114, continues processing until the IS _ SOLVED process returns a true value. One embodiment of this process is shown in fig. 17. This process determines whether all of the zero, traffic, and budget constraints are solved. If not, control returns to block 104. If so, the COMPUTE _ SPENDING procedure is invoked at block 116. This process calculates the optimal spending for each advertiser. One embodiment of this process is shown in fig. 18. The Solve process then ends at block 118.

FIGS. 2-8 illustrate the steps of solving for the zero constraint and the flow constraint. The output is CONSTRAINT [ A, M ] values that indicate whether the advertiser is zero-constrained, traffic-constrained, or unconstrained in the marketplace. The topmost cycle is located in figure 2. The algorithm first initializes all constraints in the current MARKET to NONE and then superimposes the constraints until marker _ IS _ SOLVED indicates that the current solution IS valid. In each iteration, the algorithm calls COMPUTE _ MARKET _ PARAMETERS to calculate the quantities in equations 7-12 that characterize the MARKET.

FIG. 2 is a flow chart illustrating one embodiment of the SOLVE _ MARKET process. The process begins at block 200. The INITIALIZE _ configurations procedure is called at block 202. One embodiment of this process is shown in fig. 3. This process initializes advertiser constraints in the marketplace. Next, a loop process is entered at block 204. The complete _ mark _ PARAMETERS procedure is called at block 206. This process calculates the individual quantities that make up the market. One embodiment of this process is shown in fig. 4. The ADD _ CONSTRAINT procedure is also invoked at block 206. This process adds the most important traffic (mostsignificatent traffic) or zero constants to the market. One embodiment of this process is shown in fig. 6. At block 208, the value returned by the marker _ IS _ stored procedure IS checked. One embodiment of this process is shown in fig. 8. This process determines whether all zero and traffic constraints for the market have been solved. If this process does not return a true value, loop operation continues. Otherwise, the SOLVE _ MARKET process ends at block 210.

FIG. 3 shows an algorithm for initializing market constraints. The algorithm is a loop that sets the constraints of each advertiser to NONE. The INITIALIZE _ configurations process begins at block 300. A loop process is entered at block 302. At block 304, for each advertiser under consideration, the value of the Constraint array indexed by advertiser is initialized to a NONE value. The loop continues at block 306 until all advertisers have been processed. The process ends at block 308.

FIG. 4 illustrates one embodiment of a method for calculating the various market parameters given by equations 7-12. The method begins at block 400. At block 402, the complete _ SUMS procedure is invoked. The COMPUTE _ SUMS calculates the initial quantities FREE _ SPACES, FREE _ ADVERTISERS and Z, where Z is the denominator of the harmonic mean given in equation 10. These quantities will appear in the remaining equations. The method uses the formula for V _ L given by equation 12, but if some advertisers manually adjust their spending, the same can be done with more general equation 16. One embodiment of this process complete _ SUMS is shown in fig. 5. The value of V _ Bar is calculated at block 404 and the value of V _ L is calculated at block 406. At block 408, a value of a variable TOTAL _ MARKET _ SPEED is defined. The method ends at block 410.

Fig. 5 shows an embodiment of a process for calculating FREE _ ADVERTISERS, FREE _ space and Z. FREE _ ADVERTISERS counts the number of unconstrained advertisers; FREE _ space counts the number of empty SPACES occupied by advertisers on the search result page that are not traffic-constrained; z is the sum of the reciprocals of the market value for each free advertiser. The process uses a loop to all advertisers to calculate these quantities.

The process begins at block 500. At block 503, FREE _ ADVERTISERS, FREE _ space and Z are initialized. At block 504, a loop process is entered using the advertiser as a loop index. At block 506, a determination is made whether the constraint for an advertiser is equal to NONE. If so, the value of FREE _ ADVERTISERS and Z is incremented at block 508. Control then proceeds to block 514. Otherwise, if the value of the Constraint (Constraint) on the advertiser is equal to Traffic (Traffic) (block 510), the value of FREE _ SPACES is decremented at block 512. At block 514, the loop operation continues until all advertisers have been processed. The process then ends at block 516.

Figure 6 shows an algorithm for adding the most important flow or zero CONSTRAINTs to the CONSTRAINT a, M value. If the solution is to the market, nothing is done. Otherwise, the algorithm adds a zero constraint or a traffic constraint according to the sign of EXCESS _ SPEED. If the overboost is negative, the algorithm adds a zero constraint for the free advertiser with the smallest market value. If the overboost is 0 or a positive number, the algorithm adds a traffic constraint for the free advertiser with the largest market value.

The process begins at block 600. At block 602, the process checks whether the MARKET has been SOLVED by calling the marker _ dissolved process. One embodiment of this process is shown in fig. 8. If the market has been solved, the process ends and control returns to the calling process. If not, an EXCESS _ SPEED procedure is invoked at block 604. One embodiment of this process is shown in fig. 7. If EXCESS _ SPEED returns a value less than 0, then at block 606 the algorithm adds a zero constraint for the free advertiser A with the smallest market value. If the value returned by EXCESS _ SPEED is 0 or a positive number, then at block 608, the algorithm adds a traffic constraint for the free advertiser A with the largest market value. The process ends at block 610.

Fig. 7 shows an algorithm for calculating the total signed hyper-branch given by equation 13 above. The algorithm adds the amount from each advertiser whose value is less than V _ L or greater than V _ U, and totals out the run of the excess. The algorithm ignores any advertisers subject to a zero constraint or a traffic constraint.

The process begins at block 700. At block 702, the value of the variable EXCESS _ SPECD is initialized to 0. At block 704, a loop operation is initiated with advertiser A as the loop index. In the loop process, at block 706, it is determined whether the value of the advertiser for the current index is less than V _ L, the smallest possible free value. If so, then at block 708, if there are no constraints on advertiser A, the variable EXCESS _ SPEED is incremented by the value indicated at block 708 in FIG. 7. Control then proceeds to block 714. If at block 710, the value of the advertiser for the current index is greater than V _ U, the largest possible free value, then control passes to block 712. At block 712, if there are no constraints on advertiser A, the variable EXCESS _ SPEED is incremented by the value shown at block 712 in FIG. 7. Control then proceeds to block 714. The loop operation repeats until all advertisers have been processed. The process ends at block 716.

Fig. 8 shows an algorithm for determining whether the current CONSTRAINT [ a, M ] value is a valid solution. For each free advertiser, the algorithm verifies to see if his value is less than the minimum possible free value V _ L, or greater than the maximum possible free value V _ U. The current solution is valid only if all free advertisers fall within these boundaries.

The process begins at block 800. At block 802, a loop operation is initiated with advertiser A as an index. At block 804, the value of advertiser A is compared to V _ L. If the value is less than V _ L, then at block 806, if there are NO constraints on advertiser A, then the NO value is returned by the process. Control proceeds to block 812. If the value of advertiser A is not less than V _ L at block 804, then this value is checked against V _ U at block 808. If it exceeds V _ U, then at block 810, if there are NO constraints on advertiser A, the process returns a NO value. Control proceeds to block 812. If additional advertisers remain, the loop continues at block 802. If all advertisers have been processed and the process has not returned a NO value, control exits the loop and the process returns a YES value at block 814 indicating that the market has been resolved. The process ends at block 816.

FIG. 9 shows an algorithm for initializing the budget scale factor. The algorithm is a round-robin process that sets the budget scale factor of each advertiser to 1. This process is called once at the beginning of the solva algorithm.

The process begins at block 900. At block 902, a loop operation is entered using advertiser A as a loop index. At block 904, the advertiser's budget scale factor LAMBDA is initialized to a value of 1. At block 906, the loop continues until all advertisers have been processed. The process then ends at block 908.

FIGS. 10-15 show steps for solving for the budget scale factor LAMBDA [ A ]. The top-most algorithm is shown in fig. 10. The algorithm begins by computing the work group of advertisers at the budget limits. The algorithm then builds a vector of variables to pass to the equation solver, where each advertiser in the working set corresponds to one of the variables. Each variable has an associated upper boundary and a lower boundary. The SET _ TO _ ZERO function is an external equation solver that adjusts the LAMBDA [ A ] value so that each advertiser's total cost exactly matches his budget. Any equation solver can be used herein as long as it is capable of solving a nonlinear system of equations with boundary constraints. The inputs to the equation solver are the vector objective function BUDGET _ ERROR, the number of variables N, the variable vector to be adjusted, and the boundary constraints. When the function is running, SET _ TO _ ZERO calls BUDGET _ ERROR (I) TO evaluate the I component of the target function. If it finds the knowledge, it ends with BUDGET _ ERROR (I) equal to 0 for each I. If there is no solution, it ends with one or more of the LAMBDA [ A ] values at the upper bound, and the algorithm will remove the corresponding advertiser from the workgroup on the next iteration.

FIG. 10 illustrates one embodiment of the SOLVE _ BUDGETS process for solving for the budget scale factor. The process begins at block 1000. At block 1002, the variable N is initialized to 0, and the variable WORKING _ SET is SET equal to the result of the BUDGET _ LIMITED _ ADVERTISERS process. One embodiment of this process is shown in fig. 12. At block 1004, a loop operation begins using advertiser A as a loop index. At block 1006, the variable N is incremented and the entry in the vector VARIABLES indexed by the variable N is set equal to the reference number (reference) of the entry in the vector LAMBDA for the current advertiser. The MIN _ LAMBDA process is invoked to determine the value of the variable LOWER _ BOUND. MIN _ LAMBDA calculates the minimum LAMBDA before the advertiser currently being indexed is bound to zero everywhere. One embodiment of this process is shown in fig. 13. The MAX _ LAMBDA process is then used to determine the value of the variable UPPER _ BOUND. MAX _ LAMBDA calculates the maximum LAMBDA of the advertiser currently being indexed before it is subject to traffic constraints everywhere. One embodiment of this process is shown in fig. 14. At block 1008, the loop continues until all advertiser A's have been processed.

After the loop operation is completed, the SET _ TO _ ZERO process is invoked TO solve the system of equations defined by the inputs (BUDGET _ ERROR function) as described above at block 1010. One embodiment of this function is shown in fig. 11. The solvajbuffers process ends at block 1012.

FIG. 11 illustrates a process for calculating the number of advertisers in the workgroup that exceed or fall below the budget. The process takes the ith advertiser from the workgroup and returns the difference between his current total expense and his budget margin.

The process BUDGET _ ERROR begins at block 1100. At block 1102, the I < th > advertiser is retrieved. At block 1104, the difference between the result returned by the TOTAL _ SPEED process and the advertiser A's BUDGET _ LIMIT is calculated as the value of BUDGET _ ERROR. One embodiment of the TOTAL _ SPEED process is shown in FIG. 16. The process ends at block 1106.

FIG. 12 illustrates one embodiment of a process for calculating a workgroup of advertisers at their budget limits. The workgroup includes all of these advertisers that exceed their budget, or have LAMBDA [ A ] that is less than the maximum possible value. The algorithm adds each advertiser that meets one of these two budget limit conditions to the workgroup.

The process begins at block 1200. At block 1202, a variable BUDGET _ LIMITED _ ADVERTISERS is initialized. A loop operation is entered at block 1204 using advertiser a as a loop index. At block 1206, a determination is made whether the current value of the TOTAL _ SPEED process for advertiser A exceeds the budget of advertiser A. One embodiment of the TOTAL _ SPEED process is shown in FIG. 16. If the condition checked at block 1206 is true, then at block 1208, the value of the variable BUDGET _ LIMITED _ ADVERTISERS is incremented by the advertiser A's BUDGET. If not, at block 1210, a determination is made whether the current advertiser's LAMBDA value being indexed is less than the MAX _ LAMBDA current value for advertiser A. One embodiment of the MAX _ LAMBDA process is shown in FIG. 14. If it is, then at block 1212, the value of the variable BUDGET _ LIMITED _ ADVERTISERS is incremented by the advertiser A's BUDGET. Otherwise, control proceeds to block 1214.

At block 1214, if there are more advertisers, control returns to block 1204. Otherwise, if all advertisers have been processed, the process ends at block 1216.

FIG. 13 illustrates one embodiment of a process for calculating the minimum LAMBDA [ A ] that an advertiser may have before its optimal spending becomes negative in each market. For each market, the algorithm calculates the minimum LAMBDA for the advertiser [ A ] using equation 15. The minimum value among all markets is the minimum value within any one market.

The process begins at block 1300. At block 1302, the value of the variable MIN _ LAMBDA is initialized to 1. A loop operation is entered at block 1304 using market M as a loop index. At blocks 1306, 1308, equation 15 above is implemented to determine the minimum lambda of the advertiser. In block 1310, if there are more markets left unprocessed, control returns to block 1304. Otherwise, the process ends at block 1312.

FIG. 14 illustrates a process for calculating the maximum LAMBDA [ A ] that an advertiser may have before its optimal spending reaches the traffic limits in each market. For each market, the algorithm calculates the maximum LAMBDA for the advertiser [ A ] using equation 15. The maximum value among all markets is the maximum value within any one market.

The process begins at block 1400. At block 1402, the variable MAX _ LAMBDA is initialized to 0. A loop operation is started at block 1404 using market M as a loop index. At blocks 1406, 1408, equation 15 above is implemented to determine the maximum lambda of the advertiser. The loop continues at block 1410 until all markets have been processed. The process ends at block 1412.

FIG. 15 illustrates one embodiment of a process BUDGETS _ ARE _ SOLVED for determining whether there ARE any violations of budget constraints. The algorithm checks to see that each advertiser has the maximum possible value of LAMBDA [ A ] without exceeding its budget. Only if all advertisers meet this condition does the process return YES.

The process begins at block 1502. Beginning in block 1502, a loop is made for each advertiser A. At block 1504, the result returned by the process TOTAL _ speed for advertiser a is compared to the budget of advertiser a. One embodiment of the process TOTAL _ speed is shown in fig. 16. If the result is greater than the budget, the process returns a NO value at block 1506. Otherwise, at block 1508, if the result returned by the procedure TOTAL _ speed is less than the advertiser's budget, then at block 1510, if the advertiser's LAMBDA is less than the value returned by the MAX _ LAMBDA procedure for that advertiser, then the procedure will return a NO value. One embodiment of the MAX _ LAMBDA process is shown in FIG. 14. The loop continues at block 1512 until all advertisers have been processed. If none of the advertisers returned a NO value throughout the iteration of the loop, a YES value is returned at block 1514 and the process ends at block 1516.

FIG. 16 illustrates one embodiment of a process TOTAL _ SPECD for calculating the TOTAL optimal spending of an advertiser for all markets. It uses OPTIMAL _ speed (a, M) to calculate the amount in each market and adds the respective results to the running total.

The process begins at block 1600. At block 1602, the value of the variable TOTAL _ speed is initialized to 0. In the loop including blocks 1604, 1606, 1608, for each market M, the value of the variable TOTAL _ SPEED is incremented by the value returned by the OPTIMAL _ SPEED process. One embodiment of this process is shown in fig. 19. After all markets have been processed, the process ends at block 1610.

FIG. 17 illustrates one embodiment of a process IS _ SOLVED for determining whether the current CONSTRAINT [ A, M ] and LAMBDA [ A ] values satisfy all of the zero, flow, and budget CONSTRAINTs. The algorithm first checks to confirm that each market meets its zero and flow constraints; it then checks to confirm that each advertiser meets its budget constraint. Only if all of these conditions are true, does the algorithm return YES.

The process begins at block 1700. At block 1702, a loop process is entered using market M as a loop variable. At block 1704, the value returned by the process MARKET _ IS _ SOLVED IS checked. One embodiment of the process marker _ IS _ dissolved IS shown in fig. 8. If the process returns a negative value, the process IS _ SOLVED returns a NO value. Otherwise, at block 1706, the loop continues to check for another market M. Once all markets have been verified, the values returned by the BUDGETS _ ARE _ SOLVED process ARE verified. One embodiment of the BUDGETS _ ARE _ SOLVED process is shown in FIG. 15. At block 1708, if the process does not return a positive value, the process IS _ solvad returns a NO value. Otherwise, at block 1710, the process returns a YES value. The process ends at block 1712.

FIG. 18 illustrates one embodiment of a process COMPUTE _ SPENDING for recording the final optimal SPENDING amount of each advertiser in each market. The algorithm is a loop that sets each speed [ a, M ] value to the current value of OPTIMAL _ speed (a, M).

The process begins at block 1800. At block 1802, an outer loop is entered using advertiser A as a loop variable. At block 1804, an inner loop is entered using market M as a loop variable. At block 1806, the entry in the array speed is set to the current value returned by the process OPTIMAL _ speed. One embodiment of this process is shown in fig. 19. After all markets M have been processed for an advertiser's value A, the advertiser's value, which is the loop variable for the outer loop, is incremented by 1. After all advertisers have been processed, the process ends at block 1812.

FIG. 19 illustrates one embodiment of an OPTIMAL _ SPECD process that uses equation 7 to calculate advertiser OPTIMAL spending in a single market. If the value is less than 0 or greater than the flow limit, the algorithm constrains it to the appropriate value.

The process begins at block 1900. At block 1902, a value of a variable OPTIMAL _ SPEED is determined based on the TOTAL _ SPEED of the advertiser in a market. One embodiment of the TOTAL _ speed process for this operation is shown in fig. 16. At block 1904, the result of the options _ speed is set to the greater of options _ speed and 0 and the smallest of options _ speed and TRAFFIC _ LIMIT. The process ends at block 1906.

FIG. 20 illustrates one embodiment of a process for calculating a market value for an advertiser. The process begins at block 2000. The VALUE is the product of the advertiser's budget zoom factor lambda, its revenue per click, and its click-through rate. The per click revenue and its click-through rate may be obtained from any convenient source.

The block diagram of FIG. 22 thus illustrates a distributed system 2200 comprising a plurality of client computers 2202, a plurality of advertiser web servers 2204, an account management server 2206, and a search engine web server 2208, all of which are connected to a network 2210. Network 2210 is hereinafter generally referred to as the internet. While the disclosed system and method is particularly useful for the Internet, it should be understood that client computer 2202, advertiser web server 2204, account management server 2206, and search engine web server 2208 can be connected together through one of a number of different types of networks. These networks may include Local Area Networks (LANs), other Wide Area Networks (WANs), and regional networks accessed over telephone lines, such as commercial information services. The client and server processes may even comprise different programs running on one computer at the same time.

The client computer 2202 may be a conventional Personal Computer (PC), a workstation, or any other scale computer system. Each client 2202 typically includes one or more processors, memory, input/output devices, and a network interface (e.g., a conventional modem). Advertiser web servers 2204, account management servers 2206, and search engine web servers 2208 may be similarly configured. However, each of the advertiser web server 2204, account management server 2206, and search engine web server 2208 may include multiple computers connected by isolated private networks. In fact, network 2210 may include hundreds or thousands of individual computer networks.

The client computer 2202 may execute a web browser program 2212, such as a NAVIGATOR, EXPLORER, or MOSAIC browser program, to locate a web page or record 2214 stored on the advertiser server 2204. The browser program 2212 allows the user to enter the address of the particular web page 2214 to be retrieved. These addresses are referred to as uniform resource locators or URLs. In addition, once a page is retrieved, the browser program 2212 may provide access to other pages or records after the user "clicks" on hyperlinks to other web pages. These hyperlinks are located within the web page 2214 and provide an automated way for the user to enter the URL of another page and retrieve that page. The pages may be data records, including content plain text information, or more complex digitally encoded multimedia content, such as software programs, graphics, audio signals, video, and the like.

In one embodiment, the client computers 2202 communicate over the network 2210 with the functionality provided by the Hypertext transfer protocol (HTTP) to various network information providers, including account management server 2206, search engine server 2208, and advertiser servers 2204, although other communication protocols, such as FTP, SNMP, TELNET, and a variety of other protocols known in the art, may be used. Preferably, the search engine server 2208, account management server 2206, and advertiser servers 2204 are located on the world Wide Web.

As discussed above, at least two types of servers are contemplated in various embodiments. The first server contemplated is an account management server 2206 that includes a computer storage medium 2220 and a processing system 2222. Database 2224 is stored on storage medium 2220 of account management server 2206. Database 2224 contains advertiser account information, including advertiser subscription account information in one embodiment. It will be appreciated from the description herein that the systems and methods disclosed herein may be implemented in software stored as executable instructions on a computer storage medium, such as a memory or mass storage device, of the account management server 2206. A conventional browser program 2212 running on the client computer 2202 may be used to access advertiser account information stored on the account management server 2206. Access to the account management server 2206 is preferably achieved through a firewall, not shown, that protects the account management and search result placement programs and account information from external tampering. Security may be further provided through enhancements to standard communication protocols, such as Secure HTTP (Secure HTTP) or Secure Sockets Layer.

The second server type contemplated is a search engine web server 2208. Search engine programs allow a network user or searcher, upon navigating to the web site of a search engine web server URL or other web server capable of submitting a query to the search engine web server 2208 through its browser program 2212, to enter a keyword query to identify those pages of interest among the millions of pages available from the world wide web. In one embodiment, the search engine web server 2208 generates a search result list that includes, at least in part, relevant entries derived from and formatted by the results of the bidding process conducted by the account management server 2206. Search engine web server 2208 generates a list of hypertext links that point to documents that contain information related to the search terms entered by the user at client computer 2202. The search engine web server sends this list to the web user in the form of a web page, which is then displayed on the browser 2212 running on the client computer 2202. One embodiment of a search engine web server may be found by navigating to a web page at a URLhttp：//www.overture.com。

Search engine web server 2208 is connected to the internet 2210. In one embodiment, the search engine web server 2208 includes a search database 2230 comprised of search catalog records that are used to generate search results in response to user queries. In addition, the search engine web server 2208 may also be connected to an account management server 2206. The account management server 2206 may also be connected to the internet. Search engine web server 2208 and account management server 2206 are used to address the different information needs of users located at client computers 2202.

For example, one type of user located at the client computer 2202 can be a network information provider, such as an advertising website promoter, or an advertiser having an advertiser web page 2214 located on an advertiser web server 2204. These advertising web site promoters or advertisers may wish to access account information residing in the storage device 2220 on the account management server 2206. The advertising web site promoter may participate in a competitive bidding process with other advertisers through the account residing on the account management server 2206. An advertiser may bid on any number of search terms related to the advertiser's web site content. In one implementation, the relevance between the bid-on search terms in the search listing and the corresponding web site can be evaluated using a computer program executing at the processor 2222 of the account management server 2206 that will evaluate the search terms and the corresponding web site according to a set of predefined editorial rules.

The higher the bid, the more advantageous it is to be on a search result list page generated by search engine 2208 when searching using search terms bid on by advertisers. In one embodiment, the amount bid by an advertiser includes the amount of money to be deducted from the advertiser's account each time the advertiser's web site is accessed via a hyperlink on a search results list page. In another embodiment, each time an advertiser's search listing is provided or displayed to a searcher in response to a search query, a predetermined amount is deducted from the advertiser's subscription account. The searcher "clicks" on the hyperlink using a computer input device to initiate a retrieval request to retrieve information associated with the advertiser's hyperlink. Preferably, each access or "click" to a search result list hyperlink will be redirected to the search engine web server 2208 to associate the "click" with the advertiser's account identifier. This redirection action, unknown to the searcher, encodes access to account identification information in the search results page before accessing the advertiser's URL using the search results list hyperlink clicked on by the searcher. In another embodiment, this click-through to the advertiser URL may result in a predetermined amount being deducted from the advertiser's subscription account. The account identification information is recorded in the advertiser's account as a retrieval request event along with information from the retrieval request. Since the information obtained by this mechanism ultimately matches the account identifier with the URL in a manner not possible using conventional server system logs known in the art, an accurate record of account debt will be maintained. In some embodiments, the advertiser's web site description and hyperlink on the search results list page is accompanied by an indication that the advertiser's catalog is a paid catalog.

A second class of users at client computers 2202 may include searchers seeking specific information on the network. These searchers can access, through their browser 2212, a search engine web page 2232 residing on a web server 2208. The search engine web page 2232 includes a query box into which a searcher may type search terms that include one or more keywords. Alternatively, the searcher may query the search engine web server 2208 through a query box that is hyperlinked to the search engine web server 2208 and located on a web page stored at a remote web server. After the searcher finishes entering the search terms, the searcher may send the query to the search engine web server 2208 by clicking on the provided hyperlink. The search engine web server 2208 will then generate a search result list page and send the page to the searcher at client computer 2202.

The searcher may click on the hypertext links associated with each catalog on the search result list page to access the corresponding web page. The hypertext links may access web pages anywhere on the internet and include a paid catalog to advertiser web pages 2214 located on advertiser web servers 2204. In one embodiment, the search result list also includes non-paid listings that are not results of advertiser bids but are generated by conventional Web search engines, such as the INKTOMI, LYCOS, or YAHOO! A search engine. These non-paid hypertext links may also include links manually indexed by the editorial team into the database 2230.

As can be seen from the above description, the presented embodiments provide a method and apparatus for displaying an advertiser's inventory in proportion to the amount spent by the advertiser. Each advertiser decides how much he wants to spend on a search term and the search provider displays the advertiser's listing accordingly.

While particular embodiments of the present invention have been shown and described, various modifications may be made. It is therefore intended to cover in the appended claims such changes and modifications that are within the true spirit and scope of this invention.

It is therefore intended that the foregoing detailed description be regarded as illustrative rather than limiting, and that it be understood that it is the following claims, including all equivalents, that are intended to define the spirit and scope of this invention.

Claims (24)

1. A business method for a database search system in which searchers submit search queries to a database and receive search listings including at least some advertiser-sponsored search listings, the business method comprising:

selling a specified number of searcher appointments to each advertiser at a specified price; and

next, a search catalog for each advertiser is provided in response to the search query and in proportion to the specified number of searcher engagements for the each advertiser.

2. The business method of claim 1, wherein selling a specified number of searcher engagements comprises:

and selling the search catalog of each advertiser.

3. The business method of claim 1, wherein selling a specified number of searcher engagements comprises:

a searcher click-through selling the search listings of the respective advertisers.

4. The business method of claim 1, wherein selling a specified number of searcher engagements comprises:

after selling the search listings that click through to the various advertisers, the post-click searcher action at the various advertiser's web site.

5. The business method of claim 1, wherein selling a specified number of searcher engagements comprises:

selling one of a searcher click-through and a searcher impression within a predetermined time period in the search listings of the respective advertisers.

6. The business method of claim 1, further comprising:

receiving a search request;

for each individual advertiser, determining respective difference values between the respective quantity agreed by the searcher that has been received and the respective quantity agreed by the searcher that each individual advertiser should receive; and is

And returning the search catalog according to the determined difference value.

7. The business method of claim 1, wherein selling a specified number of searcher engagements comprises:

determining at least one of:

cost per click for each advertiser, an

The estimated number of clicks for each advertiser.

8. The business method of claim 7, further comprising:

click-through rates for individual advertisers are determined based on historical data for the marketplace.

9. The business method of claim 8, wherein the step of determining a click-through rate comprises:

the click-through rate is estimated as the ratio of the number of clicks that the search listing of the respective advertiser has acquired to the number of impressions that the search listing has acquired.

10. The business method of claim 1, further comprising:

recommending optimal advertising spending to each advertiser; and

advertiser advertising expenses are allocated between different markets.

11. A computer readable storage medium having computer readable computer code stored thereon, the code configured to implement a method for a database search system in which a searcher submits a search query to a database and receives search listings including at least some advertiser-sponsored search listings, the computer readable computer code comprising:

first computer readable code for providing a specified number of searcher engagements to each advertiser at a specified price, the searcher engagements including at least one of a searcher impression and a searcher click-through; and

second computer readable code for providing search listings for respective advertisers in response to subsequently received search queries and in proportion to a specified number of searcher engagements for the respective advertisers.

12. The computer-readable storage medium of claim 11, further comprising:

third program code for determining a cost per click-through for each advertiser; and

fourth program code for determining an estimated number of click throughs that can be delivered to the respective advertiser.

13. The computer readable storage medium of claim 12 wherein the third computer program code is configured to determine the cost-per-click throughs as a function of an estimated total ad sales and an estimated click-through rate for the respective advertiser.

14. The computer readable storage medium of claim 12, further comprising fifth computer program code configured to determine the click-through rate and the estimated total ad sales based on historical data for a market.

15. The computer readable storage medium of claim 12 wherein the fourth computer program code is configured to determine the estimated number of click throughs as a function of the ratio of advertising expenses of the respective advertiser to the estimated total advertising sales.

16. The computer-readable storage medium of claim 11, further comprising:

third program code for optimizing the advertiser's advertising spending based on the total advertising budget for the individual advertisers, the advertiser's revenue-per-click-through and external return rates.

17. The computer-readable storage medium of claim 16, further comprising:

fourth computer program code for determining budget scaling factors for said respective advertisers.

18. The computer readable storage medium of claim 17, wherein the fourth computer program code is configured to:

firstly, solving all zero constraints and flow constraints;

determining a number of white spaces on a search results page to be provided in response to the search query that are not occupied by advertisers on the traffic limit, and a number of advertisers that are not currently on the zero limit or the traffic limit; and

solving a system of equations to determine budget constraints for the respective advertisers.

19. An apparatus operating on a computer network for generating a result list in response to a keyword entered by a user through a remote input device, the apparatus comprising a computer system connected to the computer network and having stored thereon:

a database containing a plurality of catalogs, wherein each catalog is associated with an advertiser;

programming code for generating a result list in response to a user input keyword, the result list including a catalog having associated keywords that match the keyword input by the user; and

programming code for managing advertiser subscriptions includes accepting advertiser subscription orders specifying a user contracted quantity, maintaining advertiser subscription accounts, and adjusting the subscription accounts of individual advertisers when an advertiser catalog is included in the generated search listing.

20. The apparatus as recited in claim 19, wherein the computer system stores the user-agreed amount in response to compensation provided by the respective advertiser.

21. The apparatus of claim 20 wherein the computer system determines an estimated number of click-throughs that will be provided in return for the compensation provided by the respective advertiser, the estimated number of click-throughs relating to a ratio of the compensation provided by the respective advertiser to a total compensation provided by all advertisers.

22. A subscription method for a pay-for-location database search system, the method comprising:

providing the advertisers with a specified number of searchers for engagement at a specified price;

establishing a subscription account with one or more subscription advertisers;

receiving a search request from a searcher;

providing search results including a search catalog of a subscribing advertiser in response to the search request; and

adjusting the subscription account of the subscription advertiser in response to providing the search result.

23. The subscription method of claim 22, further comprising:

recommending an optimal advertiser support amount to each advertiser based on at least one of an advertising budget, a click-through-per-click-through revenue, and an external rate of return for the respective advertiser.

24. The subscription method of claim 23, further comprising:

a budget scale factor is determined for the respective advertiser to limit the advertiser's spending in multiple markets.