position

InternationalJournalofIndustrialOrganization

25(2007)1163–1178

www.elsevier.com/locate/econbase

Positionauctions☆HalR.Varian

UCBerkeley,UnitedStates

Received10January2006;receivedinrevisedform1September2006;accepted3October2006

Availableonline16November2006

Abstract

IanalyzetheequilibriaofagamebasedontheadauctionusedbyGoogleandYahoo.ThisauctioniscloselyrelatedtotheassignmentgamestudiedbyShapley–Shubik,Demange–Gale–SotomayerandRoth–Sotomayer.However,duetothespecialstructureofpreferences,theequilibriaoftheadauctioncanbecalculatedexplicitlyandsomeknownresultscanbesharpened.IprovidesomeempiricalevidencethattheNashequilibriaofthepositionauctiondescribethebasicpropertiesofthepricesobservedinGoogle'sadauctionreasonablyaccurately.

©2006ElsevierB.V.Allrightsreserved.

JELclassification:D44;M3

Keywords:Auctions;Onlineadvertising;Two-sidedmatching

Searchengineadvertisinghasbecomeabigbusiness,withthecombinedrevenueofindustryleadersYahooandGoogleexceeding$11billionin2005.Nearlyalloftheseadsaresoldviaanauctionmechanism.

Thebasicdesignoftheadauctionisfairlysimple.Anadvertiserchoosesasetofkeywordsthatarerelatedtotheproductitwishestosell.Eachadvertiserstatesabidforeachkeywordthatcanbeinterpretedastheamountthatitiswillingtopayifauserclicksonitsad.

Whenauser'ssearchquerymatchesakeyword,asetofadsisdisplayed.Theseadsarerankedbybids(orafunctionofbids)andtheadwiththehighestbidreceivesthebestposition;i.e.,thepositionthatismostlylikelytobeclickedonbytheuser.Iftheuserclicksonanad,theadvertiserischargedanamountthatdependsonthebidoftheadvertiserbelowitintheranking.

IreceivedmanyhelpfulcommentsfromMarcBerndl,JohnLamping,AlexanderNiske,AmitPatel,RobShillingsburg,DianeTang,andEricVeach.IamparticularlygratefultoMeredithGoldsmithforherclosereadingofthepaper,whichimprovedtheexpositionsignificantly.IalsothankJonathanRosenbergforencouragingmetopublishtheseresults.

E-mailaddress:hal@sims.berkeley.edu.0167-7187/$-seefrontmatter©2006ElsevierB.V.Allrightsreserved.doi:10.1016/j.ijindorg.2006.10.002

☆1164H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

Battelle(2005)describesthehistoryofsearchenginesandtheauctionadvertisingmodel.Mygoalinthispaperistopresentasimplegametheoreticmodeloftheadauctionandtestthemodelagainstthedata.

1.Amodelofpositionauctions

Considertheproblemofassigningagentsa=1,…,Atoslotss=1,…,Swhereagenta'svaluationforslotsisgivenbyuas=vaxs.Wenumbertheslotssothatx1Nx2N···NxS.Wealsosetxs=0forallsNSandassumethatthenumberofagentsisgreaterthanthenumberofslots.Thisproblemismotivatedbytheadauctionsmentionedabove.Intheseauctionstheagentsareadvertisersandtheslotsarepositionsonawebpage.Higherpositionsreceivemoreclicks,soxscanbeinterpretedastheclick-throughrateforslots.ThevaluevaN0canbeinterpretedastheexpectedprofitperclicksouas=vaxsindicatestheexpectedprofittoadvertiserafromappearinginslots.

Theslotsaresoldviaanauction.Eachagentbidsanamountba,withtheslotwiththebestclickthroughratebeingassignedtotheagentwiththehighestbid,thesecond-bestslottotheagentwiththesecondhighestbid,andsoon.Renumberingtheagentsifnecessary,letvsbethevalueperclickoftheagentassignedtoslots.Thepriceagentsfacesisthebidoftheagentimmediatelybelowhim,sops=bs+1.Hencethenetprofitthatagentacanexpecttomakeifheacquiresslotsis(va−ps)xs=(va−bs+1)xs.

Itturnsoutthatthesethatpositionauctionshaveanicemathematicalstructureandastrongrelationshiptoexistingliteratureontwo-sidedmatchingmodels(RothandSotomayor,1990).Edelmanetal.(2005)independentlyexaminetheseauctionsanddeveloprelatedresultswhichIdescribebelow.

2.Nashequilibriumofpositionauction

ConsiderTable1whichdepictsthepositions,values,bidsandpaymentassociatedwithanauctionwithS=4availableslots.WeknowthatxsNxs+1byassumptionandthatbsNbs+1bytherulesoftheauction.

Ifagent3wantedtomoveupbyoneposition,itwouldhavetobidatleastb2,thebidofagent2.Butifagent2wantedtomovedownbyonepositionitwouldonlyhavebidatleastb4=p3,thebidofagent4.Weseethattomovetoahigherslotyouhavetobeatthebidthattheagentwhocurrentlyoccupiesthatslotismaking;tomovetoalowerslotyouonlyhavetobeatthepricethattheagentwhocurrentlyoccupiesthatslotispaying.

Formally,wemodelthepositionauctionasasimultaneousmovegamewithcompleteinformation.Eachagentasimultaneouslychoosesabidba.Thebidsarethenorderedandthepriceeachagentmustpayperclickisdeterminedbythebidoftheagentbelowhimintheranking.

Table1

BiddingforpositionPosition12345

Valuev1v2v3v4v5Bidb1b2b3b4b5Pricep1=b2p2=b3p3=b4p4=b50

CTRx1x2x3x40

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781165

Inequilibrium,eachagentshouldpreferhiscurrentslottoanyotherslot,whichmotivatesthefollowingdefinition.

Definition1.ANashequilibriumsetofprices(NE)satisfies

ðvs−psÞxszðvs−ptÞxtfortNsðvs−psÞxszðvs−pt−1Þxtfortbswherept=bt+1.

Notethatifanagentchangeshisbidslightlyitnormallywon'taffecthispositionorpayment,sotherewilltypicallybearangeofbidsandpricesthatsatisfytheseinequalities.Alsonotethattheseinequalitiesarelinearintheprices.Hence,given(vs)and(xs)wecanuseasimplelinearprogramtosolveforthemaximumandminimumequilibriumrevenueattainablebytheauction.TheanalysisofthepositionauctionismuchsimplifiedbyexaminingaparticularsubsetofNashequilibria.

Definition2.AsymmetricNashequilibriumsetofprices(SNE)satisfies

ðvs−psÞxszðvs−ptÞxtforalltands;Equivalently,

vsðxs−xtÞzpsxs−ptxtforalltands:

NotethattheinequalitiescharacterizinganSNEarethesameastheinequalitiescharacterizinganNEfortNs.

Forgettingabouttheauctionforamoment,supposethatthepricesforeachslotweregivenexogenouslyandagentscouldpurchaseslotsattheseprices.NotethattheSNEpricescompriseacompetitiveequilibriuminthesensethateachagentpreferstopurchasetheslotitisinratherthansomeotherslot.TheSNEpricesthusprovidesupportingpricesfortheclassicassignmentproblem,asdescribedinGale(1960),forexample.InSection4Idescribetherelationshipbetweentheassignmentproblemandthepositionauctioninmoredetail.

Ingeneral,thesesupportingpricescanonlybecalculatedusingalinearprogramorrelatedalgorithm.However,Iwillshowinaseriesofshortargumentsthatinthisspecialcase,thepricescanbecomputedexplicitlyviaasimplerecursiveformula.Fact1.Non-negativesurplusInanSNEvs≥ps.

Proof.UsingtheinequalitiesdefininganSNE,

ðvs−psÞxszðvSþ1−pSþ1ÞxSþ1¼0;sincexS+1=0.

□

ð1Þð2Þ

Fact2.MonotonevaluesInanSNE,vs−1≥vsforalls.

1166H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

Proof.BydefinitionofSNEwehave

vtðxt−xsÞzptxt−psxsvsðxs−xtÞzpsxs−ptxt:

Addingthesetwoinequalitiesgivesusðvt−vsÞðxt−xsÞz0;

whichshowsthat(vt)and(xt)mustbeorderedthesameway.

□

ð3Þð4Þ

Notethatsinceagentswithhighervaluesareassignedtobetterslots,anSNEisanefficientallocation.

Fact3.Monotoneprices

InanSNE,ps−1xs−1Npsxsandps−1Npsforalls.IfvsNpsthenps−1Nps.Proof.BydefinitionofSNEwehave

ðvs−psÞxszðvs−ps−1Þxs−1;whichcanberearrangedtogive

ps−1xs−1zpsxsþvsðxs−1−xsÞNpsxs:Thisprovesthefirstpart.

Toprovethesecondpartwewrite

ps−1xs−1zpsxsþvsðxs−1−xsÞzpsxsþpsðxs−1−xsÞ¼psxs−1:

Cancelingxs−1weseethatps−1zps.IfvsNps,thesecondinequalityisstrict,whichprovesthelastpartofthefact.□Fact4.NE⊃SNE

IfasetofpricesisanSNEitisanNE.Proof.Sincept−1zpt,

ðvs−psÞxszðvs−ptÞxtzðvs−pt−1Þxt:forallsandt.□

ThereasonthatthesetofsymmetricNashequilibriaisinterestingisthatitisonlynecessarytoverifytheinequalitiesforonestepupordowninordertoverifythattheentiresetofinequalitiesissatisfied.

Fact5.Onestepsolution

IfasetofbidssatisfiesthesymmetricNashequilibriainequalitiesfors+1ands−1,thenitsatisfiestheseinequalitiesforalls.

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781167

Proof.Igiveaproofbyexample.SupposethattheSNErelationsholdforslots1and2andforslots2and3;weneedtoshowitholdsfor1and3.Writingouttheconditionandusingthefactthatv1≥v2,

v1ðx1−x2Þzp1x1−p2x2Yv1ðx1−x2Þzp1x1−p2x2v2ðx2−x3Þzp2x2−p3x3Yv1ðx2−x3Þzp2x2−p3x3Addinguptheleftandrightcolumns,v1ðx1−x3Þzp1x1−p3x3;

aswastobeshown.Theargumentgoingtheotherdirectionissimilar.

□

Thesefactsallowustoprovideanexplicitcharacterizationofequilibriumpricesandbids.Sincetheagentinpositionsdoesnotwanttomovedownoneslot:

ðvs−psÞxszðvs−psþ1Þxsþ1

Sincetheagentinpositions+1doesnotwanttomoveuponeslot:ðvsþ1−psþ1Þxsþ1zðvsþ1−psÞxs:

Puttingthesetwoinequalitiestogetherwesee:

vsðxs−xsþ1Þþpsþ1xsþ1zpsxszvsþ1ðxs−xsþ1Þþpsþ1xsþ1:Recallingthatps=bs+1wecanalsowritetheseinequalitiesas:vs−1ðxs−1−xsÞþbsþ1xszbsxs−1zvsðxs−1−xsÞþbsþ1xs:

Definingαs=xs/xs−1b1,wehaveyetanotherwaytowritetheinequalities:vs−1ð1−asÞþbsþ1aszbszvsð1−asÞþbsþ1as:

ð7Þð6Þð5Þ

Theequivalentconditions(5)–(7)showthatinequilibriumeachagent'sbidisboundedaboveandbelowbyaconvexcombinationofthebidoftheagentbelowhimandavalue—eitherhisownvalueorthevalueoftheagentimmediatelyabovehim.The(purestrategy)Nashequilibriacanbefoundsimplybyrecursivelychoosingasequenceofbidsthatsatisfytheseinequalities.Wecanexaminetheboundarycasesbychoosingtheupperandlowerboundsininequalities(6).Therecursionsthenbecome

bUsxs−1¼vs−1ðxs−1−xsÞþbsþ1xsbLsxs−1¼vsðxs−1−xsÞþbsþ1xsThesolutiontotheserecursionsare:

X

U

bsxs−1¼vt−1ðxt−1−xtÞ:bLsxs−1¼

X

tzstzs

ð8Þ

ð9Þ

ð10Þð11Þ

vtðxt−1−xtÞ:

1168H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

ThestartingvaluesfortherecursionsfollowfromthefactthatthereareonlySpositions,sothatxs=0forsNS.Writingoutthelowerboundonthebidfors=S+1,wehave

bLSþ1xS

¼vSþ1ðxS−xSþ1Þ

¼vSþ1xS

sothatitisoptimalforthefirstexcludedbiddertobidhisvalue.ThisresulthasthesameargumentasintheusualVickreyauction.Ifyouareexcluded,thenbiddinglowerthanyourvalueispointless,butifyoudohappentobeshown(e.g.,becauseoneofthehigherbiddersdropsout)youwillmakeaprofit.2.1.Logicofthebounds

Ofcourse,anybidintherangedescribedbyEqs.(5)–(7)isanSNEandhenceanNEbid,butperhapstherearereasonswhybiddingatoneendoftheupperorlowerboundsmightbeparticularlyattractivetothebidder.

SupposethatIaminpositionsmakingaprofitof(vs−bs+1)xs.InNashequilibriummybidisoptimalgivenmybeliefsaboutthebidsoftheotheragents,butIcanvarymybidinrangespecifiedbyEq.(6)withoutchangingmypaymentsorposition.

WhatisthehighestbidIcansetsothatifIhappentoexceedthebidoftheagentabovemeandImoveupbyoneslot,IamsuretomakeatmakeatleastasmuchprofitasImakenow?

TheworstcaseiswhereIjustbeattheadvertiserabovemebyatinyamountandenduppayingmybid,bs,minusatinyamount.Hencethebreakevencasesatisfiestheequationworstcaseprofitmovingup

ðvs−b⁎sÞxs−1⁎givesusSolvingforbsb⁎sxs−1¼vsðxs−1−xsÞþbsþ1xs;

whichisthelower-boundrecursion,Eq.(9).

Alternatively,wecanthinkdefensively.IfIsetmybidtoohigh,Iwillsqueezetheprofitoftheplayeraheadofmesomuchthathemightprefertomovedowntomyposition.Thehighestbreakevenbidthatwouldnotinducetheagentabovemetomovedownis

hisprofitnow¼howmuchhewouldmakeinmypositionðvs−1−b⁎sÞxs−1¼ðvs−1−bsþ1Þxs:⁎givesusSolvingforbsb⁎sxs−1¼vs−1ðxs−1−xsÞþbsþ1xs;

whichistheupper-boundrecursion,Eq.(8).

Asamatterofpractice,itseemstomethatthefirstargumentiscompelling.Eventhoughanybidintherange(5)isaNashbid,onemightarguethatsettingthatbidsothatImakeaprofitifImoveupintherankingisareasonablestrategy.

ð12Þð13Þ

¼profitnow¼ðvs−bsþ1Þxs:

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781169

3.NErevenueandSNErevenue

SummingEqs.(10)and(11)overs=1,…SgivesusupperandlowerboundsontotalrevenueinanSNE.IfthenumberofslotsS=3,forexample,thelowerandupperboundsaregivenby

RL¼v2ðx1−x2Þþ2v3ðx2−x3Þþ3v4x3RU¼v1ðx1−x2Þþ2v2ðx2−x3Þþ3v3x3:

HowdotheseboundsrelatetotheboundsfortheNEcalculatedbythelinearprogrammingproblemsalludedtoearlier?

SincethesetofNEcontainsthesetofSNEs,onemightspeculatethatthemaximumandminimumrevenuesarelargerandsmaller,respectively,thantheSNEmaximumandminimumrevenue.Thisishalfright:itturnsoutthattheupperboundfortheSNErevenueisthesameasthemaximumrevenuefortheNE,whilethelowerboundonrevenuefromtheNEisgenerallylessthantherevenueboundfortheSNE.

Fact6.ThemaximumrevenueNEyieldsthesamerevenueastheupperrecursivesolutiontotheSNE.

NProof.Let(ps)bethepricesassociatedwiththemaximumrevenueNashequilibriumandletU(ps)bethepricesthatsolvetheupperrecursionfortheSNE.SinceNE⊃SNE,therevenue

NUassociatedwith(ps)mustbeatleastaslargeastherevenueassociatedwith(ps).FromthedefinitionofanNE,Eq.(1),wehave:

N

pNsxsVpsþ1xsþ1þvsðxs−xsþ1Þ:

Fromthedefinitionoftheupper-boundrecursion,Eq.(8),wehave:

UpUsxs¼psþ1xsþ1þvsðxs−xsþ1Þ:

Therecursionsstartats=S.SincexS+1=0wehave

UpNSVvS¼pS:

UN≥psforalls.HencetheItfollowsbyinspectingtherecursionsimmediatelyabovethatpsmaximumrevenuefromtheSNEisatleastaslargeasthemaximumrevenuefromtheNE,implyingthattherevenuemustbeequal.□

ItiseasytoconstructexampleswheretheminimumrevenueNEhaslessrevenuethanthesolutiontothelowerrecursionfortheSNE;thisisnotsurprisingsincethesetofinequalitiesdefiningtheNEstrictlycontainsthesetofinequalitiesdefiningtheSNE.Sowehavethegeneralrelations:

maximumrevenueNE¼valueofupperrecursionofSNE

zvalueoflowerrecursionofSNEzminrevenueNE

withtheinequalitiesbeingstrictexceptindegeneratecases.4.Previousliterature

IhavealreadymentionedtherecentindependentanalysisofEdelmanetal.(2005).Theyintroduceaconcepttheycall“locallyenvy-free”equilibriawhichrequiresthateachplayer“cannotimprovehispayoffbyexchangingbidswiththeplayerrankedonepositionabovehim.”Thisyieldsthesamebidsas

1170H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

thelowerboundoftheSNEsdescribedinthispaper.Theyalsointroducetheinterestingconceptofa“GeneralizedEnglishAuction”andshowthattheuniqueperfectequilibriumofthisgameisthesameasthelocallyenvy-freeoutcome.

Thereisalsoamucholderliteraturethatiscloselyrelatedtothepositionauctionproblem.ShapleyandShubik(1972)describeanassignmentgameinwhichagentsareassignedobjectswithatmostoneobjectbeingassignedtoanagent.Mathematically,letagenta'sevaluationofobjectsbegivenbyuas.Theassignmentproblemasksfortheassignmentofobjectstoagentsthatmaximizesvalue.Thisproblemcanbesolvedbylinearprogrammingorbyotherspecializedalgorithms.Itturnsoutthatanoptimalassignmentcanbedecentralizedbymeansofpricemechanism.Thatis,atanoptimalassignmenttherewillexistasetofnumbers(pa),interpretableasthepriceoftheobjectassignedtoagenta,suchthat:

uas−pazuas−pb

forallaandb:

Henceattheprices(pa)eachagentwouldweaklyprefertheobjectassignedtohimoveranyotherobject.

ComparingthistothedefinitionofthesymmetricNashinequalities,weseethatthedefinitionsarethesamewithuas=vaxsandpa=ba+1xs.Hence,thepositionauctiongamewehavedescribedissimplyacompetitiveequilibriumofanassignmentgamethathasaspecialstructureforutility.However,thespecialstructureisparticularlynaturalinthiscontext.Inparticular,wecanexplicitlysolveforthelargestandsmallestcompetitiveequilibriumduetothespecialstructureofuas.Demangeetal.(1986)constructanauctionthatdeterminesacompetitiveequilibrium.However,theauctiontheyconstructisquitedifferentfromthepositionauction.RothandSotomayor(1990),Chapter8,containsaunifiedtreatmentoftheseresults.Severalpapershavedevelopedauctionsthatyieldcompetitiveequilibriafortheassignmentgame;seeBikhchandaniandOstroy(2006)forarecentsurvey.5.Incentives

Wehaveseenthattheoptimalbidsinthepositionauctionwillingeneraldependonthebidsmadebyotheragents.Onemightwellaskifthereisawaytofindanotherauctionstructureforwhichagenta'soptimalbiddependsonlyonitsvalue.Isitpossibletofindanauctionformthathasadominantstrategyequilibrium?DemangeandGale(1985)showtheansweris“yes,”usingavariationontheHungarianalgorithmfortheassignmentproblem.

Wecanalsoapplythewell-knownVickrey–Clarke–Grovesmechanismtothisproblem.Leonard(1983)describesthisforthegeneralcase,buttheVCGmechanismtakesaparticularlysimpleformforthespecialcaseweareconsideringhere.

LetusrecallthebasicstructureoftheVCGmechanism.Supposeacentralauthorityisgoingtochoosesomeoutcomezsoastomaximizethesumofthereportedutilitiesofagentsa=1,…,A.Letagenta'strueutilityfunctionbedenotedbyua(·)anditsreportedutilityfunctionbyra(·).Inordertoalignincentives,thecenterannouncesitwillpayeachagentthesumoftheutilitiesreportedbytheotheragentsattheutility-maximizingoutcome.Thusthecenterannouncesitisgoingtomaximize

X

raðzÞþrbðzÞ

bpa

whileagentacaresabout

X

uaðzÞþrbðzÞ

bpa

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781171

Itiseasytoseethatinordertomaximizeitsownpayoff,agentawillwanttoreportitstrueutilityfunction,thatis,setra(·)=ua(·),sincethisensuresthatthecenteroptimizesexactlywhatagentawantsittomaximize.

Wecanreducethesizeofthesidepaymentsbysubtractinganamountfromagentathatdoesnotdependonitsreport.Aconvenientchoiceinthisrespectisthemaximizedsumofreportedutilitiesomittingagenta'sreport.Hencethefinalpayofftoagentabecomes

uaðzÞþ

X

bpa

rbðzÞ−max

y

X

bpa

rbðyÞ:

Thepaymentmadebyagentacanbeinterpretedastheharmthatitspresenceimposesontheotheragents:thatisthedifferencebetweenwhattheygetwhenagentaispresentandwhattheywouldgetifagentawereabsent.

Inthecontextofassigningagentstopositions,ifagents−1isomitted,eachagentbelowagents−1willmoveuponepositionwhileagentsaboves−1areunaffected.Hencethepaymentthatagents−1mustmakeis

VCGpaymentofagents−1¼

X

tzs

rtðxt−1−xtÞ;ð14Þ

wherertisthereportedvalueofagentt.InthedominantstrategyVCGequilibrium,eachagenttwillannouncert=vt,so

X

equilibriumVCGpaymentofagents−1¼vtðxt−1−xtÞ:ð15Þ

tzs

Comparingthistoexpression(11)thisiseasilyseentobethesameasthelowerboundforthesymmetricNashequilibria.

Thisrelationshipistrueingeneral,evenforarbitraryuas.DemangeandGale(1985)showthatthebest(i.e.,lowestcost)equilibriumforthebuyersinthecompetitiveequilibriumfortheassignmentproblemisthatgivenbytheVCGmechanism.SeeRothandSotomayor(1990)foradetaileddevelopmentofthistheory,andBikhchandaniandOstroy(2006)forarecentsurveyofrelatedresults.Edelmanetal.(2005)alsorecognizethecloseconnectionbetweentheVCGoutcomeandtheequilibriumconceptthattheyuse(locallyenvy-freeequilibria).

6.Boundsonvalues

ReturningtothesymmetricNashequilibriumanalysis,itispossibletoderiveusefulboundsontheunobservedvaluesoftheagentsbyusingtheobservedequilibriumprices.

Letps=bs+1betheequilibriumpricepaidbyagentsinaparticularsymmetricNash(orcompetitive)equilibrium.Thenwemusthave:

ðvs−psÞxszðvs−ptÞxt:Rearrangingthiswehave

vsðxs−xtÞzpsxs−ptxt:

1172H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

Dividingbyxs−xtandrememberingthatthesenseoftheinequalityisreversedwhenxsbxt,wehave

min

tNs

psxs−ptxtpsxs−ptxt

zvszmax:

tbsxs−xtxs−xt

Furthermore,weknowfromFact5thatthemaxandtheminareattainedattheneighboring

positions,sowecanwrite

ps−1xs−1−psxspsxs−psþ1xsþ1

zvsz

xs−1−xsxs−xsþ1

Theseinequalitieshaveaniceinterpretation:theratiosaresimplytheincrementalcostofmoving

upordownoneposition.

Wecanrecursivelyapplytheseinequalitiestowrite

v1zv2z

p1x1−p2x2

z

x1−x2p2x2−p3x3

z

x2−x3

ð16Þð17Þð18Þ

v

vSzpS

Thisshowsthattheincrementalcostsmustdecreaseaswemovetolowerpositions.Thisobservationhasthreeimportantimplications.

1.TheinequalitiesgiveanobservablenecessaryconditionforatheexistenceofapurestrategyNashequilibrium,namely,thateachoftheintervalsbenon-empty.Theconditionsarealsosufficientinthatiftheintervalsarenon-empty,wecanfindasetofvaluesthatareconsistentwithequilibrium.2.Theinequalitiesalsoyieldsimplebiddingrulefortheagents:ifyourvalueexceedsthemarginalcostofmovingupaposition,thenbidhigher,stoppingwhenthisnolongeristrue.3.FinallytheinequalitiesmotivatethefollowingintuitivecharacterizationofSNE:themarginalcostofaclickmustincreaseasyoumovetohigherpositions.Why?Becauseifiteverdecreased,therewouldbeanadvertiserwhopassedupcheapclicksinordertopurchaseexpensiveones.WecanalsodothesamecalculationsfortheNEinequalitieswhichyields:min

tNs

psxs−pt−1xtpsxs−ptxt

zvszmax:

tbsxs−xtxs−xt

ð19Þ

NotethattheupperboundsfortheNE(fortNs)arelooserthanfortheSNEandthattheynow

involvetheentiresetofbids,notjusttheneighboringbids.7.Geometricinterpretation

Fig.1showstheclickthroughratesxsonthehorizontalaxesandSNEexpenditurepsxs=bs+1xsontheverticalaxis.Werefertothisgraphastheexpenditureprofile.Theslopeofthelinesegmentsconnectingeachvertexarethemarginalcostsdescribedintheprevioussectionwhich

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781173

Fig.1.ExpenditureprofileforSNE.

wehaveshownmustboundtheagents'values.Accordingtotheabovediscussion,iftheobservedchoicesareanSNE,thisgraphmustbeanincreasing,convexfunction.

Theprofitaccruingtoagentsisπs=vsxs−psxs.Hencetheiso-profitlinesaregivenbypsxs=vsxs−πs,whicharestraightlineswithslopevsandverticalinterceptof−πs.Aprofit-maximizingbidderwantstochoosethatpositionwhichhasthelowestassociatedprofit,asshowninFig.1.Therangeofvaluesassociatedwithequilibriumaresimplytherangeofslopesofthesupportinghyperplanesateachpoint.

ThisdiagramalsocanbeusedtoillustratetheconstructionoftheSNEusingtherecursivesolutionoutlinedearlier.Supposethatthereare3slotsandwearegivenfourvalues.Sinceweknowthatp3=v4fromtheboundaryconditionforthelowerrecursion,wedrawalinewithslopev4connectingthepoints(0,0)and(x3,v4x3).Nextdrawalinewithslopeofv3startingat(x3,v4x3).Thevalueofthislineatx2willbev4x3+v3(x2−x3),whichisexactlythelowerrecursion.Continuinginthiswaytracesouttheequilibriumexpenditureprofile.

WecanalsoillustratetheNEboundsusingthesamesortofdiagram.ThelowerboundsonFig.2showstheSNEbounds,alongwiththeNEboundsfrominequalities(19).FortheNE,thelowerboundsarethesame,whiletheupperboundsarelooser(steeper)thantheSNE.

Fig.2.ExpenditureprofileforNEandSNE.

1174H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

8.Applicationstoadauctions

Upuntilnowwehavedescribedtheabstractstrategicstructureofthepositionauction.InordertoapplythistotheactualadauctionusedbyGoogle,wehavetoaddsomerefinements.

Googleactuallyrankstheadsbytheproductofameasurementofadqualityandadvertiserbid,ratherthanjustthebidalone.1Weassumethattheobservedclickthroughrateforadvertiserainpositionsistheproductofthis“qualityeffect”es,anda“positioneffect,”xs.Lettingzsbeadvertisers'sobservedclickthroughrate,wewritezs=esxs.

Advertisersareorderedbyesbsandeachadvertiserpaystheminimumamountthatisnecessarytoretainhisposition.Letqstbetheamountthatadvertiserswouldneedtopaytobeinpositiont.Byconstructionwehave

qstes¼btþ1etþ1:Solvingforqstwehave

qst¼btþ1etþ1=es:

ð20Þ

Nashequilibriumrequiresthateachagentpreferhispositiontoanyotherposition,recognizingthatthecostandclickthroughrateoftheotherpositiondependsonhisadquality:

ðvs−qssÞesxszðvs−qstÞesxt:

SubstitutingEq.(20)intothisexpressionandsimplifyingwehave

ðesvs−bsþ1esþ1Þxszðesvs−btþ1etþ1Þxt:Lettingps=bs+1es+1andpt=bt+1et+1givesus

ðesvs−psÞxszðesvs−ptÞxt:

WecannowapplythesamelogicusedinEq.(16)–(18)togiveus

e1v1ze2v2zv

p1x1−p2x2

z

x1−x2p2x2−p3x3

z

x2−x3

ð21Þð22Þð23Þ

eSvSzpS:

ThesearethetestableinequalitiesimpliedbythesymmetricNashequilibriummodel.

Finally,wealsohavetomentionthecaseof“non-fullysoldpages”whichareauctionswherethenumberofadsdisplayedontheright-handsideisfewerthan8.Inthiscase,thebottomadonthepagepaysareservepricewhichiscurrentlysetat5cents.

1Seehttp://services.google.com/awp/en_us/breeze/5310/index.html.

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–11781175

9.Informationrequirements

WehavefocusedonthesetofNashequilibriaofthepositionauctiongame.Thisis,ofcourse,afull-informationsolutionconcept,andonemightaskhowlikelyitisthatadvertisersknowwhattheyneedtoknowtoimplementafullinformationequilibrium.

Ofcourse,onecouldhardlyexpectadvertiserstobecompletelyinformedaboutallrelevantvariables.However,itisveryeasytoexperimentwithbiddingstrategiesinreal-worldadauctions.Googlereportsclickandimpressiondataonanhour-by-hourbasisandafewdaysofexperimentationcanyieldprettygoodestimatesofthenumberofclicksreceivedfordifferentbids.Furthermore,Googleitselfoffersa“TrafficEstimator”thatprovidesanestimateofthenumberofclicksperdayandthecostperdayassociatedwiththeadvertiser'schoiceofkeywords.Finally,third-partycompaniesknownas“SearchEngineManagers(SEMs)”offeravarietyofservicesrelatedtomanagingbids.Theavailabilityofsuchtoolsandservices,alongwiththeeaseofexperimentation,suggestthatthefull-informationassumptionisareasonablefirstapproximation.Aswewillseebelow,theNashequilibriummodelseemstofittheobservedchoiceswell.10.Empiricalanalysis

Givenasetofpositioneffects,qualityeffects,andbidswecanplotxtversusexpenditurebtxtandseeifthisexpenditureprofileisincreasingandconvex.Itturnsoutthatthisoftenistrue.Ifthegraphisnotincreasingandconvex,wecanaskforaperturbationofthedatathatdoesexhibittheseproperties.

Thequestionis,whattoperturb?Thenaturalvariabletoperturbistheadquality,es,sincethisisthemostdifficultvariablefortheadvertiserstoobserveandthushasthemostassociateduncertainty.Let(dses)bethevalueoftheperturbedadqualitywhere(ds)isasetofmultipliersindicatinghow

Fig.3.Examplesofdataandfits.

1176H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

mucheachadqualityneedstobeperturbedtosatisfytheNashinequalities(21)–(23).Sincethepricespsarelinearfunctionsofes,wecanalsothinkoftheperturbationsasapplyingtotheprices.Thismodelmotivatesthefollowingquadraticprogrammingproblem:choosetheperturbations(ds)tobeascloseaspossibleto1(intermsofsquarederror)constrainedbytherequirementthattheSNEinequalitiesgiveninEqs.(21)–(23)aresatisfied.Explicitly,thequadraticprogrammingproblemis

Xminðds−1Þ2

d

s

suchthat

ds−1ps−1xs−1−dspsxsdspsxs−dsþ1psþ1xsþ1

z:

ðxs−1−xsÞðxs−xsþ1ÞSincetheconstraintsarelinearin(ds),thisisasimplequadraticprogrammingproblemwhichcanbe

easilysolvedbystandardmethods.Thisminimalperturbationcalculationcanbegivenastatisticalinterpretation;seeVarian(1985).However,wedonotpursuethedetailsofthisinterpretationhere.Fig.3showssomeexamplesofexpenditureprofilesusingtheactualdataalongwiththebestfittingincreasing,convexrelationship.(Thenumericvaluesontheaxeshavebeenremovedsincethisanalysisisbasedonproprietarydata.)

Itcanbeseenthatthegeneralshapeoftheexpenditureprofiletendstobeincreasingandconvexasthetheorypredicts.Furthermore,itoftenratherflatatleastinpositions3–8.Oneexplanationfortheincreasedexpenditureonpositions1and2ontheright-handsideisthatGooglewillpromoteadsintheseslotstothetop-of-pagepositionundercertainconditions.Thusadvertisersmaywanttobidextratogettoright-handsidepositions1and2,hopingtobepromotedtoatopspot.

Iexaminedthebidsforarandomsampleof2425auctionsinvolvingatleast5adseachonaparticularday.SolvingthequadraticprogrammingproblemsyieldsasetofminimalperturbationsforeachauctionrequiredtomakethatauctionsatisfytheSNEinequalities.ForeachauctionI

Sdefinethemeanabsolutiondeviationtobe∑s=1|ds−1|/S,whereSisthenumberofadvertisersintheauction.

Fig.4depictsahistogramofmeanabsolutedeviationsnecessarytosatisfytheSNEinequalities;asitcanbeseenthedeviationstendtobequitesmall,withtheaverageabsolutedeviationoftheperturbationsbeing5.8%andthemedianbeing4.8%.Veryfewofthemeanabsolutedeviationsarelargerthan10%.IconcludethatrelativelysmallperturbationsarerequiredtomaketheobservationsconsistentwiththeSNEmodels.SincetheNEinequalitiesareweakerthantheSNEinequalities,therequiredperturbationforconsistencywithNashequilibriumwouldbeevensmaller.

Fig.4.Distributionofmeanabsolutedeviations.

H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

Table2

BoundsonvaluesPsn12345678

RawLB1.191.290.600.721.680.231.320.05

RawUB∞2.261.660.301.790.840.831.63

PerturbedLB1.191.151.190.601.470.341.080.05

PerturbedUB∞2.261.480.611.490.741.191.33

1177

Price0.480.600.480.230.400.070.240.21

WecanusetheprocedureforestimatingtheboundsonvdescribedinSection6todetermineempiricallytherelationshipbetweenthebidsandthevalues.Forexample,Table2showsthe“raw”upperandlowerboundsonvaluesforaparticularkeywordcalculatedbyusingtheobservedincrementalcostalongwiththeupperandlowerboundsonvaluecalculatedusingtheperturbedvaluesfromthequadraticprogram.Thelastcolumnisthepriceoftheclick.Inthisexample,thelowerboundssometimesexceedtheupperboundsfortherawdata,buttheperturbeddatasatisfytheboundsbyconstruction.Thepricesarenotnecessarilymonotoneduetothequalityadjustmentbutthepricetimesqualityadjustment(notshown)isalwaysmonotone.Ascanbeseenfromthetable,theestimatedvalueofaclicktothesebiddersappearstobesomewherearoundadollarandtheadvertisersarepayingaround50centsaclick.AppendixA.Bayes–Nashequilibrium

IhavearguedthatthefullinformationassumptionthatunderliesNashequilibriumisnotimplausibleinthisinstitutionalsetting.However,itisalsoofinteresttoexaminetheBayes–Nashequilibria,whichwouldbeappropriateinagamewithsubstantiallylessinformation.

Asitturnsouttheanalysisisastraightforwardvariationoftheclassicalanalysisofasimpleauction.Toseethis,letusfirstreviewtheclassicalanalysis.Letvbethevalueofaparticularbidder,P(v)theprobabilitythathewinstheauction,andp(v)hisexpectedpayment.Thebidder'sobjectiveistomaximizeexpectedsurplusS(v)=vP(v)−p(v).

Inthepositionauctioncontext,weletP(1)(v)betheprobabilitythattheplayerhasthehighestbid,P(2)(v)theprobabilitythattheplayerwithvaluevhasthesecond-highestbidandsoon.Ifthereare3positions,thesurplusbecomes

SðvÞ¼v½P1ðvÞx1þP2ðvÞx2þP3ðvÞx3󰀂−pðvÞ:

Thefirsttermistheexpectedsurplustoabidderwithvaluev,recognizingthatitgetsx1clicksifitendsupinthefirstposition,x2clicksifitendsupinthesecondposition,andsoon,witheachclickbeingworthv.Inasimpleauction,thevalueofcominginsecondiszero.Inapositionauction,thevalueofcominginsecondisvx2.

DefineH(v)=P1(v)x1+P2(v)x2+P3(v)x3andwritethesurplusas

SðvÞ¼vHðvÞ−pðvÞ:

ItisnothardtoseethatH(v)hastherelevantpropertiesofaCDF.Itismonotone,sinceitisaweightedsumofmonotonefunctions.FurthermoreifvLandvUaretheupperandlowerboundsonv,H(vL)=0andH(vU)=x1=aconstant.

1178H.R.Varian/Int.J.Ind.Organ.25(2007)1163–1178

Allofthestandardpropertiesofasimpleauctioncarryovertothepositionauction,includingrevenueneutrality,thederivationoftheoptimalreserveprice,andsoon.HencetheBayes–NashequilibriumofapositionauctionisastraightforwardgeneralizationoftheBayes–Nashequi-libriumofasimpleauction.References

Battelle,John,2005.TheSearch.PortfolioHardcover.

Bikhchandani,Sushil,Ostroy,JosephM.,2006.Fromtheassignmentmodeltocombinatorialauctions.In:Cramton,Peter,

Shoham,Yoav,Steinberg,Richard(Eds.),CombinatorialAuctions.MITPress,Cambridge,MA.

Demange,Gabrielle,Gale,David,1985.Thestrategystructureoftwo-sidedmatchingmarkets.Econometrica53,873–878.Demange,Gabrielle,Gale,David,Sotomayor,Marilda,1986.Multi-itemauctions.JournalofPoliticalEconomy94(4),

863–872.

Edelman,Benjamin,Ostrovsky,Michael,Schwartz,Michael,2005.Internetadvertisingandthegeneralizedsecondprice

auction.NBERWorkingPaper,vol.11765.November.

Gale,David,1960.TheTheoryofLinearEconomicModels.UniversityofChicagoPress,Chicago.

Leonard,HermanB.,1983.Elicitationofhonestpreferencesfortheassignmentofindividualstopositions.Journalof

PoliticalEconomy91,461–479.

Roth,Alvin,Sotomayor,Marilda,1990.Two-SidedMatching.CambridgeUniversityPress.

Shapley,Lloyd,Shubik,Martin,1972.TheassignmentgameI:thecore.InternationalJournalofGameTheory1,111–130.Varian,HalR.,1985.Nonparametricanalysisofoptimizingbehaviorwithmea-surementerror.JournalofEconometrics30

(1),445–458.In:Barnett,WilliamB.,Gallant,A.Ronald(Eds.),1990.ReprintedinNewApproachestoModelingSpecificationSelection,andEconometricInference.CambridgeUniversityPress.