Hey folks. So let's talk now about optimal auctions. And what do I mean by optimal auctions? Basically, and up till this point in the course, usually when we've been analyzing auctions, we've taken auctions as given and analyzed them. Or we've talked a little bit about optimal efficient auctions, in terms of Vickrey-Clarke-Groves mechanisms and so forth. And here the idea is that we'll think about a seller designing an auction. And the seller might have incentives, not necessarily to always do the efficient thing, but instead to maximize the price that they get, maybe expected price. So they're interested in maximizing expected revenue. And what does that mean in terms of possible losses in efficiency. It may mean that sometimes the seller doesn't sell the good, so they may risk failing to sell it. They might also even sell to a buyer that doesn't necessarily have the highest bid. And that could happen in settings where there's some asymmetries among buyers and you want to use one buyer, the threat of selling to one buyer to make sure that you increase the bids by the other buyer. And we'll see a little bit of that in a bit. So here, we're going to think now about optimal auctions in this narrow sense of trying to design an auction which is going to maximize the seller's revenue. So, what kind of setting are we going to look at? We'll keep things relatively simple, in terms of the structure, so one good to be sold, private valuations. So each buyer has some value for the good, they're each risk neutral. The bidder's valuation is going to be drawn from a nice distribution that CDF is the cumulative distribution function. So we have a cumulative distribution function, Fi with a pdf density function of Fi. Which is going to be continuous and bounded below, so nicely defined continuous distributions over values, so a uniform distribution, or a series of other distributions that will keep things nicely shaped. We're going to allow for asymmetries among the individuals. So, now we're going to allow one bidder to have one distribution and another bidder to have a different distribution. So, it could be that I think of some bidders as having deep pockets and high values, and other bidders as being more thrifty and not having as high a value for an object. So we're going to have different distributions, and the important thing is that the risk neutral seller here is going to know the distributions and has no value for the object. So zero value for the object, knows the distributions, but doesn't know the actual values. So has an idea of what range the values are and what relative probabilities of different values are, but does not know the precise values, okay? So the optimal auction here, we're going to be looking at an auction that maximizes the seller's expected revenue, subject to some form of individual rationality. In this particular case it's not going to matter so much which type of individual rationality we impose. We can think about it as exposed, or interim, you can always move things around, in terms of expected payments, given all the risk neutrality, and the transferability here. So, we want Bayesian incentive compatibility, and make sure that the buyers don't want to walk away from the auction. Okay, and we're going to think about optimal auctions. So what I'm going to do is start with simple example, and base on that example, we'll get some intuitions out for why things are working and then we'll do a general statement of theorem. And so here, let's start with two bidders, each has a value uniformly distributed on 0,1. And let's think of changing the auction in a very simple format, what we're going to do is stick in a reserve price, okay? And this is quite common in auction. So, often when people are selling things of, there'll be a minimum bid, reserve price and you're not allowed to enter into the bidding unless you exceed that threshold. And so we get a set of reserve price in here, we're going to have a second price auction to make life simple, keep with the dominant strategies, but just stick in a reserve price. Okay, so let's think about how this works. Once we've put in the reserve price, then if both people end up bidding below that we're not going to get anything so. And here's the risk now, if we didn't have a reserve price, we would always sell the object, now there's a possibility of no sale, so we're not going to get anything. If one bidder bids above the reserve and one below it, then the reserve price is going to kick in, that's going to be the second highest price. Second highest bid we'll think of the reserve price as if it was a bid, and the second highest bid is now the reserve price and so we'll sell at reserve if somebody bids above it and the other below. So again, second price auction that's going to be the second highest. And if both of them bid above it, if both bidders happen to bid above it then it will just be second highest bid that will be the price. Okay so that's the setting. Which reserve price is going to maximize the expected revenue, so let's take a look at that. So first thing to note, it's still a dominant strategy to bid your true value, and in fact, you could think of the reserved prices just like the third bidder, in this case. And so from many bidders' perspective, you're still want to be bidding your true value if it's a second price auction where you think of this reserved prices that was just affixed in out there. You just happen to know what one of the bids are, it's still the dominant strategy to bid your true value. So that makes our life easy in terms of the analysis. So, if both bids are below R, that's going to happen now with probability R squared, because people are bidding truthfully. So the chance that they're both below R with a uniformed distribution, independent draws of a uniformed distribution, probability that any one of them is below is R. So, the probability the both of them are below is R squared, in that case, the revenue is 0. The chance that one's above, and one below? Well, the chance that one's above is one minus R, the other one's below is R, and it could happen in two different ways, in terms of which bidder is above, and which bidder's below. In that case, the second highest price is the reserve price, that's the revenue. And then, it indicates where they're both above, that's going to happen with probability 1- R squared and in that case, then we're going to get the expected minimum of the two values. Conditional on both of the values being above R and if you just work out the integral of what's the expected minimum of two uniformly distributed random variables, conditional on those variables going between R to 1. So now they fall both within R to 1. Figure out what the expected minimum of that is I'll save you the algebra. It's 1 +2R over 3. Okay, so when we look at these, then we do the overall expected revenue. What do we get? We've got this probability that we're going to get a revenue of R. So multiply those out. We get 2 R squared (1- R) here. And then we've got this probability that both people are above and then we have this expected revenue so we end up with an overall expected revenue of this expression. Because if they're both below, we don't give anything so that's the overall expression as the expected revenue. If we collect terms here, in terms of Rs, you can simplify this, so the expected revenue here is given by this. Expression 1 + 3R squared- 4R cubed over 3. So now we have an expression for revenue. Just maximize that with respect to R. So let's take the derivative with respect to R and set that equal to 0. What do you get? 0 = 2R- 4R squared. Solving that, R = a half. So what does that tell us? If you're facing two bidders in a second price auction, uniform values between zero and one. You set a reserve price of a half, that's going to maximize the expected revenue. Okay, you can do calculations. So supposed let's do our calculation, when we set the reserve price of a half, what do we earn in terms of revenue? Well, you can stick your half in here, do the calculation, you end up with 5/12. If you set a reserve price of 0, then the expected revenue, you get 0 for the R's, you get one-third here. So you end up with a lower, this is just 4/12, right? So we end up with a higher expected revenue when we set reserve price at half. So increasing at reserve price, increases the expected revenue for the seller. The half was nicely chosen. If we set it too high, then you have no chance that you're going to end up with a sale. And then your profits actually go down. So it's hitting this sweet spot in terms of what the reserve price was. So the trade-offs here, you lose sales when both bids were below a half by setting this reserve price, but that was low revenue in any case and it only has a probability of one-quarter of happening. You increase the price when one of the bidder has low and the other one was high and it's actually happen with probability of a half. And so in this case.Increasing the result price lead to high venue because the increase got from here more than the onset the decrease you got by losing sales when both bids happen to be low. Okay, so you can think of adding this reserve prices as if you're adding a third bidder, a sort of increasing the competition in the auction, and even though that players know exactly where that reserve is, it's raising the overall revenue in the second price auction. So this is something that has been looked at more generally and so in terms of the overall design of optimal auctions, what do they look like? Well, there's a concept which is important in defining these and it's what's known as a Bidder's virtual valuation. And if you have a true value of vi, your virtual valuation is vi adjusted. Subtracting of a, you think of sort of shading down your value, what is it shaded down by, what shaded down by something which depends on, how many values were above what you, what's the probability of having values above the value that you're expressing. And then adjusted on the denominator by the relative frequency with what which you have the valuation that you are looking at. Now, exactly understanding the virtual valuation is a fairly difficult task. It's a fairly deep concept and it has to do with keeping track of exactly what the incentive constraints for different values are and how rapidly you're losing or gaining value as you're moving values up. So in terms of how many, what's the relative probability of different types at or above a given level. What we're going to do is assume that this thing is increasing in vi, okay? If it's not increasing in vi then the statements of the theorems we're going to make are going to be more complicated. So this object was assumed to be increasing in vi. If you check out this virtual valuation, in the case of uniform distribution,it turns out to be 2vi- 1, so indeed increasing in vi. And the way in which we'll set reserve prices is to pick the reserve price to be the level of vi at which the virtual valuation would be exactly equal to zero, okay? So if you find a value of vi at which this is exactly equal to zero we'll set, we'll call that the bidder specific reserve price. And in particular if you plug back in the uniform distribution for this, now you're getting 2vi- 1, the value of which that happens is happens to be one half, right? So you would set the reserve price, individual reserve price at half. So Roger Myerson prove to his theorem was characterize optimal auction in 1981. Actually that was part of the work that earned him a noble prize along with revelation principles and some of the other things we've seen. This has been a fairly influential theorem and let's have a look at what it says. It's a bit of a mouthful but if we look at the optimal single good auction in terms of a direct mechanism, what's the structure? The structure is you going to sell the good to the person who has the highest virtual valuation based on what they announced, okay? So look at the different individuals and instead of looking at who has the actual highest direct of it. We're going to use their virtual valuations instead of the direct valuations, okay? So we're going to make adjustments based on these virtual valuations. And we'll so it to that person as long as their value is bigger than their reserve price. If not, then we won't sell it to anybody if this isn't satisfied. If the good is sold, then the winning person is going to be charged this smallest valuation that, that person could have declared and still been winner. So we look at the smallest valuation that has them still being above their reserve price and still being the winner. And think of that as sort of the benchmark of equivalent of either the second highest price or the reserve price, that's going to be the value that they have to pay, okay. So we have an auction where now what we do is we, people put in values, declare the values for the good, but now we adjust them via these virtual valuations and have reserved prices. And choose the person who has the highest virtual valuations subject to that being above the reserve price and charge them the price that they could have gotten in terms of the lowest valuation they could have announced and still win the winner of this auction. Okay, a corollary of this where you can begin to simplify all of this. If we're looking at a symmetric setting where everybody has exactly the same distributions like we did earlier in the two better case and the second price auction case. What do we end up with? It indeed, it turns out that the optimal auction is a second price auction with the reserve price of r star where that reserve price satisfies this equation, and in the case of a uniform distribution, the reserve price is going to be a half. So would actually say that, the optimal auction in the case of the symmetric setting would be set your, if uniform zero one, set your. Reserve price to a half and then have a situation where you do a second price auction above that, okay? So the nice thing about this is it says in symmetric settings, things simplify dramatically and you're running basically second price auctions with reserve prices and the reserve price is going to depend on its distribution. What's really going on now you can understand a little more about what this virtual valuation is doing in terms of adjusting things. It's adjusting things to capture relatively how much of the distribution is at high values compared to lower values. And the reserved price has been pushed up to a point where you want to push it so that you're making sure that you're not going so high that you're going above the bids and not going to sell the item. But you want to move it up high enough to have some competition. And that trade off is being captured by exactly this expression. Okay, so the optimal auction has some features that we would have seen as in a Vickrey-Clarke-Groves mechanism. And what's a little bit different here is that we have two things going on. One is that the actual valuations are being adjusted by these virtual valuation functions. And also it's not looking like a Vickrey-Clarke-Groves mechanism in the sense that the outcome isn't always efficient. Sometimes we do not sell the good in these kinds of auctions. And how should bidders really bid in this? So the good news is that we still have a second-price auction kind of format held in this virtual valuation space. So the transformations mean that it looks slightly different in terms of what the payments are going to be and when somebody ends up winning something, but the proof that a second-price auction is dominant strategy instead of compatible or truthful still works out here. So you still get these nice properties in terms of the incentives of the auction, but it's different in terms of what the specifics are in terms of the payment rule, and we're not always doing efficient things in this world. So here again, we see that trade-off that we've seen before in the Myerson-Satterthwaite theorem. Here, when we're trying in this case, to get incentive compatibility and maximize things for the seller. So the seller's trying to figure out how they can get the most out of this auction, we end up with some inefficient trade. So the seller's going to actually have to commit to doing this, right? So you have to commit to abiding by the reserve price and if everybody's bid comes in afterwards, it's not saying, well, sorry, I didn't really mean that. I'm going to revise my reserve price and drop it down. So this mechanism works if the seller can commit to not selling the object if the bids end up below the reserve price. Okay, why does this work? What's going on here? Well, reserve prices again, are like competitors. They increase the payments of the winning bidders. The virtual valuations, why are they playing a role here in terms of deciding who's a winner? Well, if you have strong asymmetries in this auction, if you didn't do anything, and you were the seller, it could be that the really weak bidder basically isn't really competing with the strong bidder. So by changing things relative to these virtual valuations, that can make weak bidders be more competitive with strong bidders. Now that has a plus and a minus to it. One is that sometimes you end up selling it for a lower price than you would otherwise to the lower bidder. But other times, it actually inflates, it means that the higher bidder has to end up paying a higher price, and it effectively increases the competition there, in some sense makes the bidding more aggressive. Okay, so that's been a quick look at optimal auctions. The proofs of these results are actually quite involved and involve some calculus of variations and some delicate arguments. They are worth looking into, if you really enjoy this stuff, dig in to Myerson's paper and a whole series of ones that have followed up on that. They're interesting papers, and the techniques behind them have become used in other kinds of mechanism design arguments more generally. But what we want to take away from this is a couple of things. One, is that the problems are well defined and they're well defined solutions to solving for mechanisms that satisfy certain properties. The ones we've been more interested in and are probably more interested in from a societal point of view is, how do we maximize overall efficiency, total utilities? But sometimes we're also interested in understanding how sellers might act in a market, or they might want to maximize revenue, not do the efficient thing. How are they going to act? What kinds of mechanisms are they going to choose? And so mechanism design, you can put down whatever objective you want in terms of what you're trying to maximize. Is it overall societal welfare? Is it revenue? It could be some combination. And in those kinds of situations, once you're going to do that, then you put in instead of compatibility constraints, that's actually part of what goes into the proof of Myerson's theorem. Put those things in and maximize subject to those constraints and see what falls out. And that can give you a very general recipe for optimal mechanism design.
