Hybrid keyword auctions l.jpg
1 / 38

Hybrid Keyword Auctions.


53 views
Uploaded on:
Category: General / Misc
Description
Hybrid Keyword Auctions Kamesh Munagala Duke University Joint work with Ashish Goel, Stanford University Online Advertising Pricing Models CPM (Cost per thousand impressions) CPC (Cost per click) CPA (Cost per acquisition) Conversion rates:
Transcripts
Slide 1

Half breed Keyword Auctions Kamesh Munagala Duke University Joint work with Ashish Goel, Stanford University

Slide 2

Online Advertising Pricing Models CPM (Cost per thousand impressions) CPC (Cost per click) CPA (Cost per obtaining) Conversion rates: Click-through-rate (CTR), transformation from snaps to acquisitions, … Differences between these evaluating models: Uncertainty in transformation rates: Sparse information, evolving rates, … Stochastic vacillations: Even if the change rates were known precisely, the quantity of snaps/transformations would in any case shift, particularly for little specimens Kamesh Munagala, kamesh@cs.duke.edu

Slide 3

Sponsored Search Auction CTR assessment Auctioneer (Search Engine) Bid = Cost per Click Advertiser Q C Value/impression requesting: C 1 Q 1 > C 2 Q 2 > … Give impression to bidder 1 at CPC = C 2 Q 2/Q 1 VCG Mechanism: Truthful for a solitary opening, expecting static CTR appraisals Can be made honest for various spaces [ Vickrey-Clark-Groves , Myerson81, AGM06 ] This discussion will concentrate on single opening for verifications/samples Kamesh Munagala, kamesh@cs.duke.edu

Slide 4

When Does this Work Well? High volume targets (magic words) Good gauges of CTR What division of targets are high volume? Old stories: a little part Motivating issue: How to better adapt the low volume watchwords? Kamesh Munagala, kamesh@cs.duke.edu

Slide 5

Kamesh Munagala, kamesh@cs.duke.edu

Slide 6

Kamesh Munagala, kamesh@cs.duke.edu

Slide 7

Possible Solutions Coarse promotion gatherings to anticipate CTR: Use execution of promoter on conceivably irrelevant watchwords Predictive models Regression examination/highlight extraction Taxonomies/bunching Collaborative separating Our methodology: Devise wealthier valuing models Kamesh Munagala, kamesh@cs.duke.edu

Slide 8

Hybrid Scheme Bid 1 = Cost for each Impression Bid 2 = Cost for every Click Auctioneer (Search Engine) Advertiser <M,C > Kamesh Munagala, kamesh@cs.duke.edu

Slide 9

Hybrid Scheme Bid 1 = Cost for every Impression Bid 2 = Cost for every Click CTR appraisal Auctioneer (Search Engine) Advertiser Q <M,C > Kamesh Munagala, kamesh@cs.duke.edu

Slide 10

Hybrid Scheme Bid 1 = Cost for each Impression Bid 2 = Cost for every Click CTR evaluation Auctioneer (Search Engine) Advertiser Q <M,C > Advertiser’s score R i = max { M i , C i Q i } Kamesh Munagala, kamesh@cs.duke.edu

Slide 11

Hybrid Scheme Bid 1 = Cost for every Impression Bid 2 = Cost for every Click CTR assessment Auctioneer (Search Engine) Advertiser Q <M,C > Advertiser’s score R i = max { M i , C i Q i } Order by score: R 1 > R 2 > … Kamesh Munagala, kamesh@cs.duke.edu

Slide 12

Hybrid Scheme Bid 1 = Cost for each Impression Bid 2 = Cost for each Click CTR evaluation Auctioneer (Search Engine) Advertiser Q <M,C > Advertiser’s score R i = max { M i , C i Q i } Order by score: R 1 > R 2 > … Give impression to bidder 1: If M 1 > C 1 Q 1 then charge R 2 for each impression If M 1 < C 1 Q 1 then charge R 2/Q 1 for each snap Kamesh Munagala, kamesh@cs.duke.edu

Slide 13

Why Such a Model? Per-impression offer: Advertiser’s appraisal or “belief” of CTR May or may not be a precise impression of reality Backward perfect with expense per-click (CPC) offering Kamesh Munagala, kamesh@cs.duke.edu

Slide 14

Why Such a Model? Per-impression offer: Advertiser’s appraisal or “belief” of CTR May or may not be an exact impression of reality Backward perfect with expense per-click (CPC) offering Why might the publicist know any better? Sponsor totals information from different distributers Has space particular models not accessible to barker Is willing to pay a premium for inner analyses Kamesh Munagala, kamesh@cs.duke.edu

Slide 15

Benefits Search motor: Better adaptation of low volume magic words Advertiser: Opportunity to make the web crawler merge to the right CTR gauge without paying a premium Technical: Truthful Accounts for danger qualities of the promoter Allows clients to actualize complex methods Kamesh Munagala, kamesh@cs.duke.edu

Slide 16

Multiple Slots Show the top K scoring sponsors Assume R 1 > R 2 > … > R K > R K+1 … Generalized Second Price (GSP) system: For the i th promoter, if: If M i > Q i C i then charge R i+1 per impression If M i < Q i C i then charge R i+1/Q i per click Kamesh Munagala, kamesh@cs.duke.edu

Slide 17

Multiple Slots Show the top K scoring promoters Assume R 1 > R 2 > … > R K > R K+1 … Generalized Second Price (GSP) instrument: For the i th publicist, if: If M i > Q i C i then charge R i+1 per impression If M i < Q i C i then charge R i+1/Q i per snap Can likewise execute VCG [ Vickrey-Clark-Groves , Myerson81, AGM06 ] Need distinguishable CTR suspicion Details in the paper Kamesh Munagala, kamesh@cs.duke.edu

Slide 18

Bayesian Model for CTR True fundamental CTR = p Auctioneer (Search Engine) Advertiser Kamesh Munagala, kamesh@cs.duke.edu

Slide 19

Bayesian Model for CTR True hidden CTR = p Prior dissemination P auc Prior conveyance P adv (Public) (Private) Auctioneer (Search Engine) Advertiser Kamesh Munagala, kamesh@cs.duke.edu

Slide 20

Bayesian Model for CTR True basic CTR = p Per-impression offer M CTR gauge Q Prior circulation P auc Prior appropriation P adv (Public) (Private) Auctioneer (Search Engine) Advertiser Kamesh Munagala, kamesh@cs.duke.edu

Slide 21

Bayesian Model for CTR True basic CTR = p Per-impression offer M CTR gauge Q Prior dispersion P auc Prior circulation P adv (Public) (Private) Auctioneer (Search Engine) Advertiser Each operators improves in view of its flow “belief” or former: Beliefs overhauled with each impression Over time, turn out to be strongly thought around genuine CTR Kamesh Munagala, kamesh@cs.duke.edu

Slide 22

What is a Prior? Essentially models uneven data Sharper earlier  More sure about genuine CTR p E[ Prior ] require not be equivalent to p Main point of preference of per-impression offers is when: Advertiser’s former is more honed than auctioneer’s Limiting case: Advertiser sure about CTR p Priors are just for motivation behind investigation Mechanism is all around characterized paying little mind to demonstrating suspicions Kamesh Munagala, kamesh@cs.duke.edu

Slide 23

Truthfulness Advertiser accept CTR takes after dispersion P adv Wishes to expand expected benefit at current step E[ P adv ] = x = Expected conviction about CTR Utility from snap = C Expected benefit = C x - Expected cost Kamesh Munagala, kamesh@cs.duke.edu

Slide 24

Truthfulness Advertiser accept CTR takes after circulation P adv Wishes to amplify expected benefit at current step E[ P adv ] = x = Expected conviction about CTR Utility from snap = C Expected benefit = C x - Expected value Let Cy = Per impression offer R 2 = Highest other score If max ( Cy, C Q ) < R 2 then Price = 0 Else: If y < Q then: Price = x R 2/Q If y > Q then: Price = R 2 Kamesh Munagala, kamesh@cs.duke.edu

Slide 25

Truthfulness Advertiser expect CTR takes after conveyance P adv Wishes to boost expected benefit at current step E[ P adv ] = x = Expected conviction about CTR Utility from snap = C Expected benefit = C x - Expected value Bidding ( Cx, C ) is the overwhelming procedure Regardless of Q utilized by barker Regardless of P adv and genuine CTR p Elicits advertiser’s “expected belief” about the CTR! Holds in numerous different settings (all the more later) Kamesh Munagala, kamesh@cs.duke.edu

Slide 26

Conjugate Beta Priors P auc for promoter i = Beta(  ,  )  ,  are sure whole numbers Conjugate of Bernoulli appropriation (CTR) Expected worth = /(  +  ) Bayesian earlier redesign: Probability of a tick at the following step is: /(  +  ) If click, new P auc (back) = Beta(  ,  ) If no snap, new P auc (back) = Beta(  ,  ) Kamesh Munagala, kamesh@cs.duke.edu

Slide 27

Evolution of Beta Priors Click Denotes Beta(1,1) Uniform former Uninformative 1,1 No Click 1/2 1/2 2,1 1,2 2/3 1/3 1/3 2/3 E[P auc ] = 1/4 3,1 2,2 1,3 1/4 1/2 3/4 1/2 3/4 1/4 4,1 3,2 2,3 1,4 E[P auc ] = 2/5 Kamesh Munagala, kamesh@cs.duke.edu

Slide 28

Properties Larger  ,   Sharper fixation around p Uninformative former: Beta (  ,  ) = Uniform [0,1] Q = E[ P auc ] = /(  +  ) Encodes auctioneer’s “belief” Could be unique in relation to genuine CTR p Kamesh Munagala, kamesh@cs.duke.edu

Slide 29

Certain Advertiser Knows genuine CTR p and offers reasonably ( M i = p i ) P adv = p i with likelihood 1 P auc = Beta(  i ,  i ) and Q i = E [ P auc ] =  i/(  i +  i ) Revenue properties of salesperson: Worst case: 63% of CPC plan Canonical case: log n times superior to anything CPC plan Flexibility for publicist: Can make P auc meet to p without losing income But pays tremendous premium for accomplishing this in CPC closeout Kamesh Munagala, kamesh@cs.duke.edu

Slide 30

Better Monetization Illustrative Scenario: Low volume watchwords n sponsors, all snap utilities C = 1 All P auc = Beta (  , log n ) so that E [ P auc ] = Q ≈ 1/log n High change former Some p i near 1 with high likelihood Per-impression offer will evoke this high p i CPC closeout distributes opening to an arbitrary promoter Theorem: Hybrid closeout can produce log n times mo