Keyword Auctions

1 Introduction

• In the 1990’s websites started to generate revenue from advertising.

• The original method (mid 90’s) was to sell ad space as the same way it was sold
in magazine, billboards, etc:

− Ad advertiser rents/buys some space on a Web page (a banner).

− The price is for a fixed number of displays (i.e., a fixed number of visitors/time).

• At the end of the 90’s–early 00’s, this advertising model proved being unadapted:

− Advertisers can target better viewers (using cookies)

− With search engines, advertisers can know users’ interests in real time.
• Current model for ads in search engines.

− Internet user enters a search term (a “query” or “keyword”)

− Gets a page with results:

∗ First: sponsored links (the ads)

∗ Second: most relevant links (organic search results).

− If the user clicks on a sponsored link, then he is sent to the advertisers’ Web
page, and the advertiser pays the search engine for sending the user.

− The position of the sponsored link does matter: higher displayed links are clicked
more often than links displayed lower on the page.
• Sponsored search is a huge auction market.

− Google revenue in 2013: $59.83billion. (about 90∼95% of its revenue). Similar

ratio for Facebook, Twitter, etc.

− Value of targeted advertising: targeted to those with interest in related query.

− Hal Varian, Goolge Cheif Ecnonmists, says that

Most people don’t realize that all that money comes pennies at a
time.
• Why would you use auctions?

− Difficult to set so “many prices” (tens of millions of keywords).

− Demand and supply might be changing.

− Retain some price-setting ability via auction design.

• Issues

− On the Internet, things can change very quickly, i.e., search engines sell a flow
of perishable advertising service, and capacity can be wasted (no ad displayed for
a particular query).

− Also, ad prices can change almost continuously.

2 Keyword Auctions

• Advertisers submit bids for keywords: a dollar payment per click ⇒ “pay-per-
click”.

− Alternatives: price per impression or per transaction.

• Separate auction for every query.

− Positions awarded in the order of bids.

− Advertisers pay bid of the advertiser in the position below.

− Generalized Second Price (GSP) auction format.

• Some important features.

− Multiple positions, but advertisers submit only a single bid.

− Broad match (single bid for a set of related keywords).

• Brief history

− First service to start an auction for displayed ads with PPC: GoTo in 1997
(renamed Overture in 2001, bought by Yahoo! in 2003) with a first-price auction.

− 2000s: Goolge and Overture modify keyword auction to have advertisers pay
minimum amount necessary to maintain their position (GSP).

− Afterwards: quality-weighting and auction design become more sophisticated

− Today: nearly all the ads we can see on any website are the outcome of an
auction.
3 Competitive equilibria

Example 1. There are two positions, each of them receives 200 and 100 clicks per
day. There are three bidders with values per click of $10, $4, $2, respectively.

Top 2nd
Bidder 1 2,000 1,000
Bidder 2 800 400
Bidder 3 400 200

• Efficient allocation creates value $2,400.

− Bidder 1 gets top slot: value created 200 × 10 = 2, 000.

− Bidder 2 gets 2nd slot: value created 100 × 4 = 400.

• Set prices so that demand = supply. Can we set per-click?

• General characterization of competitive per-click prices in Example 1:

− Bidder 3 demands nothing, so p1, p2 ≥ 2.

− Bidder 2 demands slot 2, so

100 × (4 − p2) ≥ 0
100 × (4 − p2) ≥ 200 × (4 − p1)

− Bidder 1 demands slot 1, so

200 × (10 − p1) ≥ 0

200 × (10 − p1) ≥ 100 × (10 − p2)
• Competeitive equilibria
p1

6 p1 ≥ 2 + 12 p2
p1 ≤ 5 + 12 p2

2 ≤ p2 ≤ 4

2 4 p2

− Revenue = 200p1 + 100p2.

− Can we use an auction to “find” these prices?

4 Overture Model: Pay-Your-Bid Auction

• In Example 1:

− Two positions: receive 200 and 100 clicks per day.

− Advertisers 1, 2, 3 have per-click value $10, $4, $2.

• Overture auction (pay-your-bid auction)

− Advertiser 3 will offer up to $2 per click

− Advertiser 2 has to bid $2.01 to get second slot.

− Advertiser 1 wants to bid $2.02 to get top slot.

− But then advertiser 2 wants to top this, and so on.

• Pay-your-bid auction is unstable!

• Overture bid patterns

− Edelman and Ostrovsky (2007): “sawtooth” pattern caused by auto-bidding

programs.
5 Facebook Model: Vickery Auction

• Bidders submit bids (per-click). Seller treats bids as true values

• Find assignment that maximizes total value.

• Charge each winner the value displaced by him.

− Calculate total value of opponents given i takes his slot.

− Calculate total value of opponents if i didn’t take his slot.

− Difference in these values is the value displaced by i

• Dominant strategy to bid one’s true value.

• In the sponsored search, positions are assigned in order of bids, so each winning
bidder displaces bidders with lower bids by exactly one position.
• Recall Example 1:

− Two positions receive 200 and 100 clicks per day.

− Advertisers 1, 2, 3 have per-click value $10, $4, $2.

• Vickery payment for bidder 2

− Bidder 2 displaces 3 from slot 2. Value lost from displacing 3 is 100 × $2 = $200.

− Bidder 2 pays $200 (for 100 clicks), or $2 per click.

• Vickery payment for bidder 1

− Displaces 3 from slot 2: pay $200.

− Displaces 2 from slot 1 to 2: pay (200 − 100) × $4 = $400.

− Bidder 1 pays $600 (for 200 clicks), or $3 per click.

• Vickery “prices” are therefore p2 = 2 and p1 = 3, revenue is $800.

• Vickery prices
p1

3
Vickery prices

2 p2

− Vickery prices are the lowest competitive equilibrium prices.

− Revenue = 200 × $3 + 100 × $2 = $800.

5.1 Vickery-Clarke-Groves (VCG) Mechanism

• Suppose items are initially owned by a “seller” that has zero value for all of the
items.

• The seller wants to allocate the items efficiently.

• VCG mechanism

− Each buyer reports her values of all items.

− The seller picks the assignment that maximizes the total (reported) values, and
charges “appropriate” prices.
• N = {1, . . . , n}: the set of bidders, K = {k1, . . . , kk }: the set of items.

• Each bidder i has a valuation of vi over the sets of items.

− Eg. K = {k1, k2, k3}. vi({k1, k2})) = 20, vi({k2, k3}) = 15, vi(K) = 10.

− vi is a function that assigns for each subset K ′ ⊆ K a valuation vi(K ′).

− vi(K ′) means how much bidder i is willing to pay to get the items K ′.

• Assignment of item: µ : N → 2K

− µ(i) = the set of items that goes to bidder i.

− If k ∈ µ(i), then there is no j ̸= i such that k ∈ µ(j).

• µ∗ maximizes the total value if

X X
∗
vi(µ (i)) ≥ vi(µ(i)) for any other assignment µ.
i∈N i∈N
• Paying the externality
X X
pV CG(i) = max vi(µ(j)) − vj (µ∗(j))
µ
j̸=i j̸=i

− The payment equals the maximal surplus that would be generated without her
minus the surplus that accrue to the other buyers with her around.

− Effectively, each agent is charged the “net externality” she is causing to the
remaining buyers.

Example 2. There are two bidders and two items. Assume that the valuations are
k1 k2 k1&k2
Bidder 1 10 5 11
Bidder 2 5 3 6

− Efficient allocation: µ∗(1) = k1 and µ∗(2) = k2.

− pV CG(1) = 6 − 3 = 3 and pV CG(2) = 11 − 10 = 1.

 Theorem 1.
VCG mechanism is strategy-proof and individually rational, yields an effi-
cient assignment, and admits buyer-optimal stable payoff.

Proof for strategy-proofness. Suppose bidder i bids v̂i(·) instead of vi(·), and let
µ̂(i) be the assignment maximizing (v1, . . . , vi−1, v̂i, vi+1, . . . , vn). Her payoff is
h X X i
bi = vi(µ̂(i)) − max
U vj (µ(j)) − vj (µ̂(j)) ,
µ
j̸=i j̸=i

while bidder i’s payoff from bidding truthfully vi(·) is

h X X i
Ui = vi(µ∗(i)) − max vj (µ(j)) − vj (µ∗(j)) .
µ
j̸=i j̸=i

Thus,
h X i h X i
bi = vi(µ∗(i)) +
Ui − U vj (µ∗(j)) − vi(µ̂(i)) + vj (µ̂(j)) ≥ 0.
j̸=i j̸=i
| {z } | {z }
= j vj (µ∗ (j))
P P
= j vj (µ̂(j))
• Intuition for the strategyproofness:

− Each buyer i becomes a residual claimant and collects her marginal social con-
tribution
h X X i
∗ ∗ ∗
vi(µ (i)) − pV CG(i) = vi(µ (i)) − max vj (µ(j)) − vj (µ (j))
µ
j̸=i j̸=i
X X
= vj (µ∗(j)) − max vj (µ(j))
µ
j j̸=i
P
− Note that maxµ j̸=i vj (µ(j)) does not depend on i’s bid.

− So, she has an incentive to maximize it by reporting truthfully.

• Remark: in the auction contest, VCG mechanism is the same as a second-price

auction.
5.2 Problem with the VCG mechanism

• In practice, the VCG auction is not used in many cases. Why?

− A crucial step is to find an assignment that maximizes the social welfare.

− Amounts to compare all possible assignments: this can be a gigantic number.

− We also need to ask bidders to submit a valuation function over a large number
of possibilities.

− If there are 10 objects, the bidder would have to submit 210 = 1024 different
valuations.
• Suppose that there are 10 bidders and 10 items. Each bidder only wants 1 item.

− To find the optimal assignment µ∗: 10! = 3, 628, 800 combinations.

− For each bidder, the optimal assignment when not present: 10! = 3, 628, 800
combinations

− So to compute payoffs one need: 10! + 10 × 10! = 39, 916, 800

• Computer scientists say that this problem is “NP complete”:

− NP means “nondeterministic polynomial-time”

− We don’t know how to find a solution in “reasonable time”

− If we multiply by 2 the size of the problem (number of bidders and objects) the
number of calculations increases by a factor more than 2 (exponential).
6 Google Model: GSP Auction

• Generalized Second Price (GSP) Auction.

− Bidders submit bids (per click)

− Top bidder gets slot 1, second bidder gets slot 2, and so on.

− Each bidder pays the bid of the bidder just below him.

• Questions

− Is it the same as Vickery auction?

− Do the bidders want to bid truthfully?

− If not, how do they bid?

• Truthful bidding? Not a dominant strategy to bid “truthfully”!

− Two positions, with 200 and 100 clicks.

− Consider bidder with value 10. Suppose competing bids are 4 and 8.

− Bidding 10 wins top slot, pays 8: 200 × (10 − 8) = $400.

− Bidding 5 wins next slot, pays 4: 100 × (10 − 4) = $600.

• Edelman, Ostrovsky and Schwarz (2007b) and Varian (2007) analyze equilibrium
bidding strategies.
6.1 GSP auction in Example 1

• Two positions: receive 200 and 100 clicks per day.

• Bidders have per-click vlaues $10, $4, $2.

• GSP: here it is a Nash equilibrium to bid truthfully.

− Verifying the Nash equilibrium with bids 10, 4, 2.

∗ Bidder 3 would have to pay $4 to get slot 2 — not woth it.

∗ Bidder 2 would have to pay $10 to get slot 1 — not worth it.

∗ Bidder 1 could bid below $4 and pay $2 for the lower slot, rather than $4 for
the top, but wouldn’t be profitable.

− Prices paid in this NE are 4 and 2 (per click).

− Payments are 200 × $4 + 100 × $2 = $1, 000 (>Vickery!).

• GSP equilibrium prices
p1

GSP eqm
4
3
Vickery prices

2 p2

− GSP prices are also competitive equilibrium prices.

− Not the only GSP equilbirium, however.

• Another GSP equilibrium with Vickery prices

− Bidder 1 bids $10, Bidder 2 bids $3, Bidder 3 bids $2.

− Verifying the equilbirium.

∗ Bidder 3 would have to pay $3 to win bottom — not worth it.

∗ Bidder 2 would have to pay $10 to win top — not worth it.

∗ Bidder 1 pays $3 for top position, better than $2 for bottom because profits are

200 × (10 − 3) > 100 × (10 − 2).

− In this equiibrium, per-click prices are $3 and $2.

• Still another GSP equilibrium (with higher prices)

− Bidder 1 bids $6, Bidder 2 bids $5, Bidder 3 bids $3.

− Verifying the equilibrium.

∗ Bidder 2 and 3 don’t want to pay $6 and $5 to move up.

∗ Bidder 1 prefers to pay $5 for top position rather than $3 for bottom position
because
200 × (10 − 5) > 100 × (10 − 3).

− Prices in this equilibrium are $5 and $3.

• GSP equilibrium prices
p1

GSP eqm
5
GSP eqm
4
3
Vickery prices

2 3 p2

− In fact, for every competitive equilibrium price, there is a corresponding GSP

equilibrium!
6.2 General model

• There are K positions, k = 1, . . . , K, and N bidders, n = 1, . . . , N .

− vn: per-click-value for bidder n. v1 > v2 > · · · > vn.

− xk : # of clicks of ad in the kth slot. x1 > x2 > · · · > xk > xk+1 = 0.

− bn: bidder n’s per-click-bid.

• If bidder n wins position k and pays pk per click, then his payoff is xk (vn − pk ).

• Efficient allocation is assortative:

− Bidder k should get slot k to maximize the total value.

• Market clearing prices:

− Each bidder k wants to buy position k.

− (Per-click) prices that clear the market satisfy

xk (vk − pk ) ≥ xm(vk − pm) for all k, m.

− Because bidder k wants potions k and not m = k − 1

xk (vk − pk ) ≥ xk−1(vk − pk−1) ⇒ xk−1(pk−1 − pk ) ≥ (vk − pk )(xk−1 − xk ) ≥ 0

− Per-click prices must be higher for better positions.

• Price algorithms

− To find the lowest prices, fix pK = vK+1, and set recursively

xk
pk−1 = vk − (vk − pk )
xk−1
∗ Price pk−1 is just high enough that bidder k won’t move up a slot.

− To find the highest prices, fix pK = vK , and set recursively

xk
pk−1 = vk−1 − (vk−1 − pk )
xk−1
∗ Price pk−1 is the highest price such that bidder k − 1 won’t move down a slot.

− Recall Example 1: K = 2 with x1 = 200 > x2 = 100 and N = 3 with

v1 = 10 > v2 = 4 > v3 = 2.

∗ Lowest market clearing prices: (3, 2).

∗ Highest market clearing prices: (7, 4).
• Look for Nash equilibria of GSP that are efficient.

• Bids b1 > · · · > bN are an efficient and a Nash equilibrium if

xk (vk − bk+1) ≥ xm(vk − bm+1) for all m > k,

xk (vk − bk+1) ≥ xm(vk − bm) for all m < k.

Definition 2.
Bids b1 > · · · > bN are an efficient and locally envy free Nash equilibrium
or Symmetric Nash equilibrium (SNE) of GSP if for all k and m

xk (vk − bk+1) ≥ xm(vk − bm+1).

− Idea: no bidder wants to “trade positions” with another bidder and pay what
that bidder is paying.
• Replacing bk+1 with pk , we have the definition of market clearing prices (i.e.,
competitive equilibrium prices).

Theorem 3.
Outcome of any locally envy free equilibrium—or SNE—of the GSP coin-
cides with a competitive equilibrium allocation.

− This implies that any locally envy-freem GSP equilibrium generates at least as
much revenue as Vickery.
7 Generalized English Auction (GEA)

• The previous theory of GSP auction is the static model abstracts from rich dy-
namic environments.

− Is the one-shot game of complete information a good approximation of the dy-

namic aspects of sponsored search auctions?

• Idea:

− The second-price auction is a one-shot/simultaneous version of the English auc-

tion.

− Can we define a “generalized English auction” so that GSP would be its one-
shot/simultaneous version?
• Generalized English auction

− There is a clock showing the current price, which increases over time.

− Start: price = 0, all advertisers are in the auction.

− Advertiser can drop at any time. Their bid is the price on the clock at the time
they drop out.

− Auction over when the next-to-last advertiser drops out.

− Last advertiser ranked 1st, all other ranked according to the time they dropped
out (the latest, the higher).

− Each advertiser pays the bid of the advertiser ranked just below him/her.
 Proposition 4 (Edelman, Ostrovsky and Schwarz (2007b)).
There is a unique (perfect Bayesian) equilibrium of the generalized English
auction, where an advertiser with valuation v drops out at the price
xi
p∗ = v − (v − bi+1),
xi−1
where i = # of bidders remaining (including him/her).

• These prices imply that the payoffs in the generalized English auction are the
same as in the VCG auction.
• Intuition

− Suppose that there are i bidders remaining (including me), and the next highest
bid is bi+1.

− The next bidder who drops out will pay bi+1. If I’m the next to drop out my
payoff is xi(v − bi+1)

− If I wait a bidder to drop out (at price p) and drop out just after, my payoff is
xi−1(v − p)

− Since xi−1 > xi, if p = bi+1, then

xi(v − bi+1) < xi−1(v − p),

− The right hand side decreases in p. So, there will be a price p∗ such that waiting
and not waiting gives the same payoff:
∗ ∗ xi
xi(v − bi+1) = xi−1(v − p ) ⇒ p = v − (v − bi+1).
xi−1
8 Experimental Evidence

• Two issues with the theory:

(1) The static model abstracts from rich dynamic environments.

⇒ Is the one-shot game of complete information a good approximation of the

dynamic aspects of sponsored search auctions?

(2) Multiplicity of equilibrium - VCG outcome is suggested as most focal.

⇒ Are symmetric Nash equilibria, particularly the lowest-revenue SNE, em-

pirically valid?

• Che, Choi and Kim (2017) conducts lab experiment and finds: “Yes” to (1) and
“No” to (2).
• Three bidders and two positions: click #’s: (20, 10) and (11, 10).

• Per-click values randomly drawn from {1, . . . , 100}

• Three treatments

− SC (Static Complete Info): Same as theory

− DI (Dynamic Incomplete Info): Each bidder has 15 rounds to revise bids.

− SI (Static Incomplete Info): Control.

9 Keyword auction design

• Search engines retain some control over prices.

− Restricting the number of slots can increase prices.

− Setting a reserve price can increase prices.

• They can also “quality-adjust” bids

− In practice, ads that are more “clickable” get promoted.

− Bids can be ranked according to bid× quality.

− This gives an advantage to high-quality advertisements.

Example 3. There are two positions with 200 and 100 clicks. Three bidders each
with per-click value $2, $1, $1.

• Efficient assignment is assortative.

• Market clearing prices

− Bidder 2 pays $100 for slot 2 (or, p2 = $1): high enough to deter bidder 3 but
not so much that bidder 2 wants to drop out.

− Bidder 1 pays $200-$300 for slot 1. p1 ∈ [1, 3/2]: high enough to deter bidder 1
but not so much that bidder 1 wants to drop down.
• GSP equilibrium

− Bids required to suppose p1 ∈ [1, 3/2] and p2 = $1.

− Bidder 3 bids $1 per click.

− Bidder 2 bids p1 ∈ [1, 3/2]

− Bidder 1 bids at least p1.

− Revenue=$100+$(200-300)=$300-400.

• Should the seller sell only one position?

− Focus on lowest equilibrium (Vickrey) prices.

− Selling two positions: revenue of $300.

− Selling one position: revenue of $200.

∗ Bidder 2 and 3 will pay up to $1 per click. Market clearing price is $1 click for
bidder 1.
• Can the seller benefit from a reserve price?

− No reserve price: revenue of $300.

− Reserve price of $2: revenue of $400

∗ Sell only one position, but for $2 per click.

• Consider Example 3. Suppose that the two positions have 200 and 100 “base”
clicks and each of three bidders have quality score 2, 1, 1.

• Rank bids by bid×quality.

− Bidder 2 pays $1 per-click for position 2.

− Bidder 1 pays $0.50 per-click for position 1.

− Total revenue is $1 × 100 + $0.50 × 400 = $300.

10 Budget constraints

• Google states that

Your daily budget is the amount that you set for each ad campaign to
specify how much, on average, you’d like to spend each day. [· · · ] When
your budget is reached, your ads will typically stop showing for that day.

• As soon as its expenses (or number of clicks) attain some number, the ad drops
out the auction.

• With budget constraints, bidders can behave strategically to exhaust other bid-
ders’ budgets.

• Koh (2013) analyzes this case.

• Model:

− The auction is conducted through a day, t ∈ [0, 1].

− Each bidder submits bid bi and daily budget Bi only once at t = 0.

− There is a flow of clicks on each slot: # of clicks on slot k up to time t is xk t.

• Allocations:
xk xk

x1 x1

x2 x2
Bidder 1
x3 x3 Bidder 2
t Bidder 3
t
t1 t2 t3 1 Bidder

(a) t1 < t2 < t3 ≤ 1 (b) t1 = t2 = t3 = 1

• Upward deviation
xk xk

x1 x1

x2 x2
x2 x2t + x1(1 − t)

t t
t= B1 1 t= B1 1
x1 b′2 x1 b′2

(a) Initial Allocation (b) b′2 = b1 − ϵ > b2

− Bidder 2 increases his bid from b2 to b′2 = b1 − ϵ.

B1
− Bidder 1 drops out at time t = x1 b′2
< 1, and bidder 2 will then move up.

− Bidder 2’s payoff is [x2t + x1(1 − t)](v2 − b3), while it was x2(v2 − b3).
• Downward deviation
xk xk

x1 x1

x1
x2 x2
x2t + x1(1 − t)

t= B2 1 t= B2 1
x1 b′1 x1 b′1

(a) Initial Allocation (b) b′1 = b2 − ϵ < b2

− Bidder 1 lowers his bid from b1 to b′1 = b2 − ϵ.

− Bidder 1 is assigned to slot 2 and bidder 2 is assigned to slot 1.

B2
− Bidder 1 moves up to slot 1 at time t = x1 b′2
< 1.

− Bidder 1’s payoff is [x2t + x1(1 − t)](v1 − b3), while it was x1(v1 − b2).
Example 4. One slot with 100 clicks. Two bidders with value $8 and $2. Both
bidders have budget B = $400.

• GSP equilibrium without budget constraints.

− Bidder 2 bids $2 per click. Bidder 1 bids at least $2 per click.

− Bidder 1’s payoff = 100 × $(8 − 2) = $600.

− Bidder 2’s payoff = 0.

− Search engine’s revenue = 100 × $2 = $200.

• Equilibrium with budget constraints.

− Bidder 2 bids $5 per click. Bidder 1 bids at least $5 per click.

400
− Bidder 1 drops out at t = 100×5 = 0.8.

− Bidder 1’s payoff = 100 × 0.8 × $(8 − 5) = $240.

− Bidder 2’s payoff = 100 × 0.2 × $2 = $40.

− No bidder has incentive to deviate:

∗ Bidder 2 has no incentive to deviate, clearly.

∗ If bidder 1 lowers his bid to b′1 < 5, bidder 2 will drop out at t′ = 400
100×b′1
> 0.8.

∗ Bidder 1’s payoff from deviation is 100 × (1 − t′) × $8 < 160.

− Search engine’s revenue = 100 × 0.8 × $5 = 400.

− Search engine’s revenue can be higher!

References
Che, Yeon-Koo, Syngjoo Choi and Jinwoo Kim (2017), “An Experimental Study of Sponsored-Search
Auctions,” Games and Economic Behavior, 102, 20–43.

Edelman, Benjamin and Micheal Ostrovsky (2007), “Strategic Bidder Behavior in Sponsored Search
Auctions,” Decision Support Systems, 43, 192–8.

Edelman, Benjamin, Micheal Ostrovsky and Michael Schwarz (2007), “Internet Advertising and the
Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords,” American
Economic Review, 97, 242–59.

Koh, Youngwoo (2013), “Keyword Auctions with Budget Constrained Bidders,” Review of Eco-
nomic Design, 17, 307-21.

Varian, Hal (2007), “Keyword Auctions,” International Journal of Industrial Organization, 25,

1163–78.