Introduction Anytime you have an auction, you have the potential for the winner’s curse, a simple, yet surprising, statistical phenomenon. Despite its simplicity, the effect can have significant financial implications for anyone participating in auctions. We care about the winner’s curse at NextRoll because we participate in about 100,000 ad auctions per second. In this […]

Anytime you have an auction, you have the potential for the

winner’s curse,

a simple, yet surprising, statistical phenomenon. Despite its

simplicity, the effect can have significant financial implications

for anyone participating in auctions.

We care about the winner’s curse at NextRoll because we

participate in about 100,000 ad auctions per second. In this

post, we explain the curse and explore the way it manifests

itself in our ad-buying systems.

Let’s pretend Alice is auctioning off a jar containing exactly

$25 of spare change she has collected. N of Alice’s friends

participate in the auction, hoping to purchase Alice’s jar of

change. No one can open the jar before the auction, but each of

Alice’s friends can inspect the jar to estimate the total worth

of the coins contained within. After completing their valuations,

each of Alice’s friends submit a bid.

Alice’s friends assume one of them can make a few dollars here.

However, it may be the case that one of them overestimates the

value of the coins in the jar. As a result, that person may bid

too much into Alice’s auction. If this happens, that person may,

depending on the auction dynamics and the other bids, end up

paying Alice more for the jar than the value of the coins

contained within.

It turns out that the winner of Alice’s auction will end up

overpaying for the jar of change much more frequently than we

would naively expect; this is the winner’s curse. To see how

this works, let’s denote Alice’s ith friend’s valuation as

follows:

%<![CDATA[

begin{equation}

V_i = 25 + epsilon_i

end{equation}

%]]>

where epsilon_i is the error each friend makes in their

valuation. The highest valuation of the jar of coins among

Alice’s N friends will be:

%<![CDATA[

begin{equation}

max(V_1, … ,V_N) = 25 + max(epsilon_1, … , epsilon_N)

end{equation}

%]]>

This highest valuation is very likely to be larger than $25. To

see why, let’s assume Alice’s friends are equally likely to

overestimate the value of the coins as they are to underestimate

it. In this case, for the highest valuation to be less than $25,

all N of Alice’s friend’s bids have to underestimate the value

of the jar of coins. This happens only frac{1}{2^N} of the

time.

This discussion of the highest valuation is important because,

typically, the person with the highest valuation will win the

auction. Let’s call this person with the highest valuation, whom

we expect to win the auction, Bob. If Bob wins the jar of change

and tallies up the money, he is probably in for a nasty surprise.

Almost every time, the jar will have less money than he anticipated

it having. Many times, this effect is so pronounced that not only

will Bob have not made as much profit as he had anticipated, he

will have lost money! Just like that, Bob has fallen victim to

the curse!

To further illustrate this effect, we can make some concrete

assumptions and run a simulation. Let’s pretend the error each

of Alice’s friends make when estimating the jar of coins’ value

is distributed normally with a mean of $0 and a standard

deviation of $3. That is, epsilon_i sim mathcal{N}(0, 3^2).

Let’s pretend Alice is running a second-price auction, in which

the bidders naively assume bidding their noisy valuation is

optimal. Below we see what happens with 4, 7, and 10 of Alice’s

friends bidding into her auction.

In this simulation, Bob usually paid more for the jar of coins

than it is worth. This happened almost every time with just ten

of Alice’s friends participating in the auction. Also notice,

the more participants the auction has, the worse the winner’s

curse becomes.

This shows that when you’ve estimated the value of an item in an

auction, you should reduce your bid, not just to account for

auction dynamics, but also to account for uncertainty in your

valuation. In particular, despite conventional wisdom saying to

bid your true valuation in a second-price auction, you should

actually reduce your bid a bit in most real-world situations.

Now that we understand the winner’s curse, we can see what it

looks like in some real data. There are two places we observe

the winner’s curse at NextRoll. When an ad exchange notifies

us of an ad opportunity, we have to select an ad for which to

bid. This is done via an internal auction and is the first place

this effect manifests. Next, we submit the highest internal bid

to the ad exchange, and an auction is run amongst bidders like

NextRoll. This external auction is the second place we observe

the winner’s curse.

To be clear, I highlight these instances of the winner’s curse

because the effect is interesting, not because these cases are

particularly problematic. Unlike in the example of Bob losing

money by purchasing Alice’s jar of coins, the impact of the

winner’s curse on NextRoll’s bidding systems is minor overall.

The internal auction is where we decide which ad from our

thousands of advertisers will be submitted to the external

auction. Some of this decision is made for us by simply applying

the advertiser’s targeting criteria. Selecting among the remaining

advertisers’ eligible ads is done with an auction that has two steps.

First, we select the most valuable eligible ad for each advertiser.

As you can see below, the more ads from which we have to select for

a given advertiser, the more overvalued the selected ad is. This is

analogous to the winner of Alice’s auction paying more for the jar

of coins when there are more bidders. This is the winner’s curse in

action!

The second step in the internal auction is to choose the most

valuable ad amongst each advertisers’ best candidates. As in the

case above, the more advertisers targeting the opportunity, the

more overvalued the selected ad is. Again, this is the winner’s

curse.

Once we have decided which ad to select and what to bid for it, we

send that information to the ad exchange. The exchange runs another

auction, and based on the results, makes the final decision on which

ad to show. Unlike in our internal auction, we are not the

auctioneer in the external auction, which means we don’t have

complete information about the auction’s bids. This makes confidently

observing the winner’s curse more challenging.

The first sign of the winner’s curse in the external auction is that

we consistently predict ad impressions to be slightly more valuable

than they turn out to be. To have confidence that these

overvaluations really are the winner’s curse, rather than an

undiscovered bug, we will need to understand a bit about the

interaction between our machine learning and the external auction.

The key thing to understand is that the valuations predicted by our

machine learning system are very closely related to when we win the

external auction. In particular, when our models overvalue a

potential impression, we tend to bid higher, which causes us to win

the auction more often. In other words, we win a disproportionate

amount of the bids whose value we overestimate. This selection bias

is visualized below.

Fortunately, when we win the external auction and show an ad, we

receive feedback on the ad’s correct value. This, in turn, feeds

into our machine learning models as training data. As a result,

mistakes made by previous iterations of the model are corrected.

Unfortunately, no model is perfect, and our newer model iteration

will make new mistakes.

The crucial insight for our investigation is that by comparing the

predictions (and mistakes) made by older and newer model iterations

over the same slice of backtesting data, we can learn whether the

overvaluations we observe are, in fact, caused by the winner’s

curse, or more menacingly, an undiscovered bug.

To make this concrete, let’s say that we trained model A ten days

ago, and that we trained model B yesterday. Consider what we would

expect to happen if we used both models A and B to predict over

yesterday’s ad impression data that model B bid on and purchased.

If the winner’s curse were the cause of the overvaluations in the

external auction, we’d expect model B to overvalue these impressions

that it purchased because of the selection bias discussed above.

We’d also expect model A to value these impressions accurately.

This is because this selection bias affecting model B does not

apply to model A, since it was not used to bid on and purchase

these impressions.

The plot above shows this experiment run over real data on 11

different days. As you can see, model A does not overvalue the ad

impressions purchased by model B. This means we really are

observing the winner’s curse in the external auction!

You’re more likely to win an auction when you bid too high. That is

the essence of the winner’s curse, a surprisingly simple, yet

counter-intuitive, statistical effect. In this post, we learned how

the curse works in theory, and we observed it in some real data.

Often, those of us interested in auctions ignore the fact that

bidders estimate the value of an item, assuming instead that they

know it exactly. However, bidders having uncertain valuations is all

that’s needed for the winner’s curse to appear. When the curse strikes,

buyers realize less profit than expected from the auctions in which

they participate. In extreme cases, this effect can even result in

the buyer losing money, as we saw with Bob and Alice. Beware of the

curse!

Source: AdRoll