gsp_ad_auction.ipynb

Kernel: Python 3 (ipykernel)

Table of Contents

• 1  Generalized Second Price Ad Auction
  • 1.1  Laddered Auction
• 2  Reference

# code for loading the format for the notebook
import os

# path : store the current path to convert back to it later
path = os.getcwd()
os.chdir(os.path.join('..', 'notebook_format'))

from formats import load_style
load_style(css_style='custom2.css', plot_style=False)

os.chdir(path)

# 1. magic to print version
# 2. magic so that the notebook will reload external python modules
%load_ext watermark
%load_ext autoreload
%autoreload 2

from typing import List

%watermark -a 'Ethen' -d -u -t -v

Author: Ethen

Last updated: 2022-04-25 10:14:09

Python implementation: CPython
Python version       : 3.7.11
IPython version      : 7.27.0

Generalized Second Price Ad Auction

Whenever we go to our favorite search engine, and we type a search term, a.k.a query into the search engine. We get back a list of results, containing both organic and sponsored links, a.k.a ads. When this happens, that means an advertiser is willing to pay the search engine additional dollars for his/her link to be shown at a more prominent position. In these types of sponsored search systems, ads are usually ranked in descending order using the product of estimated click through rate (at a query and ad level) and the bid that each advertisers have given to their ad. This bid value represents the maximum price that an advertiser is willingly to pay the search engine when a user clicks on the advertisement. Here, we describe a popular way in which search engine runs these auctions to determine to final price that an advertiser pays when a click occurs, the Generalized Second Price Auction.

Suppose there are $N$ advertisers' ad participating in an ad auction. Let $b_i$ denote the $i_{th}$ advertiser's bid price and $s_i$ denote the ads' click through rate. $b$ is set by the advertiser, whereas $s$ is estimated by the search engine potentially using sophisticated machine learning models. The rank of these ads are then determined by multiplication of the two terms, $s_i b_i$. Suppose we have a ranked list. $s_1 b_1 > s_2 b_2 > s_N b_N$, the generalized second price tells us the final price charged to advertiser 1, a.k.a clearing price, will be adjusted based on the ranking score of the next highest advertiser, i.e. $\frac{s_2 b_2}{s_1}$.

To understand why this is desirable and not desirable, let's consider some scenarios.

Consider 3 ads A, B and C bidding for 2 slots. Let all three of them have a click through rate of 0.5 at the top slot and 0.4 at the bottom slot. Let the true valuations per click of the three ads be 200, 180, and 100 respectively.

If search auction is a first price auction. In this scenario, if advertiser C bids 101. Then advertiser A or B will not want to bid more than 102, as he/she does not need to pay more than that to get the top spot. In other words, an advertiser in position $i$ will never want to pay more than one bid increment above advertiser in position $i+1$'s bid. Instead of bidding for their true valuation, advertisers will be playing this constant bid adjustment games.

This type of drawback makes moving to second price auction highly desirable, as advertiser in the first position pays a price per click that equals the bid of the second advertiser plus an increment. The multiplication of $s$, click through rate, further incentives the advertiser to promote higher quality ads. If we look closely at the formula $\frac{s_2 b_2}{s_1}$, we'll notice that as $s_1$ gets higher, the lower the generalized second price will be, i.e. the higher the ads' click through rate, the lower the price it needs to pay when winning an ad auction.

The less desirable part is during a multi-slot scenario, generalized second price also does not encourage advertisers to bid their true valuation. In our exmaple, if all ads are bidding truthfully, ad A ends up paying a price of 180 per click, making an expected profit of (200−180)×0.5 = 10 per impression. In this case, however, ad A has an incentive to undercut B by lowering its bid to 110, and make a net profit of (200 − 100) × 0.4 = 40.

Laddered Auction

Laddered auction extends generalized second price auction to a multi slot scenario, given there are $N$ advertisers bidding for $K < N$ slots on a specific keyword. It calculates the clearing price using the following formula:

$$\begin{align} p_i = \sum_{j=i}^K \big( \frac{CTR_{j} - CTR_{j+1}}{CTR_{i}} \big) \frac{s_{j+1} b_{j+1}}{s_i} \end{align}$$

Where, $p_i$ denotes the paid per click price charged to advertiser $i$, often times referred to as clearing price, $CTR_{j}$ denotes click through rate for advetisers at $j$ rank.

Let's see a toy example, where we already have 4 ads that are sorted in descending order of score, $s$, times bid, $b$, the product of the two is called rank score in the following table.

Ad	Score	Bid	Rank Score
Ad1	0.6	25	15
Ad2	0.4	30	12
Ad3	0.5	16	8
Ad4	0.4	15	6

$CTR$ for each slot is also given:

Slot	CTR
1	0.4
2	0.3
3	0.2

e.g.

• For ad3, its final clearing price: (0.5 - 0) / 0.5 * 6 / 0.5 = 12

• For ad2, its final clearing price: (0.3 - 0.2) / 0.3 * 8 / 0.4 + (0.2 - 0) / 0.3 * 6 / 0.4 = 16.67

• etc.

class Bidder:

    __slots__ = ('bidder_id', 'score', 'bid', 'rank_score')

    def __init__(self, bidder_id, score, bid):
        self.bidder_id = bidder_id
        self.score = score
        self.bid = bid
        self.rank_score = score * bid

    def __repr__(self):
        return f'bidder_id: {self.bidder_id}, score: {self.score}, bid: {self.bid}'

# we pad the slot-wise ctr out site of top k with 0
ctrs = [0.4, 0.3, 0.2, 0]

# assume bidders are already sorted in descending order
# of score * bid
bidders = [
    Bidder(1, 60, 25),
    Bidder(2, 40, 30),
    Bidder(3, 50, 16),
    Bidder(4, 40, 15)
]
bidders

[bidder_id: 1, score: 60, bid: 25,
 bidder_id: 2, score: 40, bid: 30,
 bidder_id: 3, score: 50, bid: 16,
 bidder_id: 4, score: 40, bid: 15]

def ladder_auction(bidders: List[Bidder], ctrs: List[float], topk: int = 3):
    clearing_prices = []
    for slot in range(topk):
        slot_bidders = bidders[slot:]
        slot_ctrs = ctrs[slot:]
        n_slots = len(slot_ctrs)
        clearing_price = 0.0
        for j in range(n_slots - 1):
            relative_ctr = (slot_ctrs[j] - slot_ctrs[j+1]) / slot_ctrs[0]
            clearing_price += relative_ctr * slot_bidders[j+1].rank_score

        clearing_price = round(clearing_price / slot_bidders[0].score, 2)
        clearing_prices.append(clearing_price)            

    return clearing_prices

ladder_auction(bidders, ctrs, topk = 3)

[13.33, 16.67, 12.0]

In this documentation, we gave a light weight introduction on generalized second price auctions as well as it variant. Regardless of the form, the motivation of these ad auction is to make it truthful. In other words, it encourages the advertiser to bid on keyword's true valuation instead of playing a cat and mouse game to try and bid only 1 bid increment above their runner up competitor.

As for coming up with true valuation: one can use heuristic such as price / ROAS * purchase through rate. Suppose we are selling an item that's worth 100, we know we want our return on ads spend to be around 5, this leads to spending around 20 on advertising. Purchase through rate defined here as number of purchase over number of clicks. Say we have a purchase through rate of 0.01, that means we need around 100 clicks to receive a purchase. This translates to spending around 20 / 100, 0.2 on our bid. The above analagoy is an "over" simplified view of how to determine one's max CPC bid.

Reference

• Paper: G. Aggarwal, A. Goel, R. Motwani - Truthful Auctions for Pricing Search Keywords (2006)

• Paper: B. Edelman, M. Ostrovsky, M. Schwarz - Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords (2005)