An Introduction to Generalized Second-Price Auctions

In this post I discuss some of the most important decisions one needs to make when designing ad auctions and explore some of their trade-offs. I then provide my definition of what a Generalized Second-Price Auction is.

A watercolor illustration of a gavel resting on its sound block, in soft pink, lavender, and cream tones.
A gavel, minimalist style, soft colors, in paper with water colors. GPT 6.

Disclaimer: This post reflects my personal opinions, not those of my employer. Mistakes, if any, are my own.

In a previous post, An Introduction to Auctions, we discussed first-price and second-price auctions. That post was meant to be an introduction to auctions so that we could discuss how ads can actually be sold in practice. In this post we do that.

If you were to search online, “how does the ads business work?” or something along those lines, you would quickly find the term “Generalized Second Price Auction” (hereafter, GSP). Unfortunately, what would follow is a very specific instance of what I call a GSP, and it would introduce quantities such as click-through rate and “valuations” without explaining why those quantities are needed (see, for example, Wikipedia). I also haven’t been happy with the definitions that chatbots have given me.

In this post I will provide my definition of a GSP1. But before I do that, I want to introduce you, the auctioneer, to the choices you would have to make when designing an auction to sell ads. Shortly after, we will discuss some of their trade-offs.

These are four main choices you’d have to make:

  1. The billing model. When will you charge your advertisers? Will you do so every time a user sees their ad? When the user clicks? Or only when they convert?
  2. The bid submission model. This refers to: how will you ask your advertisers to submit their bids? Will you ask them how much they are willing to pay for an impression? A click? A conversion? Actually, do you even have any flexibility given your choice of billing model?
  3. The ranking function. After the advertisers have submitted their bids, how will you decide what to show first to the user? Will you rank by highest bid? Or by whoever has the largest $bid \cdot pconv$?
  4. The Pricing Rule. After a user has seen/clicked/converted on an ad (whatever it is you selected as the billing model), how much will you charge the advertiser? Will you charge them their bid, as in a first-price auction? Will you charge them the runner-up’s bid, as in a second-price auction? Or will you use some other formula that takes into account the quality of their ad?

As you can see, the design space is huge, and it’s unclear what makes one choice better than another one. Also, notice that these are only a subset of the choices you’d have to make. In practice you may also have to consider things like “quality floors”, or “reserve prices” which complicate things even further. For now we will consider only the four choices I just mentioned. Now let’s examine trade-offs.

The Billing Model

As I mentioned earlier, choosing a billing model means deciding when you are going to charge an advertiser. Some common options are to charge by impression, click, or conversion.

Billing by impression is convenient for the auctioneer because when running the auction it knows for sure how much money it will make if there is an impression. However, an advertiser may prefer to pay per conversion. Imagine you are an advertiser and you make \$5 every time there is a conversion. It would be nice to know that you will always pay \$1 per conversion, leaving you \$4 to pay for production of the thing you are selling and hopefully make some profit. Now, if you tell the advertiser that they must pay by impression, they have to figure out, on average, how many impressions result in a conversion. This introduces friction: the advertiser needs to be sophisticated, may need a large budget, and has to actively manage their bids in case they never win any auctions or spend their budget too quickly.

So, while you may prefer to bill by impression, if other platforms bill by conversion, you may struggle to bring advertisers to your platform. Billing by click gives you a middle ground, you may not be making money on every impression, but the advertiser is also not spending money on impressions that don’t produce any engagement.

The Bid Submission Model

After you’ve picked a billing model, asking advertisers to bid per the billing model is the most straightforward thing to do. For example, if you bill by impression and advertisers submit a bid for impression, advertisers know exactly how much they would pay in case of an impression. Similarly, if you bill by click or conversion and ask for click or conversion bids, things are still straightforward.

The interesting thing is that your billing model and the bid type need not match. For example, you could still bill by impression but ask advertisers to submit the maximum they are willing to pay per click/conversion. This is where quantities such as $ctr$, click-through-rate and $conv$, the conversion-rate, show up. For now; let’s assume we have a model that can perfectly predict the click-through-rate i.e. $pctr=ctr.$ If an advertiser submits a bid per click $b^{click}$ then you can translate that to a bid per impression by multiplying $b^{click}$ by $pctr$ so ${\underline{b}}^{imp} \triangleq pctr \cdot b^{click}$ (I’m underlining the $b$ to distinguish it from what could be the advertiser input $b^{imp}$). The reason setting $\underline{b}^{imp}$ like that works is because the expected number of impressions the ad would need to receive for it to get a click is $\frac{1}{pctr}$, so $\frac{1}{pctr}$ impressions to get a click times $pctr \cdot b^{click}$ dollars per impression gives you $b^{click}$ dollars per click. Similarly, you can translate a bid per conversion to a bid per impression by multiplying by $pconv$.

An important detail here is that you need to know the true $ctr$/$conv$ to make things work, in practice, these quantities are unknown and you’d build an ML model to predict them, but these predictions will of course not be perfect. Let me show you how things could go wrong.

What could go wrong? Imagine we decided we will bill per impression, and we ask an advertiser to submit their bid per conversion, imagine $b^{conv} = 10$ dollars, and our model predicts the probability of a conversion to be $pconv = .10$. Unfortunately, the actual conversion rate is $conv = 0.05$. When we translate their conversion bid to a per impression bid we get \$1 per impression, but in expectation we will need $\frac{1}{.05} = 20$ impressions before we deliver a conversion. This means that, in expectation assuming we charge them their per impression bid, we will be charging \$20 per conversion, double what the advertiser told us they are willing to pay! This is one of the downsides of decoupling the billing model with the bid submission model. Another downside is that, if you under predict the conversion rate, you will undercharge for impressions.

The Ranking Function

Once you have selected a billing model and told advertisers that they need to submit a bid per impression/click/conversion, you have to make the decision of how to rank those ads. As we will see shortly, the decision space is pretty large. I will only focus on two simple cases to make this easy to read and because I think they will get my point across.

How to Rank When Billing by Impression With Per-Impression Bids

Let’s assume we decide to bill by impression and that advertisers submit their per-impression bids. The most straightforward thing to do is to rank by bid. The problem with this is that the highest bidder could be an ad of terrible quality (for example, the creative is gen AI slop). An ad of such bad quality would likely have a very low $pctr$ so you may be tempted to rank according to $bid \cdot pctr$2. This looks like the translated bid $pctr \cdot b^{click}$ from the previous section, so it seems reasonable, right? Well, this mistake could cost you a lot of money. Let me give you a simple example and let’s assume we charge advertisers their bid.

Assume we have 100 identical impressions to sell and two advertisers with the following stats:

  Advertiser A Advertiser B
Bid per impression \$10 \$5
pCTR 2% 10%
Budget \$1,000 \$1,000
pCTR × bid \$0.20 \$0.50

If we rank according to the bid, then Advertiser A wins all the 100 auctions and our revenue is \$1000. But if we decide to rank by $bid \cdot pctr$ then Advertiser B wins every auction and our revenue would be only \$500, a 50% drop! That being said, we do gain some “quality”, when we rank by $bid \cdot pctr$ the expected number of clicks is 10 instead of just 2 when we rank by just bid.

But it is not always true that ranking by $bid \cdot pctr$ will result in an increase in quality. If instead of 100 impressions to sell we had 300 then Advertiser B wins the first 200 auctions, runs out of budget and then Advertiser A gets the remaining 100 auctions. This is exactly the same outcome we would get by ranking by bid, so multiplying by $pctr$ bought us no extra quality. We had so much ad supply that some of the users ended up being exposed to the lower quality ads. So, if you really care about users not seeing lower quality ads, one of the things you can do is impose a quality floor e.g. “if pctr is not greater than 3% then the ad can not enter the auction.”

To summarize, if you are billing by impression, and trying to maximize revenue, ranking by bid is a reasonable choice, ranking by $bid \cdot pctr$ is not, even if you are adding the $pctr$ for “quality” purposes.

How to Rank When Billing by Click With Per-Click Bids

Now, suppose you decided you will be billing per click and have asked your advertisers to submit their per-click bids. How will you rank? A natural approach may be to sell to the highest bidder just as we discussed in the previous subsection right? If you do this, you may again, leave a lot of money on the table. Consider two advertisers with bids and pctrs equal to $bid_1 = \$1$, $pctr_1=.1$ and $bid_2 = \$.9 $, $pctr_2=.5$ respectively. Let’s compute the expected value of showing each ad, and let’s assume we charge advertisers their full bids in the event of a click. The expected value of showing ad 1 is $\$1 \cdot pctr_1 + 0 \cdot (1-pctr_1) = \$0.1$ since we would get a click with probability $pctr_1=.1$ and in that case we would charge \$1, in the event that there is no click, which happens with probability $(1-pctr_1)$ we charge nothing. Similarly, the expected value of showing ad 2 would be \$0.45. So, if we want to maximize our expected revenue we should be ranking by $bid^{click} \cdot pctr$! Unlike in the setting where we bill by impression and take per-impression bids, when billing by click with per-click bids we should multiply the bids by $pctr$.

eCPM Bids, Mixed Auctions, “Quality”

Say you decided to bill by conversion and advertisers submit their per-conversion bids. How would you rank if you are trying to maximize expected revenue? That’s right, you should rank by $bid^{conv} pconv$ by a similar argument as in the previous subsection.

From the three billing/bid-submission scenarios we’ve discussed in this section, you should be able to see that we are ranking ads by how much expected revenue we would get per impression. These quantities $bid^{impression}$, $bid^{click} \cdot pctr$, and $bid^{conv} \cdot pconv$, when tied to their corresponding billing models, are usually called “eCPM” bids, eCPM stands for “effective cost per-mille”, or in non-pretentious English: “effective cost per thousand impressions”. Well, technically you have to scale down by a factor of a thousand, but you get my point…

What’s cool about eCPM bids and ranking according to them is that 1) you are ranking ads by how much revenue they generate, something very sensible to do for an auctioneer and 2) in a single (mixed) auction you can allow advertisers to submit whatever bid type/model they prefer (assuming your ML models are good enough).

Important Remark. Before we move on, I want us to re-acknowledge that, when ranking, $pctr$ and $pconv$ (multiplied by their corresponding bids under the matching billing model) are not there to show the most “relevant” ads. They are simply what we need to multiply by so that we can rank by expected revenue.

The Pricing Rule

The last choice we have to make is to select a pricing rule. If you decided to charge per impression, you could simply charge advertisers their per-impression bid whenever there is an impression. Or, if you liked the incentive-compatible property of second-price auctions (see the previous post), you could charge second-price. To help us generalize shortly, note that second-price is also the minimum bid the advertiser would need to submit to preserve the ranking.

Let’s spell out the exact second-price generalization of the pricing formula when we bill per click, advertisers submit their per-click bids, and we rank by eCPM. If ad 1 ranks above ad 2 then we have that $pctr_1 \cdot bid^{click}_1 \geq pctr_2 \cdot bid^{click}_2$, and the smallest bid advertiser 1 would need to submit to preserve the ranking would be equal to $\frac{pctr_2 \cdot bid^{click}_2}{pctr_1}$. Similarly, if we were billing by conversion with per-conversion bids and advertiser 1 ranked first, we would charge $\frac{pconv_2 \cdot bid^{conv}_2}{pconv_1}$.

What Is a Generalized Second Price Auction?

My definition of a Generalized Second Price Auction (GSP) is the following. Let $\text{billing_event} \in \{impression, click, conversion, install\}$. Let $p_i$ be the probability of a billing event conditioned on an impression on ad $i$. Let $b_i$ be the bid per-billing-event associated with ad $i$. A GSP is an auction that:

  1. Charges advertisers per billing_event
  2. Takes as input the advertisers bids $\{b_i\}$
  3. Ranks ads by $p_i \cdot b_i$
  4. Charges advertisers the minimum bid they would have had to submit to retain their rank. The lowest ranked ad is charged a floor (selected in advance).

That’s it. The definition should be very natural given our previous discussion on the four design choices.

The reason I’ve emphasized that this is my definition of a GSP is because you could for example, charge per impression, charge the minimum to retain rank, and score according to $b^{impression} + \alpha pctr + \beta pconv \cdot b^{impression} + \gamma b^{impression} \exp^{\delta pctr}$. Technically, by setting all the parameters equal to zero you recover a second price auction. But as we have seen before, slightly changing ranking can have severe consequences. So I wouldn’t consider this example a GSP.

Examples

Now let me give you some examples of auction designs that are GSPs and some that are not. The first three examples may look trivial but I feel the need to add them for completeness.

  1. [A trivial GSP] Let billing_event $=impression$, $b_i = b^{impression}_i$ be the bid per impression of ad $i$, set $p_i = 1$ for all ads. Rank ads according to $b_i$, charge ad $i$ the bid of the ad ranked right below it. Since $p_i=1$ we are just ranking by price and charging second price. We have recovered a second-price auction!
  2. [A GSP for clicks] Let billing_event $=click$, let $b_i = b^{click}_i$ be the bid per-click of ad $i$, set $p_i = pctr_i$ for all ads. Rank ads according to $b^{click}_i \cdot pctr_i$ and charge ad $i$ $\frac{pctr_{i’} \cdot bid^{click}_{i’}}{pctr_i}$ where $i’$ is the ad ranked right below $i$.
  3. [A GSP for conversions] Let billing_event $=conversion$, let $b_i = b^{conv}_i$ be the bid per-conversion of ad $i$, set $p_i = pconv_i$ for all ads. Rank ads according to $b^{conv}_i \cdot pconv_i$ and charge ad $i$ $\frac{pconv_{i’} \cdot bid^{conv}_{i’}}{pconv_i}$ where $i’$ is the ad ranked right below $i$.
  4. [Not a GSP]. Let billing_event $=impression$, and $b_i = b^{impression}_i$ be the bid per impression of ad $i$. Rank by $b^{impression}_i \cdot pctr_i$ and charge $b^{impression}_{i’}$ where $i’$ is the ad ranked right below $i$. Since we are not charging the minimum to retain the rank, this auction does not satisfy our definition of a GSP.
  5. [A GSP that charges per impression but takes per-click bids] Let billing_event $=impression$ and $b^{click}_i$ be the per-click bids, rank by $b^{click}_i \cdot pctr_i$ and charge $pctr_{i’} \cdot bid^{click}_{i’}$. To see that this is a GSP, set $b_i = b^{click}_i \cdot pctr_i$. Since we charge per impression, $p_i = 1$ for all ads, so we are ranking by $p_i \cdot b_i$. It’s easy to check that the price is the minimum bid needed to retain the ranking.

Conclusion

In this post we explored four of the main design choices you have to make when designing ad auctions, we discussed trade-offs, and defined the concept of a Generalized Second Price Auction.

Before wrapping up, I want to mention a couple of aspects of auction design that we didn’t discuss that I think are very important in practice. Some of these are:

These are only a few but I hope they show how rich a problem space auction design is.

  1. If you have previously provided a definition and mine matches yours, please message me so I can acknowledge your work. ↩

  2. I want to note that the choice to incorporate $pctr$ in a multiplicative way is arbitrary, we could have gone the additive way with something like $bid + \alpha \cdot pctr$ for some $\alpha > 0$. ↩

  1. Myerson, R. B. (1981). Optimal auction design. Mathematics of Operations Research, 6(1), 58–73.