0:09

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.

Â 2:48

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.

Â 8:02

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?

Â 11:38

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.

Â 18:10

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.

Â