CS 345 Data MiningOnline algorithms Search advertisingOnline algorithmsoClassic model of algorithmsnYou get to see the entire input, then compute some function of itnIn this context, “offline algorithm”oOnline algorithmnYou get to see the input one piece at a time, and need to make irrevocable decisions along the wayoSimilar to data stream modelsExample: Bipartite matching1234abcdGirlsBoysExample: Bipartite matching1234abcdM = (1,a),(2,b),(3,d) is a matching Cardinality of matching = |M| = 3GirlsBoysExample: Bipartite matching1234abcdGirlsBoysM = (1,c),(2,b),(3,d),(4,a) is a perfect matchingMatching AlgorithmoProblem: Find a maximum-cardinality matching for a given bipartite graphnA perfect one if it existsoThere is a polynomial-time offline algorithm (Hopcroft and Karp 1973)oBut what if we dont have the entire graph upfront?Online problemoInitially, we are given the set BoysoIn each round, one girls choices are revealedoAt that time, we have to decide to either:nPair the girl with a boynDont pair the girl with any boyoExample of application: assigning tasks to serversOnline problem1234abcd(1,a)(2,b)(3,d)Greedy algorithmoPair the new girl with any eligible boynIf there is none, dont pair girloHow good is the algorithm?Competitive RatiooFor input I, suppose greedy produces matching Mgreedy while an optimal matching is MoptCompetitive ratio = minall possible inputs I (|Mgreedy|/|Mopt|)Analyzing the greedy algorithmoConsider the set G of girls matched in Mopt but not in MgreedyoThen it must be the case that every boy adjacent to girls in G is already matched in MgreedyoThere must be at least |G| such boysnOtherwise the optimal algorithm could not have matched all the G girlsoTherefore |Mgreedy| |G| = |Mopt - Mgreedy| |Mgreedy|/|Mopt| 1/2Worst-case scenario1234abc(1,a)(2,b)dHistory of web advertisingoBanner ads (1995-2001)nInitial form of web advertisingnPopular websites charged X$ for every 1000 “impressions” of adoCalled “CPM” rateoModeled similar to TV, magazine adsnUntargeted to demographically tagetednLow clickthrough ratesolow ROI for advertisersPerformance-based advertisingoIntroduced by Overture around 2000nAdvertisers “bid” on search keywordsnWhen someone searches for that keyword, the highest bidders ad is shownnAdvertiser is charged only if the ad is clicked onoSimilar model adopted by Google with some changes around 2002nCalled “Adwords”Ads vs. search resultsWeb 2.0oPerformance-based advertising works!nMulti-billion-dollar industryoInteresting problemsnWhat ads to show for a search?nIf Im an advertiser, which search terms should I bid on and how much to bid?Adwords problemoA stream of queries arrives at the search enginenq1, q2,oSeveral advertisers bid on each queryoWhen query qi arrives, search engine must pick a subset of advertisers whose ads are shownoGoal: maximize search engines revenuesoClearly we need an online algorithm!Greedy algorithmoSimplest algorithm is greedyoIts easy to see that the greedy algorithm is actually optimal!Complications (1)oEach ad has a different likelihood of being clickednAdvertiser 1 bids $2, click probability = 0.1nAdvertiser 2 bids $1, click probability = 0.5nClickthrough rate measured historicallyoSimple solutionnInstead of raw bids, use the “expected revenue per click”The Adwords InnovationAdvertiserBidCTRBid * CTRABC$1.00$0.75$0.501%2%2.5%1 cent1.5 cents1.125 centsThe Adwords InnovationAdvertiserBidCTRBid * CTRABC$1.00$0.75$0.501%2%2.5%1 cent1.5 cents1.125 centsComplications (2)oEach advertiser has a limited budgetnSearch engine guarantees that the advertiser will not be charged more than their daily budgetSimplified model (for now)oAssume all bids are 0 or 1oEach advertiser has the same budget BoOne advertiser per queryoLets try the greedy algorithmnArbitrarily pick an eligible advertiser for each keywordBad scenario for greedyoTwo advertisers A and BoA bids on query x, B bids on x and yoBoth have budgets of $4oQuery stream: xxxxyyyynWorst case greedy choice: BBBB_nOptimal: AAAABBBBnCompetitive ratio = oSimple analysis shows this is the worst caseBALANCE algorithm MSVVoMehta, Saberi, Vazirani, and VaziranioFor each query, pick the advertiser with the largest unspent budgetnBreak ties arbitrarilyExample: BALANCEoTwo advertisers A and BoA bids on query x, B bids on x and yoBoth have budgets of $4oQuery stream: xxxxyyyyoBALANCE choice: ABABBB_nOptimal: AAAABBBBoCompetitive ratio = Analyzing BALANCEoConsider simple case: two advertisers, A1 and A2, each with budget B (assume B 1)oAssume optimal solution exhausts both advertisers budgetsoBALANCE must exhaust at least one advertisers budgetnIf not, we can allocate more queriesnAssume BALANCE exhausts A2s budgetAnalyzing BalanceA1A2BxyBA1A2xOpt revenue = 2B Balance revenue = 2B-x = B+yWe have y x Balance revenue is minimum for x=y=B/2 Minimum Balance revenue = 3B/2 Competitive Ratio = 3/4Queries allocated to A1 in optimal solutionQueries al