Before we can analyze auctions, let's first understand, when will auctions be useful? So take a step back. Now, auction is one of the many ways to do resource allocation in a crowd or network. We'll see many other examples later in the course. And in an auction, it's particularly useful when the seller does not really understand who really should get the item or the items, and how much to charge. So when you're confused or not sure about this, these questions, then, you want to search for the right price. For the right price, then maybe auction is a good mechanism for you. When you're not sure about the pricing signal. And most of the analysis of auctions assume two kinds of behaviors about the valuations. Now, you may recall C times R, click through rate expected times the average revenue per click that was the valuation in the case of Google selling ad spaces. And when you're talking about other kinds of auction, could be a house, could be a the spectrum by the government for 3G license, or any other item. Right. You have some kind of intrinsic view by yourself. Subjective, but you know it. Vi for the Ith buyer as the valuation. I would assume that these valuations are private, meaning that the auctioneer or the other potential buyers do not know your valuation, neither do you know the others. And furthermore, it's independent. So VI, it just depends on I. It doesn't depend on the VJs where J is not = to I. And of course, in many cases the valuation is not completely private, for example, on eBay as we have seen in an example, you get a glimpse of other people's potential valuation, just by watching the announcement of the asked prices. And whenever there is a secondary market. For example, houses, for closure houses on auction block. The secondary market existence means that, when you think about evaluation of a house, is influenced by other people's evaluation, if you want to ever sell it again in the secondary market. But, having said that, lets assume private and independent evaluation for what we need to do with add space auctions. So in order to compare one auction mechanism with another, one allocation with another, we'll have to think about the metrics to compare them with. So what does each party in this ecosystem want? For the seller obviously the most important one is the revenue. How much do I generate by this particular way to allocate and price? For the buyers, each of them, it is the payoff that matters. It's the difference between the valuation of getting this item, and the price they have to pay as the Ith buyer. And later we'll look at the difference between happiness and the price. We call that net utility. In this case we call this a payoff. Now of course valuation is determined by you and as I said, we assume it's independent of others, but the price is not completely determined by you, it's determined by what other buyers do and the rules of this auction. So the auction will decide what prices you have to pay. So clearly if you know the auction rule changed, you may change your bidding behavior because your payoff is the difference between the valuation and the price. Now the auction designer, which could be the seller itself will like to be sure the auction induces an efficient and fair outcome. Now how do we define efficiency and fairness. We'll see some example in other contexts later in the course. But for today we will take proxy, as a proxy the truthful bidding property that says if you view this item with a valuation of VI then just bid, that's your bid exactly the I. You think that sounds pretty intuitive. Actually, you will see that, in quite a few cases, that's not necessarily true. So today, we will simplify the picture, and say that truthful bidding is so desirable that we want to maintain it. But actually, it may not lead to revenue maximization or payoff maximization in all cases. So that's how we're going to compare auctions. And then, we're going to analyze auctions as games. Just like last lecture, when we talked about disputed power control, and look at the power control game in cellular networks. We can view auctions as games. As mentioned, each game is defined by three tubbles. Set of players, strategy space per player, and a payoff function per player. So who are the players in the auction game? Simple. It's just the set of buyers and their end of them.. We'll assume that it's a fixed seller. And who are they, what are the strategy spaces? For each player I, each buyer I, basically, there is a set of bids that she's willing to submit. I'll make this simple by saying it can be any positive real number. What is interesting is the payoff function. First of all there are two possible outcomes. You may get the item in the single item case. In a multiple item case you may get some item okay, or maybe you don't get it. Now this outcome of allocation is determined clearly by the collection of all the bits submitted by everyone. So this defined by the vector b, not just your own, not just bi, but all the b's. B1, B2 up to Bn. And in the case that you get the item. I don't know, congratulations, now let's take a look at your payoff. It is your valuation minus the price you pay. Again, the price is a function of the entire b vector. And the auction designer will determine the shape of this function. How do you map the whole vector bids into a single number called the price to the winner? We'll come back to that in a minute. But whatever that might be, this difference is your payoff. [inaudible] UI, the notation for payoff, which clearly is a function of co-vector b as well. That's the coupling of all the actions by the buyers. But in case you don't get it, then you get nothing. You get zero, because you pay nothing, you receive nothing. Now, vi minus pi could be positive, could be negative, could be zero. We don't know, depends on what is the valuation and what is the price. Again, valuation is assumed to be private, no one knows, and independent, doesn't depends on anyone else. But the prize clearly depends on others' behavior, the others' bidding behavior. And what is interesting is that, by deciding a different function that maps bidding behavior to prize, you will, in turn, induce different bidding behavior. Okay. Different auction rules will induce different bidding strategies in this auction game. For example, lets take a look at a, a simple example. Coming back to this. This is the definition of payoff function, branching to two possibilities, determined by the b vector in one case, you look at the difference. This part of difference determined by the b vector. So, let's just look at this part. P I as a function of vector B. And maybe I should just say let it be B I. Okay, your own bid so if you win it then [inaudible] is the first prize. You pay the first prize, and that is exactly what we saw. And, it sounds quite intuitive. Okay, see what envelope, then just, you know, you give it to whoever is the highest bidder and that decides the allocation. As to the pricing, just pay the price that person bid it. Then in this case your payoff, UI, is just VI minus BI. Right? Your own valuation minus your own business, if you get it. So you may think what should I bid. Well, if I bid bigger than my valuation, I'll get a negative utility or payoff. That's not good. If I bid exactly as my valuation that's not good either cuz I get zero. I may as well just not bid the item. So, I'm going to bid a little below the I, but if I bid too low, I may not get item, so how should I bid in order to maximize my payoff? And was impact on Google's revenue that's actually pretty complicated question. We won't have time to talk about that today. Instead we're going to look at the intuitively not making sense but actually very sensible second price this says. The price you pay is actually somebody else bid. And this J user is exactly the second highest bidder. And your utility or payoff, trying to differentiate U from V is your V minus this BJ somebody else J. And it so happens that by decoupling the winning and losing decision from the actual price, you pay. Remember, utility depends on both allocation and the pricing. Decoupled allocation decision and the pricing decision actually induces truthful bidding behavior from all the potential buyers.
