Online Ad Serving: Theory And Practice - UMD

New ALG: “Two suggested matchings”1. Offline: Find two disjoint matchings2. Online: try the first one, then if that doesn’t work, try thesecond one.

New ALG: “Two suggested matchings”Warmup: complete graphITwo disjoint perfect matchings: blue (1-ary), red (2-ary).

New ALG: “Two suggested matchings”Warmup: complete graphITwo disjoint perfect matchings: blue (1-ary), red (2-ary).IUnion of matchings cycles with alt. blue and red edges

New ALG: “Two suggested matchings”For particular node a A:Pr[a is chosen ] Pr[i arrives once, or i 0 arrives twice] 1 Pr[i never arrives & i 0 arrives once] 1 (1 2/n)n n(1/n)(1 2/n)n 1 1 2/e 2Thus, E[# nodes in A chosen] (1 2/e 2 )n .729n(This also concentrates.)

Algorithm (Offline)IHow to find a matching with flow.

Algorithm (Offline)IHow to find a matching with flow.

Algorithm (Offline)IHow to find a matching with flow.

Algorithm (Offline)ISolve an “augmented flow” problem instead.

Algorithm (Offline)ISolve an “augmented flow” problem instead.

Algorithm (Offline)IExamine edges in flow.

Algorithm (Offline)IColor the edges as shown

Algorithm (Online)IWhen node i I arrives:ITry the blue edge first, then the red edge.

Algorithm (Online)IConsider a node a A:IPr[a is chosen ] Pr[i arrives once, or i 0 arrives twice]

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):Ia AB . We get at least AB (1 1/e).

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):IIa AB . We get at least AB (1 1/e).a ABR . We get at least ABR (1 2/e 2 ).

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):IIIa AB . We get at least AB (1 1/e).a ABR . We get at least ABR (1 2/e 2 ).a ABB . We get at least ABB (1 1/e 2 ).

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):IIIIa AB . We get at least AB (1 1/e).a ABR . We get at least ABR (1 2/e 2 ).a ABB . We get at least ABB (1 1/e 2 ).a AR . We get at least AR (1 2/e).

Performance of the AlgorithmIClassify a A based on its neighbors in the flow. flow 2 ABR 2 ABB AB AR IUsing Balls-in-bins concentration results (Azuma’s inequality):IIIIa AB . We get at least AB (1 1/e).a ABR . We get at least ABR (1 2/e 2 ).a ABB . We get at least ABB (1 1/e 2 ).a AR . We get at least AR (1 2/e).Bound on ALG in terms of flow (using B R ): 123ALG 1 2 ABB 1 2 ABR 1 ( AB AR )ee2eI

Bounding OPTIIIFind min-cut in augmented flow graph (from G ).Eδ is a matching.By max-flow min-cut, flow 2( AT IS ) Eδ .

Bounding OPTIIIIOPT cut(H). (Remember H (A, Î , Ê ).)Use min-cut in G as “guide” for cut in H.W.h.p., IS ÎS . Eδ ?For any node a S with an edge in the cut in Ê (H), move itto T # nonempty nodes in Eδ (1 e1 )Eδ .

Putting things togetherIEventually (after moving a few nodes around) you getIOPT . IS AT (1 1/e) Eδ .

Putting things togetherIEventually (after moving a few nodes around) you getIIOPT . IS AT (1 1/e) Eδ .A lemma relating the decomposition to the cut givesI Eδ 23 ABR 43 ABB AB 13 AR ,

Putting things togetherIEventually (after moving a few nodes around) you getIIA lemma relating the decomposition to the cut givesII Eδ 23 ABR 43 ABB AB 13 AR ,which, when combined withIIIIOPT . IS AT (1 1/e) Eδ . flow 2( AT IS ) Eδ flow 2 ABR 2 ABB AB AR ,ALG (1 e12 ) ABB (1 e22 ) ABR (1 givesALGOPTI ALGOPTI221 1/e1 2/e min{ 5/3 4/3e, 4/3 2/3e, 1 3/2e1 1/e } .6732e )( AB AR ),

Putting things togetherIEventually (after moving a few nodes around) you getIIA lemma relating the decomposition to the cut givesII Eδ 23 ABR 43 ABB AB 13 AR ,which, when combined withIIIIOPT . IS AT (1 1/e) Eδ . flow 2( AT IS ) Eδ flow 2 ABR 2 ABB AB AR ,ALG (1 e12 ) ABB (1 e22 ) ABR (1 givesALGOPTI ALGOPTII221 1/e1 2/e min{ 5/3 4/3e, 4/3 2/3e, 1 3/2e1 1/e } .67The analysis is tight.32e )( AB AR ),

Ad Allocation: Problems and ModelsWorst CaseStochastic(i.i.d.)Online Matching:via sia 1Greedy: 12 ,[KVV]: 1 e1 -aprx[FMMM09]:0.67-aprxi.i.d with knowndistributionDisp. Ads (DA):sia 1Inapproximable?AdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max via

Ad Allocation: Problems and ModelsWorst CaseStochastic(i.i.d.)Online Matching:via sia 1Greedy: 12 ,[KVV]: 1 e1 -aprx[FMMM09]:0.67-aprxi.i.d with knowndistributionDisp. Ads (DA):sia 1Inapproximable?[FHKMS10,AWY]:1 -aprx,if opt max viaand n mrandom order i.i.d. model with unknown distributionAdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max via

Stochastic DA: Dual AlgorithmmaxXvia xiamini,aXaxia 1( i)xia Ca( a)aXXCa βa Xziizi via βa ( i, a)βa , zi 0ixia 0( i, a)Algorithm:I Observe the first fraction sample of impressions.I Learn a dual variable for each ad βa , by solving the dualprogram on the sample.I Assign each impression i to ad a that maximizes via βa .( i, a)

Stochastic DA: Dual AlgorithmmaxXvia xiamini,aXaxia 1( i)xia Ca( a)aXXCa βa Xziizi via βa ( i, a)βa , zi 0ixia 0( i, a)Algorithm:I Observe the first fraction sample of impressions.I Learn a dual variable for each ad βa , by solving the dualprogram on the sample.I Assign each impression i to ad a that maximizes via βa .( i, a)

Stochastic DA: Dual AlgorithmFeldman, Henzinger, Korula, M., Stein 2010Thm[FHKMS10,AWY]: W.h.p, this algorithm is a (1 O( ))-aprx,as long as each item has low value (via m optlog n ), and largecapacity (Ca m log n) 3

Stochastic DA: Dual AlgorithmFeldman, Henzinger, Korula, M., Stein 2010Thm[FHKMS10,AWY]: W.h.p, this algorithm is a (1 O( ))-aprx,as long as each item has low value (via m optlog n ), and largecapacity (Ca m log n) 3Fact: If optimum βa are known, this alg. finds optI Proof: Comp. slackness. Given βa , compute x as follows:xia 1 if a argmax(via βa ).

Stochastic DA: Dual AlgorithmFeldman, Henzinger, Korula, M., Stein 2010Thm[FHKMS10,AWY]: W.h.p, this algorithm is a (1 O( ))-aprx,as long as each item has low value (via m optlog n ), and largecapacity (Ca m log n) 3Fact: If optimum βa are known, this alg. finds optI Proof: Comp. slackness. Given βa , compute x as follows:xia 1 if a argmax(via βa ).Lemma: In the random order model, W.h.p., the sample βa0 areclose to βa .I Extending DH09.

General Stochastic Packing LPsIIm fixed resources with capacity CaItems i arrive online with options Oi , values vio , rsrc. use sioa .IChoose o Oi , using up capacity sioa in all a.Thm[FHKMS10,AWY]: W.h.p, the PD algorithm is a(1 O( ))-aprx, as long as items have low value (vio small size (sioa 3 Calog n ). optlog n )and

General Stochastic Packing LPsIIm fixed resources with capacity CaItems i arrive online with options Oi , values vio , rsrc. use sioa .IChoose o Oi , using up capacity sioa in all a.Thm[FHKMS10,AWY]: W.h.p, the PD algorithm is a(1 O( ))-aprx, as long as items have low value (vio small size (sioa optlog n ) 3 Calog n ).Other Results and Extensions (random order model):IAgrawal, Wang, Ye: Updating dual variables by periodic2nsolution of the dual program: Ca m logor sioa MCa 2and

General Stochastic Packing LPsIIm fixed resources with capacity CaItems i arrive online with options Oi , values vio , rsrc. use sioa .IChoose o Oi , using up capacity sioa in all a.Thm[FHKMS10,AWY]: W.h.p, the PD algorithm is a(1 O( ))-aprx, as long as items have low value (vio small size (sioa optlog n )and 3 Calog n ).Other Results and Extensions (random order model):IAgrawal, Wang, Ye: Updating dual variables by periodic2nsolution of the dual program: Ca m logor sioa MCa 2IVee, Vassilvitskii , Shanmugasundaram 2010: extension toconvex objective functions: Using KKT conditions.

Ad Allocation: Problems and ModelsWorst CaseStochastic(i.i.d.)Online Matching:via sia 1Greedy: 12 ,[KVV]: 1 e1 -aprx[FMMM09]:0.67-aprxi.i.d with knowndistributionDisp. Ads (DA):sia 1Inapproximable?[FHKMS10,AWY]:1 -aprx,if opt max viaand n mAdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max via

Ad Allocation: Problems and ModelsOnline Matching:via sia 1Worst CaseGreedy: 12 ,[KVV]: 1 e1 -aprxStochastic(i.i.d.)[FMMM09]:0.67-aprxi.i.d with knowndistributionDisp. Ads (DA):sia 1InapproximableFree Disposal[FKMMP09]:1 e1 -aprx[FHKMS10,AWY]:1 -aprx,if opt max viaand n mAdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max via

DA: Free Disposal Model0.07Ad 1: C1 1

DA: Free Disposal Model0.07Ad 1: C1 1

DA: Free Disposal Model0.070.7Ad 1: C1 1

DA: Free Disposal Model0.07Ad 1: C1 10.7IAdvertisers may not complain about extra impressions, but nobonus points for extra impressions, either.

DA: Free Disposal Model0.07Ad 1: C1 10.7IIAdvertisers may not complain about extra impressions, but nobonus points for extra impressions, either.Value of advertiser sum of values of top Ca items she gets.

Greedy AlgorithmAssign impression to an advertisermaximizing Marginal Gain (imp. value - min. impression value).

Greedy AlgorithmAssign impression to an advertisermaximizing Marginal Gain (imp. value - min. impression value).ICompetitive Ratio: 1/2. [NWF78]IFollows from submodularity of the value function.

Greedy AlgorithmAssign impression to an advertisermaximizing Marginal Gain (imp. value - min. impression value).ICompetitive Ratio: 1/2. [NWF78]IFollows from submodularity of the value function.n copies1Ad 1: C1 n1 Ad 2: C2 n

Greedy AlgorithmAssign impression to an advertisermaximizing Marginal Gain (imp. value - min. impression value).ICompetitive Ratio: 1/2. [NWF78]IFollows from submodularity of the value function.n copies1Ad 1: C1 n1 n copies1Ad 2: C2 n

Greedy AlgorithmAssign impression to an advertisermaximizing Marginal Gain (imp. value - min. impression value).ICompetitive Ratio: 1/2. [NWF78]IFollows from submodularity of the value function.n copies1Ad 1: C1 n1 n copies1Evenly Split?Ad 2: C2 n

A better algorithm?Assign impression to an advertiser amaximizing (imp. value - βa ),where βa average value of top Ca impressions assigned to a.

A better algorithm?Assign impression to an advertiser amaximizing (imp. value - βa ),where βa average value of top Ca impressions assigned to a.n copies1Ad 1: C1 n1 n copies1Ad 2: C2 n

A better algorithm?Assign impression to an advertiser amaximizing (imp. value - βa ),where βa average value of top Ca impressions assigned to a.1n copiesAd 1: C1 n1 1n copiesICompetitive Ratio:I12Ad 2: C2 nif Ca 1. [FKMMP09]Primal-Dual Approach.

An Optimal AlgorithmAssign impression to an advertiser a:maximizing (imp. value - βa ),IGreedy: βa min. impression assigned to a.IBetter (pd-avg): βa average value of top Ca impressionsassigned to a.

An Optimal AlgorithmAssign impression to an advertiser a:maximizing (imp. value - βa ),IGreedy: βa min. impression assigned to a.IBetter (pd-avg): βa average value of top Ca impressionsassigned to a.IOptimal (pd-exp): order value of edges assigned to a:v (1) v (2) . . . v (Ca ):Cβa aX1 j 11v (j)(1 ) .Ca (e 1)Caj 1

An Optimal AlgorithmAssign impression to an advertiser a:maximizing (imp. value - βa ),IGreedy: βa min. impression assigned to a.IBetter (pd-avg): βa average value of top Ca impressionsassigned to a.IOptimal (pd-exp): order value of edges assigned to a:v (1) v (2) . . . v (Ca ):Cβa aX1 j 11v (j)(1 ) .Ca (e 1)Caj 1IThm: pd-exp achieves optimal competitive Ratio: 1 e1 ifCa O( 1 ). [Feldman, Korula, M., Muthukrishnan, Pal 2009]

Online Generalized Assignment (with free disposal)IMultiple Knapsack: Item i may have different value (via ) anddifferent size sia for different ads a.IDA: sia 1, AW: via sia .maxXvia xiamini,aXaxia 1( i)sia xia Ca( a)aXixia 0X( i, a)Ca β a Xziisia βa zi viaβa , zi 0( i, a)( i, a)

Online Generalized Assignment (with free disposal)IMultiple Knapsack: Item i may have different value (via ) anddifferent size sia for different ads a.IDA: sia 1, AW: via sia .maxXvia xiamini,aXXaxia 1( i)sia xia Ca( a)Xziisia βa zi viaaXCa β a βa , zi 0( i, a)( i, a)ixia 0( i, a)1eIOffline Optimization: 1 δ-aprx[FGMS07,FV08].IThm[FKMMP09]: There exists a 1 Ca1algorithm if maxsia .1e -approximation

Proof Idea: Primal-Dual Analysis [BJN]maxXvia xiai,aXxia 1( i)aXminsia xia Ca( a)XaCa βa Xziisia βa zi viaixia 0( i, a)βa , zi 0( i, a)( i, a)

Proof Idea: Primal-Dual Analysis [BJN]maxXvia xiai,aXxia 1( i)aXminsia xia Ca( a)aCa βa Xziisia βa zi viaixia 0IX( i, a)βa , zi 0( i, a)( i, a)Proof:1. Start from feasible primal and dual (xia 0, βa 0, andzi 0, i.e., Primal Dual 0).2. After each assignment, update x, β, z variables and keepprimal and dual solutions.3. Show (Dual) (1 e1 ) (Primal).

Ad Allocation: Problems and ModelsOnline Matching:via sia 1Worst CaseStochastic(randomarrivalorder)Greedy: 12 ,[KVV]: 1 e1 -aprx[FMMM09]:0.67-aprxDisp. Ads (DA):sia 1InapproximableFree Disposal[FKMMP09]:1 e1 -aprx[FHKMS10,AWY]:1 -aprx,if opt max viaand n mAdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max via

Outline: Online AllocationIOnline Stochastic Assignment ProblemsIIIIIOnline (Stochastic) MatchingOnline Generalized Assignment (with free disposal)Online Stochastic PackingExperimental EvaluationOnline Learning and Allocation

Dual-based Algorithms in PracticeIAlgorithm:IAssign each item i to ad a that maximizes via βa .

Dual-based Algorithms in PracticeIAlgorithm:IIAssign each item i to ad a that maximizes via βa .More practical compared to Primal Algorithms:IIJust keep one number βa per advertiser.Suitable for Distributed Ad Serving Schemes.

Dual-based Algorithms in PracticeIAlgorithm:IIMore practical compared to Primal Algorithms:IIIAssign each item i to ad a that maximizes via βa .Just keep one number βa per advertiser.Suitable for Distributed Ad Serving Schemes.Training-based AlgorithmsICompute βa based on historical/sample data.

Dual-based Algorithms in PracticeIAlgorithm:IIMore practical compared to Primal Algorithms:IIIJust keep one number βa per advertiser.Suitable for Distributed Ad Serving Schemes.Training-based AlgorithmsIIAssign each item i to ad a that maximizes via βa .Compute βa based on historical/sample data.Hybrid approach (see also [MNS07]):IStart with trained βa (past history), blend in online algorithm.

Experiments: setupIReal ad impression data from several large publishersI200k - 1.5M impressions in simulation periodI100 - 2600 advertisersIEdge weights predicted click probabilityIEfficiency: free disposal modelAlgorithms:IIIIIIgreedy: maximum marginal valuepd-avg, pd-exp: pure online primal-dual from [FKMMP09].dualbase: training-based primal-dual [FHKMS10]hybrid: convex combo of training based, pure online.lp-weight: optimum efficiency

Experimental Evaluation: dAvg Efficiency%1006977828789Ipd-exp & pd-avg outperform greedy by 9% and 14% (withmore improvements in tight competition.)Idualbase outperforms pure online algorithms by 6% to 12%.IHybrid has a mild improvement of 2% (up to 10%).Ipd-avg performs much better than the theoretical analysis.

Other Metrics: FairnessIQualititative definition: advertisers are “treated equally.”

Other Metrics: FairnessIIQualititative definition: advertisers are “treated equally.”Quantitative definition that achieves this:Ivaried and often subjective.

Other Metrics: FairnessIIQualititative definition: advertisers are “treated equally.”Quantitative definition that achieves this:IIvaried and often subjective.One suggestion[FHKMS10]: Compute ”fair” solution x ,measure 1 distance to x .

Other Metrics: FairnessIIQualititative definition: advertisers are “treated equally.”Quantitative definition that achieves this:IIIvaried and often subjective.One suggestion[FHKMS10]: Compute ”fair” solution x ,measure 1 distance to x .Fair solution:IIEach a chooses best Ca impressions (highest via )Repeat:IIImpressions shared among those who chose them.If some a not receiving Ca imps, a chooses an additional imp.

Other Metrics: FairnessIIQualititative definition: advertisers are “treated equally.”Quantitative definition that achieves this:IIIvaried and often subjective.One suggestion[FHKMS10]: Compute ”fair” solution x ,measure

Contract-based Online Advertising I Pageviews (impressions) instead of queries. I Display/Banner Ads, Video Ads, Mobile Ads. I Cost-Per-Impression (CPM). I Not Auction-based:o ine negotiations Online allocations. Display/Banner Ads: I Q1, 2010: One Trillion Display Ads in US. 2:7 billion. I Top Publishers: Facebook, Yahoo and Microsoft sites. I Top Advertiser: AT&T, Verizon, Scottrade.