Challenges in the Design of Sponsored Search Auctions

MALE SPEAKER: We have Nicole Immortica, the speaker, today.
Nicole got her PhD at MIT a little under two years ago.
NICOLE IMMORTICA: 2005, yeah.
MALE SPEAKER: Although I've never seen the diploma, so
it's only hearsay anyway.
I actually had the pleasure of meeting Nicole at
a workshop in Italy.
That was a nice place to have a workshop, I must say.
So she's going to speak to us today
about her view of AdWords.
NICOLE IMMORTICA: There's not just AdWords, you know.
There's also AdCenter.
MALE SPEAKER: Lock and load.
NICOLE IMMORTICA: So I'm going to be talking about the
challenges in the design of sponsored search auctions.
So in 1994 we saw the first online advertising in banner
ads for Zima and AT&T, and they appeared on hotwire.com.
They were sold in pay per impression system.
And they were quite successful in bringing the idea of
monetization into online services.
In '96 we also started to see some affiliate marketing.
These are the ads for Amazon and CD Now and sites like
that, where they post ads for a particular product on a host
web page, and then when somebody buys this product
Amazon or CD Now pays some percentage back to
the host web page.
And then finally in '98 goto.com developed the first
pay per click advertising systems. And these are ads for
text based ads on search web pages.
And they were adopted by Google in 2002, with some
slight differences in the selling mechanism.
So in these systems advertisers pay only when the
user clicks on their ad.
It's some kind of pay for performance model, and it's a
middle ground between the pay per impression and pay per
acquisition schemes that we had seen
previously in the industry.
And one nice thing about these pay for performance models, of
which pay per click and pay per acquisition are one kind
of them, is that it provides incentives for the host to
improve the ad displays, because the host only gets
paid when the ad is successful in some sense.
As opposed to banner ads, where users start suffering
from banner blindness, as it's called, the host doesn't
really care because they're still getting paid.
So the other innovation in this scheme was that the
advertisements were sold through an auction mechanism
where advertisers are bidding on key words.
And this had two huge advantages.
One is that it allowed for increased targeting
opportunities, because you could specify what sorts of
key words you wanted your ad to appear on.
But another big benefit here was that it really made a low
barrier to entry for a lot of the mom and pop shops that
were on the internet.
So you have all of these very small businesses, they can't
afford to negotiate contracts for banner advertising with
the host web pages, and so the auction mechanism was quite
easy for them to use and they could start to have
online ads as well.
So I want to talk about this market design of the pay per
click advertising.
And in order to do that I want to introduce to you what I
assume is a general framework for what the three major
players in this market are using these days, being
Google, Yahoo, and MSN.
So we have a web page, let's focus now on search.
And so whenever somebody searches for a key word we get
some algorithmic search results, which appear
underneath the key word.
And on the right hand side, or sometimes above the
algorithmic search results, we get some ad slots.
And it's these ad slots that are sold
through the auction mechanism.
I'm going to describe the rules of auction as I'm going
to assume them to be for the rest of this talk through the
rest of an example.
I have here two add slots and three advertisers.
And they say that these three advertisers are interested in
being shown along with his key word.
And each advertiser submits to the search engine the amount
that they're willing to pay for a click that they receive
after a user searches for this key word.
So in my example advertiser A has $10 value per click, B has
$5.00 value per click, and C has $50.00 per click.
Additionally, each advertiser has an associated click
through rate, it's some parameter that the search
engine learns over time.
And I think, these days, people are starting to call
these quality scores.
But basically the click through rate is some estimate
of the probability, at least the way I'm going to think of
it, is it's an estimate of the probability that this user
will click on that ad.
And then the search engine takes the bid times the click
through rate of each advertiser.
Now this can be interpreted as the expected bid per
impression, it's how much it's worth to the advertiser to be
shown on the search page.
And it then allocates the ad space in decreasing order of
this expected bid per impression.
So here, advertiser B, who actually had the lowest bid
per click, anyway, has the highest expected bid per
impression and is shown in the first ad slot.
Advertiser A is shown in the second ad slot, and advertiser
C is not shown because I'm assuming that I had just two
ad slots in this search engine page.
So now this is the allocation scheme.
I also need to, in order to specify the mechanism, I need
to define the pricing scheme.
So what this search engine does is some sort of, quote
unquote, "second price auction. " What
do I mean by that?
I mean that when they receive a click, I'm going to charge
each advertiser the minimum amount that he would have had
to bid to maintain his position in the ranking.
So here, for example, when I have a click, let's see how
much I'm going to charge advertiser B when
he's clicked on.
His closest competitor in the ranking is advertiser A, who
has a bid times click through rate of one.
And advertiser B's own click through rate was 0.5, so by
taking the ratio of these two numbers I see that so long as
B bid at least $2.00 he would have maintained his position
in the ranking.
And therefore I charge him $2.00 per click.
I can similarly calculate the per click price of advertiser
A, it will be $5.00.
And advertiser C is not shown, never clicked on, and never
charged for this search, at least.
So this is the general framework I'm going to explore
in this talk.
And there are many challenges that are introduced by this
market design.
For one, we need to think about what is the right
bidding language for these advertisers?
So currently we're asking advertisers how much you value
each click, and what's your maximum budget?
Are these the questions that we should be asking?
Should we allow the advertiser to have more expressivity?
I learned earlier today that in Google we are now allowing
advertisers to bid on which slot they want
on the search page.
So that's an example of making the bidding language more
expressive, and it might enable the advertisers to more
accurately reflect their true utilities.
But it also might introduce complications in the auction
scheme and reduce the transparency of the auction.
So it takes a lot of thought to figure out what is the
right bidding language.
Another interesting question is what is the
right product to sell?
So here in the market, as I've described it,
we're selling clicks.
That's our product.
So why should we sell clicks?
We we had seen before people were selling impressions and
people had been selling acquisitions.
Should we be selling impressions or acquisitions or
some combination of clicks, impressions, and acquisitions?
So this is another thing we need to be thinking about.
Then we have to think about we can compensate the eyeballs.
So far in this market we've been thinking about this as a
market for advertisers.
And the players in this market are the advertisers and the
host websites, the search engines, for example.
But there's a third player in this market that's actually
extremely important to the success of the market, and
that's the eyeballs of the searchers.
And this is essentially what we're selling.
We're kind of, if you like to think of it this way,
exploiting the users and making money for us by showing
them these ads.
And it's not exactly exploitation, because we're
giving them the product, free web services, as a
compensation.
But is this really the right compensation?
Should we perhaps, additionally, give them some
monetary compensation?

Finally, there's--

MALE SPEAKER: That was the whole point of keyword based
advertising, was that there are some assumption that the
user's actually interested in that ad.
NICOLE IMMORTICA: Yeah, we can make the user more interested
in that ad if we give him some discount on the product that
he might buy by following through with the link.
Imagine, for example, if you click on this ad we're going
to give you some coupon for the product that the
advertiser sells.
This will incentivize the advertisers to produce more
relevant ads.

Another thing that I want to think about is how can we use
stochastic information in the allocation?
So the auction framework that I presented is that every time
a key word comes I run this auction.
And this auction is run blind to the fact that future
auctions will be run for the same keyword, or that past
auctions had been run for the same keyword.
And, in fact, search engines have a very good idea of how
many searches there are for any particular key word in any
given day from historical data.
And shouldn't we be using this information in a more direct
way when we figure out how to run the auction for each
particular word?
In fact, why we are running these auctions per word?
Why don't we run them at the beginning of the day and sell
all the supply we have in an offline setting?
And we all know that offline algorithms are much more
efficient than online algorithms.
So understanding how to use stochastic information in the
allocation is also related to the idea that we can try to
introduce mechanisms that guarantee the supply for the
advertisers so we can sell an advertiser 100 clicks, and we
can guarantee that he'll get 100 clicks.
And if we under allocate to him the number of clicks we
promised we can try to reimburse him.
And this, more directly, mimics the systems in place
for banner advertising.
And it also could be attractive to advertisers as a
way of eliminating risk.
So I'm not sure that this is the right direction to go, per
say, but it's an interesting thing to think about.

So these are all just vague idea that I've had about this
market design, and many other people have had about this
market design.
The things I want to talk about in more detail today are
the issue of click fraud and the complications that arise
from the fact that advertisers have budget constraints.
So let me start with click fraud.
What do I mean by click fraud?
That's the act of clicking on an ad with the sole intent of
increasing or decreasing the spending of an advertiser.
And it's been in the media a lot, and is clearly a serious
problem with these pay per click systems.
Why is it a problem with pay per click systems?
An advertiser's charged only when a user clicks his ad.
And so a fraudulent user may click on ads just to increase
the spending of an advertisers.
And since each click costs on the order of $1.00, of course
this figure varies a lot across key words, but $1.00 is
a typical cost. This means that 1 million fraudulent
clicks are going to cost the advertiser $1 million.
And it's very easy to generate 1 million fraudulent clicks.
You can write a simple script.
I'm sure anyone in this room could go home over the weekend
and write a simple script to go out and click on ads.
You don't have to be smart to do this, as evidenced by the
second bullet here.
A California man wrote some simple script to click on ads
and told Google that they should show up in his garage
and pay him $1 million or he was going
to release the script.
And so at the appointed time the FBI showed up in his
garage and arrested him.

It's also true that scripting is not the only way to
generate click fraud.
It's becoming increasingly common to see companies hiring
people in second and third world countries, typically
India and Eastern Europe, to just sit at home
and click on ads.
And this is a great source of income for them, since the ads
cost the advertisers about $1.00.
These people, when I was doing this literature search, they
were being paid about $0.20 per click to go click on an
ad, spend 90 seconds on the target web site looking around
at the product that the advertiser was selling, and
they were happy to do this.
They could sit at home, do this with their
kids on their lap.

There's a lot of click fraud that's being generated.
How can we hope to combat this fraud?
Currently one main technique for doing this, at least we
assume, so in the academic literature, is
through machine learning.
So we automatically try to detect and discount frauds.
And this could be double checked by humans, and so on.
These techniques are somewhat successful, but they have
possibly high classification error.
And they're also quite susceptible to the India model
attack, because it's rather difficult to distinguish
between a human committing fraud and a human that's
really shopping online.
It's possible, but they look pretty similar.

Another proposal for reducing click fraud that's been talked
about a lot in the literature is to change the market model.
This is really an issue with the fact that
we're selling clicks.
So why are we selling clicks?
Why don't we sell per impression?
Maybe we can still keep some of the benefits of the per
click models on selling per impression if we, say, do it
along with an auction.
Also we could sell on, Goodman proposed in the Sponsored
Search Workshop in 2005, selling per percentage.
So you can buy 100% of the key words for blah, as [INAUDIBLE]
should show your ad.
Or say 50% of the key words your ad will be shown.
So while these models do reduce the possibility of
fraud, they are a departure from a developed industry
standard and are likely to be met with resistance by the
advertisers.
And they also lose some of the benefits of the developed
industry standard.
So in a recent paper what we did was we tried to come up
with a way to reduce click fraud by changing the way that
the auction is run behind the scenes.
And the reason that we had some hope of doing this is the
following observation, that each fraudulent click incurs a
short term loss, which is due to the cost of the click.
But it also gives you a long term benefit, because it
increases the search engine's estimate of
click through rate.
And the price of future clicks is inversely proportional to
the click through rate.
So what we do is we propose a class of CTR learning
algorithms in which these effects cancel, and thereby
click fraud is reduced to impression fraud.
You can't cost an advertiser more than you could cost him
by creating false impressions in an impression based system.
So in order to explain this work in more detail, let me
first define what I mean by a CTR learning algorithm.
There's many ways you could imagine estimating the
probability that an ad receives a click.
You can look in the history, the last 100 hours.
Count the number of times that you showed this ad and count
the number of times that you showed this ad and it got a
click, and take the ratio of these two numbers.
You could look at the last 100 impressions, and look at the
number of times that this ad received a click.
Divide that by 100.
You could look at the last 100 clicks.
Count how many impressions did it take for the ads to receive
these one hundred clicks and take 100 over that number.
So these are just three examples of learning
algorithms. You can come up with many more
yourself, I'm sure.

In order to define a general class of which these three
learning algorithms are examples, let me introduce
some notation.
I'm going to label the impressions, starting with the
most recent, by one, two, up to n.
And I'm going to let ti be the amount of time that elapsed
after impression i.
ci is the number of clicks that were received after
impression i.
And xi is an indicator variable that the i's
impression got a click.
So then, I will say, an algorithm is a CTR learning
algorithm if it's parametrized by some discounting function,
delta, which is a function of these three parameters, the
time since the i's last impression, the number of
clicks since the i's last impression, and i.
And the CTR learning algorithm is simply the weighted average
over the impressions of the number of clicks.
So in this formula here, you see that I can use it to
express all the three learning algorithms I proposed in the
previous slide.
The averaging over a fixed time window, you just simply
set this discounting function to be zero after the time, ti,
is larger than your time window, t.
And you can check that the other two algorithms can be
represented with this kind of formula.
So the first observation is that for appropriate
parameters all three of these algorithms estimate the true
click through rate to within an arbitrary accuracy on a
random sequence of clicks generated from a constant CTR.
So if we have a scenario without fraud, let's assume
that the true click through rate, the true probability
that an ad receives a click, is constant.
If I have a long enough sequence of random experiments
in which I'm showing this ad, and this probability of
receiving a click is constant, all three of these algorithms
are going to be able to estimate this true
probability.

And when that happens the system behaves exactly like a
pay per impression system, which is what we want.
So this brings up the question, does that mean that
all of these algorithms are equally resistant to fraud?
And in order to answer that question I first have to tell
you what I mean by fraud.
When do I say an algorithm is fraud resistant?
I say an algorithm is fraud resistant if a scammer cannot
significantly increase the average price per impression
of an advertiser in a scenario with fraud as compared to a
scenario without fraud.
This is intuitively what I mean.
For the exact parameters of what significantly is, and
things like this, you can look at the paper.
Basically, what I'm going to assume in the rest of this
talk is that I have just one slot with a reserve price, p.

And I am not considering the kind of fraud that causes an
advertiser to fall off this slot.
I have just one advertiser, it's always going to be shown
in the slot.
Can I generate a sequence of clicks on this advertiser to
increase his price per impression beyond p?

The answer is that no, not all algorithms are equally
resistant to fraud.
And in order to see, this is just going to be a sketch of
an idea of how to scam the following algorithm that
averages over the last 10 impressions.
When there's no fraud we convert each of these
impressions to a click, represented by a green line,
with some constant probability.
And the estimated CTR, according to this algorithm,
is going to be constant.
But a scammer can come along and insert a bunch of fraud,
uniformly, at random, represented by red lines here.
And in bursts he's going to convert parts of this fraud to
clicks and parts of it he's not going to do the click.
And this bursty behavior is going to cause the estimate of
the CTR to vary over time.
If he used his basic intuition, and through the
math you'll see that this is going to cause the advertiser
to actually spend more money per impression than he did in
the scenario without fraud.
This is for that particular algorithm that was averaging
over the last 10 impressions.
I'm going to say that an algorithm is click based if
this discounting function, delta, depends only on the
number of clicks after impression i, that variable I
was calling c sub i.
And what we prove in the paper, in line 2005, is that
click based algorithms are fraud resistant.

So the proof is by a charging argument.
And I think I'll skip the proof, and we can come back to
it if we have time at the end of the talk and you're
interested in actually seeing that math details.

One last thing I wanted to say about the quick fraud work is
that it gives you a way to try to implement a pay per
acquisition system in a manner that incentive advertisers to
truthfully report their acquisitions.
We can define an acquisition rate of an advertiser--

MALE SPEAKER: In the statement of the results that the thing
is fraud resistant, does it say that the advertiser
doesn't have to pay more on episodes where there were not
large amounts clicks, due to the effect of clicks on the
essence of the click through rate?
Or does it also include the costs of the
actual fraudulent clicks?
Do you see what I mean?
There are two possible sources in that.

NICOLE IMMORTICA: The thing is that you don't pay more per
impression in a scenario with fraud that without fraud, but
in the scenarios with fraud there are more impressions.

So you're going to pay more because of this factor.
But that's exactly what I mean by saying that it's reducing
click fraud to impression fraud.
You're not going to be able to cause the advertiser more
expenditure than if you had been selling per impression,
and the guy was creating impression fraud.
Does that make sense?

So we can use these techniques to develop a pay per
acquisition system where advertisers have an
acquisition rate, we rank advertisers in order of their
acquisition rate times their bid per acquisition.
And we learn the acquisition rate using acquisition based
ATR learning algorithm.
So exactly everything I've just said now about clicks you
can say about acquisitions.

So if there are no more questions about the click
based work I'll move on to the budgets work.
You still seem suspicious.
MALE SPEAKER: I'm afraid I may not understand the impression
fraud idea after all.
So do you count the impression?
Is it anytime there was an opportunity to click on an ad?
NICOLE IMMORTICA: So by impression I mean the
appearance of an ad.
And it can be both an impression and the click if
the impression converted to a click.
MALE SPEAKER: So why are there more
impressions when there's--
NICOLE IMMORTICA: I'm looking at one scenario.
I have one history which was generated according to this
random process, where ads are clicked on with some fixed
probability, and then I'm allowing a scammer to come
along and insert extra impressions which he can then
either click on or not click on.
So this is going to create extra impressions.
You saw this in this example here.
MALE SPEAKER: [INAUDIBLE]
that impressions would be cheaper than clicks?
Is that right?
NICOLE IMMORTICA: So I'm thinking that the click
through rates are on the order of 1%, and the cost per click
is on the order of $1.00.
So impressions cost $0.01.
So you can't, for example, pay someone $0.20 to create false
impressions.
That's one reason that it's--
MALE SPEAKER: Something that was confusing me a little bit
is I'm imagining I'm a scammer that creates a 1% increase in
the number of impressions, which would result in 1%
increase in the cost if you were paying per impression,
but clicks on all of them, and so that would double the
number of clicks, right?

NICOLE IMMORTICA: But if he clicks on all of them the cost
per click is going to become very cheap for the advertiser,
because the estimate of the click through
rate is going to skyrocket.
We're capitalizing on this.

If you learn the click through rate appropriately you're
going to track the fluctuations at exactly the
right rate in order to discount the fraud.
So let me move on to the bidding with budget
constraints work.
So let's talk about budget constraints.
Advertisers have a utility, vi, per click, and per click
per key word.
Let's just focus on one key word for this definition.
So they have a utility of vi per click, and they have a
hard budget constraint, bi, on the amount they can
spend in one day.
And what does this really mean in terms of the utility of
advertiser?
The happiness of advertiser for his allocation in price?
What I'm assuming it means is that if the advertiser
receives j clicks and his price is p, his utility is
going to be j times his value per click, minus p, so long as
this price, p, is less than his budget constraint.
But if the price, p, exceeds his budget constraint, his
utility is going to be minus infinity.
And, of course, I can generalize this to multiple
key word setting.

MALE SPEAKER: What is i there?
NICOLE IMMORTICA: i is the advertiser.

So how can I design an auction setting for bidders with
budget constraints?
A very standard technique in auction theory for designing a
truthful auction is called the VCG mechanism.
This mechanism chooses the allocation, which maximizes
the social welfare.
The social welfare is simply the total value that all the
bidders have for the allocation.
So in this case, if you want to maximize the total value of
all bidders for the allocation you should simply give all
clicks to the bidder with the maximum value.
This would be the welfare maximizing solution.
But by individual rationality, we can charge each bidder, at
most, his budget constraint.
Otherwise he's going to walk away from our auction with
infinite negative utility.
And this means that the VCG auction, in this
case, is not truthful.
Because if this was your auction, give all the units to
the person with the highest value and charge them, at
most, their budget constraint.
You, of course, would come in and you would say your value
is infinite and your budget is zero.
And you're going to get all the clicks.
This is not very surprising, because VCG is truthful
precisely when the utility functions are quasi linear,
which means that they're linear
in this price parameter.
And you'll notice that this utility function is not linear
in this price parameter, because when the price just
exceed b the utility jumps to minus infinity.
So we could try to circumvent this problem.
A natural way to do that would be to cap the welfare of a
bidder to be his budget constraint.
So if your value is infinity but your budget is zero, I'm
not going to allow you to have more than a zero welfare for
that allocation.
And again, this modified algorithm, modified VCG I call
it, is not truthful, even if the
budgets are public knowledge.

So let's go through the example.
Here I have two bidders.
Bidder one has a value of $10 for each of these objects, but
has a budget constraint of $10.
And bidder two has a value of $1.00 for each of these
objects and a budget constraint of $10.
Now, according to this modified definition of
welfare, the welfare maximizing solution is to give
one unit to bidder one and one unit to bidder two.
This gives you a total welfare of $11.
The sum of the evaluations of the bidders for this
allocation is $11.
I haven't told you how VCG computes the prices, but if
you were to compute the prices you would see that the payment
of bidder one is $1.00 and bidder two is $0.00.
And thus the utility of bidder one in the scenario is $9.00.
Now, if we change this set up and bidder one lies about his
value and says his value is actually $5.00 instead of $10,
now the welfare maximizing solution will give both units
to bidder one for a total welfare of $10.
And again, you can calculate the payments and see that the
payment would be $2.00, and thus his utility is $18, which
is more than it was in the previous setting.
So he has an incentive to lie here.
And this begs the question if there's any truthful mechanism
for bidders with budget constraints.
Maybe this was just the wrong mechanism.
In fact, we can show that there is no truthful mechanism
which satisfies three properties.
You can argue about how reasonable they are, but there
are things that you might want to assume about a mechanism.
I don't want to go into detail about what they mean here.

So this is a pretty strong negative result.
We can also give an accompanying positive result,
which is truthful auction which maximizes the revenue by
breaking some of those natural assumption.
Let me tell you what the mechanism is.
It splits the bidders randomly into two groups, A and B. And
it computes the optimal price, pa, of selling, at most, half
the units to the bidders in A. And it, again, similarly
computes price, pb, which sells, at most, half the units
to bidders in B.
So what do I mean by optimal price?
I mean if you were going to sell all these units at a
fixed price, what price would you set in order to maximize
your revenue?

I have to find these two prices, pa and pb.
And I'm going to sell my units at a price of pa to the
bidders in b and at a price of pb to the bidders in a.
So you can't affect the price that you're offered by
changing your bid.
And furthermore I'm going to sell these units in an
arbitrary order to bidders.
So I'm going to offer, say Kevin, here's the price.
How many units do you want?
And I'm just going to go around the room in order and
sell the units, however many units each person wants at
this fixed price, until the units are all gone.
So you can't affect how many units you'll be offered by
your bid, either.
Therefore the mechanism is truthful.
Why is it not satisfactory?
First let me state the result.
The mechanism is truthful and it generates close to the
optimal posted price revenue.
So if you were going to sell all m units to all the bidders
and you knew all their valuations and you didn't have
to worry about truthfulness, how much money could you make
at a fixed price?
That's what I call opt.
And this mechanism gets close to that opt, so long as the
maximum budget of any particular bidder is small.

What is not satisfactory about this mechanism is that you
can't guarantee any allocation, even, by
increasing your bid.
It could be that you're last in the lineup and everybody
else, by their fixed bids, are winning particular amounts,
such that by the time the auction gets to you there are
no units left over.
And even if you're bidding infinity you're not going to
win anything.
And this is violating the first of those assumptions I
set in last slides, consumer sovereignty.
It also violates some other things, but this is one very
negative property of this algorithm.
So this is a very common technique in auction design,
random sampling it's called.
Another frustrating thing about these algorithms is they
usually are dual priced.
They offer one price to half the people and another price
to the other half of the people.
And psychologically that pisses off people in the half
that's getting the bigger price.
MALE SPEAKER: What does small mean, the last small p in
there, where the [INAUDIBLE] budget over the optimal
revenue is small?
NICOLE IMMORTICA: This is going to be some parameter
epsilon in the probability that the mechanism generates
this revenue.
MALE SPEAKER: And the relationship to delta?
NICOLE IMMORTICA: I don't remember the exact
relationship.

MALE SPEAKER: So for example, if you have a market in which
there are only two suppliers then is it survival
assumption?
NICOLE IMMORTICA: Two suppliers?
No, this is an assumption about the bidders' budgets.
So the question is, is it reasonable to assume that I'm
not giving you all your revenue?
If you have just one company, say eBay, that's contributing
half the revenue of AdWords, that's a
problem for this mechanism.
But if all of your players in the market are pretty small,
no single person has too much power, this theorem is going
to go through.
And the reason that you need something like this is because
if I have a very high value and a very high budget
compared to everybody else the optimal posted price mechanism
is going to be able to extract all of my budget because it
knows I can't lie to it.
The optimal posted price would be to charge me my value and
get all of my budget.
But truthfully you can't hope to do that.
Because clearly I could always pretend to be much
smaller than I am.
So you need something like this.
And all of these random sampling auctions have some
assumption that has this kind of flavor.

I think that's a reasonable assumption.
I don't think that's why it's not used in practice.
MALE SPEAKER: But for some markets it could be there's
just very few people who are actually interested in
purchasing that.
And the budget for a given advertiser may actually be
fairly close to what the total revenue
derivable from that is.
In which case that assumption wouldn't be valid anymore.
NICOLE IMMORTICA: Yes, that's true.
You need to use these in markets where there's a lot of
demand and fixed supply.

Those previous sites demonstrated that there's a
lot of complication in actually designing the auction
when bidders have budget constraints.
There's a lot of things we need to take into
consideration.
Also, budget constraints impose some complications on
the bidders, on how they should bid.
And to see this, let's think about the system that I
presented at the beginning of the talk, how bidders with
budgets should behave in these AdWords style systems.
So I have two key words.
One is popular, in that there are a lot of searches for it
every day, and another is not so popular.
There are some searches but not too many.
And for the popular key word there's a lot of advertisers
with unlimited budgets and utility of $1.00 that are
interested in that key word.
I also have another advertiser, the yellow dot
here, which is interested in both the popular and the not
so popular key word.
And has a budget constraint of $500 and a utility of $2.00
for either of these key words.
Now, when I just have everybody bid truthfully in
the system what's going to happen?
Well, every time the popular key word is shown, the budget
constrained advertiser is going to win the auction.
Let's assume the click through rates are all equal.
The budget constraint advertiser is going to win the
auction because he has a higher utility than the
unlimited budget advertisers.
And so he's going to win the auction and he's going to pay
$1.00 every time and he's going to quickly run through
his budget.
This makes him unhappy.
On the other hand, if he were to pretend that he is not
interested in the popular key word he's going to win the not
so popular keyword and there's no competitors
for that key word.
So he's going to just pay the reserve price and he's going
to exist throughout the whole day.
He's going to be much happier and, actually, so would the
search engine in this case.
Because we're still making revenue on the popular key
word as well as the unpopular key word.

So how should an advertiser bid for the key words when
he's given his budget constraint?
What what should you do?
This is a discreet several resource allocation problem
which is well studied in the OR literature.
The resource here being the budget of the advertiser.
And if we know the price of each slot for each page, then
this problem becomes a generalization of Knapsack.
So if I know the price of every slot for every key word
then what I'm trying to do is I'm trying to choose, at most,
one instantiation of each object for my Knapsack.
The objects here being the key words.
And I'm trying to choose a price level for that key word
such that the sum of the prices fits in my Knapsack,
the Knapsack being my budget constraint,
and my value is maximized.
So a lot of papers in the literature have looked at this
interpretation of bidding in auctions with budget
constraints with various assumptions about the
knowledge of the advertiser and the dependencies between
the key words and the arrival sequence of key words.
Oftentimes such bidding heuristics are not good enough
because they're not fast enough.
That could be one reason.
And another reason is that advertisers often don't have
all the information that these algorithms would assume of
some of them.
For example, they often have only local information about
the prices of various slots on various key words.
They know the price of the slots near them, perhaps, but
not all the slots.
So as a result it makes sense to study some simpler bidding
heuristics.
And here I propose one natural bidding heuristic called the
return on investment, equalizing return on
investment.
What do I mean by this?
Well, the return on investment is defined to be the ratio of
the utility that you get from an ad divided by its cost.
That's the return on investment.
And the heuristic is, if your budget is limited you should
try to equalize the return on investment of all your ads.
If you're overspending your budget you should reduce your
bid on the ad which has the lowest return on investment,
thereby moving your ad down to a lower slot and increasing
the return on investment for that ad.
If you're underspending you should increase your bid, up
to, at most, your utility, of course, for the ad that's
giving you the best return on investment.
By increasing your bid you're going to move up to a higher
slot and thereby increase the price of that ad and decrease
the ROI that's starting to equalize it
across all your ads.
So this is the heuristic.
It's a pretty natural heuristic.
You'll see, when you talk to, at least, people at iProspect
and other SEMs, they say that they're using
things similar to this.

I also wanted to mention that this is very similar to the
two approximation for the Knapsack algorithm.
In fact, if all of the ads had just one slot you would be
exactly running the two approximation to the Knapsack
algorithm, except that in the two approximation at the last
step you sometimes add with the highest value instead of
taking the prefix ordering.
Here we're just taking the prefix ordering, for those of
you that know the two approximation for Knapsack.
Anyway, so I was saying that SEMs seem to
be using this algorithm.
It's natural for advertisers to try and use this algorithm.
Therefore we should worry about the equilibrium when
everybody is using this algorithm, the system
equilibrium.
For example, AdCenter wants to offer this as an
optimization tool.
And many bidders are going to use this tool.
And what's going to be the result when everybody
is using this tool?
What are the prices going to converge to, or will they
cycle endlessly?
Will allocations cycle endlessly?
Are we going to lose all our revenue if we do these
optimizations for the advertisers, or if advertisers
are doing these optimizations themselves?

One bad news is that there are examples that don't converge.
Here's one such example.
I have two bidders and I have one item.
And these bidders are budget constrained.
And on day one bidder one bids slightly more than bidder two.
At the end of the day, bidder one has overspent her budget
and bidder two has underspent her budget because bidder one
was winning all of these ads up to the end of the day when
they ran out of budget.
So bidder two was winning very few ads at the end of the day.
So on the next day bidder one, according to this algorithm,
this heuristic, is going to decrease her bid, and bidder
two is going to increase his bid.
And so they're going to change places.
And now on day two we're going to see the same behavior.
So we're going to get this alternation where the bids
move up and down throughout the day.
And the allocations also move from bidder one to bidder two
on even an odd days, respectively.
So this causes cycling in the bidding behavior.
And cycling patterns have been observed, according to some of
the papers and the literature.
This is a paper of Zhang 2006 from the history of
a key word on Yahoo.
And you can see, when I enlarge that box there, that
the bids do seem to cycle according to the data that
this person had access to.
There are many, many reasons for the cycling.
And I'm not trying to say that this explanation that I gave
is the cause of the cycling, but it might be
contributing to it.
And such cycling is bad.
it introduces uncertainty for the advertisers and
they don't like it.

What we show is--
MALE SPEAKER: Are the colors different bidders?
NICOLE IMMORTICA: Yeah, the colors are different bidders.
MALE SPEAKER: What's the time scale here?

NICOLE IMMORTICA: Each of these is a different bid.
I don't know what the time scale is.
The x-axis is the change in the bid.
MALE SPEAKER: This is within one allocation
of budget you think?
NICOLE IMMORTICA: Yeah.
I don't have access to this data.
This is from Yahoo.
And this is what I interpreted from that paper.
But you could try to ask Zhang instead of me.

One thing we observe in a paper in this upcoming
[? dub dub tub ?]
is that in a perturbed first price auction this is not
going to happen.
We can prove this.
This is a theorem in our paper, that if you allow them
mechanism, the auctioneer, when you take in that bid what
you do is you randomly decrease each bid by a very
small amount.
And then we're going to run the same sort of auction I was
describing at the beginning of the talk, except instead of
charging an advertiser the minimum amount he should pay
to maintain his position in the ranking I'm going to
charge him exactly his bid, his perturbed bid.
So why is this a good idea?
Well, if two bids are very close, as in that example I
was giving you where the bids were cycling on even and odd
days, then the lower bid still has some chance of winning.
So we're going to smooth the allocation.
Essentially we're letting the two bidders
share the key word.
When their bids are very close we should be giving half of
the appearances of the key word to one advertiser and
half to the other.
Also, this perturbation idea is very useful for a solution
for spiteful bidding.
Spiteful bidding is scenarios in which an advertiser tries
to fit just under the bid of the guy above him in order to
cause him to spend as much a very fast. But now if you try
to do such a thing you have some chance of winning the
object at a price that's too expensive for you.
So in general I think perturbations are a good thing
in auction design.
And probably, actually, because of the CTR parameter
you actually are doing some kind of random perturbation in
your auction.
I'm not sure exactly what you're doing, but I wouldn't
be surprised if you are effectively perturbing the
bids because of some other parts of your auction design.
So we have this result for first price auctions.
We also are able to simulate what's going on in second
price auctions and see that, again, the prices and
allocations seemed to converge to the market equilibrium for
a second price auction.
But we are unable to prove that.
And that's one interesting thing to do.

So here's the simulation for that simple example I was
mentioning in the previous slide where I have two bidders
and one key word.
And each bidder has a fixed budget of $500 and a value
$1.00 per unit and there's 1,000 units coming per day.

As I explained in the example, you can see from the blue dots
that when we don't have perturbations the bidders each
increased their bid to about 0.5.
At that moment they're starting to run out of budget
and so they alternate the allocation
on even an odd days.
And this graph shows you the bid level of one of the
advertisers.
It's the same for both advertisers.
On the other hand, when I use perturbation both of the
advertisers will increase their bid to $1.00 and that's
their value so they don't increase it beyond that.
And they're not running out of budget when they're bidding at
$1.00, because they're sharing the key word, more or less,
equally among each other because of these random
perturbations.
So both the allocation has stabilized and the revenue of
the auctioneer has doubled in this instance.
So this was just a contrived example.
This graph here is trying to get at the fact that this
contrived example is not so rare.
Here we have, if I recall correctly, 10 advertisers, 20
key words, 1 slot per key words.
Each advertiser's interested in each keyword with
probability 1/3.
They have values drawn uniformly between zero and one
for the key word.

And they have budget constraints which follow some
kind of power law distribution.
And when we run the perturbed auctions, represented by the
black x's and the pink stars, we see that the efficiency of
the auction stabilizes over time.
On other hand, if we run the first and second price
auctions without the perturbations, those are the
red diamonds and the blue circles, we see that on even
and odd days the allocation completely changes.
So it might look to like there's two lines here for the
red diamonds and the blue circles.
In fact there's only one, but it's just zigzagging on even
and odd days.
And this is because the allocation is switching on
even and odd days.
And the advertisers on one of those days have higher value
for the allocation than on the other.
Finally, we looked at the convergence properties of our
algorithms. What do I mean by convergence?
In that same scenario I described simulations set up I
described in the last slide.
I'm running the auction for 300 days and I'm looking at
how many advertisers actually ended up spending close to all
of their budget and staying in the auction to close to the
end of the day.

And in the first price auction and second price auction,
without perturbations, in many of the cases not very many
advertisers converged.
But when we perturbed the auctions we see that almost
all the time all 10 advertisers converge.

I see I'm already over time but let me try to wrap up a
little bit.
First, about online advertising.
I think this market's very interesting
and it's still evolving.
It's still quite new, actually, if
you think about it.
It started, really, in '98, 2000.
As the market evolves we're going to see more targeted and
highly fragmented sales.
So each eyeball is going to become almost unique.
And we're going to have to figure out how to price these
very unique eyeballs.
We're going to see increased connections between various
media types.
We're going to see connections between what you watch on Tivo
and what advertisements you see on your search engines and
what you read on your Gmail, and so on.
There's going to be new revenue sources for online
advertising.
We've already seen YouTube starting to introduce online
advertising in video games.
There's a whole big push for getting some sort of online
advertising when you're, say in a car race game.
The billboards you see are sold through some kind of
online auction system.
And also we'll see new sorts of allocation problems. Maybe
we can sell ads with particular lengths instead of
just one block per ad.
You can buy some number of lines of text.
I just wanted to briefly mention some of my other
research, in case any of you get a chance to talk to me and
wanted to ask questions about it.
One thing I'm very interested in is social networks.
And I've done some work on the evolution of social networks
and the diffusion of information and technology in
these networks.
I'm also quite interested in matching markets, and you
Almaden people saw me talk about the National Residency
Matching Program a few years ago.
There's many more matching markets that are being studied
these days.
There's the kidney exchange, where if you have a donor for
a kidney that's failing that doesn't match your blood type
you can try to exchange your donor's kidney for some other
donors kidney that might match your blood type.
And also you know AdSense, for example, is some kind of
matching program at its heart.
Because you're trying to match advertisers and web sites.
So I've done a lot of work on incentive properties in
matching markets and also on the use of stochastic
information in these markets.
And finally something I'm very interested in these days are
secretary problems, or hiring problems. This is, how do you
hire the best employee when you need to make
your decision online.
So these problems have a lot of connections to online
auctions and they're also just interesting online decision
problems in their own right.
So I've studied these also with the motivation of bidding
in ad auctions in mind.
I think that's all I have, so I can take any questions.

MALE SPEAKER: They're clapping, you can't hear them.