You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions. All the features of this course are available for free. It does not offer a certificate upon completion.
Selling Ad Spaces through Auctions
Loading...
From the course by Princeton University
Networks: Friends, Money, and Bytes
79 ratings
From the lesson
How Does Google Sell Ad Spaces?
How does Google sells the ads that appear on its search results page through auctions? We learn about different types of auction mechanisms, including those for single and multiple items. QUESTION 3: We explore PageRank, the famous algorithm that underlies how Google orders its list of search results whenever we type in a query.
Meet the Instructors
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
Welcome to the second lecture of Networks: Friends, Money and Bytes.
In this lecture, we'll try to formulate and answer this question, how does Google
sell advertising spaces? Now you must have used Google's search
results. And indeed, in the next lecture, we will
be looking at the PageRank algorithm that computes the order of the search results.
But, on a search page, here's Google's bar.
There are these search results that we'll talk about next lecture.
There's also often advertising space, shaded region on the right hand side, with
some so-called sponsored content. These are basically advertisements that
tag along on a search result page. Sometimes, they're even placed in the main
panel on top. Now, you may wonder, what decides which
advertisement shows up here or here, versus here or here.
Well, we have to go back a little bit, and just think about the general space of
online advertising, which reached 95 billion worldwide, in the year 2012.
And, in this ecosystem there are sellers, for example Google, and there are buyers,
which are the advertising companies. Back in the early days of the web, for
example, around 94, 95, advertise, advertisement on web, was sold on a
impression based mechanism. So as long as I show you an advertisement,
then you've got to pay me. For example, you know, $50 per 1000
impresssions. And then a company called Goto, which later became Overture in 97
introduced a different mechanism called click based. So if I just show you and no one actually
clicked on it, then I won't charge you. But if I show this to people and then some
of them actually clicked on it, then for every click I would charge you.
Then along came Google in 1998 with the Google search engine.
Then a few years later Google introduced an auction based mechanism to sell the
advertisements on the search result page. It's called Google's AdWords system.
And anyone like you or me can go there and say, each time somebody search on Google's
page for certain keywords, let's say burgers, then please link to my wonderful
burger shop. Now the question is you have to tell
Google how much you're willing to pay for different spaces.
And then Google will decide who gets what. So the very first question you have to
answer is where will your advertisement appear.
Now of course, where it appears matters a lot.
We all know how important the Google search results and the advertisements there
are in driving the traffic to different websites.
So, different spots on the given page have different values.
We can summarize that value through a single number called C.
This is a positive, real number. And it is the expected click through rate.
Since rate, so we are talking about how many per unit of time, for example.
If C is 80, is 80 clicks per hour. Based on some historical data that, the
advertisement placed at this spot will generate 80 clicks every hour.
Of course, this is an expected. It's not necessarily the actual click
through rate when your advertisement is placed there.
We'll also assume that this number C is independent of the actual ad placed there.
Of course, some ads are just more attractive than others, so that will also
impact C. But we'll assume that's not the case.
Now, throughout this whole course, you see that whenever we say assume something, it
means the rest of the sentence is an incorrect statement.
That's why we call them assumptions, rather than facts.
But some assumptions will lead to still useful models and conclusions, whereas
other assumptions will destroy the predictive power.
Now, this assumption turns out to be not particularly bad.
So now we know that we have a single number C for each advertising spot.
It's called the expected click through rate.
The second question is, how do advertisers pay Google?
So when you acually click, then the advertiser has to pay Google.
But we'll assume that this actual click through rate say, you know, C1 for the
first hour your advertisement is there, C2 and so on, they will just be the same as
the expected the click through rate. The third question is, that what's in it
for the advertisers? They pay Google based on the click through
rate which we will assume to be the same as expected click through rate and Google
got a revenue stream. That's good for it.
But what about the advertisers? Well, presumably, some people who look at
the advertisement will actually click on it, and some of those that click on it
will actually buy the product or the service.
Let's say 80 percent of the people who click will actually buy it, and then each
time they buy it you generate a $10 revenue.
Then you multiply the two together. You say $8 per, is the average revenue
in dollar that I can expect from each click.
We call this number R. It's the average revenue per click that
you can anticipate. Now remember we just talked about
another symbol C, denoting the average number of clicks per hour.
So if you multiply the two together, C times R this is the average click per hour
this is the average revenue per click and therefore the total count by this
multiplication is the average revenue, in dollars per hour.
And this is a very important quantity we'll come back to many times today called
the valuation of this advertisement space to this buyer.
The different ad spaces, the different Cs, and different buyers have different Rs.
Either, because your product sells for different revenue or because the
percentage of people you can expect among those who clicked the advertisement will end
up buying it is different. Either way, R will be different for
different buyers, but in any case the multiplication of these two numbers is the
valuation. So you may think maybe I should bid the
valuation. What we'll see if you do that, we call
that truthful bidding in an auction. If you don't do that then it's called
non-truthful bidding. What kind of auction will induce truthful
bidding? That is one of the main themes in this
lecture. We'll come back to that, but first we have
to define what is an auction. So auction is a particular way to do
resource allocation, in a crowd or in a network.
In this case the resource, is not signal interference ratio like in last lecture.
The resource in this case is the list of advertising spaces.
And the allocation mechanism is auction. Now, auctions have been used since over
2,000 years ago. It was used in Roman, ancient Roman Empire,
and of course, today it's used very heavily on platforms that we know, all
know, like eBay in the U.S. And Google's search sponsored content.
So in these kind of auctions, we just have one seller, say Google.
And buyers and advertisers in K items. It's the K advertisement spaces.
We will first focus on the Ks of K equals to one.
Which, perhaps, suits eBay modeling better before we generalize to any number
of items. Now, these buyers, and there are N of
them, will submit this in an auction. And then, the seller will make two
decisions. The first is the allocation decision.
Which item goes to which buyer? If there's only one item, then, where does
this item go? Which buyer will get it?
And you may think, whoever bids the highest should get it, and that's indeed a
very reasonable intuition. We'll come to that in a minute.
And then the second decision you have to make is, how much do you charge for that?
And this is where things start to get a little tricky, even for a single item.
So let's take a look at some very well known kind of auction mechanism,
focusing on single-item for now. So you've got one item you want to sell
through an auction. Let's say you have a public venue.
There's a podium, there's auctioneer standing behind it, holding the item.
And there is a crowd of people, potential buyers sitting there.
And then this auctioneer is going to say, I got something I want to sell.
Okay? I don't know who will get it.
I don't know how much you will be charged.
But let's go through the process. One possibility is the so-called ascending
price. Perhaps, by far, the most popular one.
You've seen this in some movies or TV series for sure.
The auctioneer will say, well we start with $10 for this lamp.
And each time you at least have to go above the current highest bid by $1.
So please let's get started, $10 anyone? And then somebody say yeah, $10 me.
And then, another person say eleven, $12 then somebody jump ahead and say
$20, somebody jump ahead said 10,000. At some point a guy stand ups and say 155
billion. Alright, and nobody want to go up further.
The auctioneer will say 155 billion once, twice, three time, okay?
Gone. This item is yours and please give us the
$155 billion. So, the highest bidder wins and pays
the price whenever this auction stops. However, notice that, that price, 155
billion, may not be the true valuation of this particular buyer.
She might be willing to go even higher. She stops because no one matches that
price. And that's a subtle but important point
we'll come back to in a minute. There's a less popular version, a
descending price, where the auctioneer start with a big number, okay?
$4 billion for this lamp. Anyone?
Everybody silent. Then start dropping the price on some
regular or irregular increment, or decrement, I should say.
Eventually, it goes down to, alright, so this goes to one cent.
Anybody? And then one person raise their hand.
Yeah, okay. one cent for me.
So say, okay. You got the lamp, and you pay one cent.
And notice that in the descending price, when it stops, it actually matches the
valuation of that particular user. Alright, so that's public auction.
But, many cases you don't have a public venue, or you have one but you just don't
want to use it. In auctioning off many things, for
example, government auctioning off municipality projects and so on.
You use a so-called sealed envelope. So, here's the auctioneer okay and all
these buyers standing here. They will each pass an envelope to the
auctioneer, and the envelope has a number written on it.
And then the auctioneer will say alright I'm going to go back to my room, open all
the envelopes at the same time, and I see what are the numbers in there.
Okay, ten, fifteen, twelve and so on. Then I have to make the two decisions, a
allocation. Well, I guess whoever bids the highest
will get the item. We're still talking about single item
right now. But then comes the more tricky part, how
much should I charge it? You might say, well charge whatever she
wrote down in the envelope. That will be first price.
But it turns out that first price is necessarily not a smart arrangement.
We will come to defining what is a smart auction,
what's a good auction mechanism, in a minute.
But suffice to say that, actually, there is an alternative that most governments
and corporations use. It's called second price.
That is, she gets the item but she pays not her own price, but the price of the
second highest bidder. Whoever that might be in this case at
$12. You say, hold on a second, that doesn't
make any sense, right? Because, if this is the case, if I know
this is the rule, I'm going to bid in the following way.
I'm will bid a huge amount, ridiculously. Okay?
$85 trillion so I get the item, and then I will pay the low price by someone else.
Well, it turns out that intuition itself, is flawed.
And it's easy to see why. Because you're not the only smart person
in the room. You think this way.
Others seem to think so as well. Everybody strategizes at the same time.
So nobody was going to bid a ridiculously small bid just so that, you can pay the
small price. And indeed, actually, we will soon see why
second price is a smart arrangement. In particular, it induces truthful bidding
that we just talked about briefly. Now how to prove that it does that.
We're going to spend some, ten minutes or so, very soon.
But first, let's finish this quick intro. Going from one item to general K item.
For example, this is the Google search result page and on the right panel there
are these say, three good spots. And the top one of course, will have a
higher click through rate, in general, than the second,
in turn, than the third. And let's say there are also three buyers,
three advertisers. So K = N in this case.
It doesn't have to be. But to make it simple for now.
And then they will submit bid to Google. The question is, what should the bids look
like? Let's say, and we'll come back to justify
this in a minute, that they would each submit a single
number, okay? You'd think they should submit three numbers
because there are three things to bid. But, let's say they submit one number,
which they could choose to be the average revenue per click R, for each one.
R1, R2, R3, or they can pick some, any other non-truthful bidding strategies.
And then Google will say, alright, I got three items.
I got three bids from three buyers, respectively.
How should I allocate? One way to allocate is to say, well,
highest bidder get the best spot. Second highest bidder get the second best spot.
Third highest bidder get the third best spot,
there's allocation. Now how much should I charge it?
Well. I trust the belief that the second price
is a good one. We'll come to justify that but let's say,
for now, that's a good idea. Alright.
So the first winner will pay the price that's the same as the bid from the one
below it, the second highest bid. And let me generalize that second price
idea to say the second highest buyer will pay the price of the third highest bid and
if there's more than three you can keep on going like that.
So basically. The top advertiser pays the bid that got
the other advertisement, advertiser the second best spot.
The second highest buyer will pay the price that's the bid from the third
highest bid. And it keeps on going like that, till you
pay the price coming from the person who got the spot right below you.
In this generalizes the second-price idea to multiple item and we indeed give it an
intuitive name, Generalized Second Price auction, GSP, and this is the one used to
buy Google. In fact, I think before Google, this one
was not seriously considered by the auction research community.
But since Google started doing that, people started analyzing it.
Now, the question is, does this actually generalize second price?
As we just saw, that second price has a wonderful property.
That it induces truthful bidding, truthful bidding.
So the question is, GSP, does it induce truthful bidding, too,
in the multiple auction, multiple item auctions?
Turns out the answer is no. There are special cases where it does, but
generally speaking GSP does not. So, there must be something else going on
here, and indeed, if you want to induce truthful bidding you need something called
Vickrey-Clarke-Groves, VCG auction for multiple items named after three
economists. We'll come to the intuition of why second
price for single items induces truthful bidding,
but generalized second price is not the right to generalization if you want to
keep that property. We'll come to that intuition towards the
end of the lecture, and then we will save the VCG details, what is it and
why does it induce this truthful bidding, to the advanced material part of the lecture.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
