So far I've only looked at single items auction.

So, the first and second price for, for single item, and the example on eBay is

also for single item. But, of course, in ad space auction, you

have multiple ad spaces on the same page. For example, three ad spaces, one, two and

three. And let's say, they're ordered in

descending order of their visual importance on the web page.

Let's say the click-through rate are, respectively, five, and the smallest

three, and the smallest one, click per unit of time, say one hour.

So now our job is to allocate not just one, but three items and then charge them

accordingly. As we just mentioned that Google runs the

so-called generalized second prize auction.

So what is that? Let's illustrate that with this particular

example. On the right hand side are the products,

this case ad spaces, the items. On the left hand side we draw a list of

three bidders, okay, labeled one, two, and three.

It doesn't have to be three. It could be four.

It could be two, but in this case we just let N be the same as K and both are three

for the simplicity of illustration. And each of these bidders is an

advertiser, and, they have an expected revenue per click, which is $ten per

click, $five per click, and $one per click.

And obviously we have ordered these three bidders, in descending order of their

revenues, per click. So these are the r values.

And these are the C values, the click through rates for each app space and the

expected revenue per click for each of the three buyers.

And what GSP does is to say, each bidder can send in a vector of bids.

Okay? Because there are three items.

But, that vector actually is just a scaler.

It is really what they value, for each click, their valuation per click.

Now, they can choose to. Submit a bid that's the actual revenue per

click. The true valuation per click, if they

wanna follow a truthful bidding pattern. Or they can pick any other number.

It could be a fictitious valuation per click.

That's the single number submitted to Google by each bidder.

But we can also view that as a vector. It is just that scaler.

This evaluation per click multiplying the vector of click through rates.

In this case it's five, three, one. So for example if the three bidders all

decide to do truthful bidding, meaning that they would each submit ten, five and

one respectively as their bids the true evaluation per click.

Then Less equivalent to saying that. Bidder one is submitting a vector

consisting of three bids: ten times five, 50.

Ten times three, 30 and ten times one, ten.

Because this is just a scaled version of the click through rate vector.

The scaling, the proportionality constant, is the scaler bid.

So we can view it either as, a scalar bid, or as a vector bid.

Either way, because this vector, truly just the scalar multiplying the given

constant click the rate. Similarly, buyer two, submit truthful

evaluation, suppose, and there will be five, that's the bid.

We can also view that as a vector of five, five.

25 for the first ad space. Five 315 for the second ad space.

And five one, which is five for the third ad space.

And similarly, for the third bidder as well.

Either a scalar bid one, or a vector bid of 531 for the three ad spaces,

respectively. Now we have something called a bipartite

graph. We'll come back to this in a minute.

We have on the left hand side, these three bidders.

On the right hand side, these ad spaces. And our job is to match these white dots

with the black dots. By matching, we mean that each one of

these white dots would be matched to one and exactly one of these black dots.

This is an equals K. We'll see basically a perfect match, one

white dot matching to one black dot, and all white and all black dots will be

matched. So there are actually quite a few

possibilities here, because the one, this one can be matched to any one of the three

black ones. Now we have to decide which one to match,

that is the allocation part of GSP. And the GSP rule says that, it's quite

simple, we just match the top ad space, the most valuable ad space to the highest

bidder, and match the second valuable space to the second highest bidder, and

the third valuable space to the third highest bidder.

In this case since both left and right sides have been already arranged in

descending order, the matching is a simple horizontal matching.

That is the matching that GSP would provide.

And then GSP need to decide the charges, how to charge.

And generalize that second prize simply by saying well, the top ad space given to the

top bidder will be charged by the bid from the second highest bidder.

Oay, so in this case would be 25. And the second highest most valuable

airspace going to the second highest bidder.

The charge will be according to the third highest bidder.

Now, since there are only three items and three bidders, what about the third pair?

Well you can either say they get charged nothing.

Or, in reality, they always have a minimum.

Let's say, a delta of charge. So it would be charged delta dollars per

click. The delta, let's say, equals .5 dollars.

Okay, that's the very bare minimum that Google has to charge you, cuz there is no

lower bidder than you now. So this is the process of GSP.

So again, let's take a look at this example, okay?

The bidding is basically, For each buyer there's a bid, scale of BI which.

Multiplies the vector of C1, C2 dot, dot, dot, C, K for K items.

These are the click through rates for each item.

They are multiplied by BI. So you can either view this as scalar bit

or you can view it as a vector bit of BI, C1, BI, C2, dot, dot, dot, BI, CK.

The allocation is very simple. The Ith highest bidder gets the Ith most

valuable ad space. And the charging mechanism is that the Ith

one charged. By the one below it, the I plus 1th bid,

Unless you have no one below you, then you just charged by the basic minimum dollars

per click. Okay.

So, before we go on further, a very quick detour, on two questions, one.

We brought this up briefly before. Why not each buyer submit an actual vector

of multiple bids? For example, instead of saying it's a

scalar, say ten, times. The vector of click through rates, 5-3-1.

How'bout we ask them to submit truly different entries in the vector, not just

all multiples of this given. Click through vector, for example.

100, five, and one. Okay?

Just, just say that I really value the top slot so much, that I'm willing to bid a

lot more for the very top one. And indeed, that will be the more general

scenario. The only reason we're not using that

scenario, but instead focus on this simplified version is because, this is

what Google practices in ad words system. It is simpler than this one.

And in several lectures time, we'll look at a case where each user will input a

truly, different entries in the vector of preferences.

And that will give us a lot more information about the scale of the

preferences. In fact, too much information for us to

consolidate those input vectors into a common output.

We'll later come to this in voting systems discussion.

The second question is, we saw, we had a bipartite graph, right?

Three white dots representing three bidders.

Three black dots representing three ad spaces.

If you arrange them by RNC respectively in descending order, then GSP's matching is a

simple straight line. In general, we have other kinds of

bipartite graphs. What kind of graphs are bi-, bipartite, it

means that all the nodes basically can be grouped into left and right.

They don't have to, say, have the same sides, could, could be three on the left,

five on the right. As long as all the links connecting the

nodes are across the left and right, but not within left or within right.

We call this a bipartigraph, and this is a very useful visualization and analytic

tool in many graph-theoretic solutions. Auction is being a particular special

case. Of bipartite graphs usage.

We're going to later see more graphs, more bipartite graphs, and more matching

methodology in bipartite graphs. So that's a quick detour.

Now, let's go back to that example. Which example?

This example, okay? We've got three bidders with ten, five,

one being the R's, . And three ad spaces with five, three, one

as the click through rates. So before we forget, let's write those

down, okay? Ten, five, one.

And five, three, one, okay? So now let's finish the discussion of this

example. What kind of bidding will they provide?

Let's assume they do truthful bidding. The keyword is assume.

We'll later come back to why this is not in generally in channel two.

But assuming that they do truthful bidding, then their bids are exactly ten,

five, one, respectively out of the three buyers.

Okay. So, in that case, we know exactly how much

they'll bid. They'll bid $50, and $30, and $ten for the

three ad spaces by the first user. The second user will bid five x five, $25,

fifteen, and $five for the three s-, ad spaces.

The third one will bid five, three, one for the three ad spaces.

Those are the bids. Okay?

50, 30, ten. 25, fifteen.

Five and 531. And the allocation is simple.

Okay, first one get this one, second get this one, third one get this one.

What about the charging? So the charging basically is that the

first one would be charged by this. It's 25 clicks, dollars per click.

Second one will be charged by The bidder, the bid from the third, bidder, on the

second space. So it would be charged three.

The last one would be charged the very small minimum, which is.5 in this case.

Okay? These are in dollar amounts.

Per click. So now we can take look at the revenue.

So, Google collects the following revenue: which is 25 from the first bidder, three

from the second, and .5 from the third, which is $28.5.

And then the payoff to the buyers. The three buyers.

So have to make three calculations. Remember, a payoff u equals valuation v

minus price p. So, for the first one, you've got the,

ties the spot. So, your valuation, 'tis ten.

Subtract the price you pay, which is five per click, equals five per click.

Or equivalently. $Five per click times five clicks per hour

on average is $25 per hour. And the second bidders payoff is $five

minus one. That's your valuation and that's the price

you pay. So what you get is $four that's per click.

Which translates into $four times three clicks per hour, that is $twelve per hour.

Finally, the third one your valuation for the third ad space that you received is

one and the price you pay is the minimum. So the payoff is half a dollar per click

which translates into half a dollar per click times one click per hour which is

half a dollar per hour. So the total payoff is $25 per hour for

the first bidder, +12for the second bidder, + half for the third bidder, which

is 37.5. And this is in per hour, just like here,

per hour, cuz it reflects both. The payoff per click and the expected

number of clicks per hour. So this is how much Hugo is receiving in

the revenue and this is how much net happiness payoff is received by the three

bidders all together. So you may think GSP sounds pretty good.

It's pretty simple to explain the allocation and the charging, and as long

as we can assume they do truthful bidding seems to be a pretty efficient allocation

system except we cannot assume that people will do truthful bidding, 'kay?

So here's a very simple example. I can write it in the margin of the slide.

Let's say there are, there's two ad spaces.

The top one get 400 clicks per hour. The next one gets 300 clicks per hour.

Okay, both are pretty powerful but the first one it's lightly better.

And there are three bidders, one, two and three.

Their valuation which is the number of dollars per click expected is $twelve,

$eight and $four respectively. Now, let's say, what should the first

bidder do? Let me think.

Well, maybe she should bid a truthful bidding.

So, she should bid twelve, or equivocally twelve times 400 for the first spot,

twelve times 300 for the second spot. But, actually, if that's what she does.

Okay. She's going to win the first spot.

And the valuation in that case or the payoff, I'm sorry, in that case, is the

valuation twelve minus the price you pay, just by GSP eight.

Dollars per click times 400 clicks per hour, and that would be $1600 per hour.

However, she can do better. She can actually, instead of bidding the

2-1, she can say, I'm going to bid, say, $seven.

You say, but then you won't get the top spot in the ad space.

That's fine. Winning the top spot is not my goal.

My goal is to maximize my payoff. And indeed, if I do this, then I will get

the second spot. Because the second bidder assuming the

truthful bidding, will get the top spot. I didn't do the truthful bidding, I got

the second spot. But look what happens to my payoff

function, u. I, I get, my net utility or payoff

function be the difference of, between my valuation which is twelve and the price I

have to pay, and once I have got the second spot, I should pay the third

highest bid. Again assuming the third buyer bids

truthfully that will be four. But, of course, for each click, for each,

for this spot I got, I don't get 400. I only got 300 clicks per hour, 12-1 is

$eight per click. That translates into $2400 per hour.

Now, this is a higher payoff than the truthful bidding one.

Of course, this assumes that the second and third bidder bids truthfully, only the

first one chooses not to. But nonetheless, it is a simple but

effective counter example to show that GSP does not induce truthful bidding.

The most, one of the most desirable properties of second prize is not carried

from single to multiple items in GSP.

Generalized Second Price (GSP) Auction and Numerical Example

Redes: Amigos, Dinheiro e Bytes

Conheça os instrutores