Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Selling Ad Spaces through Auctions

Loading...

Networks: Friends, Money, and Bytes

Princeton University

4.8 (85 ratings) | 16K Students Enrolled

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.

Reviews

4.8 (85 ratings)

5 stars
72 ratings
4 stars
10 ratings
3 stars
1 ratings
2 stars
1 ratings
1 star
1 ratings

PS

Mar 12, 2016

It is really a exceptional course which illustrates networking problems and answers with real life examples.

M

Jan 31, 2016

thanks to get world class education at home, my name is Mutlu from turkey

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.

Selling Ad Spaces through Auctions19:18

Auction Definitions10:59

Second Price Single Item Auction20:52

Generalized Second Price (GSP) Auction and Numerical Example20:14

Vickrey–Clarke–Groves (VCG) Auction8:38

Taught By

Mung Chiang
Professor
Christopher Brinton
Lecturer

Transcript

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.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates