Adadsence

DesigningaRevenueMechanismforFederatedSearchEnginesLauraBonettiDEI,PolitecnicodiMilanopiazzaLeonardodaVinciMilano,Italylaura.
bonetti@mail.
polimi.
itSoaCeppiDEI,PolitecnicodiMilanopiazzaLeonardodaVinciMilano,Italyceppi@elet.
polimi.
itNicolaGattiDEI,PolitecnicodiMilanopiazzaLeonardodaVinciMilano,Italyngatti@elet.
polimi.
itABSTRACTFederatedsearchenginesconstituteanewclassofsearchcomputingparadigmswherebyamulti–domainqueryisde-composedinanumberofsingle–domainqueries,eachoneaddressedbyadomain–speciccontentserviceprovider.
Theparadigmprovidesanumberofadvantages,inparticu-larthepossibilitytodiscovermorepertinentinformationbyscouringthedeepWebandtondautomaticallycorrelationsamongtheserviceproviders'results.
Inourwork,wefocusonthedesignofarevenuemechanismforsuchparadigm.
Thistask,althoughbeingofextraordinaryimportance,hasnotreceivedenoughattentionintheliteraturesofar.
Inparticular,inthispaperwedescribearevenuemechanismintermsofbusinessmodel,specifyingwhopaysandwhen,andmicroeconomicmodel,specifyinghowtheoptimalpaymentcanbecomputed.
Futhermore,wediscussitsproperties.
CategoriesandSubjectDescriptorsJ.
4[SocialandBehavioralSciences]:Economics;H.
3.
5[OnlineInformationServices]:CommercialServicesGeneralTermsDesign,EconomicsKeywordsOnlineAdvertising,FederatedSearchEngines,RevenueMech-anisms,Microeconomics1.
INTRODUCTIONThemaingeneral–purposesearchenginescrawltheWebandindexWebpages,ndingthebestpagesforeachspeciclistofkeywordswithgoodprecision.
However,theso–calleddeepWebcontainsinformationthatislargelymorevaluablethantheonethatacurrentgeneral–purposesearchenginecandiscover.
ThedevelopmentofnewsearchingparadigmsabletoaddressmorecomplexsearchesthanthoseaddressedPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationontherstpage.
Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecicpermissionand/orafee.
ThisarticlewaspresentedattheworkshopVeryLargeDataSearch(VLDS)2011.
Copyright2011.
tothecurrentsearchenginesandtodiscoverdeeperinforma-tioniscurrentlyoneofthemostinterestingchallengesinthesearchcomputingeld.
Currently,theemergingparadigmisbasedonthecombinationofamulti–domainqueryap-proachwiththeintegrationofheterogeneousdatasourcescapabletoscourthedeepWeb.
Thishasresultedinanewgenerationofsearchparadigms,calledfederatedsearchen-gines(FSEs),thatintegratesearchresultsfromheteroge-neousdomain–speciccontentserviceproviders[20].
Considerforinstanceauserthatsearchesforarestaurantclosetoagivenhotelinagivencity.
General–purposesearchenginesallowtheusertomakeexclusivelysingle–domainqueriesonrestaurantsorhotels.
Then,theusermustman-uallyscourtheresultsofthequeryonrestaurantandofthequeryonhoteltondarestaurantandanhotelclosetogether.
Instead,allowingausertomakemulti–domainqueries,theuserneedstomakeonlyasinglequeryinwhichshespeciesalltheeldsofthesearch.
Theresultssheob-tainscontainbothhotelsandrestaurantsthataredisplayedinawaythathelpstheusertoselecttheclosestones.
WhilethescienticcommunityhasbeenworkingonthedevelopmentofFSEenablingtechnologiesforsomeyears[4],theproblemofdesigningasuitablerevenuemechanismhasnotyetreceivedenoughattention.
ThisissueisofparamountimportanceforthesuccessoftheFSEparadigm.
Inthepresentpaper,wefocusonthisproblem.
Thestartingpointofourworkistheanalysisoftherevenuemechanismscur-rentlyadoptedinthesearchapplications.
Arevenuemech-anismiscomposedbyabusinessmodel,thatspecieswhopaysandwhen,andbyamicroeconomicmodel,thatspeci-eshowtheoptimalpaymentcanbecomputed.
Bothmod-elsplayacrucialroleinthedesignofasuccessfulrevenuemechanismanddependoneachother,e.
g.
,insightsfromthemicroeconomicscanbeusedtodesignthebusinessmodelthatallowsonetomaximizetherevenue.
Sincemanydif-ferentrevenuemechanismsarecurrentlyused,weproposeaclassication,emphasizingactorsandpaymentschemes.
Then,wefocusontheFSEscenarios.
Theyinvolvemanyactorsandrequirethedesignofanewrevenuemechanism.
ThisisbecauseexistingrevenuemechanismsarenotabletointegratedierentadvertisingservicesandtoprovidetheactorsinvolvedintheFSE'sactivitywithappropriatemon-etaryincentives.
Weproposeanad–hocrevenuemechanism,statinginitiallyitsrequirementsandsubsequentlydesigningabusinessmodelandamicroeconomicmodelthatsatisfytherequirements.
Bothmodelsextendtheexistingones.
WealsoreportanexampleofapplicationandsomeverypreliminaryexperimentalresultswithYahoo!
dataset.
Thepaperisstructuredasfollows.
Inthenextsection,weclassifytheexistingrevenuemechanismsforsearchap-plications.
InSection3,wepresentourbusinessmodelforFSEs,while,inSection4,wedescribethemicroeconomicmodel.
Section5concludesthepaper.
2.
REVENUEMECHANISMSFORSEARCHAPPLICATIONSWeprovideaclassicationofthecurrentlyadoptedrev-enuemechanismsintheattempttoprovideaclassicationintermsofbusinessmodelsandmicroeconomicmodels.
2.
1BusinessModelsAbusinessmodelcanbecharacterizedintermsofactorsandpaymentschemes.
Actorscanbeclassiedasfollows.
User:heraimistosearchforcontents/advertisement.
Advertiser:itsaimistoappearinsponsoredlinksorbannersdisplayedtotargetedusers.
Contentserviceprovider:itsaimistoproducealistofcontents(organicsearch),givenaninputprovidedbytheuser.
Theinputcanbealistofkeywordsoramorestruc-turedquery.
Contentsareusuallyextractedfromdatabases.
AsinthecaseofZillow[26],thatprovidescontentsabouthousestorentandsell,andofExpedia[10],thatgiveslinks(e.
g.
,ightsandrooms)relatedtotourism.
Contentscanbedisplayedbytheprovideritselforbyanotheractor.
Ad-vertisingserviceprovider:itsaimistoproducealistofads(sponsoredlinks)thattargetatbesttheusergivenaninput.
Theinputcanbealistofkeywordsoralistofcontents(e.
g.
,webpages)anditisusedtotargettheads,asinthecaseofAdSence[1](i.
e.
,Google'sadvertisingserviceprovider[12]).
Adscanbedisplayedbyanotheractorthatusestheservice.
Integratedcontentandadvertisingserviceprovider:itsaimistoproducealistofcontentsandalistofads.
Thelistofadsischosentotargetatbesttheuser.
Theinputisalistofkeywords,e.
g.
,inthecaseofGooglethatdisplaysor-ganiclinksandsponsoredlinksusingAdWords[2].
Contentintegrator:itsaimistointegratetheorganicsearchresultsofdierentcontentserviceproviders.
Verysimpleexam-plesaremetasearchengines,e.
g.
,Ecosia[7],thatintegratescontentfromYahoo!
[25]andBing[3],andIxquick[14]thatuseslinksfromGoogle,Yahoo!
,Exalead[9],Wikipedia[24]andalotofothers.
Thepaymentschemedeneswhen(usuallyintermsofevents)anactormustpayanotheractor.
Thepaymentschemesusuallyadoptedinsearchapplicationsarethefol-lowing.
Pay–per–query:apaymentisrequiredtohaveac-cesstodata.
Pay–per–impression:apaymentisrequiredtohavealinkdisplayed.
Pay–per–click:apaymentisrequiredwhenagivendisplayedlinkisclicked.
Pay–per–conversion:apaymentisrequiredwhenaconversion(e.
g.
,atransaction)isaccomplished.
Nowwedescribethebasicbusinessmodelsintermsofac-torsandpaymentscheme(searchapplicationscanusemorethanonebasicbusinessmodel,aswediscusbelow).
Businessmodel1:capturesthesituationinwhichauserneedstoaccessdataofacontentserviceprovider.
Theac-torsareauserandacontentserviceprovider,whilethepaymentschemeispay–per–query.
Exactly,theuserpaysanamountofmoneyperaccesstodatatothecontentser-viceprovider.
InZillow,arealestatesearchengine,auser,whowantstobuyahouse,shouldenterthecityasaninput,forexampleSanFrancisco.
Zillowreturnsalistofhouseswithrelatedinformation.
Iftheuserwantstoobtainmoredetailsonhousesand/orwantstomakeanoerforapur-chase,shemustregisterandpayZillow.
Somevariations(e.
g.
,pay–per–thousands)includethecaseinwhichauserpaysagivenamountofmoneyforagivenamountofac-cesses.
Thisbusinessmodelcanbeappliedalsowhenacontentintegratoractsintheplaceoftheuser.
Businessmodel2:capturesthesituationinwhichausermakesasearchonanintegratedcontentandadvertisingserviceprovider.
Theactorsareauser,anintegratedcon-tentandadvertisingserviceprovider,andsomeadvertisers,whilethepaymentschemeispay–per–click.
Exactly,theintegratedcontentandadvertisingserviceproviderdisplayscontentsandadvertisementand,whentheuserclicksonanad,thecorrespondingadvertiserpaysagivenamountofmoneytotheserviceprovider.
GoogleanditsadvertisingserviceproviderAdWordshavethisbusinessmodel.
Ifauserentersakeyword,forexampleightstoMilan,thesearchenginereturnsalistoforganiclinks,asairlinessites,andsomeads,forexamplecontentserviceprovidersforhotels(e.
g.
,Booking.
com).
WhenauserclicksononeoftheadstherelatedadvertiserpaysGoogle.
Businessmodel3:capturesthesamesituationofthepre-viousbusinessmodelexceptthatthecontentservicepro-viderusesanexternaladvertisingserviceprovider.
Theactorsareauser,acontentserviceprovider,anadvertis-ingserviceprovider,andsomeadvertisers,whilethepay-mentschemeispay–per–click.
Exactly,thecontentserviceproviderdisplayscontentsitgeneratesandtheadvertise-mentgeneratedbytheadvertisingserviceprovider.
Whentheuserclicksasponsoredlink,thecorrespondingadver-tiserpaysagivenamountofmoneytotheadvertisingser-viceproviderthat,initsturn,paysaratiotothecontentserviceprovider.
Vivisimo[23]hasthisbusinessmodel.
Ifauserentersakeyword,forexamplehotelsinSanFrancisco,thesearchenginereturnsalistoforganiclinks,ashotelweb-sites,andsomeads,forexamplebookingsearchenginesasEdreams[8]andTrivago[22].
TheselinkscomefromGoogleAdSense.
WhenauserclicksononeoftheseadstherelatedadvertiserpaysAdSenceforthereceivedclickandVivisimoreceivesapercentageofthispayment.
Businessmodel4:capturesthesituationinwhichausersearchesforinformationtomakeaconversionandnoad-vertisementisinvolved.
Theactorsareauserandacon-tentserviceprovider,whilethepaymentschemeispay–per–conversion.
Exactly,whentheuserhastheconversion(e.
g.
,apurchase),shepaysagivenamountofmoneytothecon-tentserviceprovider.
ThisisthebusinessmodelusedbyExpedia[10].
Weassumethattheuserwantstobookahotel.
Heintroducesthecity,suchasSanFrancisco,andchoosesadate,forexample,fromAugust6–thtoAugust11–th.
Expediareturnsfreerooms.
Iftheuserdecidestobookaroomthesitechargesareservationfee.
Businessmodel5:capturesthesituationinwhichausersearchesforinformationtomakeaconversionandonlyad-vertisementisinvolved.
Theactorsareauser,anadvertisingserviceprovider,andsomeadvertisers,whilethepaymentschemeispay–per–conversion.
Exactly,whentheuserhastheconversion(e.
g.
,apurchase),theadvertiserpaysagivenamountofmoneytotheadvertisingserviceprovider.
Jel-lyshusesthisbusinessmodel.
Weassumethattheuserwantstobuyapairofshoesandsheinserts'sneakers'askeyword.
Jellyshreturnsanumberofproductsconsistentwiththesearch.
Iftheuserdecidestobuytheproduct,thesellerpaysJellysh.
Actorsmayusemorethanoneoftheabovebusinessmod-els.
AnexampleisTripadvisor[21]thatmergesbusinessmodel3andbusinessmodel5.
Ausercansearchforhotels,ights,restaurantsandactivities.
WeassumethattheuserwantstondaroominSanFranciscofromAugust6–thtoAugust11–th.
Tripadvisorreturnshotelswithafreeroominthespeciedperiod.
Theusedbusinessmodelisbusinessmodel5,i.
e.
,iftheuserbooksaroom,Tripadvisorreceivesapaymentfromtheadvertiser.
Moreover,foreachsearch,adsarealsodisplayed.
Inthiscase,Tripadvisoralsoadoptsbusinessmodel3.
2.
2MicroeconomicModelsEssentiallytwogeneralmicroeconomicmodelsapplytothepreviousbusinessmodels:pricingmodelsandauctionmodels.
Bothmodelsarebasedonmathematicaloptimiza-tiontheoryand,specically,ongametheory[11].
Pricingmodelsdenethebestpriceatwhichaservicecanbesoldandtheyareusuallybasedonoligopolies[11].
Thesemodelscapturestaticsituations(e.
g.
,inbusinessmodel1thepricerequiredbythecontentserviceproviderisxed)andtheassociatedoptimizationproblemissolvedoine.
Auctionmodelsdenehowsomeresourcesareallocatedandhowmuchtheplayerwhoreceivesaresourcemustpay.
Thesemodelscapturedynamicsituations(e.
g.
,inbusinessmodel3theadsdisplayeddependonthespecicsearchoftheuserandthebudgetoftheadvertisers)andtheassociatedop-timizationproblemissolvedonline.
Thefactthatauctionmodelsmustbesolvedonlinemakesthestudyofthesemod-elsmoreinteresting.
Duetothiswelimitoursurveytothem.
Inonlinesearchapplications,auctionsareusedbyadver-tisingserviceprovidersalsofordecidingwhichadstodisplay.
Dierentkindsofonlineadvertisementcanbeused[16].
Themainonesarethefollowing.
Banneradsordisplayads:anadisalongthinstripofinformationthatmaybeeitherstaticormayincludeahyperlinktotheadvertiser'swebpage;richmedia:thebanneradisenrichedbystreamingvideo,audio,andinteractivitythatcanallowuserstoviewandtointeractwithproductsandservices;sponsoredsearch:advertiserspaytobelistedandlinkedwhenaspecicwordorphraseissearchedbyauser.
Wedescribethegeneralmodelofanauctionforadvertis-ing.
AnauctionMisdenedasatupleM=A,X,Θaa∈A,f,paa∈AwhereA=a1,amisthesetofadvertisers;Xisthesetofpossibleallocationsofadsonthewebpage,whereanal-locationxdeneswhichadsaredisplayedbytheadvertisingserviceproviderandinwhichorder;Θaisthesetofpossiblebidsthatadvertiseracansubmittotheadvertisingserviceprovider,usuallyΘa=R+;f:(Θa1Θam)→Xisthesocialchoicefunction,i.
e.
,giventhebidssubmittedbyalltheadvertisers,thesocialchoicefunctiondeterminestheallocation;paisthepaymentruledeningthepaymentofadvertisera.
Essentially,anauctionputsincompetitionalltheadvertisersthatareinterestedinbeingdisplayedforthesamequery.
InthecaseofGoogleandAdWords,advertis-ersregistertheiradsforagivensetofkeywordsand,everytimeausersearchesforsuchkeywords,anauctionamongtheregisteredadvertisersiscarriedout.
Figure1:ReferencescenarioforaFSE'sinstance(forsimplicity,usersandadvertisersareomitted).
Themoststudiedauctionsinliteratureareecientauc-tions,denedasauctionsinwhichfreturnstheallocationthatmaximizethesumofthebidsofdisplayedads.
Dif-ferentrulespacanbefound.
Themostknown,whenthereisonlyoneresourcetoallocate(e.
g.
,asinglebannerorasingleadslot),aretherstpriceauction,inwhicheachad-vertiserpaysanamountofmoneyequaltoitsbid,andthesecondpriceauction,inwhichadvertiserpaysanamountofmoneyequaltothesecondhighestbid.
Generalizationsofthem,forthecaseinwhichtheresourcestoallocatearemorethanone,arethegeneralizedrstprice(GFP)andthegeneralizedsecondprice(GSP).
TheGFPistherstauctionmechanismadoptedbyOverturein1997[16].
Nowadaysthismechanismisnolongerused,allthemaingeneral–purposesearchengines(e.
g.
,Google)adopttheGSPmechanism[16].
Anotherauctionmodelforscenarioswithmultiplere-sourcesistheVickrey–Clarke–Groves(VCG)auction.
ItspaymentruleissimilartotheGSP'sone,butitpresentsbettermicroeconomicproperties.
Whenthepay–per–clickpaymentschemeisused(thisisthemostfrequentcase),renementsoftheseauctionmodelsarerequired.
Moreprecisely,eachadisassociatedwithaclickprobability(denotedbyqaandestimatedbytheadver-tisingserviceprovider)thatcandependontheuser'ssearch(e.
g.
,thesearchedkeywords),thespecicad,thepositioninwhichtheadisdisplayed,andtheotherdisplayedads.
Usu-ally,tohaveabettertargetedadvertisement,ausermodelinwhichtheuserscanstheadsfromthetoptothebottom,isconsidered.
3.
ABUSINESSMODELFORFEDERATEDSEARCHENGINESThefederatedsearchengineparadigmisbasedonthepossibilityforuserstomakemulti–domainqueriesthataredecomposedinmultiplesingle–domainqueriesthataread-dressedtoadomain–speciccontentserviceprovider.
AnFSEisessentiallyamoresophisticatedcontentintegratorthatexploits(andintegrates)existingactors(thosedescribedinSection2.
1).
Inourmind,dierentinstancesofFSEsarepossible.
Theorganizationofeachonestrictlydependsonthespecicapplication.
Ourattemptisthedesignofaref-erencescenario,specifyingactorsandtheirinteraction,thatcanbeappliedtoeveryinstanceofFSE.
Onthebasisofthisscenario,wedesignourbusinessmodel.
Referencescenario.
Thescenario,depictedinFig.
1,ischaracterizedbythefollowingactors:auser,theFSE,mcontentserviceproviders,kadvertisingserviceproviders,hintegratedcontentandadvertisingserviceproviders,andsomeadvertisers.
Inthisscenario,auserinsertsintotheFSEamulti–domainquerycomposedbynkeywordsQ1Qn.
TheFSEdecomposesthemulti–domainqueryintosingle–domainqueriesandaddresseseachofthemtothepertainingcon-tentserviceprovidersand/oradvertisingserviceprovidersand/orintegratedcontentandadvertisingserviceproviders.
Forexample,keywordQ1composesthesingle–domainqueryoftherstintegratedcontentandadvertisingserviceprovider;itisalsocommunicatedtotherstcontentserviceproviderwhosesingle–domainqueryiscompostedbykeywordQ1,Q2,andQ3.
EachserviceprovidercommunicatestotheFSEitsresults.
Ifitisacontentserviceprovider,itcom-municatesitsorganicsearchresultsandinformationtocom-binetheminaneectiveway;ifitisanadvertisingcontentserviceprovider,itcommunicatesitsadsandinformationtomergetheminanecientway;ifitisanintegratedcontentandadvertisingserviceprovider,itcommunicatesdataandinformationaboutbothorganicsearchresultsandads.
WhentheFSEreceivestheresultsfromalltheserviceproviders,itintegratestheorganicsearchresultsinanin-terrelatedwayandmergestheadslists.
Thenitdisplaysthemtotheuser.
Requirements.
Theabovescenariorequiresanintricatebusinessmodelduetothelargenumberofactors.
Wedenethreemainrequirementsforthebusinessmodel.
Heterogeneity:thebusinessmodelmustintegratedier-ent(heterogeneous)basicbusinessmodels(typically,thosedescribedinSection2.
1),adopting,foreachactor,themostappropriateone.
Redistribution:thebusinessmodelmustassure(bymeansofrevenueredistribution)thateveryactor,thattakesparttotheFSE'sactivity,receivesanappropriatemonetaryin-centive.
Flexibility:thebusinessmodelmustbe(exibly)tailoredaccordingtothespeciconlinesearchapplication.
Modeldesign.
Inordertosatisfytheaboverequire-ments,wedesignabusinessmodelthatcombinessomebasicbusinessmodelsdescribedinSection2.
1withanewbusinessmodel.
Theheterogeneityisaddressedbyallowingtheco-existenceofmultiplebasicbusinessmodels.
Moreprecisely,weexpectthattheinteractionbetweenFSEandtheotheractorswillbedenedasfollows:whenFSEusesacontentserviceprovidertohaveac-cesstodata,thepaymentschemeispay–per–queryandthereforebusinessmodel1isused;whenFSEusesanadvertisingserviceprovider,thepaymentschemeispay–per–clickorpay–per–conversionandthereforebusinessmodels3or5isused;whenFSEusesanintegratedcontentandadvertisingserviceprovider,thepaymentschemeispay–per–clickorpay–per–conversionandthereforebusinessmodels3or5isused.
Theabovecombinationofbusinessmodelsdoesnotaddresstheredistributionrequirement,notassuringalltheactorstoreceiveamonetaryincentivetoparticipatetotheFSE'sactivity.
Thecrucialissueconcernsthemergeofmultipleintegratedcontentandadvertisingserviceproviders.
Theabovebusinessmodelsprescribethattheadvertiserwhoseadhasbeenclickedpaystheserviceprovidertowhichitisregisteredandtheserviceprovidergivesapartoftherev-enuetotheFSE.
Accordingtobusinessmodel3,alltheadsgeneratedbytheadvertisingserviceprovidermustbedis-played,butthisisnotpossiblewhenmanyserviceprovidersareusedduetospacelimitationonthewebpage.
Inad-dition,theadvertisementofoneprovidercouldresultmuchmorepertinenttothequeries,aectingnegativelytheclickprobabilitiesoftheadvertisementoftheotherproviders.
Asaresult,thisbusinessmodeldoesnotassurethatalltheser-viceprovidersreceiveamonetaryincentivetotakeparttotheintegration,thereforeaprovidercouldrejectit.
Fur-thermore,weshouldgrantthatanintegratedcontentandadvertisingserviceprovidergainsmorethancontentserviceproviders,otherwiseitwouldchangethebusinessmodel,providingonlycontents.
Whatweneedistoguaranteethat:whenauserclicksonanad,thepaymentmustberedistributedoveralltheinvolvedactorsassuringthateachactorreceivetheappropriatemonetaryincentivetotakeparttotheFSE'sactivity.
Theappropriatenessofthemonetaryincentivesisdenedbymeansofconstraints(onthebasisofcommercialcon-tracts)thatareconsideredinthedenitionofthemicroe-conomicmodel,e.
g.
,assuringagiven(minimal)revenuetoeachprovider.
Essentially,weassumethattherevenueofeachactorinvolvedintheFSE'sactivitywillbecomposedofaminimumxedamountofmoneyfromeachqueryplusapartthatdependsonthespecicdisplayedads.
Theexibilityrequirementcanbeaddressedbyallowingthechangeoftheactorsandtheirinteractions.
Thisre-quirementcanbedirectlyaddressedbydesigningaexiblemicroeconomicmechanism.
Example.
Wereportnowanexample,depictedinFig.
2,offutureapplicationofFSE.
TheuserValentinaisinter-estedinplanninghersummerholidayinSanFrancisco.
Shewantstobookightsfrom/toMilanoto/fromSanFrancisco,andshewantstondanhotelandfewrestaurantsinSanFrancisco.
Moreover,Valentinahasdecidedtodobungeejumpingasextremeexperienceduringtheholiday,andshewantstondaplacewheredoingit.
Toobtainallthein-formationsheneedstoplanherholiday,Valentinamakesamulti–domainquerycomposedbythefollowingkeywords:Q1dateofarrival:August6–th2011;Q2dateofdeparture:August11–th2011;Q3thetransfersheprefers:airplane;Q4thecityfromwhichshedeparts:Milano;Q5theactivityshewantstodo:bungeejumping;Q6thepreferreddateinwhichdoingtheactivity:Au-gust10–th2011;Q7whereshewantstogo:SanFrancisco.
TheFSEaddressesthesingle–domainqueriestothedomain-specicserviceprovidersasfollows:totheadvertisingserviceproviderspecicforhotels(e.
g.
,Booking),theFSEaddressesasinglequerycom-posedbyAugust6–th2011,August11–th2011,andSanFrancisco;tothecontentserviceproviderspecicfortransport(e.
g.
,Lufthansawebsite[15]),theFSEaddressesasinglequerycomposedbyAugust6–th2011,August11–th2011,airplane,Milano,andSanFrancisco;tothecontentserviceproviderspecicforactivities(e.
g.
,SanFranciscoTravel[19]),theFSEaddressesasinglequerycomposedbybungeejumping,August10–th2011,andSanFrancisco;totheintegratedcontentandadvertisingserviceprovid-er(e.
g.
,SanFrancisco.
com[17])andtotheadvertisingserviceproviderspecicforrestaurants(e.
g.
,BestofSanFranciscoGuide[18]),theFSEaddressesasinglequerycomposedbySanFrancisco.
Figure2:Anexampleofinteractionamongactors.
4.
AMICROECONOMICMODELFORFED-ERATEDSEARCHENGINESTheaimofthissectionisthedesignofasuitablemicroe-conomicmodeltodeterminetheappropriatepaymentforeveryinvolvedactor.
Asdiscussedintheprevioussection,theproposedbusinessmodelfortheFSEinvolvesanumberofbasicbusinessmodelsdescribedinSection2.
1andmicroe-conomicmodelsdescribedinSection2.
2.
Inaddition,specif-icallyfortheFSE,weneedanovelmicroeconomicmodeltocapturetheintegrationoftheadvertisementandtondtheappropriateredistribution.
ThismodelmustdeterminetheoptimalpaymentsbetweentheFSEandalltheadvertisingserviceproviders.
Weresorttoauctionmodelswithredistributionschemes.
OurmodelextendsthemodelsdescribedinSection2.
2.
Inordertointegratedierentsourcesofadsandmakeitinef-cientway,theFSEneedstohavealltheinformationabouttheads(i.
e.
,thequalitiesandthevalues).
Otherwise,theFSEwouldnotbeinthepositiontotargetatbesttheadsfortheuserandcouldnotextractthemaximumrevenuefromtheadvertisement(e.
g.
,withoutinformationontheads,theFSEcoulddisplayadswhoseclickprobabilitiesarenotthelargestones).
Theresultingauctionmodel(wheretheFSEisanauctioneerandtheadvertisingserviceprovidersarethebidders)prescribesthatthebidderssubmitthequalitiesoftheadsinadditiontothevalues.
Modeldenition.
Theformalmicroeconomicmodelisatuple:M=S,A,X,Θss∈S,f,pss∈SwhereS=s1,snisthesetofadvertisingserviceproviders(includedintegratedcontentandadvertisingserviceproviders),A=a1,amisthesetofadvertisers;Xisthesetofpos-sibleallocations,whereanallocationxdeneswhichadsaredisplayedbytheFSEandinwhichorder;Θsisthesetofpossiblecombinationofvalueandquality,oneforeachad,thatadvertisingserviceproviderscancommunicatetotheFSE;f:(Θs1*···*Θsn)→Xisthesocialchoicefunction,i.
e.
,giventhevaluesandqualitiescommunicatedbyalltheadvertisingserviceproviders,thesocialchoicefunctionde-terminestheallocation;psisthepaymentruleofadvertisingserviceproviders.
Inaddition,wedenetsastheminimalrevenuetheFSEmustgivetoactorsaccordingtoagivencontractandrsastheredistributedrevenuefors.
Thetotalrevenueofsisdenedasθspa+rs.
Requirements.
Westatethemicroeconomicrequire-ments.
Someofthesearetheclassicalones[11].
Individualrationality:themonetaryrevenueexpectedbyeachactor(excepttheFSE)isnon–negative.
Weakbudgetbalance:themonetaryrevenueexpectedbytheFSEisnon–negative.
Incentivecompatibility:noactorcangainmorebymisre-portingitstruevaluation(inthecaseofadvertising,quali-tiesandthevaluesoftheirads).
Whilethersttworequirementsareobvious,thethirdonemaybenot.
Thislastrequirementisnecessaryforthestabil-ityofthemarket.
Inabsenceofthisrequirement,thebidsoftheactorscanuctuateduringtime,reducingtherev-enuefortheactors.
Anadditionalclassicalmicroeconomicrequirement,neededtoextractthemaximumrevenuefromtheauction,is:Allocativeeciency:thechosenallocationmaximizesthecumulativeexpectedrevenue.
Duetothebusinessmodeldenedintheprevioussection,weneedtointroducetwoadditionalrequirements:Redistribution:therevenuemustbesharedinsomewayovertheactorswithoutviolatingtheaboverequirements.
Flexibility:themicroeconomicmodelmustworkwithpo-tentiallydierentconstraintsduetodierentcontracts.
Modeldesign.
Inordertosatisfytheaboverequire-ments,wedesignM(intermsoffandps)asanextensionoftheVCGmechanism(itistheuniquemechanismsatisfyingtherequirements[16]).
Itiscomposedoftwocomputationalphases:intherstphase,aVCGissolvedtodenethelistofadstodisplayandthepaymentswithoutredistribution;inthesecondphase,theredistributioniscomputed.
Phase1.
Thesocialchoicefunctionisdenedas:f(θ)=argmaxxXsθs(x)theVCGpaymentsaredenedas:ps(θ)=Xj=sθj(f(θs))Xj=sθj(x).
whereθ=(θs1θsn)isthesetofcommunicatedcom-binationsofvaluesandqualitiesandθsisthesetofcom-municatedcombinationsofvaluesandqualitiesexcepttheonescommunicatedbyserviceproviders.
Wedeneinaddition:VCG(θ)=Xsps(θ).
Phase2.
InthecasetheFSEisaprivateentityandtheredistributionmustbetheminimum,eachactorreceivesexactlyrs=ts.
InthecasetheFSEisano–protentity,thecomputationoftheredistributionsismorecomplicated.
(Redistributioncannotbedenedarbitrarily,otherwisetheaboverequirementswouldnotbesatised.
)Callπapriorityovertheactors.
Theredistributiontosis:rπs(θs)=minθ′s∈Θs{VCG(θ′s,θs)Xπ(i)sti}whereθ′sisapossiblecombinationofvaluesandqualitiescommunicatedbyserviceproviders,π(i)sdenotesthebiddersithatfollowsinπ.
Thisredistributionschemeassuresthattheredistributedrevenueisthemaximumone,asshownin[13].
Properties.
First,weneedtoreportanimpossibilityresult.
Theaboveauctionmodeldeterminespaymentsin-dependentlyoftheactualadsclickedbytheuserandthesepaymentscannotbeimposedbyapay–per–clickscheme.
Asshownin[5,6],thepay–per–clickschemecannotbeusedwithoutviolatingincentivecompatibilitywhendierentadsourcesareintegrated.
Theuniquepaymentschemewecanuseispay–per–impression.
Theredistributionschemeisguaranteedtobeundominated,i.
e.
,itisnotpossibletoredistributemorerevenuewithoutviolatingtheincentivecompatibilityproperty.
Weexperimentallyevaluatetheav-eragepercentageoftheredistributedrevenuewiththeWeb-scopeA3Yahoo!
dataset.
Thisvalueisabout70%.
Thatis,inmanypracticalcasesitisnotpossibletoredistributealltherevenuetotheserviceproviders.
Wewillexperimen-tallyevaluatetherevenueoftheFSEwithYahoo!
datasetinfuturework.
Example.
WeconsidertherunningexampledescribedinSection3andwesupposethattheintegratedcontentandadvertisingserviceproviders1communicatestheada1totheFSE,theadvertisingserviceproviderforrestaurantss2communicatesada2,andtheadvertisingserviceproviderforhotelss3communicatestheada3.
Theproductsbetweenthevaluesandthequalitiesoftheseadsfollow:θs1=0.
4,θs2=0.
45,andθs3=0.
2.
Moreover,wesupposethattheFSEhasacontractwitheachcontentserviceproviderthatestablisheshowmuchtheFSEhastopaythemforeachquery.
TheFSEhastopaythecontentserviceproviderfortransport$0.
03perquery,andtheoneforactivity$0.
05perquery.
Sincetheintegratedcontentandadvertisingserviceprovidermustnothaveincentivestocommunicateonlyitsorganicsearchresults,i.
e.
,itisnotmotivatedtobehaveasacontentserviceprovider,theFSEhastoguaranteeitarevenueofatleast$0.
05,i.
e.
,max{$0.
03,$0.
05}.
Thus,wendoutthatthesumoftheexpectedpaymentsreceivedbytheFSEis$0.
4perquery,andthatthesurplusitcanredis-tributeisequalto$0.
32.
Weconsiderthatthepriorityπis:theintegratedcontentandadvertisingserviceproviderforrestaurants,theadvertisingserviceproviderforrestaurants,andtheadvertisingserviceproviderforhotels.
Applyingtheredistributionmechanismwepropose,theFSEredistributesonlytotheintegratedcontentprovideravalueof$0.
12.
5.
CONCLUSIONSANDFUTUREWORKSAnewsearchcomputingparadigm,calledfederatedsearchengines,consistsintheintegrationofheterogeneousdomain–specicserviceprovidersabletoscourthedeepWebandndinformationthatthecurrentgeneral–purposesearchenginesarenotabletodiscover.
Intheliterature,alotofworksthatdealwiththisparadigmrecentlyappeared,butnoneofthesestudiesisaboutrevenuemechanismssuitabletoFSEs.
De-signingsucharevenuemechanismisanissueofparamountimportanceforthesuccessofFSEparadigm.
Inthispa-perwehaveinitiallyanalyzedexistingrevenuemechanisms.
Inparticular,wehavedescribedthebusinessmodels,thatspecifywhopaysandwhen,andthemicroeconomicsmod-els,thatspecifyhowtheoptimalpaymentcanbecomputed,thatareadoptedbytheexistingmechanisms.
WepointoutthattheFSErequiresanewandcomplexbusinessmodelandnoneoftheknownmicroeconomicsmodelscanbeusedinourscenario.
Duetothis,wehavefacedtheproblemofdesigninganewheterogeneousandexiblerevenuemech-anismforFSEthatsatisessomedesirablepropertiesandthatallowsforredistributionofFSE'ssurplus.
Ournextstepconsistsindoinganexperimentalevalu-ationofthemechanismwehaveproposedinthispaper.
Thisexperimentalevaluationinvolvesthepresenceofhu-mansthatinteractwithademooftheFSEthatintegratesorganicsearchresultsasdescribedintheSeCoproject,andthatusestherevenuemechanismproposedinthispaperforthemergedadslist.
Moreoverwewouldliketounderstandhowtotargetatbestthedisplayedadsforthespecicuserthathasdonethesearch.
Toreachthisgoalwehavetoaccomplishtwotasks.
First,wehavetodeeplyinvestigatethedierentwaysinwhichadsbelongingtodierentlistscanbemergedtogetherdependingonthesearchthathasbeendone,i.
e.
,theproblemiswhichadstoselect.
Second,wehavetodenemultipledierentusermodels,tocapturetheinterestleveloftheuserintheadsandhowshelooksatthem,i.
e.
,theproblemistounderstandhowtodisplayatbesttheadsgiventhemodeloftheuserthathasmadethesearch.
Thereisalsoaninterestingfuturesearchdi-rectionrelatedtointegratedcontentandadvertisingserviceprovidersandcontentserviceprovidersthatdisplayadspro-videdbyanadvertisingserviceprovider.
Inthiscase,theorganicsearchresultsandtheadslistcancontainthesamelinks.
Obviously,displayingsuchlinksinboththeresultslistsisnotthemostecientsolution.
Weneedtodesignanewbusinessmodelthatdenesthebeststrategythattheseserviceprovidersmustadoptinsuchasituation.
6.
REFERENCES[1]AdSense.
http://www.
google.
com/adsense/.
[2]AdWords.
http://www.
adwords.
google.
it/.
[3]Bing.
http://www.
bing.
com/.
[4]D.
Braga,S.
Ceri,F.
Daniel,andD.
Martinenghi.
Mashingupsearchservices.
IEEEInternetComputing,12(5):16–23,2008.
[5]S.
CeppiandN.
Gatti.
Anautomatedmechanismdesignapproachforsponsoredsearchauctionswithfederatedsearchengine.
InAMEC,pages127–140,2010.
[6]S.
Ceppi,N.
Gatti,andE.
Gerding.
Mechanismdesignforfederatedsponsoredsearchauctions.
InAAAI,2011.
[7]Ecosia.
http://ecosia.
org/.
[8]Edreams.
http://www.
edreams.
it/.
[9]Exalead.
http://www.
exalead.
com/search/.
[10]Expedia.
http://www.
expedia.
it/.
[11]D.
FudenbergandJ.
Tirole.
GameTheory.
1991.
[12]Google.
http://www.
google.
com/.
[13]M.
GuoandV.
Conitzer.
UndominatedVCGredistributionmechanisms.
InAAMAS,pages1039–1046,2008.
[14]Ixquick.
http://www.
ixquick.
com/.
[15]Lufthansa.
http://www.
lufthansa.
com/.
[16]Y.
Narahari,D.
Garg,R.
Narayanam,andH.
Prakash.
GameTheoreticProblemsinNetworkEconomicsandMechanismDesignSolutions.
Springer,February2009.
[17]Restaurantadv.
http://www.
sanfrancisco.
com/restaurants/.
[18]Restaurantint.
http://bestofsanfrancisco.
net/restaurants.
htm.
[19]SanFrancisco.
http://www.
sanfrancisco.
travel/.
[20]SeCo.
http://www.
search-computing.
it/s.
[21]Tripadvisor.
http://www.
tripadvisor.
it/.
[22]Trivago.
http://www.
trivago.
it/.
[23]Vivisimo.
http://www.
sedoparking.
com/vivisimo.
it.
[24]Wikipedia.
http://it.
wikipedia.
org/.
[25]Yahoo!
http://www.
yahoo.
com/.
[26]Zillow.
http://www.
zillow.
com/.