Web Advertising
Note to other teachers and users of these slides: We would be delighted if you found this our material useful in giving your own lectures. Feel free to use these slides verbatim, or to modify them to fit your own needs. If you make use of a significant portion of these slides in your own lecture, please include this message, or a link to our web site: http://www.mmds.org
Types of Web Ads
! Advertisers post ads directly
Ø Craig’s List, auto trading sites, social networks
! Advertisers pay for display ads to be placed on websites Ø Fixed price per impression (one display of the ad with download of
page by a user)
! Online stores show ads
Ø Amazon, Macy’s, etc.
Ø Selected by store to maximize probability customer will buy product Ø Collaborative Filtering
! Search ads are placed among results of a search query
Ø Advertisers bid for right to have their ad shown in response to certain
queries
Ø Pay only if ad is clicked on
2
Types of Web Ads
! Advertisers pay for display ads to be placed on websites
Ø Often has a fixed price per impression (one display of the ad with
download of page by a user)
! Online stores show ads Ø Amazon, Macy’s, etc.
Ø Selected by store to maximize probability customer will buy prod Ø Collaborative Filtering
! Search ads are placed among results of a search query
Ø Advertisers bid for right to have their ad shown in response to certa
queries
Ø Pay only if ad is clicked on
3
Types of Web Ads
! Online stores show ads
Ø Amazon, Macy’s, etc.
Ø Selected by store to maximize probability customer will buy product Ø Collaborative Filtering
4
Types of Web Ads: Search Ads
5
Search Ads Overview
! Most lucrative venue for on-line advertising: SEARCH
! Impression of an Ad Ø Ad is displayed
Ø User clicked on the ad link to download the page
! Search engine charges advertisers for impression of their
ads
! Adwords model (Google): matching search queries to advertisements
Ø Require algorithms for optimizing this assignment • Greedy algorithms
• Online algorithms
6
Google AdWords
7
Google AdWords
8
Matching Keywords with Searches
! Match types: exact, phrase, broad, negative
9
Online Algorithms
! Classic model of algorithms
Ø Use the entire input to compute some result
• “offline algorithm” ! Online Algorithms
Ø You get to see the input one piece at a time, and need to make irrevocable decisions along the way
Ø Make decisions without knowing the future
Ø For search: only know past queries and current query; don’t know
what queries will come in later
Ø Similar to handling data streams
! An online algorithm cannot always do as well as an offline algorithm
10
Example 8.1
! Knowing the future could help
! Manufacturer A of conventional furniture
Øbids 20 cents on both terms “sofa” and “chesterfield” ! Manufacturer B of antique furniture
Øbids 10 cents on search term “chesterfield” ! Both have monthly budget of $100
ØB can place its ad 1,000 times, A can place its ad 500 times ! Query “chesterfield” arrives
! Can only display one ad
! Might display A’s ad because A bid more, but…
11
Example 8.1
! Knowing the future could help
! Might display A’s ad because A bid more
Ø 20 cents vs 10 cents
! However, if there are many queries for “sofa” and few for “chesterfield,” B will never spend its full budget
Ø B only bids on “chesterfield”
! Sending “chesterfield” queries to B might increase overall
revenue
! Without knowing the future, on-line algorithm may not perform as well as offline
12
Offline Query-Ad Matching Problem
! Advertisers, each
ØBids on keywords : “sofa”: 10 cents/impression ØHas a budget, e.g., $100/mon
! A set of queries in some month, say Sep 2015 Øe.g., 600 “chesterfield”, 100 “sofa”
! Find assignments of queries to bids, such that ØTotal profit is maximized
13
Greedy Approach
! Consider two furniture manufacturers A and B ØA: bids 20 cents on “chesterfield”; 10 cents on “sofa”
ØB: bids 10 cents on “chesterfield” ØBoth A and B have budget: $100/month
! Queries: 600 “chesterfield”, 100 “sofa” Ø“chesterfield”: 500 to A => profit: $100 Ø“chesterfield”: 100 to B => profit: $10
=> Total profit: $110
14
Optimal Solution
! Consider two furniture manufacturers A and B
Ø A: bids 20 cents on “chesterfield”; 10 cents on “sofa” Ø B: bids 10 cents on “chesterfield”
Ø Both A and B have budget: $100/mon
! Queries: 600 “chesterfield”, 100 “sofa”
! Optimal solution: assignment of queries to bids that generates
the largest profit
! Queries: 600 “chesterfield”, 100 “sofa” Ø “sofa”: 100 to A => profit: $10
Ø “chesterfield”: 450 to A => profit: $90
Ø “chesterfield”: 150 to B => profit: $15
=> Total profit: $115
15
Comparison
Bids
Chesterfield
Sofa
Budget
A
20 cents
10 cents
$100
B
10 cents
$100
Queries
Chesterfield (600)
Sofa (100)
Profit
A
500
$100
B
100
$10
Greedy, Total profit: $110
Queries
Chesterfield (600)
Sofa (100)
Profit
A
450
100
$100
B
150
$15
Non-Greedy (Optimal), Total profit: $115
16
Online Bipartite Matching
Ads
Queries
18
The Matching Problem
! Simplified version of the problem of matching ads to search queries
! Looking for “Maximal matching” in a bipartite graph Ø involves bipartite graphs with two sets of nodes
! All edges connect node on left set to node in right set
a 2b
1
c 4d
Nodes: Queries and Ads
Goal: Match queries to ads so that maximum number of matchings are made
3
Example: Bipartite Matching
a 2b
1 3
c
Ads 4 d Queries
M = {(1,a),(2,b),(3,d)} is a matching Cardinality of matching = |M| = 3
19
Example: Bipartite Matching
a 2b
1 3
c
Ads 4 d Queries
M = {(1,c),(2,b),(3,d),(4,a)} is a perfect matching
Maximal matching: a matching that contains the largest
possible number of matches
Perfect matching: all vertices of the graph are matched 20
Matching Algorithm
! Problem: Find a maximal matching for a given bipartite graph
ØA perfect one if it exists
! There is a polynomial-time offline algorithm based on augmenting paths
Ø Hopcroft & Karp 1973, see http://en.wikipedia.org/wiki/Hopcroft- Karp_algorithm
! But what if we do not know the entire graph upfront?
21
Online Graph Matching Problem
! Initially, we are given the set ads
! In each round, one set of query terms is added
Ø Relevant edges are revealed
Ø Indicate which advertisers have
bid on those query terms
! At that time, we have to decide to either:
Ø Pair the query with an ad
Ø Do not pair the query with any ad
1a 2b
3c 4d
(1,a) (2,b) (3,d)
22
Greedy Algorithm
! Greedy algorithm for the online graph matching problem:
ØPair the new query with any eligible ad • If there is none, do not pair query
! How good is the algorithm?
23
Competitive Ratio
! For input I, suppose greedy produces matching Mgreedy while an optimal matching is Mopt
Competitive ratio =
minall possible inputs I (|Mgreedy|/|Mopt|)
greedy’s worst performance over all possible inputs I
24
Analyzing the Greedy Algorithm
! Consider a case: Mgreedy≠ Mopt ! Consider the set Q of queries
1 Mopt a
matched in Mopt but not in Mgreedy
to a non-matched query in Q, and A is
already matched in Mgreedy
Ø If there exists such a non-matched
(by Mgreedy) ad linked to a non-matched query, then greedy would have matched them
2 ! Aisthesetofadsthatarelinked 3
b
c
d
Q={ }
4
A={ }
! Since ads A are already matched in Mgreedy then (1) |Mgreedy|≥ |A|
25
Mgreedy
Analyzing the Greedy Algorithm
! Summary so far:
Ø Queries Q matched in Mopt but not in Mgreedy Ø (1) |Mgreedy|≥ |A|
1 Mopt 2
a
b
c
d
Q={ }
! There are at least |Q| such ads in A 3 (|Q| ≤|A|) otherwise the optimal algorithm
couldn’t have matched all queries in Q Ø So: |Q| ≤ |A| ≤ |Mgreedy|
4
A={ }
! Q’: matched in Mopt and also in Mgreedy Ø| Mopt | = | Q | + | Q’ | and | Q’ | ≤ |Mgreedy|
Ø|Mopt| ≤ |Q| + |Mgreedy|
Ø Worst case is when |Q| is maximum |Q|= |A| = |Mgreedy| ! |Mopt| ≤ 2|Mgreedy| then |Mgreedy|/|Mopt| ≥ 1⁄2
! Competitive Ratio = 1⁄2
! Greedy’s worst performance over all possible inputs I
26
Mgreedy
1
(1,a) (2,b)
Worst-case Scenario
a 2b
c 4d
3
• Worst case is when |Q| = |A| = |Mgreedy|
• Q = {c,d} – queries with no matching ad
• A={1,2}–adsthatareadjacenttoaqueryinQbutare
already matched to another query
• |Mgreedy|=2,|Q|=2,|A|=2
• Optimal matching: (1,c), (2,d), (3,b), (4,a)
• |Mopt| = 4
• |Mgreedy|/|Mopt| = 1⁄2 (competitive ratio)
27
Performance-based Web Advertising
History of Web Advertising
! Banner ads (1995-2001)
ØInitial form of web advertising
ØPopular websites charged $X for every 1,000 “impressions” of the ad
• Called “CPM” rate
(Cost per thousand impressions)
• Modeled similar to TV, magazine ads
CPM…cost per mille Mille…thousand in Latin
ØFrom untargeted to demographically targeted
ØLow click-through rates
• Low Return on Investment (ROI) for advertisers
29
Performance-based Advertising
! Introduced by Overture around 2000
ØAdvertisers bid on search keywords
ØWhen someone searches for that keyword, the highest bidder’s ad is shown first
ØAdvertiser is charged only if the ad is clicked on
! Similar model adopted by Google with some changes around 2002
ØCalled Adwords
30
Web 2.0
! Performance-based advertising works!
ØMulti-billion-dollar industry
! Interesting problem:
What ads to show for a given query?
Ø(Today’s lecture)
! If I am an advertiser, which search terms should I bid on and how much should I bid?
Ø(Not focus of today’s lecture)
31
! Given:
Adwords Problem
Ø1. A set of bids by advertisers for search queries
Ø2. A click-through rate (CTR) for each advertiser-query pair
Ø3. A budget for each advertiser (say for 1 month)
Ø4. A limit on the number of ads to be displayed with each search query
! Respond to each search query with a set of advertisers such that:
Ø1. The size of the set is no larger than the limit on the number of ads per query
Ø2. Each advertiser has bid on the search query
Ø3. Each advertiser has enough budget left to pay for the ad
if it is clicked upon
32
Adwords Problem
! A stream of queries arrives 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 ØSimple solution: Instead of raw bids, use the
“expected revenue per click” (i.e., Bid*CTR) ! Clearly we need an online algorithm!
33
The Adwords Innovation
Advertiser
Bid
CTR
1%
2% 2.5%
Click through rate
Bid * CTR
1 cent
1.5 cents
1.125 cents
Expected revenue
A $1.00
B $0.75
C $0.50
34
The Adwords Innovation
Advertiser
Bid CTR
Bid * CTR
1.5 cents 1.125 cents 1 cent
B $0.75 2%
C $0.50 2.5%
A $1.00 1%
35
Complications: Budget
! Two complications: Ø Budget
ØClick-through rate (CTR) of an ad is unknown ! Each advertiser has a limited budget
ØSearch engine guarantees that the advertiser
will not be charged more than their daily or monthly budget
36
Complications: CTR
! CTR: Each ad has a different likelihood of being clicked
ØAdvertiser 1 bids $2, click probability = 0.1
ØAdvertiser 2 bids $1, click probability = 0.5
ØClick-through rate (CTR) is measured historically
• Very hard problem: Exploration vs. exploitation
Exploit: Should we keep showing an ad for which we have good estimates of click-through rate
or
Explore: Shall we show a brand new ad to get a better sense of its click-through rate
37
Greedy Algorithm
! Our setting: Simplified environment ØThere is 1 ad shown for each query ØAll advertisers have the same budget B ØAll ads are equally likely to be clicked ØValue of each ad is the same (=1)
1a 2b
! Simplest algorithm is greedy:
ØFor a query pick any advertiser who has
bid 1 for that query ØCompetitive ratio of greedy is 1/2
c 4d
3
38
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: x x x x y y y y
ØWorst case greedy choice: B B B B _ _ _ _ ØOptimal: AAAABBBB
ØCompetitive ratio = 1⁄2
! This is the worst case!
ØNote: Greedy algorithm is deterministic – it always resolves draws in the same way
39
Greedy algorithm with non-equal bids
! Greedy algorithm would assign the query to the highest bidder who still has budget left
40
Greedy Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
Remaining Budget for A1
40
Remaining Budget for A2
50
41
Greedy Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A1
Remaining Budget for A1
40
20
Remaining Budget for A2
50
50
42
Greedy Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A1
A1
Remaining Budget for A1
40
20
0
Remaining Budget for A2
50
50
50
43
Greedy Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A1
A1
A2
Remaining Budget for A1
40
20
0
0
Remaining Budget for A2
50
50
50
40
44
Greedy Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A1
A1
A2
A2
A2
A2
A2
No ad
Remaining Budget for A1
40
20
0
0
0
0
0
0
0
Remaining Budget for A2
50
50
50
40
30
20
10
0
0
45
BALANCE Algorithm [MSVV]
! BALANCE Algorithm by Mehta, Saberi, Vazirani, and Vazirani
ØFor each query, pick the advertiser with the largest unspent budget
• Break ties arbitrarily (but in a deterministic way)
46
Example: BALANCE
! Two advertisers A and B
ØA bids on query x, B bids on x and y ØBoth have budgets of $4
! Query stream: x x x x y y y y
! BALANCE choice: A B A B B B _ _
ØOptimal: A A A A B B B B
! In general: For BALANCE on 2 advertisers Competitive ratio = 3⁄4
47
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
Remaining Budget for A1
40
Remaining Budget for A2
50
48
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
Remaining Budget for A1
40
40
Remaining Budget for A2
50
40
49
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
Remaining Budget for A1
40
40
20
Remaining Budget for A2
50
40
40
50
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
A2
Remaining Budget for A1
40
40
20
20
Remaining Budget for A2
50
40
40
30
51
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
A2
A2
Remaining Budget for A1
40
40
20
20
20
Remaining Budget for A2
50
40
40
30
20
52
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
A2
A2
A1
Remaining Budget for A1
40
40
20
20
20
0
Remaining Budget for A2
50
40
40
30
20
20
53
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
A2
A2
A1
A2
Remaining Budget for A1
40
40
20
20
20
0
0
Remaining Budget for A2
50
40
40
30
20
20
10
54
BALANCE Example:
Two advertisers bid on a query q
! BidderA1: bidx1 =20 budgetb1 =40 ! BidderA2: bidx2 =10 budgetb2 =50 ! AssumetiesarebrokeninfavorofA1
Query q
At start
1st query q
2nd query q
3rd query q
4th query q
5th query q
6th query q
7th query q
8th query q
Assigned to Bidder (A1, A2 or No Ad)
—-
A2
A1
A2
A2
A1
A2
A2
No Ad
Remaining Budget for A1
40
40
20
20
20
0
0
0
0
Remaining Budget for A2
50
40
40
30
20
20
10
0
0
55
Analyzing BALANCE
! Consider simple case (w.l.o.g.):
Ø2 advertisers, A1 and A2, each with budget B (31) ØOptimal solution exhausts both advertisers’ budgets
! BALANCE must exhaust at least one advertiser’s budget:
ØBecause optimal exhausts both
ØIf not, we can allocate more queries
• Whenever both advertisers bid on the query, chosen advertiser’s unspent budget only decreases
! Assume BALANCE exhausts A2’s budget,
but allocates x queries fewer than the optimal
! Revenue: BAL = 2B – x
56
Analyzing Balance
B
A1 A2 x
y
A1 A2 Not
used
B
x
Queries allocated to A1 in the optimal solution Queries allocated to A2 in the optimal solution
Optimal revenue = 2B Balance Algorithm:
Assume Balance gives revenue = 2B-x or B+y Unassigned queries can only be assigned to A2
(if we could assign to A1 we would, since we still have budget Goal: Show we have y 3 x
Case 1) ≤ 1⁄2 of A1’s queries got assigned to A2 then y >= B/2, so y >= x (y+x = B)
BALANCE exhausts A2’s budget
57
)
B1
x y
Analyzing Balance
Queries allocated to A1 in the optimal solution Queries allocated to A2 in the optimal solution
Optimal revenue = 2B Balance Algorithm:
Assume Balance gives revenue = 2B-x or B+y
B x
A1 A2 Not used
Unassigned queries can only be assigned to A2
Goal: Show we have y 3 x
Case 2) > 1⁄2 of A1’s queries got assigned to A2, consider last of A1’s queries assigned to A2:
1) B2 >= B1 since Balance chose A2
2) B2 <= B/2 (since at least 1⁄2 of A1’s queries got assigned to A2)
3) B1<=B2<=B/2sox(orB1)<=B/2andx+y=B->y>=x
Balance revenue is minimum for x=y=B/2 (i.e., Max x = B/2) Minimum Balance revenue = 3B/2
Competitive Ratio = 3/4
58
BALANCE: General Result
! For Balance algorithm with many bidders
! In the general case, worst competitive ratio of
BALANCE is 1–1/e = approx. 0.63 ØInterestingly, no online algorithm has a better
competitive ratio!
! Let’s see the worst case example that gives this ratio
59
Kalyanasundaram, B., & Pruhs, K. R. (2000). An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2), 319-325.
Worst case for BALANCE
! N advertisers: A1, A2, … AN Ø Each with budget B
! Queries:
Ø N·B queries appear in N rounds of B queries each
! Bidding:
Ø Round 1 queries: bidders Ø Round 2 queries: bidders Ø Round i queries: bidders
! Optimum allocation: Allocate round i queries to Ai
Ø Optimum revenue N·B
A1, A2, …, AN A2, A3, …, AN Ai, …, AN
! BALANCE:
Ø Assigns each query in round 1 to N advertisers equally, since all bid on q1 Ø Prefers bidder with largest remaining budget
Ø For q2, divided equally among A2, A3, …, AN
Ø For each query qi, advertisers Ai, …, AN get queries
60
BALANCE Allocation
•
•
Eventually, budgets of higher-numbered advertisers exhausted
j is approximate value where all advertisers are out of budget or do not bid on remaining queries
A1 A2 A3
AN-1 AN
…
B/(N-2)
B/(N-1) B/N
61
A1 A2 A3
AN-1 AN
B/(N-2)
B/(N-1) B/N
…
BALANCE Allocation
• Eventually, budgets of higher- numbered advertisers exhausted
• j is approximate value where all advertisers are out of budget or do not bid on remaining queries
Last round, last bidder used up all budget, B:
• • • •
(1+1/2+…+1/n) – (1+1/2+…+1/(n-j)) = 1/(n-j+1)+…+1/n
So we want j such that ln N – ln (N-j) = 1 (approximately)
j = N(1-1/e) -> Each round has revenue B so the approx. total revenue is B x j
Approximate revenue of Balance Algorithm is BN(1-1/e) Competitive ration is 1-1/e
62
Kalyanasundaram, B., & Pruhs, K. R. (2000). An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2), 319-325.
General Version of the Problem
! Balance works well when bids are 1,0
! In practice, bids and budgets can be arbitrary
! In a general setting, BALANCE can perform poorly
! Example 8.9: Consider two advertisers A1 and A2 Ø A1: bid1 = 1, budget1 = 110
Ø A2: bid2 = 10, budget2 = 100
Ø Consider: we see 10 instances of q
Ø BALANCE always selects A1 because it has largest remaining budget Ø Earns total revenue = 10
Ø Favors advertiser with larger remaining budget
Ø Optimal earns 100
63
Modifications Needed to BALANCE Algorithm
! Bias choice of ad in favor of higher bids
! Consider the fraction of budget remaining, so we bias
toward using some of each advertiser’s budget
! More “risk averse”: don’t leave too much of any advertiser’s budget unused
64
Generalized BALANCE Algorithm
! Arbitrary bids: consider query q, bidder i ØBid = xi
ØBudget = bi
ØAmount spent so far = mi
ØFraction of budget left over fi = 1- (mi/bi)
! Define yi(q) = xi * (1-e-fi) y (psi) Øbid * (1-e-(fraction of budget left))
! Allocate query q to bidder i with largest value of yi(q) ! Same competitive ratio (1-1/e)
65
Example 8.10
! BidderA1:x1 =1,b1 =110
! BidderA2:x2 =10,b2 =100
! First occurrence of query q: fraction 1 of budgets b1 and b2 remain
! y1(q) = x1(1-e-f1) = 1(1-e-1) = 1 – 1/e = 0.63
! y2(q) = x2(1-e-f2) = 10(1-e-1) = 6.3
! SofirstqisawardedtoA2
! y2(q) decreases, but for the next 9 instances of q: y2(q) > y1(q) and queries are awarded to A2
! For 10th instance of q, remaining fraction of budget b2 is 1/10
! y2(q) = x2(1-e-f2) = 10(1-e-1/10) = 0.95, which is > 0.63
! After10queriesq,havespentallofA2’sbudget,andadditionalqueries q will be awarded to A1
! Totalrevenuefor10queriesq=100
! GeneralizedBalanceAlgorithm:Successfullybiasedtowardhigherbids,
took into account fraction of budget remaining
66
Additional Observations
! Algorithm as described does not account for possibility that click-through rate differs for different ads
! Multiply bid by CTR when computing y
! Also can consider historical frequency of queries
! Use historical frequency to predict future frequency
67
Adwords Aspects Not in Our Model
Matching bids and search queries:
! In our simplified model, advertisers bid on sets of words
! An advertiser’s bid is eligible to be shown for search queries
with exactly the same set of words as advertiser’s bid
! In reality, Google, Yahoo, Microsoft all offer advertisers
“broad matching”: inexact matches of the bid keywords
! Examples: subsets, supersets, words with very similar meanings
! Charge advertisers based on complicated formulas that take into account how closely related the search query is to the advertiser’s bids
! Proprietary algorithms
68
Adwords Aspects Not in Our Model
Charging Advertisers for Clicks
! In our simplified model, when a user clicks on an ad, the advertiser is charged the amount they bid
! Known as a first-price auction
! In reality, search engines use a more complicated system
known as a second-price auction
! Each advertiser pays approximately the bid of the advertiser who placed immediately behind them in the auction
Ø Example: First-place advertiser would pay the bid of the second- place advertiser plus one cent
! Less susceptible to being gamed by advertisers than first- price auctions
! Lead to higher revenues for search engines
Ø https://blogs.cornell.edu/info2040/2012/10/27/google-adwords-auction-a-second-price-sealed-bid-auction/
69