Federated search engines constitute a new class of search computing paradigms whereby a multi-domain query is decomposed in a number of single-domain queries, each one addressed by a domain-specific content service provider. The paradigm provides a number of advantages, in particular the possibility to discover more pertinent information by scouring the deep Web and to find automatically correlations among the service providers' results. In our work, we focus on the design of a revenue mechanism for such paradigm. This task, although being of extraordinary importance, has not received enough attention in the literature so far. In particular, in this paper we describe a revenue mechanism in terms of business model, specifying who pays and when, and microeconomic model, specifying how the optimal payment can be computed. Futhermore, we discuss its properties.
J.4 [Social and Behavioral Sciences]: Economics; H.3.5 [Online Information Services]: Commercial Services
The main general–purpose search engines crawl the Web and index Web pages, finding the best pages for each specific list of keywords with good precision. However, the so–called deep Web contains information that is largely more valuable than the one that a current general–purpose search engine can discover. The development of new searching paradigms able to address more complex searches than those addressed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. This article was presented at the workshop Very Large Data Search (VLDS) 2011.
Copyright 2011.
to the current search engines and to discover deeper
information is currently one of the most interesting challenges in the
search computing field. Currently, the emerging paradigm
is based on the combination of a multi–domain query
approach with the integration of heterogeneous data sources
capable to scour the deep Web. This has resulted in a new
generation of search paradigms, called federated search
engines (FSEs), that integrate search results from
heterogeneous domain–specific content service providers [
Consider for instance a user that searches for a restaurant close to a given hotel in a given city. General–purpose search engines allow the user to make exclusively single–domain queries on restaurants or hotels. Then, the user must manually scour the results of the query on restaurant and of the query on hotel to find a restaurant and an hotel close together. Instead, allowing a user to make multi–domain queries, the user needs to make only a single query in which she specifies all the fields of the search. The results she obtains contain both hotels and restaurants that are displayed in a way that helps the user to select the closest ones.
While the scientific community has been working on the
development of FSE enabling technologies for some years [
Then, we focus on the FSE scenarios. They involve many actors and require the design of a new revenue mechanism. This is because existing revenue mechanisms are not able to integrate different advertising services and to provide the actors involved in the FSE’s activity with appropriate monetary incentives. We propose an ad–hoc revenue mechanism, stating initially its requirements and subsequently designing a business model and a microeconomic model that satisfy the requirements. Both models extend the existing ones. We also report an example of application and some very preliminary experimental results with Yahoo! dataset.
The paper is structured as follows. In the next section, we classify the existing revenue mechanisms for search applications. In Section 3, we present our business model for FSEs, while, in Section 4, we describe the microeconomic model. Section 5 concludes the paper.
We provide a classification of the currently adopted revenue mechanisms in the attempt to provide a classification in terms of business models and microeconomic models. 2.1
A business model can be characterized in terms of actors and payment schemes.
Actors can be classified as follows. User : her aim is to
search for contents/advertisement. Advertiser : its aim is to
appear in sponsored links or banners displayed to targeted
users. Content service provider : its aim is to produce a list
of contents (organic search), given an input provided by the
user. The input can be a list of keywords or a more
structured query. Contents are usually extracted from databases.
As in the case of Zillow [
The payment scheme defines when (usually in terms of events) an actor must pay another actor. The payment schemes usually adopted in search applications are the following. Pay–per–query: a payment is required to have access to data. Pay–per–impression: a payment is required to have a link displayed. Pay–per–click : a payment is required when a given displayed link is clicked. Pay–per–conversion: a payment is required when a conversion (e.g., a transaction) is accomplished.
Now we describe the basic business models in terms of actors and payment scheme (search applications can use more than one basic business model, as we discus below).
Business model 1 : captures the situation in which a user needs to access data of a content service provider. The actors are a user and a content service provider, while the payment scheme is pay–per–query. Exactly, the user pays an amount of money per access to data to the content service provider. In Zillow, a real estate search engine, a user, who wants to buy a house, should enter the city as an input, for example San Francisco. Zillow returns a list of houses with related information. If the user wants to obtain more details on houses and/or wants to make an offer for a purchase, she must register and pay Zillow. Some variations (e.g., pay–per–thousands) include the case in which a user pays a given amount of money for a given amount of accesses. This business model can be applied also when a content integrator acts in the place of the user.
Business model 2 : captures the situation in which a user makes a search on an integrated content and advertising service provider. The actors are a user, an integrated content and advertising service provider, and some advertisers, while the payment scheme is pay–per–click. Exactly, the integrated content and advertising service provider displays contents and advertisement and, when the user clicks on an ad, the corresponding advertiser pays a given amount of money to the service provider. Google and its advertising service provider AdWords have this business model. If a user enters a keyword, for example flights to Milan, the search engine returns a list of organic links, as airlines sites, and some ads, for example content service providers for hotels (e.g., Booking.com). When a user clicks on one of the ads the related advertiser pays Google.
Business model 3 : captures the same situation of the
previous business model except that the content service
provider uses an external advertising service provider. The
actors are a user, a content service provider, an
advertising service provider, and some advertisers, while the
payment scheme is pay–per–click. Exactly, the content service
provider displays contents it generates and the
advertisement generated by the advertising service provider. When
the user clicks a sponsored link, the corresponding
advertiser pays a given amount of money to the advertising
service provider that, in its turn, pays a ratio to the content
service provider. Vivisimo [
Business model 4 : captures the situation in which a user
searches for information to make a conversion and no
advertisement is involved. The actors are a user and a
content service provider, while the payment scheme is pay–per–
conversion. Exactly, when the user has the conversion (e.g.,
a purchase), she pays a given amount of money to the
content service provider. This is the business model used by
Expedia [
Business model 5 : captures the situation in which a user searches for information to make a conversion and only advertisement is involved. The actors are a user, an advertising service provider, and some advertisers, while the payment scheme is pay–per–conversion. Exactly, when the user has the conversion (e.g., a purchase), the advertiser pays a given amount of money to the advertising service provider. Jellyfish uses this business model. We assume that the user wants to buy a pair of shoes and she inserts ‘sneakers’ as keyword. Jellyfish returns a number of products consistent with the search. If the user decides to buy the product, the seller pays Jellyfish.
Actors may use more than one of the above business
models. An example is Tripadvisor [
Essentially two general microeconomic models apply to
the previous business models: pricing models and auction
models. Both models are based on mathematical
optimization theory and, specifically, on game theory [
In online search applications, auctions are used by
advertising service providers also for deciding which ads to display.
Different kinds of online advertisement can be used [
We describe the general model of an auction for advertising. An auction M is defined as a tuple
M = hA, X, hΘaia∈A, f, hpaia∈Ai where A = a1, . . . , am is the set of advertisers; X is the set of possible allocations of ads on the web page, where an allocation x defines which ads are displayed by the advertising service provider and in which order; Θa is the set of possible bids that advertiser a can submit to the advertising service provider, usually Θa = R+; f : (Θa1 × · · · × Θam) → X is the social choice function, i.e., given the bids submitted by all the advertisers, the social choice function determines the allocation; pa is the payment rule defining the payment of advertiser a. Essentially, an auction puts in competition all the advertisers that are interested in being displayed for the same query. In the case of Google and AdWords, advertisers register their ads for a given set of keywords and, every time a user searches for such keywords, an auction among the registered advertisers is carried out.
The most studied auctions in literature are efficient
auctions, defined as auctions in which f returns the allocation
that maximize the sum of the bids of displayed ads.
Different rules pa can be found. The most known, when there
is only one resource to allocate (e.g., a single banner or a
single ad slot), are the first price auction, in which each
advertiser pays an amount of money equal to its bid, and the
second price auction, in which advertiser pays an amount
of money equal to the second highest bid. Generalizations
of them, for the case in which the resources to allocate are
more than one, are the generalized first price (GFP) and the
generalized second price (GSP). The GFP is the first auction
mechanism adopted by Overture in 1997 [
Another auction model for scenarios with multiple resources is the Vickrey–Clarke–Groves (VCG) auction. Its payment rule is similar to the GSP’s one, but it presents better microeconomic properties.
When the pay–per–click payment scheme is used (this is the most frequent case), refinements of these auction models are required. More precisely, each ad is associated with a click probability (denoted by qa and estimated by the advertising service provider) that can depend on the user’s search (e.g., the searched keywords), the specific ad, the position in which the ad is displayed, and the other displayed ads. Usually, to have a better targeted advertisement, a user model in which the user scans the ads from the top to the bottom, is considered. 3.
The federated search engine paradigm is based on the possibility for users to make multi–domain queries that are decomposed in multiple single–domain queries that are addressed to a domain–specific content service provider. An FSE is essentially a more sophisticated content integrator that exploits (and integrates) existing actors (those described in Section 2.1). In our mind, different instances of FSEs are possible. The organization of each one strictly depends on the specific application. Our attempt is the design of a reference scenario, specifying actors and their interaction, that can be applied to every instance of FSE. On the basis of this scenario, we design our business model.
Reference scenario. The scenario, depicted in Fig. 1, is characterized by the following actors: a user, the FSE, m content service providers, k advertising service providers, h integrated content and advertising service providers, and some advertisers.
In this scenario, a user inserts into the FSE a multi– domain query composed by n keywords Q1 + · · · + Qn. The FSE decomposes the multi–domain query into single–domain queries and addresses each of them to the pertaining content service providers and/or advertising service providers and/or integrated content and advertising service providers. For example, keyword Q1 composes the single–domain query of the first integrated content and advertising service provider; it is also communicated to the first content service provider whose single–domain query is composted by keyword Q1, Q2, and Q3. Each service provider communicates to the FSE its results. If it is a content service provider, it communicates its organic search results and information to combine them in an effective way; if it is an advertising content service provider, it communicates its ads and information to merge them in an efficient way; if it is an integrated content and advertising service provider, it communicates data and information about both organic search results and ads. When the FSE receives the results from all the service providers, it integrates the organic search results in an interrelated way and merges the ads lists. Then it displays them to the user.
Requirements. The above scenario requires an intricate business model due to the large number of actors. We define three main requirements for the business model.
Heterogeneity: the business model must integrate different (heterogeneous) basic business models (typically, those described in Section 2.1), adopting, for each actor, the most appropriate one.
Redistribution: the business model must assure (by means of revenue redistribution) that every actor, that takes part to the FSE’s activity, receives an appropriate monetary incentive.
Flexibility: the business model must be (flexibly) tailored according to the specific online search application.
Model design. In order to satisfy the above requirements, we design a business model that combines some basic business models described in Section 2.1 with a new business model. The heterogeneity is addressed by allowing the coexistence of multiple basic business models. More precisely, we expect that the interaction between FSE and the other actors will be defined as follows: • when FSE uses a content service provider to have access to data, the payment scheme is pay–per–query and therefore business model 1 is used; • when FSE uses an advertising service provider, the payment scheme is pay–per–click or pay–per–conversion and therefore business models 3 or 5 is used; • when FSE uses an integrated content and advertising service provider, the payment scheme is pay–per–click or pay–per–conversion and therefore business models 3 or 5 is used.
The above combination of business models does not address the redistribution requirement, not assuring all the actors to receive a monetary incentive to participate to the FSE’s activity. The crucial issue concerns the merge of multiple integrated content and advertising service providers. The above business models prescribe that the advertiser whose ad has been clicked pays the service provider to which it is registered and the service provider gives a part of the revenue to the FSE. According to business model 3, all the ads generated by the advertising service provider must be displayed, but this is not possible when many service providers are used due to space limitation on the web page. In addition, the advertisement of one provider could result much more pertinent to the queries, affecting negatively the click probabilities of the advertisement of the other providers. As a result, this business model does not assure that all the service providers receive a monetary incentive to take part to the integration, therefore a provider could reject it. Furthermore, we should grant that an integrated content and advertising service provider gains more than content service providers, otherwise it would change the business model, providing only contents. What we need is to guarantee that: • when a user clicks on an ad, the payment must be redistributed over all the involved actors assuring that each actor receive the appropriate monetary incentive to take part to the FSE’s activity.
The appropriateness of the monetary incentives is defined by means of constraints (on the basis of commercial contracts) that are considered in the definition of the microeconomic model, e.g., assuring a given (minimal) revenue to each provider. Essentially, we assume that the revenue of each actor involved in the FSE’s activity will be composed of a minimum fixed amount of money from each query plus a part that depends on the specific displayed ads.
The flexibility requirement can be addressed by allowing the change of the actors and their interactions. This requirement can be directly addressed by designing a flexible microeconomic mechanism.
Example. We report now an example, depicted in Fig. 2, of future application of FSE. The user Valentina is interested in planning her summer holiday in San Francisco. She wants to book flights from/to Milano to/from San Francisco, and she wants to find an hotel and few restaurants in San Francisco. Moreover, Valentina has decided to do bungee jumping as extreme experience during the holiday, and she wants to find a place where doing it. To obtain all the information she needs to plan her holiday, Valentina makes a multi–domain query composed by the following keywords: • Q1 date of arrival: August 6–th 2011; • Q2 date of departure: August 11–th 2011; • Q3 the transfer she prefers: airplane; • Q4 the city from which she departs: Milano; • Q5 the activity she wants to do: bungee jumping; • Q6 the preferred date in which doing the activity: August 10–th 2011; • Q7 where she wants to go: San Francisco.
The FSE addresses the single–domain queries to the
domainspecific service providers as follows:
• to the advertising service provider specific for hotels
(e.g., Booking), the FSE addresses a single query
composed by August 6–th 2011, August 11–th 2011, and
San Francisco;
• to the content service provider specific for transport
(e.g., Lufthansa website [
The aim of this section is the design of a suitable microeconomic model to determine the appropriate payment for every involved actor. As discussed in the previous section, the proposed business model for the FSE involves a number of basic business models described in Section 2.1 and microeconomic models described in Section 2.2. In addition, specifically for the FSE, we need a novel microeconomic model to capture the integration of the advertisement and to find the appropriate redistribution. This model must determine the optimal payments between the FSE and all the advertising service providers.
We resort to auction models with redistribution schemes. Our model extends the models described in Section 2.2. In order to integrate different sources of ads and make it in efficient way, the FSE needs to have all the information about the ads (i.e., the qualities and the values). Otherwise, the FSE would not be in the position to target at best the ads for the user and could not extract the maximum revenue from the advertisement (e.g., without information on the ads, the FSE could display ads whose click probabilities are not the largest ones). The resulting auction model (where the FSE is an auctioneer and the advertising service providers are the bidders) prescribes that the bidders submit the qualities of the ads in addition to the values.
Model definition. The formal microeconomic model is a tuple:
M = hS, A, X, hΘsis∈S, f, hpsis∈Si where S = s1, . . . , sn is the set of advertising service providers (included integrated content and advertising service providers), A = a1, . . . , am is the set of advertisers; X is the set of possible allocations, where an allocation x defines which ads are displayed by the FSE and in which order; Θs is the set of possible combination of value and quality, one for each ad, that advertising service provider s can communicate to the FSE; f : (Θs1 × · · · × Θsn ) → X is the social choice function, i.e., given the values and qualities communicated by all the advertising service providers, the social choice function determines the allocation; ps is the payment rule of advertising service provider s. In addition, we define ts as the minimal revenue the FSE must give to actor s according to a given contract and rs as the redistributed revenue for s. The total revenue of s is defined as θs − pa + rs.
Requirements. We state the microeconomic
requirements. Some of these are the classical ones [
Individual rationality: the monetary revenue expected by each actor (except the FSE) is non–negative.
Weak budget balance: the monetary revenue expected by the FSE is non–negative.
Incentive compatibility: no actor can gain more by misreporting its true valuation (in the case of advertising, qualities and the values of their ads).
While the first two requirements are obvious, the third one may be not. This last requirement is necessary for the stability of the market. In absence of this requirement, the bids of the actors can fluctuate during time, reducing the revenue for the actors. An additional classical microeconomic requirement, needed to extract the maximum revenue from the auction, is:
Allocative efficiency: the chosen allocation maximizes the cumulative expected revenue.
Due to the business model defined in the previous section, we need to introduce two additional requirements:
Redistribution: the revenue must be shared in some way over the actors without violating the above requirements.
Flexibility: the microeconomic model must work with potentially different constraints due to different contracts.
Model design. In order to satisfy the above
requirements, we design M (in terms of f and ps) as an extension of
the VCG mechanism (it is the unique mechanism satisfying
the requirements [
Phase 1. The social choice function is defined as: f (θ) = arg max X θs(x)
x s the VCG payments are defined as: ps(θ) = X θj(f (θ−s)) − X θj(x).
j6=s j6=s where θ = (θs1 , . . . , θsn ) is the set of communicated combinations of values and qualities and θ−s is the set of communicated combinations of values and qualities except the ones communicated by service provider s.
We define in addition:
V CG(θ) = X ps(θ).
s Phase 2. In the case the FSE is a private entity and the redistribution must be the minimum, each actor receives exactly rs = ts. In the case the FSE is a no–profit entity, the computation of the redistributions is more complicated. (Redistribution cannot be defined arbitrarily, otherwise the above requirements would not be satisfied.) Call π a priority over the actors. The redistribution to s is: rsπ(θ−s) = θms′∈iΘns{V CG(θs′, θ−s) − X riπ(θi) −
X ti}
π(i)<s
π(i)>s
where θs′ is a possible combination of values and qualities
communicated by service provider s, π(i) < s denotes the
bidders i that precede s in π, and π(i) > s denotes the
bidders i that follow s in π. This redistribution scheme
assures that the redistributed revenue is the maximum one,
as shown in [
Properties. First, we need to report an impossibility
result. The above auction model determines payments
independently of the actual ads clicked by the user and these
payments cannot be imposed by a pay–per–click scheme.
As shown in [
Example. We consider the running example described in Section 3 and we suppose that the integrated content and advertising service provider s1 communicates the ad a1 to the FSE, the advertising service provider for restaurants s2 communicates ad a2, and the advertising service provider for hotels s3 communicates the ad a3. The products between the values and the qualities of these ads follow: θs1 = 0.4, θs2 = 0.45, and θs3 = 0.2. Moreover, we suppose that the FSE has a contract with each content service provider that establishes how much the FSE has to pay them for each query. The FSE has to pay the content service provider for transport $0.03 per query, and the one for activity $0.05 per query. Since the integrated content and advertising service provider must not have incentives to communicate only its organic search results, i.e., it is not motivated to behave as a content service provider, the FSE has to guarantee it a revenue of at least $0.05, i.e., max{$0.03, $0.05}. Thus, we find out that the sum of the expected payments received by the FSE is $0.4 per query, and that the surplus it can redistribute is equal to $0.32. We consider that the priority π is: the integrated content and advertising service provider for restaurants, the advertising service provider for restaurants, and the advertising service provider for hotels. Applying the redistribution mechanism we propose, the FSE redistributes only to the integrated content provider a value of $0.12.
the merged ads list. Moreover we would like to understand how to target at best the displayed ads for the specific user that has done the search. To reach this goal we have to accomplish two tasks. First, we have to deeply investigate the different ways in which ads belonging to different lists can be merged together depending on the search that has been done, i.e., the problem is which ads to select. Second, we have to define multiple different user models, to capture the interest level of the user in the ads and how she looks at them, i.e., the problem is to understand how to display at best the ads given the model of the user that has made the search. There is also an interesting future search direction related to integrated content and advertising service providers and content service providers that display ads provided by an advertising service provider. In this case, the organic search results and the ads list can contain the same links. Obviously, displaying such links in both the results lists is not the most efficient solution. We need to design a new business model that defines the best strategy that these service providers must adopt in such a situation.