A05 · Multi-slot GFP, GSP, and VCG
Prerequisites: foundations 31–34; A04.
Evidence: explicitly constructed mechanism experiments, not real ad logs. This chapter does not claim industrial-system reproduction or online gains.
Learning order: predict → change one variable → run → explain.
English companion. All instructional Markdown is translated. Experiment code, Chinese language examples, execution counts, and saved outputs remain as in the source edition; historical output text may therefore be Chinese. The initial setup cell anchors the working directory and Python import path for this companion's deeper folder; it does not change the experiment. Saved outputs are historical evidence, not a new run. Run from the top after preparing the required data and models.
# English companions live one directory deeper; keep the original experiment code unchanged.
from pathlib import Path as _TranslationPath
import os as _translation_os
import sys as _translation_sys
_translation_root = next((p for p in [_TranslationPath.cwd(), *_TranslationPath.cwd().parents]
if (p / "reclab").is_dir()), None)
if _translation_root is None:
raise RuntimeError("Open this notebook from inside the Search Recommendation Ads Lab checkout.")
_translation_os.chdir(_translation_root)
if str(_translation_root) not in _translation_sys.path:
_translation_sys.path.insert(0, str(_translation_root))
Problem and input/output contract
Assume separable clicks P(click|i,k)=α_k with equal ad quality. Values and bids are currency per click. Slot factors are α=(1,.4); the third bidder is not displayed but provides competition. GFP charges own bid per click; GSP charges the next bid; VCG charges the externality: others’ optimal welfare without the winner minus their original welfare. Output payment is expected payment per request; CPC=payment/α. Do not mix units. Efficiency applies under this separable model with ranking by true values.
Before running, predict which result the changed variable will affect and which invariants must hold.
from pathlib import Path
import sys
root=Path.cwd()
if not (root/'reclab').exists(): root=root.parent
if str(root) not in sys.path: sys.path.insert(0,str(root))
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from reclab import ads_curriculum as acRun the one-variable comparison
Inputs are small constructed examples visible in source. Output units and constraints are defined above. Run assertions to verify mathematics and accounting.
for mechanism in ('gfp','gsp','vcg'):
print(mechanism);display(pd.DataFrame(ac.slots(mechanism=mechanism)))
vcg=ac.slots();assert np.allclose([r['payment'] for r in vcg],[4.,.4])
from itertools import permutations
assert max(1*[7,6,1][p[0]]+.4*[7,6,1][p[1]] for p in permutations(range(3),2))==9.4
def utility(b,mechanism):
row=next((r for r in ac.slots((b,6,1),mechanism=mechanism) if r['bidder']==0),None)
return 7*row['click_probability']-row['payment'] if row else 0.
grid=np.arange(0,10,.25)
assert max(utility(b,'vcg') for b in grid)<=utility(7,'vcg')+1e-10
print('GSP truthful/shaded utility',utility(7,'gsp'),utility(5,'gsp'))
assert utility(5,'gsp')>utility(7,'gsp')Saved notebook output · not executed on this page
gfp
| bidder | slot | click_probability | payment | cpc | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1.0 | 7.0 | 7.0 |
| 1 | 1 | 1 | 0.4 | 2.4 | 6.0 |
gsp
| bidder | slot | click_probability | payment | cpc | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1.0 | 6.0 | 6.0 |
| 1 | 1 | 1 | 0.4 | 0.4 | 1.0 |
vcg
| bidder | slot | click_probability | payment | cpc | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1.0 | 4.0 | 4.0 |
| 1 | 1 | 1 | 0.4 | 0.4 | 1.0 |
GSP truthful/shaded utility 1.0 2.4000000000000004
Interpretation and limits
VCG charges externalities: the top expected payment is 4, not the next bidder’s CPC of 6. In this example, lowering a GSP bid can increase utility, so single-item second-price truthfulness cannot simply be transferred. Grid assertions verify this case only. General VCG incentive results also depend on quasilinear utility, independent private values, no budgets, and related assumptions.
Inspect source, then try an exercise
Change the second slot’s α from .4 to .8 and recompute payments. Add quality q_i and derive the quality-adjusted GSP threshold instead of continuing to charge the next raw bid.
import inspect
print(inspect.getsource(ac.slots))Saved notebook output · not executed on this page
def slots(bids=(7.,6.,1.), alpha=(1.,.4), mechanism='vcg'):
"""Homogeneous quality, separable position CTR alpha, bids in currency/click.
payment is expected currency per request, not CPC. Zero reserve; stable ties.
"""
bids=np.asarray(bids,float); alpha=np.asarray(alpha,float)
if mechanism not in ('gfp','gsp','vcg') or len(bids)<len(alpha) or np.any(bids<0) or np.any(np.diff(alpha)>0) or np.any(alpha<=0):
raise ValueError('Invalid auction')
order=sorted(range(len(bids)),key=lambda i:(-bids[i],i)); winners=order[:len(alpha)]
welfare=sum(alpha[k]*bids[i] for k,i in enumerate(winners)); rows=[]
for k,i in enumerate(winners):
if mechanism=='gfp': pay=alpha[k]*bids[i]
elif mechanism=='gsp': pay=alpha[k]*(bids[order[k+1]] if k+1<len(order) else 0.)
else:
other=[j for j in order if j!=i][:len(alpha)]
without=sum(alpha[t]*bids[j] for t,j in enumerate(other))
pay=without-(welfare-alpha[k]*bids[i])
rows.append(dict(bidder=i,slot=k,click_probability=float(alpha[k]),payment=float(pay),cpc=float(pay/alpha[k])))
return rows
Sources and next step
A-CCR pp. 73–94; A-RTB pp. 21–36. Historical platform descriptions are not treated as current facts. This is an original Lab exercise, not a copy of the complete lecture text.
Chinese GitHub chapter · Authors’ RTB slides. The Chinese deck is not a complete modern advertising-engineering course. Historical descriptions of platforms are not presented as current market facts.
After the exercise, return to the ads learning path and continue to the next semantic unit.