Sponsored Search Auctions

Motivation: auctioning attention next to search results

Offline, advertising is sold by negotiation or posted price. Online, search engines auction space beside their algorithmic results. When a user searches “ipod,” Apple or Best Buy may appear in the sponsored listings.

Why per click rather than per impression? Traditional media sell exposure because effectiveness is hard to measure. The Web can track clicks, and direct marketers prefer to pay for them. The next step, paying per action or conversion, is discussed under Open questions.

---

Existing mechanisms

Advertisers submit keyword–bid pairs plus a budget. On each search, the interested advertisers with budget remaining enter an auction.

Mechanism	Weights	Price per click
GSP, rank by bid (Overture/Yahoo!)	$w_j = 1$	next bid $b_{j+1}$
GSP, rank by revenue (Google)	$w_j = \alpha_{1j}$	$s_{j+1}/w_j$
GFP (Yahoo! before 2004)	rank by bid	your own bid

graph TD
  B1["Slot 1: highest score"] -->|"pays next score / own weight"| B2["Slot 2"]
  B2 -->|"pays next score / own weight"| B3["Slot 3"]
  B3 -->|"sets slot 3's price"| B4["First excluded bidder"]

---

The static model

Four assumptions need salt:

Assumption	Reality check
static (one-shot)	auctions recur constantly; the chapter accepts this for tractability
value per click is slot-independent	some claim top-slot clicks convert worse (errors, less serious users); tracking data (Isobar) says the top slot converts about as well
no externalities between bidders	Avis may value Hertz being absent
CTRs are common knowledge	engines learn CTRs from rich context (a hard ML problem with an explore/exploit trade-off); bidders know less; CTRs fluctuate

Revenue maximization and efficiency

In the static model, the optimal designs are already known.

GSP is not VCG

DerivationExact VCG prices in this example

Bidder 1’s externality: without her, bidders 2 and 3 get $\mu_1v_2 + \mu_2v_3$. With her, bidder 2 gets $\mu_2v_2$ and bidder 3 gets nothing. So she pays $$\mu_1v_2 + \mu_2v_3 - \mu_2v_2 = (\mu_1 - \mu_2)v_2 + \mu_2v_3,$$ which is $\big(1 - \frac{\mu_2}{\mu_1}\big)v_2 + \frac{\mu_2}{\mu_1}v_3$ per click. Bidder 2 pays $\mu_2v_3$, i.e. $v_3$ per click.

(The chapter states bidder 1’s VCG price as $(1 - \mu_2/\mu_1)v_2$. That matches its sequential-auction story, where slot 2 is priced at 0. The full externality adds the $\frac{\mu_2}{\mu_1}v_3$ term. This computation is mine.)

Ranking auctions

Equilibrium properties

Not being truthful doesn’t settle efficiency or revenue. The equilibria might still be good.

ProofAdjacent-swap inequalities give assortativity; LP duality gives the converse

(⇒ optimal) It suffices to show assortativity. Let $j$ hold slot $i$ and $j'$ hold slot $i+1$. Local envy-freeness for each, toward the other’s slot:

$$\mu_iv_j - p_i^*\ge\mu_{i+1}v_j - p_{i+1}^*, \qquad \mu_{i+1}v_{j'} - p_{i+1}^*\ge\mu_iv_{j'} - p_i^*.$$

Adding them cancels the prices: $(\mu_i - \mu_{i+1})(v_j - v_{j'})\ge0$. Since $\mu_i > \mu_{i+1}$, we get $v_j\ge v_{j'}$.

(⇐ locally envy-free) Take an optimal dual $(p^*,q^*)$. For $x^*_{rj} = 1$, complementary slackness and dual feasibility give

$$\mu_rv_j - p_r^* = q_j^* = \max_i\{\mu_iv_j - p_i^*\}\ge\max\{\mu_{r-1}v_j - p_{r-1}^*,\ \mu_{r+1}v_j - p_{r+1}^*\}.$$

The dual prices are in fact globally envy-free.

∎

ProofBid the VCG price of the slot above, scaled by its CTR

Order values $v_1\ge v_2\ge\cdots$, and let $p_i^*$ be the Vickrey total price of slot $i$.

Step 1: The bids. Bidder 1 bids $b_1 = v_1$. Each bidder $j\ge2$ bids $b_j = p^*_{j-1}/\mu_{j-1}$. Under GSP, slot $j$ pays the next bid $b_{j+1}$ per click, for a total of $\mu_jb_{j+1} = p_j^*$: exactly the VCG price.

Step 2: Bids are decreasing, so GSP assigns efficiently. Local envy-freeness of the VCG outcome for bidder $j$ looking up gives $p^*_{j-1}\ge p^*_j + (\mu_{j-1} - \mu_j)v_j$. VCG profits are nonnegative, so $v_j\ge p^*_j/\mu_j$. Combining,

$$p^*_{j-1}\ge p^*_j + (\mu_{j-1}-\mu_j)\frac{p^*_j}{\mu_j} = \frac{\mu_{j-1}}{\mu_j}p^*_j \;\Rightarrow\; b_j = \frac{p^*_{j-1}}{\mu_{j-1}}\ge\frac{p^*_j}{\mu_j} = b_{j+1}.$$

For $j = 1$: $b_1 = v_1\ge p_1^*/\mu_1 = b_2$. So bidder $j$ gets slot $j$. Bidders beyond $m$ pay nothing.

Step 3: No profitable deviation. Each bidder receives her efficient slot at her VCG price, and the prices are envy-free (Theorem 28.1). The chapter concludes that no one wants to change her bid.

(Step 2’s cleaned-up inequality chain is mine; the printed version has shifted indices. Step 3 is the chapter’s brief argument.)

∎

---

Dynamic aspects

These auctions are really repeated games of incomplete information, which have rich equilibrium sets. Two phenomena stand out:

Online allocation with budgets

Even without strategy, budgets across keywords make efficient allocation an online problem.

Component	Detail
$\beta_j$	shadow price of advertiser $j$‘s budget: extra revenue per extra dollar of $B_j$
$b_{ij}\beta_j$	opportunity cost of spending $b_{ij}$ of $j$‘s budget now
$b_{ij}(1 - \beta_j)$	net value of allocating query $i$ to $j$

Online: the query frequencies $r_i$ are unknown, and queries must be allocated as they arrive. Performance is measured by competitive ratio against the offline optimum of (28.11) (see online-mechanisms).

Proof ideas. Discretize budgets into $k$ levels. A bidder is of type $j$ if she has spent a fraction in $(\frac{j-1}{k},\frac jk]$ of her budget. Let $s_j$ be the total budget of bidders ending at type $j$, and $w_i$ the money spent from the $i$-th slice of bidders’ budgets. Use the discrete tradeoff

$$\Psi(s) = 1 - \Big(1 - \frac1k\Big)^{k-s}\;\to\;\phi(s/k), \tag{28.12}$$

which is decreasing in $s$. Assume OPT exhausts all budgets, so $\mathrm{OPT} = \sum_is_i$.

ProofCharge each query to OPT’s choice

Step 1: Compare at one query. When query $q$ arrives, let OPT give it to a bidder of current type $t$ (final type $t'\ge t$), earning $b_{\text{opt}}$. The algorithm gives it to a bidder of type $i$, earning $b_{\text{alg}}$.

$$\Psi(t')\,b_{\text{opt}}\overset{(a)}{\le}\Psi(t)\,b_{\text{opt}} \overset{(b)}{\le}\Psi(i)\,b_{\text{alg}}.$$

• (a) $\Psi$ is decreasing and $t'\ge t$.
• (b) The algorithm maximizes (discretized) $b\cdot\Psi(\text{type})$.

Step 2: Sum over queries. The left side, weighted by each bidder’s final type, sums to $\sum_i\Psi(i)s_i$. The right side, weighted by the type at the moment of spending, sums to $\sum_i\Psi(i)w_i$.

∎

---

Open questions

---

Quick reference

Object	Statement	Note
Sponsored search	per-query continuous auctions for ordered slots	pay per click
CTR	$\alpha_{ij}$, decreasing in slot	everyone ranks slots alike
Score	$s_j = w_jb_j$; rank by score
GSP price per click	$s_{j+1}/w_j$	rank by bid ($w = 1$) / by revenue ($w = \alpha_{1j}$)
GFP	pay your own bid	no pure full-info equilibrium
Static model	private $v_j$ per click; CTRs known	four strong assumptions
Revenue optimum	VCG on virtual values (reserves)	Myerson with $x_j$ = expected CTR
Efficiency LP (28.1)	max-weight assignment	totally unimodular ⇒ integral
Dual (28.5)	$p_i + q_j\ge\alpha_{ij}v_j$	VCG = optimal dual minimizing $\sum p_i$
Assortative	$\alpha_{ij} = \mu_i$ ⇒ sort by $v$	Northwest corner rule
Two-slot example	top price $(1 - \mu_2/\mu_1)v_2 < v_2$	lower slot is an outside option
Truthful ranking payment (28.8)	$P = b\,x(b) - \int_0^bx(t)\,dt$	GSP and GFP don’t use it
GFP Bayes-Nash	symmetric, monotone ⇒ efficient	bid cycling when repeated
Locally envy-free (28.9–28.10)	no envy toward adjacent slots
Thm 28.1	optimal ⟺ locally envy-free	adjacent swap + duality
Thm 28.2	GSP equilibrium with $b_j = p^*_{j-1}/\mu_{j-1}$ gives VCG	efficient, VCG revenue
Bid rotation / vindictive bidding	repeated-game pathologies	your bid prices the slot above
Online LP (28.11)	budgets $B_j$, volumes $r_i$	allocate to $\max b_{ij}(1 - \beta_j)$
$\beta_j$	budget shadow price, i.e. opportunity cost
Greedy	$1/2$-competitive, tight	ignores opportunity cost
Algorithm 1	maximize $b_{ij}(1 - e^{f_j-1})$	budget smoothing
Thm 28.3	$1 - 1/e$, optimal	Lemma 28.4 charging argument

Facts to keep to hand

• LP duality prices everything here. VCG payments are the seller-minimal optimal dual of the assignment LP. Envy-free prices are dual solutions (Theorem 28.1). The online rule discounts bids by the budget constraint’s dual variable.
• Reducing to Vickrey for one item proves nothing for many. A second slot is an outside option that lowers willingness to pay for the first. VCG accounts for this and GSP doesn’t, so truthful GSP bidding overpays at the top.
• Non-truthful mechanisms can have good equilibria. GFP (Bayesian) and GSP (full information, locally envy-free) both reach efficient allocations, and GSP’s constructed equilibrium matches VCG revenue exactly. Truthfulness is sufficient for good outcomes, not necessary.
• Static equilibria can mislead dynamically. GFP’s lack of a pure full-information equilibrium became bid cycling in practice. GSP’s “price-setting from below” enables vindictive bidding. Repeated play enables rotation.
• Budgets make allocation online, and opportunity cost is the fix. Greedy spends the wrong budgets first (1/2). Pricing budget depletion with $\phi(f) = 1 - e^{f-1}$ spreads spending and achieves the best possible $1 - 1/e$.
• $1 - 1/e$ keeps appearing. Greedy for monotone submodular maximization (cascading-behavior-in-networks) and optimal online budgeted allocation share the same constant. It is the signature of “diminishing marginal value, handled online or greedily.”
• Monotone CTR decay is the structural gift. Identical slot rankings make keyword auctions condominium auctions: efficient assignment is just sorting, and local envy-freeness implies global.

References

• Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 28 (Lahaie, Pennock, Saberi, Vohra)