# Chapter 15. Sponsored Search Markets

[TOC]

## 15.1 Advertising Tied to Search Behavior
Just an introduction to **keyword-based advertising**
- Conventions of the search industry:
1. Paying per click
2. Setting prices through an auction
- This chapter would focus on **how to design such an auction**.
:::info
**3 stages:**
1. If the search engine knew all the advertisers’ valuations for clicks
- Apply matching market model _(Section 15.2)_
2. If we assume that the advertisers’ valuations are not known
- Apply VCG principle to encourage truth-telling _(Section 15.3, 15.4)_
3. It is not clear that the VCG procedure is the best way to generate revenue for the search engine
- The industry has adopted GSP auction in practice _(Section 15.5, 15.6)_
:::

## 15.2 Advertising as a Matching Market
### Definition
- **Clickthrough rates:** the number of clicks per hour that an ad placed in that slot will receive
- **Revenues per click:** the expected amount of revenue the advertiser receives per user who clicks on the ad

:::info
Let $r_i$ denote the **clickthrough rate** of slot $i$, and $v_j$ denote the **revenue per click** of advertiser $j$:

$\Rightarrow r_iv_j$ = **Expected benefit** of $j$ received from being shown in slot $i$
:::

### Relate to matching market
:::info
**Quick review**
- Each buyer $j$ has a valuation for the item offered by each seller $i$, and we denote it $v_{ij}$
- The goal is to find a perfect matching between sellers and buyers
:::
- Slots $\leftrightarrow$ Sellers
- Advertisers $\leftrightarrow$ Buyers
- The problem of assigning slots to advertisers $\leftrightarrow$ The problem of assigning sellers to buyers
- The advertiser's expected benefit $r_iv_j$ $\leftrightarrow$ The buyers’ valuations $v_{ij}$

With the connection to matching markets, we can use the framework from Chapter 10 to determine **market-clearing prices**.
:::danger
**What if the search engine doesn’t know the advertisers’ valuations?**
- We need to define a price-setting procedure for matching markets to encourage truthful reporting of valuations
:::

## 15.3 Encouraging Truthful Bidding in Matching Markets: The VCG Princlple
### Definition
- **Vickrey-Clarke-Groves (VCG) principle:**
Each individual is charged an amount equal to the **"harm"** they cause to the other bidders
- **Harm:** the total amount better off everyone else would be if this individual weren’t there
- Example:
|With advertiser $x$|Without advertiser $x$|
|---|---|
|||
|Total evaluation of $y$ and $z$ = 12|Total evaluation of $y$ and $z$ = 25|
**The harm caused by $x$ is $25-12=13$**

### Notation
- $S$: the set of sellers
- $S−i$: the set of sellers with seller $i$ removed
- $B$: the set of buyers
- $B-j$: the set of buyers with buyer $j$ removed
- $V^S_B$: the **maximum total valuation** over all possible perfect matchings of sellers and buyers
:::info
1. If we give item $i$ to buyer $j$, then the best total valuation the rest of the buyers could get is $V^{S−i}_{B−j}$
2. If buyer $j$ simply didn’t exist, but item $i$ were still an option for everyone else, then the best total valuation the rest of the buyers could get is $V^{S}_{B−j}$
3. The VCG price $p_{ij}$ that we charge to buyer $j$ for item $i$ = the harm caused by $j$
$$
p_{ij} = V^{S}_{B−j} - V^{S−i}_{B−j}
$$
:::

### Price-setting procedure
1. Ask buyers to announce valuations for the items
2. Choose an optimal assignment of items to buyers
3. **Charge each buyer the appropriate VCG price**

Example:
- **Step 1:** Collect valuations and choose and optimal assignment
- $V^S_B = 30+10+2 = 42$
- $V^{S-a}_{B-x} = 10+2 = 12$
- $V^{S-b}_{B-y} = 30+2 = 32$
- $V^{S-c}_{B-z} = 30+10 = 40$

- **Step 2:** Charge $x$ its harm as the VCG price
|Assume $x$ doesn't exist|Evaluate $x$'s harm (VCG price)|
|---|---|
|$V^S_{B-x} = 20+5 = 25$|$p_{ax} = V^{S}_{B−x} - V^{S−a}_{B−x} = 25-12 = 13$|
|||
- **Step 3:** Charge $y$ its harm as the VCG price
|Assume $y$ doesn't exist|Evaluate $y$'s harm (VCG price)|
|---|---|
|$V^S_{B-y} = 30+5 = 35$|$p_{by} = V^{S}_{B−y} - V^{S−b}_{B−y} = 35-32 = 3$|
|||
- **Step 4:** Charge $z$ its harm as the VCG price
|Assume $z$ doesn't exist|Evaluate $z$'s harm (VCG price)|
|---|---|
|$V^S_{B-z} = 30+10 = 40$|$p_{cz} = V^{S}_{B−z} - V^{S−c}_{B−z} = 40-40 = 0$|
|||

## 15.4 Analyzing the VCG Mechanism: Truth-Telling as a Dominant Strategy
The following contexts show that the VCG procedure encourages truth-telling in a matching market.
:::info
**Claim**
If items are assigned and prices computed according to the VCG procedure, then truthfully announcing valuations is a dominant strategy for each buyer
:::
:::success
**Proof**
- The main idea is to show that a buyer will **NOT** get better payoff if she lies about her valuations
- If buyer $j$ decides to lie about her valuations, then one of two things can happen:
1. Buyer $j$ still gets the same item $i$
- Her payoff remains $v_{ij} - p_{ij}$
2. Buyer $j$ gets another item $h$
- We need to show that $v_{ij} - p_{ij} \geq v_{hj} - p_{hj}$

$$
\begin{aligned}
& v_{ij} - p_{ij} \geq v_{hj} - p_{hj} \\
\Rightarrow \ & v_{ij} - (V^{S}_{B−j} - V^{S−i}_{B−j}) \geq v_{hj} - (V^{S}_{B−j} - V^{S−h}_{B−j}) \\
\Rightarrow \ & v_{ij} + V^{S−i}_{B−j} \geq v_{hj} + V^{S−h}_{B−j} \\
\Rightarrow \ & V^{S}_{B} \geq v_{hj} + V^{S−h}_{B−j}
\end{aligned}
$$

- The LHS is the maximum total valuation **over all possible perfect matchings**, while the RHS the maximum total valuation **with a restriction** _(only over those matchings that pair $j$ with $h$)_, so the inequality must hold
:::

## 15.5 The General Second-Price Auction(GSP)

### Definition

- $n$ ad slots with clickthrough rate $r_i$
- $r_i$ stands for the probability of being clicked
- WLOG, say $r_i\geq r_{i+1}$
- $n$ advertisers with true value $v_j$, bid in price $b_i$
- $v_i$ stands for the revenue per click
- WLOG, say $b_i\geq b_{i+1}$
- bidder $i$ wins the $i$th slot, in charge of $r_ib_{i+1}$
- payoff of $i$th bidder is $r_i(v_i-b_{i+1})$

### Remark
- if there are fewer ad slot, we add virtual slot with rate $r=0$
- if there is only one slot, then it is equivalent to Second-Price Auction
- truth-telling may not be an equilibrium
- consider $x$ change from $7$ to $5$
- there may be more than one equilibrium
- $(5,4,2)$ and $(3,5,1)$
- the revenue of GSP can be either higher or lower than VCG
- GSP
- $(5,4,2)\rightarrow48$, $(3,5,1)\rightarrow34$
- VCG
- $(40,4,0)\rightarrow 44$


- in practice, search engine impose a minimum bid(reserve price) $p_i$

## 15.6 Equilibria of the Generalized Second-Price Auction

:::info
**Theorem.**
Let $G$ be a GSP graph, then $G$ has a Nash Equilibrium

**Proof.**
Let $p_i$ be the market-clearing prices of slot $i$ and $p^\star_j=p_j/r_j$. Claim that
$$
p^\star_1\geq p^\star_2\geq\ldots\geq p^\star_n
$$
Given $j\geq k$, advertiser $k$ perfer slot $k$ to $j$, that is
$$
r_k(v_k-p_k^\star)\geq r_j(v_k-p_j^\star)
$$
since $r_k\leq r_j$, thus $p_j^\star\geq p_k^\star$
Then define advertiser $1$ bid $p_1^\star+1$ and advertiser $j$ bid $p_{j-1}^\star$, then it is an equilibrium
:::

## 15.7 Ad Quality
- We assume an ad slot has a fixed click rate $r_i$
- Yahoo!
- In reality, the click rate depends on the advertiser
- Google improved model
- add the *quality factor* $q_j$ for advertiser $j$
- if advertiser $j$ appears at the slot $i$, then the click rate is $q_jr_i$
- assign the order by $q_jb_j$
- Google don't reveal how they compute $q_j$

## 15.8 Complex Queries and Interaction among Keywords
- keyword-based advertising market is complicated

## 15.9 Advanced Material: VCG Prices and the Market-Clearing Property

All number are integers.

:::info
**Theorem.**

the VCG prices is the unique set of market-clearing prices of minimum total sum of price. Recall the VCG price is defined by
$$
p_i=V_{B-j}^S-V_{B-j}^{S-i}
$$
:::

:::info
**Lemma 1.**
Let $G$ be a preferred-seller graph, $M$ be a perfect matching on $G$ with minimum sum of price, $i$ be an item that $v_i>0$, then there is an item $j$ with $v_j=0$ and an alternating path from $i$ to $j$, begin with non-matching edge.
**Proof.**
Suppose $i$ has no non-matching edge, then we can reduce the price.

Let $X$ be set that $i$ can reach by alternating path starting with non-matching edge, then
- $X\setminus\{i\}\neq\emptyset$
- if buyer $k\in X$, then the item $k$ matchs is also in $X$
- if item $h\in X$, then buyers connect to $h$ with non-matching edge are in $X$
- assume for item $h\in X$, $p_h\neq 0$

Now claim if we substract price of all items in $X$ by $1$, it is still market-clearing. Assume buyer $n$ was matched with item $e$, and an item $f$ has less payoff after that, then
- price of $f$ is reduced, $f\in X$
- price of $e$ is not changed, $e\not\in X$
- $nf\in EG$
- $n\in X$, then $e\in X$, contradiction

Thus, it yields that matching edges are not changes, thus it is still market-clearing after subtraction. Then contradiction to the minimum price.
:::

:::info
**Lemma 2.**
Let $G$ be a matching market with minimum market-clearing prices $p$, $M$ be a perfect matching on $G$, and a buyer $j$, then
- the prices $p$ is also market-clearing when $j$ is zeroed out
- $j$ recieves a zero-priced item
- the payoffs of buyers not $j$ stay the same

**Proof.**
Let $i$ be the item matched by $j$, then there exist an alternating path $P$ from $i$ to a zero-priced item $i^\star$, then after zero out $j$, buyers on $P$ change their matching item along $P$, and $j$ matches $i^\star$.
:::

:::info
**Theorem.**

the VCG prices is the unique set of market-clearing prices of minimum total sum, that is
$$
p_i=V_{B-j}^S-V_{B-j}^{S-i}
$$
**Proof.**
Let
- $v_{ij}$ be the valuaion of buyer $j$ for item $i$
- $p_i$ be the price of item $i$
- if $j$ recieve $i$, the payoff $z_j=v_{ij}-p_i$
- $P$ be the sum of all price of items
- $Z$ be the sum of all payoff

Note that
$$
\mbox{total payoff on }M=\mbox{total valuation on }M-\mbox{total price}
$$
That is
$$
Z=V_B^S-P
$$
On the other hand, if $j$ matchs $i$, we have
$$
v_{ij}+V_{B-j}^{S-i}=V_B^S
$$
Now, if we zero out $j$
- the total valuation is $V_{B-j}^S$
- the total price stays the same by Lemma 2, thus $P$
- the payoff stay the same except $j$, thus the new total payoff is $Z-z_i$

thus we have
$$
Z-z_j=V_{B-j}^S-P
$$
implies that
$$
z_j=V_B^S-V_{B-j}^S
$$
thus
$$
v_{ij}-p_i=z_j=V_B^S-V_{B-j}^S=(v_{ij}+V_{B-j}^{S-i}-V_{B-j}^S)
$$
concludes that
$$
p_i=V_{B-j}^S-V_{B-j}^{S-i}
$$
:::