stanford大學-大數(shù)據(jù)挖掘-advertising-19(編輯修改稿)
2025-01-26 18:45 本頁面
【文章內(nèi)容簡介】 rrives at the search engine ? q1, q2,… ? Several advertisers bid on each query ? When query qi arrives, search engine must pick a subset of advertisers whose ads are shown ? Goal: maximize search engine’s revenues ? Clearly we need an online algorithm! Greedy algorithm ? Simplest algorithm is greedy ? It’s easy to see that the greedy algorithm is actually optimal! Complications (1) ? Each ad has a different likelihood of being clicked ? Advertiser 1 bids $2, click probability = ? Advertiser 2 bids $1, click probability = ? Clickthrough rate measured historically ? Simple solution ? Instead of raw bids, use the “expected revenue per click” The Adwords Innovation Advertiser Bid CTR Bid * CTR A B C $ $ $ 1% 2% % 1 cent cents cents The Adwords Innovation Advertiser Bid CTR Bid * CTR A B C $ $ $ 1% 2% % 1 cent cents cents Complications (2) ? Each advertiser has a limited budget ? Search engine guarantees that the advertiser will not be charged more than their daily budget Simplified model (for now) ? Assume all bids are 0 or 1 ? Each advertiser has the same budget B ? One advertiser per query ? Let’s try the greedy algorithm ? Arbitrarily pick an eligible advertiser for each keyword Bad scenario for greedy ? Two advertisers A and B ? A bids on query x, B bids on x and y ? Both have budgets of $4 ? Query stream: xxxxyyyy ? Worst case greedy choice: BBBB____ ? Optimal: AAAABBBB ? Competitive ratio =
公司管理相關推薦
鄂ICP備17016276號-1