1y ago

43 Views

2 Downloads

1.34 MB

161 Pages

Transcription

Online Ad Serving: Theory and PracticeVahab Mirrokni(Three papers in collaboration with Googlers)Google Research, New YorkOctober 20, 2010

Contract-based Online AdvertisingIPageviews (impressions) instead of queries.IDisplay/Banner Ads, Video Ads, Mobile Ads.

Contract-based Online AdvertisingIPageviews (impressions) instead of queries.IDisplay/Banner Ads, Video Ads, Mobile Ads.ICost-Per-Impression (CPM).INot Auction-based: offline negotiations Online allocations.

Contract-based Online AdvertisingIPageviews (impressions) instead of queries.IDisplay/Banner Ads, Video Ads, Mobile Ads.ICost-Per-Impression (CPM).INot Auction-based: offline negotiations Online allocations.Display/Banner Ads:IQ1, 2010: One Trillion Display Ads in US. 2.7 billion.ITop Publishers: Facebook, Yahoo and Microsoft sites.ITop Advertiser: AT&T, Verizon, Scottrade.

Contract-based Online AdvertisingIPageviews (impressions) instead of queries.IDisplay/Banner Ads, Video Ads, Mobile Ads.ICost-Per-Impression (CPM).INot Auction-based: offline negotiations Online allocations.Display/Banner Ads:IQ1, 2010: One Trillion Display Ads in US. 2.7 billion.ITop Publishers: Facebook, Yahoo and Microsoft sites.ITop Advertiser: AT&T, Verizon, Scottrade.IAd Serving Systems e.g. Facebook, Google Doubleclick,AdMob.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Ad Serving: Targeting:Allocation:1. Planning: Contracts/Commitments with Advertisers.2. Ad Serving:IITargeting: Predicting value of impressions.Ad Allocation: Assigning Impressions to Ads Online.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Offline, OnlineStrategic, StochasticAd Serving: Targeting:Allocation:Online, Stochastic1. Planning: Contracts/Commitments with Advertisers.2. Ad Serving:IITargeting: Predicting value of impressions.Ad Allocation: Assigning Impressions to Ads Online.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Offline, OnlineForecastingStrategic, StochasticSupply of impressionsDemand for adsAd Serving: Targeting:Allocation:Online, Stochastic1. Planning: Contracts/Commitments with Advertisers.2. Ad Serving:IITargeting: Predicting value of impressions.Ad Allocation: Assigning Impressions to Ads Online.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Delivery Constraints, BudgetOffline, OnlineForecastingStrategic, StochasticSupply of impressionsDemand for adsAd Serving: Targeting:Allocation:Online, Stochastic1. Planning: Contracts/Commitments with Advertisers.2. Ad Serving:IITargeting: Predicting value of impressions.Ad Allocation: Assigning Impressions to Ads Online.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Delivery Constraints, BudgetOffline, OnlineForecastingStrategic, StochasticSupply of impressionsDemand for adsAd Serving: Targeting:CTRAllocation:Online, Stochastic1. Planning: Contracts/Commitments with Advertisers.2. Ad Serving:IITargeting: Predicting value of impressions.Ad Allocation: Assigning Impressions to Ads Online.

Display Ad Delivery: OverviewDisplay Ad DeliveryPlanning:Delivery Constraints, BudgetOffline, OnlineForecastingStrategic, StochasticSupply of impressionsDemand for adsAd Serving: Targeting:CTRAllocation:Online, StochasticIObjective Functions:IIEfficiency: Users and Advertisers. Revenue of the Publisher.Smoothness, Fairness, Delivery Penalty.

TargetingEstimating Value of an impression.

TargetingEstimating Value of an impression.I Behavioral TargetingIIInterest-based Advertising.Yan, Liu, Wang, Zhang, Jiang, Chen, 2009, How much canBehavioral Targeting Help Online Advertising?

TargetingEstimating Value of an impression.I Behavioral TargetingIIIInterest-based Advertising.Yan, Liu, Wang, Zhang, Jiang, Chen, 2009, How much canBehavioral Targeting Help Online Advertising?Contextual TargetingIIInformation Retrieval (IR).Broder, Fontoura, Josifovski, Riedel, A semantic approach tocontextual advertising

TargetingEstimating Value of an impression.I Behavioral TargetingIIIContextual TargetingIIIInterest-based Advertising.Yan, Liu, Wang, Zhang, Jiang, Chen, 2009, How much canBehavioral Targeting Help Online Advertising?Information Retrieval (IR).Broder, Fontoura, Josifovski, Riedel, A semantic approach tocontextual advertisingCreative OptimizationIExperimentation

Predicting value of Impressions for Display AdsIEstimating Click-Through-Rate (CTR).IIBudgeted Multi-armed BanditProbability of Conversion.

Predicting value of Impressions for Display AdsIEstimating Click-Through-Rate (CTR).IIIBudgeted Multi-armed BanditProbability of Conversion.Long-term vs. Short-term value of display ads?IArchak, Mirrokni, Muthukrishnan, 2010 Graph-based Models.IIComputing Adfactors based on AdGraphsMarkov Models for Advertiser-specific User Behavior

Contract-based Ad Delivery: OutlineIBasic InformationIAd Planning: ReservationAd Serving.IIITargeting.Online Ad Allocation

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

Online Ad AllocationIWhen page arrives, assign an eligible ad.Ivalue of assigning page i to ad a: via

Online Ad AllocationIWhen page arrives, assign an eligible ad.IIvalue of assigning page i to ad a: viaDisplay Ads (DA) problem:IIMaximize value ofPads served: maxCapacity of ad a: i A(a) xia CaPi,a via xia

Online Ad AllocationIWhen page arrives, assign an eligible ad.IIrevenue from assigning page i to ad a: bia“AdWords” (AW) problem:IIMaximize revenuePof ads served: maxBudget of ad a: i A(a) bia xia BaPi,abia xia

General Form of LPmaxXvia xiai,aXxia 1( i)sia xia Ca( a)aXixia 0Online Matching:via sia 1( i, a)Disp. Ads (DA):sia 1AdWords (AW):sia via

General Form of LPmaxXvia xiai,aXxia 1( i)sia xia Ca( a)aXixia 0Worst-CaseOnline Matching:via sia 1Greedy: 21 ,[KVV]: 1 e1 -aprx( i, a)Disp. Ads (DA):sia 1InapproximableAdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx

Ad Allocation: Problems and ModelsWorst CaseOnline Matching:via sia 1Greedy: 12 ,[KVV]: 1 e1 -aprxDisp. Ads (DA):sia 1Inapproximable?AdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx

Ad Allocation: Problems and ModelsWorst CaseOnline Matching:via sia 1Greedy: 12 ,[KVV]: 1 e1 -aprxStochastic(i.i.d.)Disp. Ads (DA):sia 1Inapproximable?AdWords (AW):sia via[MSVV,BJN]:1 e1 -aprx[DH09]:1 -aprx,ifopt max viaStochastic i.i.d model:Ii.i.d model with known distributionIrandom order model (i.i.d model with unknown distribution)

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 viaStochastic i.i.d model:Ii.i.d model with known distributionIrandom order model (i.i.d model with unknown distribution)

Online Stochastic Matching: MotivationIPageview supply from the past should tell us something aboutthe future [Parkes, Sandholm, SSA 2005][Abrams,Mendelevitch, Tomlin, EC 07] [Boutilier, Parkes, Sandholm,Walsh AAAI 08].

Online Stochastic Matching: MotivationIPageview supply from the past should tell us something aboutthe future [Parkes, Sandholm, SSA 2005][Abrams,Mendelevitch, Tomlin, EC 07] [Boutilier, Parkes, Sandholm,Walsh AAAI 08].IPrimal Algorithm:IIIConstruct an expected instance,Compute an optimal solution to this expected instance,Use this solution to guide the online allocation.

Online Stochastic Matching: MotivationIPageview supply from the past should tell us something aboutthe future [Parkes, Sandholm, SSA 2005][Abrams,Mendelevitch, Tomlin, EC 07] [Boutilier, Parkes, Sandholm,Walsh AAAI 08].IPrimal Algorithm:IIIIConstruct an expected instance,Compute an optimal solution to this expected instance,Use this solution to guide the online allocation.Can we extend the theory of online algorithms to thisarchitecture?

Online Stochastic Matching: iid (known dist.)Given (offline):- Bipartite graph G (A, I , E ),- Distribution D over I .Online:- n indep. draws from D.- Must assign nodes upon arrival.

Primal Algorithm: “Two-suggested-matchings”ALG(H)“ALG is α-approximation?” if w.h.p., OPT(H) αSimple Primal Algorithm:IFind one matching in expected graph G offline, and try toapply it online.ITight 1 e1 -approximation.

Primal Algorithm: “Two-suggested-matchings”ALG(H)“ALG is α-approximation?” if w.h.p., OPT(H) αSimple Primal Algorithm:IFind one matching in expected graph G offline, and try toapply it online.ITight 1 e1 -approximation.Better Algorithm: Two-Suggested-MatchingsIOffline: Find two disjoint matchings, blue(B) and red(R), onthe expected graph G .IOnline: try the blue matching first, then if that doesn’t work,try the red one.

Primal Algorithm: “Two-suggested-matchings”ALG(H)“ALG is α-approximation?” if w.h.p., OPT(H) αSimple Primal Algorithm:IFind one matching in expected graph G offline, and try toapply it online.ITight 1 e1 -approximation.Better Algorithm: Two-Suggested-MatchingsIOffline: Find two disjoint matchings, blue(B) and red(R), onthe expected graph G .IOnline: try the blue matching first, then if that doesn’t work,try the red one.IThm: Tight1 2/e 24/3 2/3e 0.67(Feldman, M., M., Muthukrishnan, 2009).

Background: Balls in binsISuppose n balls thrown into n bins, i.i.d. uniform.

Background: Balls in binsISuppose n balls thrown into n bins, i.i.d. uniform.I# non-empty bins concentrates:

Background: Balls in binsISuppose n balls thrown into n bins, i.i.d. uniform.I# non-empty bins concentrates:IB particular subset of bins.

Background: Balls in binsISuppose n balls thrown into n bins, i.i.d. uniform.I# non-empty bins concentrates:IB particular subset of bins.Is # bins in B with 1 ball.

Background: Balls in binsISuppose n balls thrown into n bins, i.i.d. uniform.I# non-empty bins concentrates:IB particular subset of bins.Is # bins in B with 1 ball.IThen w.h.p., s B (1 e1 ).

Analysis: Two-suggested-matching AlgorithmIProof Ideas: Balls-into-Bins concentration inequalities,structural properties of min-cuts, etc.

Analysis: Two-suggested-matching AlgorithmIProof Ideas: Balls-into-Bins concentration inequalities,structural properties of min-cuts, etc.Bounding ALG: Classify a A based on its neighbors in theblue and red matchings: ABR , ABB , AB , AR 231ALG 1 2 ABB 1 2 ABR 1 ( AB AR )ee2eI

Analysis: Two-suggested-matching AlgorithmIProof Ideas: Balls-into-Bins concentration inequalities,structural properties of min-cuts, etc.Bounding ALG: Classify a A based on its neighbors in theblue and red matchings: ABR , ABB , AB , AR 231ALG 1 2 ABB 1 2 ABR 1 ( AB AR )ee2eIIBounding opt: Find min-cut in augmented expected graph G ,and use it min-cut in G as a “guide” for cut in each scenario.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.IDoes no better than 1 1/e.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.IDoes no better than 1 1/e.IProof:ISuppose G complete graph.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.IDoes no better than 1 1/e.IProof:IISuppose G complete graph.Then OPT(H) n.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.IDoes no better than 1 1/e.IProof:IIISuppose G complete graph.Then OPT(H) n.But w.h.p. only 1 1/e fraction of I will ever arrive. ALG (1 1/e)n.

First Attempt: “Suggested matching”1. Find a maximum matching in G .2. Use that matching as nodes arrive online.IDoes no better than 1 1/e.IProof:IIIISuppose G complete graph.Then OPT(H) n.But w.h.p. only 1 1/e fraction of I will ever arrive. ALG (1 1/e)n.In fact, this algorithm does achieve 1 1/e (in paper).

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.

Related Documents: