Bid Landscaping, Part 1: Learning the Win Curve from the Auctions We Lost

Recently, while working for a client in the AdTech domain, I got to understand how Google’s hotel ads mechanism works end to end - how a hotel’s rate surfaces into an auction, how Ad Rank resolves it, and how the advertiser’s bid knob actually connects to the clicks that come out the other side. My task was to design the bid optimization algorithm: given what we know about each auction context, what should we bid?

Digging into that problem, I kept running into the same wall from a different direction each time, and the concept that finally resolved it was bid landscaping. It wasn’t entirely new to me - back at Walmart, while working on improving campaign budget underutilization, I had used bid-landscape win rates as an input to pacing decisions. But that was a consumer’s view of the landscape: a curve someone else had estimated, which I read numbers off. This time I had to build one, and building it forced me to understand where the curve comes from, why the obvious way to estimate it is quietly wrong, and why the correct tool is - of all things - a statistical method from medical survival studies.

This post is that detailed take: what a bid landscape is, why lost auctions are the most misunderstood data we have, and how the Kaplan-Meier estimator turns them into a win curve, worked end to end on a toy dataset.

1. What is a Bid Landscape?

A bid landscape (also called a win curve) is a function:

\[W(b) = P(\text{we win the auction} \mid \text{we bid } b)\]

We’re trying to estimate the probability of winning an ad auction, given we bid with a price b.

Before going further, two prices need to be pinned down, because confusing them derails everything downstream:

• $b$ - our bid. The amount we submit to the auction; the lever we control. In the landscape $W(b)$ it is the x-axis: “if we were to bid $b$…”.
• $P$ - the winning threshold. The minimum effective bid we would have needed to win that auction. It is not our bid; it is a property of the auction, set by everything we don’t control - competitors’ bids, their quality scores, reserve prices - and different every time.

We win an auction iff $b \ge P$. In a textbook second-price auction, $P$ is simply the highest competing bid (the clearing price), and it is also what we pay on a win. Real platforms are messier: Ad Rank folds in quality, reserves set floors, and much of RTB now runs first-price. To isolate the statistical problem, this article assumes the clean second-price case - winning reveals $P$ exactly (we paid it), losing reveals only that $P > b$.

That observation structure - not merely the auction’s label - is what the Kaplan-Meier method requires. The same machinery works whenever the platform exposes the exact winning threshold on a win and a lower bound on a loss. It is worth being strict about what “winning reveals the threshold” actually demands, because a platform labelled “second-price” does not automatically satisfy it. The exact-threshold reading is valid only when:

• the logged payment equals the minimum effective bid that would have won (not merely a price);
• no opaque quality/rank transform sits between our bid and the clearing comparison, so the numbers live in one comparable currency;
• fees, bid increments, reserves, and currency normalization are accounted for;
• the figure is not simply our own first-price bid;
• no post-auction adjustment changes the effective cost after the fact.

In a ranked auction the deciding threshold may live in score space (bid × quality), so recovering a comparable price needs the quality adjustment undone. A standard first-price payment, meanwhile, is our own bid; it does not reveal the minimum bid that would have won. If all we receive is win/loss at our submitted bid, we need a different estimator, a distinction Part 2 makes explicit.

The win curve is monotonically increasing - bid more, win more - and it is the missing half of the bidding problem. Most bid optimization pipelines model the value side well: pCTR, pCVR, expected revenue per click (the prediction models from the intelligence-layer overview). The bid landscape is the cost side: what does it take to actually win, and what will winning cost?

\[\text{profit}(x, b) = \underbrace{\text{value}(x)}_{\text{from won clicks}} - \underbrace{\text{cost}(x, b)}_{\text{from the landscape}}\]

Here $x$ is the auction context - the bundle of features describing the particular auction we are bidding into: query, device, geography, time of day, placement, and so on. The value of winning depends on the context alone; the cost of winning depends on the context and on how much we bid. Everything in this article - the win curve, the toy example - is implicitly per-context: one landscape for each segment of comparable auctions, a point Part 2 returns to.

A bidder that models only value is competition-blind. It knows what an impression is worth but has no idea what the market charges for it.

2. The Problem: We Only Observe Half the Story

Under the clean second-price feedback assumed in this article, here is what the auction log gives us:

Auction outcome	What we observe about the clearing price
Won	The exact price $P$ (we paid it)
Lost	Only that $P > \text{our bid}$

The tempting shortcut is to estimate the price distribution from won auctions only - after all, those are the only rows with an actual price in them. This is exactly the wrong move, and the reason is selection bias: we only ever observe prices below our historical bids. The entire upper region of the distribution - the prices that beat us - is systematically missing from our sample.

This is the classic WWII bomber problem. The military examined returning planes, mapped where the bullet holes were, and proposed armoring those spots - until Abraham Wald pointed out that they were only studying the planes that came back. The holes they could see were, by definition, the survivable ones. Estimating competing prices from won auctions is studying the planes that returned.

An even cruder shortcut is:

\[\hat{W} = \frac{\text{auctions won}}{\text{total auctions}}\]

which produces a single flat number - “we win 50% of the time” - with no dependence on the bid at all. It punishes our win-rate estimate at \$5 with auctions we lost at \$3, even though those losses say nothing about our ability to win at \$5. We will see this fail concretely on the toy dataset below.

So the situation is: lost auctions clearly carry information (“the price was higher than \$X” is a real fact about the competition), but we can’t use them naively, and we can’t drop them without bias. We need machinery built for partial observations.

That machinery exists. It just lives in a different field.

3. A Detour Through the Hospital: Survival Analysis

Picture a waiting room full of patients. Periodically a name is called - the event happens (in the medical original, something like death or relapse). But some patients leave before their name is called, and for them we know something real but incomplete: they waited at least this long, but we don’t know how long they would have waited.

Every subject in a survival study is therefore one of two types:

Subject	What happens	Statistical term
Name is called	The event occurs, at an observed time	Event
Leaves early	Observation stops before the event	Censored (right-censored)

The defining challenge of survival analysis is what to do with the censored subjects, and the key insight is that we cannot do either of the two obvious things:

• We can’t drop them. Each departure still proves that the patient remained event-free up to that point. Throwing away that partial survival time generally biases a naive estimate downward.
• We can’t count them as events. Their event never happened while observed. Pretending it did biases the estimate even more.

The Kaplan-Meier estimator is the tool that uses these incomplete records correctly - keeping each subject in the “still at risk” pool for exactly as long as it was observed, then quietly removing it, never inventing an event that wasn’t seen.

If the phrase “we know it was more than X, but not how much more” is ringing a bell, it should.

4. An Auction Is a Survival Problem

Map the waiting room onto the auction log. The quantity that plays the role of survival “time” is the clearing price $P$ - the competition’s price, not our bid:

Survival analysis	Our auction problem
Subject (a patient)	One auction
“Time” $T$	Clearing price $P$
Event observed at $T$	We win → we pay $P$ → we observe $P$ exactly
Right-censored at $c$	We lose → we only know $P > \text{our bid}$ → censored at our bid
Survival function $S(t) = P(T > t)$	$S(b) = P(P > b)$ = probability we lose at bid $b$

Two things to lock in:

• A win is a fully-observed data point. We paid the clearing price, so we know $P$ exactly.
• A loss is a censored data point. We only learn $P > b$. We never see the lost price - and we don’t need to. The bid alone is the censoring point. The lost price being invisible is the expected state of the data, not a blocker.

And the curve we want falls straight out:

\[W(b) = P(\text{win at bid } b) = P(P \le b) = 1 - S(b)\]

If Kaplan-Meier gives us $S$ (the loss curve), the win curve is just $1 - S$.

5. The Kaplan-Meier Estimator, Piece by Piece

Part 2 spends five caveats on when this estimator can be trusted, but the core assumptions deserve to sit before the derivation rather than after it. Read this as the estimator’s model card:

What KM assumes here. (1) The auction records in a modeled stratum are comparable and independent draws from one threshold distribution. (2) Censoring is non-informative given context - our bid does not, after conditioning on the segment’s features, carry extra information about the threshold (the endogeneity caveat in Part 2 makes this concrete). (3) The threshold distribution is stable over the estimation window. (4) Wins and losses are encoded exactly as event/censoring at the right value. (5) There is adequate support - enough auctions still at risk - over the bids we intend to read off. Where these hold, KM is unbiased for the win curve; where they do not, it degrades in the specific ways Part 2 catalogs.

With the assumptions stated, pin down the record the estimator sees. Every auction $j$ contributes two fields (plus the context columns that define the segment):

\[Y_j = \begin{cases} P_j & \text{if won (the exact winning threshold)} \\ B_j & \text{if lost (our bid)} \end{cases} \qquad \delta_j = \begin{cases} 1 & \text{if won} \\ 0 & \text{if lost} \end{cases}\]

$Y_j$ is the furthest price up to which that auction’s record takes us. On a win it is the exact threshold, so the record resolves there. On a loss it is our bid, so the record ends there with only the knowledge that the true threshold lies somewhere higher. KM is fitted on $(Y_j, \delta_j)$; no lost clearing price is invented or required.

To compute KM we sweep a candidate bid $b$ upward from zero and, at each price where we observed a win, step the survival curve down a little. Four quantities drive it:

• Event price $t_i$ - a price at which we observed a win (a fully-observed clearing price). These are the only prices where the curve moves.
• Number of events $d_i$ - how many auctions cleared at exactly $t_i$ (how many wins landed at that price).

• Risk set $n_i$ - how many auction records still reach price $t_i$. Mechanically, an auction belongs to the risk set when its recorded endpoint $Y_j$ is at least $t_i$:

  \[n_i = \sum_{j=1}^{n} \mathbb{1}\{Y_j \ge t_i\}\]

  This is not a claim about every auction’s unknown true threshold. It counts only the auctions whose observed evidence lets us vouch that the threshold reached $t_i$. There are two ways to have left the pool before $t_i$:

  • A win at a price below $t_i$ is resolved - its threshold is known exactly, and it is lower. It has nothing left to say about $t_i$.
  • A loss at a bid below $t_i$ leaves because our information ran out at that bid. Its true threshold may be just above the bid or far above $t_i$; we cannot tell. Keeping it in the pool would assert evidence we do not have.
• Censored count $c_i$ - losses recorded at that value. These do not move the curve, but they shrink the risk set for all higher prices - we stop tracking that auction past its bid.

Risk set $n_i$: one concrete snapshot

Preview the eight-auction dataset used in the next section and freeze the price sweep at $t=5$. For each auction, ask one mechanical question: does its observed record prove that its threshold reached at least \$5?

Auction	Observed record	In $n(5)$?	Why?
1	Won at $P=2$	No	Its threshold resolved below 5
5	Won at $P=3$	No	Its threshold resolved below 5
3	Lost with bid 3	No	We know only $P>3$, not that $P\ge5$
8	Lost with bid 4	No	Its threshold could be 4.10 or 40; the record cannot tell us
4	Won at $P=5$	Yes	Its threshold is exactly 5
7	Won at $P=5$	Yes	Its threshold is exactly 5
2	Lost with bid 5	Yes	Losing proves $P>5$
6	Lost with bid 7	Yes	Losing proves $P>7$, and therefore $P>5$

So $n(5)=4$. Two of those four auctions resolve exactly at 5, so $d(5)=2$ and the survival factor at this rung is:

\[1 - \frac{d(5)}{n(5)} = 1 - \frac{2}{4} = 0.5\]

The subtle case is auction 8. Removing it at \$4 does not mean we believe its threshold was below \$5. It means only that its observation ended at \$4, so it supplies no defensible information at \$5. Conversely, auction 2 is censored exactly at \$5 and is included in the denominator at that price before being removed; its loss proves that its threshold made it past the rung.

The intuition before the formula

Now generalize that snapshot. At any event price $t_i$, the risk set contains $n_i$ auction records whose evidence reaches the rung. Of those, $d_i$ resolve there - their threshold turned out to be exactly $t_i$. So the ratio

\[\frac{d_i}{n_i} = \hat{P}\big(\text{threshold} = t_i \;\big|\; \text{threshold} \ge t_i\big)\]

is the estimated chance that an auction’s threshold resolves at this price rung, given that it climbed this far. (Survival analysis calls this the hazard at $t_i$.) Its complement,

\[1 - \frac{d_i}{n_i} = \hat{P}\big(\text{threshold} > t_i \;\big|\; \text{threshold} \ge t_i\big)\]

is the chance of getting past the rung. Picture the sweep upward as a climb: each event price asks the auctions still climbing one question - “did the threshold resolve here?” - and $1 - d_i/n_i$ is the fraction that answered no and kept climbing.

The estimator simply chains these rung-survival probabilities together:

\[\hat{S}(b) = \prod_{t_i \le b} \left(1 - \frac{d_i}{n_i}\right)\]

Why a product?

Read $S(b)$ as “the threshold survives past $b$” - i.e., “we would still lose at bid $b$.” To survive past $b$, the threshold must get past every event price along the way, so the chain rule of probability multiplies the conditional pieces:

\[S(b) = P(\text{survive past } t_1) \cdot P(\text{survive past } t_2 \mid \text{survived } t_1) \cdots\]

and each conditional factor is exactly the rung-survival probability $1 - d_i/n_i$ we just built.

Censored losses never contribute a factor - they aren’t events. They only lower $n_i$ for later prices, which is exactly how a “we know it’s bigger than X” observation should count. That one sentence is the whole reason KM is the right tool: a lost auction with no known price still pulls its weight, through the risk set, without us ever inventing its price.

6. Worked Example: Eight Auctions

One context - say, a single ad-group on mobile. For each auction we logged our bid and the outcome. On wins we also see the price we paid (the clearing price, since this is second-price); on losses we see nothing but our own bid.

Auction	Our bid	Outcome	Clearing price seen	KM “value”	KM type
1	\$5	win	\$2	2	event
5	\$4	win	\$3	3	event
3	\$3	lose	- (only know > \$3)	3	censored
8	\$4	lose	- (only know > \$4)	4	censored
4	\$6	win	\$5	5	event
7	\$6	win	\$5	5	event
2	\$5	lose	- (only know > \$5)	5	censored
6	\$7	lose	- (only know > \$7)	7	censored

$n = 8$ auctions: 4 wins (events) and 4 losses (censored). Note that we win at or below our bid (we pay the second price) and we lose above our bid.

Tie convention: when an event and a censored observation share the same value (here, value 5 has 2 wins and 1 loss), the censored one is treated as occurring just after the events - so it is still counted in the risk set at that event price, then removed afterward.

The computation, step by step

Section 5 wrote the estimator as one product containing every event-price factor up to $b$. Here we evaluate that same product recursively, one price at a time:

\[\hat{S}(t_i) = \hat{S}(t_i^-)\left(1-\frac{d_i}{n_i}\right), \qquad \hat{S}(0)=1\]

$\hat{S}(t_i^-)$ is the estimate immediately before the event at $t_i$. It already contains the product of all earlier factors, so multiplying it by the new factor extends the same product by one rung. At a censor-only price there is no new factor and the curve stays flat, although the censoring still shrinks later risk sets.

The hat matters: $S(b)=P(P>b)$ is the unknown population survival curve, while $\hat{S}(b)$ is its Kaplan-Meier estimate from these eight auctions. The corresponding estimated win curve is $\hat{W}(b)=1-\hat{S}(b)$.

Sort everything by value and walk upward. The risk set $n$ at each price is the number of auctions whose recorded value is $\ge$ that price.

Price 2 - 1 win, 0 losses. Risk set = all 8 (every value $\ge 2$).

\[\hat{S}(2) = 1 - \tfrac{1}{8} = 0.875\]

Price 3 - 1 win (auction 5) + 1 loss (auction 3). Risk set = 7 (everyone except auction 1, whose price of 2 is already resolved).

\[\hat{S}(3) = 0.875 \times \left(1 - \tfrac{1}{7}\right) = 0.875 \times \tfrac{6}{7} = 0.750\]

After this price, auction 5 (event) and auction 3 (censored) leave the pool.

Price 4 - 0 wins, 1 loss (auction 8). Risk set = 5. No event ⇒ the curve does not step. The loss just removes auction 8 going forward.

\[\hat{S}(4) = 0.750 \quad (\text{unchanged})\]

Price 5 - 2 wins (auctions 4, 7) + 1 loss (auction 2). Risk set = 4 (auctions 2, 4, 6, 7 remain).

\[\hat{S}(5) = 0.750 \times \left(1 - \tfrac{2}{4}\right) = 0.750 \times 0.5 = 0.375\]

After this, auctions 4 and 7 (events) and auction 2 (censored) leave. Only auction 6 remains.

Price 7 - 0 wins, 1 loss (auction 6). Risk set = 1. No event ⇒ no step.

\[\hat{S}(7) = 0.375 \quad (\text{unchanged})\]

The full table

Price $t$	Risk set $n$	Wins $d$	Losses $c$	Step $1 - d/n$	$\hat{S}(t)$ = estimated lose prob	$\hat{W}(t) = 1 - \hat{S}(t)$ = estimated win prob
2	8	1	0	7/8	0.875	0.125
3	7	1	1	6/7	0.750	0.250
4	5	0	1	-	0.750	0.250
5	4	2	1	2/4	0.375	0.625
7	1	0	1	-	0.375	0.625

The bid landscape we just built

Reading off the estimated win curve $\hat{W}(b)$ (a right-continuous step function):

\[\hat{W}(b) = \begin{cases} 0.000 & b < 2 \\ 0.125 & 2 \le b < 3 \\ 0.250 & 3 \le b < 5 \\ 0.625 & b \ge 5 \ \ (\text{known only up to } \$7) \end{cases}\]

How to use it:

• Bid $\rightarrow$ win rate: bid \$5 $\Rightarrow$ ~62.5% win probability; bid \$3 $\Rightarrow$ ~25%.
• Target win rate $\rightarrow$ bid: want ~25% coverage? Bid ~\$3. Want ~62%? Bid ~\$5.
• Spend curve: under second-price, when we win at bid $b$ we pay the clearing price ($\le b$). The expected cost per win comes from the KM curve itself - worked out next, because there is a trap in it.

From KM jumps to expected cost

The steps of $\hat{F}(b) = \hat{W}(b) = 1 - \hat{S}(b)$ are not just a picture - each jump is a probability mass sitting at an observed win price:

\[\hat{p}_i = \hat{F}(t_i) - \hat{F}(t_i^-)\]

From our table: mass $0.125$ at \$2, $0.125$ at \$3, $0.375$ at \$5. The expected cost per win at bid $b$ weights the event prices by these masses:

\[\mathbb{E}[P \mid P \le b] = \frac{\sum_{t_i \le b} t_i \, \hat{p}_i}{\hat{F}(b)}\]

At $b = 5$:

\[\mathbb{E}[P \mid P \le 5] = \frac{2(0.125) + 3(0.125) + 5(0.375)}{0.625} = \frac{2.5}{0.625} = \$4.00\]

The trap: averaging the observed win prices directly - $\{2, 3, 5, 5\}$, giving \$3.75 - is wrong for the same reason the naive win rate was wrong. It weights by the won sample, in which the \$5 wins are underrepresented (the losses at \$3 and \$4 thinned the pool exactly there). The KM masses undo that distortion, and the corrected cost is higher. Combine win-rate × cost-per-win × volume and we have $\text{spend}(b)$, which is what a budget-pacing loop needs.

Why this beats the naive estimate

The naive “wins/total = 4/8 = 50% at any bid” answer is visibly wrong in the figure: it understates the win rate at \$5 and overstates it at \$3. KM fixes this precisely through the risk set. The loss at bid \$3 (auction 3) and the loss at bid \$4 (auction 8) leave the pool below \$5, so they do not enter the risk set at the \$5 event. Each point on the curve uses only the auctions that are genuinely informative at that bid - which is why $\hat{W}(5)=1-\hat{S}(5)=0.625$ rather than a muddied 50%.

One honesty note before moving on: 62.5% from eight auctions is mechanics, not measurement. KM comes with standard uncertainty estimates (Greenwood’s formula), and at $n = 8$ the band is embarrassingly wide - not a figure of speech. Greenwood gives a standard error of about $0.20$ on $\hat{S}(5)$, so the lifelines fit below reports a 95% confidence interval on $\hat{W}(5)=0.625$ of roughly $[0.28,\ 0.94]$: the point estimate is almost uninformative on its own. And because the expected-cost figure is a mass-weighted sum of the same jumps, that ₹4.00 inherits the identical uncertainty. The toy exists to show the machinery. In production, landscape numbers should ship with these intervals, minimum-volume thresholds, or shrinkage toward a broader parent segment before anyone bids real money on them - and the point estimate should never be read without the risk-set size ($n=4$ at the \$5 rung here) that generated it.

The same computation in code

The entire worked example is a few lines with any survival library (lifelines here). The only modeling decision is the encoding from the schema above: duration = price if won, bid if lost; the event flag = won.

import numpy as np
import pandas as pd
from lifelines import KaplanMeierFitter

# The eight auctions from the worked example
auctions = pd.DataFrame({
    "bid":   [5, 4, 3, 4, 6, 6, 5, 7],
    "won":   [True, True, False, False, True, True, False, False],
    "price": [2, 3, np.nan, np.nan, 5, 5, np.nan, np.nan],  # seen only on wins
})

duration = np.where(auctions["won"], auctions["price"], auctions["bid"])
event = auctions["won"].astype(int)          # 1 = event (win), 0 = censored

kmf = KaplanMeierFitter()
kmf.fit(duration, event_observed=event)

win_curve = 1 - kmf.survival_function_["KM_estimate"]    # W_hat(b) = 1 - S_hat(b)

# CDF jumps are probability masses -> expected cost per win at bid b
masses = win_curve.diff().fillna(win_curve)
def expected_cost_per_win(b):
    m = masses[masses.index <= b]
    return (m.index * m).sum() / win_curve[win_curve.index <= b].max()

Running it reproduces the table exactly: $\hat{W}(5) = 0.625$ and expected cost per win at \$5 = \$4.00. In production the same ten lines run per segment (stratified by the context columns), not once globally - for reasons Part 2’s caveats make concrete.

7. Recap and What Comes Next

Treat each auction as a survival “subject” whose event is the clearing price. A win reveals that price exactly (an event); a loss reveals only that the price exceeded our bid (right-censored at the bid - no lost price needed). Kaplan-Meier multiplies, at each observed win-price, the conditional chance of “not yet winning” - $(n_i - d_i)/n_i$ - using a risk set that censored losses quietly shrink. The result is $S(b)$, and $W(b) = 1 - S(b)$ is the bid landscape: the win probability at any bid, learned from every auction, won or lost.

The medical statisticians who built this machinery in 1958 were trying not to lie about patients who left the study early. That same discipline - refusing to invent data we didn’t observe, while refusing to throw away the partial information we did - is exactly what turns a pile of won and lost auctions into an honest win curve.

We now have the curve. Part 2: From Win Curve to Bidding, Pacing, and Its Limits spends it: how the landscape sets a bid under second-price and first-price mechanisms, how a budget shades that bid, how it forecasts a new policy offline - and the five ways it quietly lies if we read it past its evidence.

References

• Kaplan, E. L. & Meier, P. (1958). Nonparametric Estimation from Incomplete Observations. JASA.