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.
