Mechanism Design Basics: Auctions & Game Theory

[00:00:01]So, let's go ahead and get started. For those of you who just came in, if you didn't have a chance to sign up Monday, signup sheets are going around. If you did sign up Monday, of course, uh you don't need to sign up again. So, I'm going to go ahead and start with the lecture material. I'll pause uh in a couple places for some course announcements, but I want to get started uh by giving you an introduction to mechanism design. Remember, as discussed on Monday, mechanism design is in some sense the science of rulemaking. And the overarching goal is to design systems which have strategic participants but nevertheless perform well. The sensible place to start a discussion of mechanism design is single item options.

[00:00:55]So, here's the setup. There's a seller and the seller owns one good.

[00:01:07]I bought an iPhone 4S almost 2 years ago. Maybe it's time for me to upgrade.

[00:01:13]Maybe I want to auction off my 4S phone.

[00:01:18]If you like, think about an eBay auction. Those are single item auctions.

[00:01:24]There's some number of players or biders potentially interested in buying the good for sale.

[00:01:32]And we're going to want to make statements about how bidders behave in different auctions depending on the auction rules. So, we need to have a model of bidder behavior. And for that we need to have a model of what biders want. So the first key concept is that of a valuation.

[00:01:53]So each bidder I has a valuation denoted V subi and the valuation is the maximum amount that I would be willing to pay for the good for sale. So maybe for my iPhone 4S, there's some bidder out there and it's willing to to pay up to $90 for my iPhone 4S. Of course, subject to buying it, it wants to get us as cheaply as possible, but it doesn't want it at all if the price is bigger than its valuation. In this example, $90.

[00:02:37]So that's a valuation. How much you're willing to pay for the item. And what's really important and what makes the auction design problem difficult is that this information, the valuation, it is what we call private to bidder. I by private I mean the seller has no idea what it is. In some sense, that's the reason you're running the auction because you don't know what people are willing to pay. And we're also going to assume that the other biders do not know the valuation of bitter eye. In that sense, it's a private valuation.

[00:03:14][Music] So now let me tell you about what a bidder wants formally. So I'm going to introduce a utility model and we're mostly going to stick with the simplest sort of first cut most natural utility model you might use in such a in an auction setting. It's called quasillinear utility. It's not really important you know that term but you might see that in the textbook.

[00:03:55]for example.

[00:04:02]And all it means is that if you're a bidder in this auction and you lose, your utility is zero.

[00:04:16]Your utility of winning, well, it depends. First of all, it depends on your valuation. what is the most you would have been willing to pay for it. Second of all, it depends on the sale price, what you actually had to pay for it. And your utility is just the difference between those two quantities.

[00:04:40]Okay, so that's a definition. Okay, for most of our discussion of mechanism design when we have money i.e. all of the auction discussion we will model participants as acting to maximize their quasillinear utility. We will model them as wanting to maximize this quantity.

[00:05:16]I want to focus today on a very simple type of auction format. Sealed bid auctions.

[00:05:31]These work as follows.

[00:05:36]The first thing that happens is each bidder submits a bid to the seller to the auctioneer.

[00:05:52]Privately in a sealed envelope if you like.

[00:05:57]Now the auctioneer or the auction designer has to make two decisions.

[00:06:01]Okay. First of all, so given the bids, so now you have n bids from the people who are vying for this good. First of all, which of them gets it? Second of all, what do they pay?

[00:06:33]Now for step two, there's a pretty natural choice to make.

[00:06:39]So what do you think? You get these end bids from everybody. You have to pick somebody or if you want nobody that's allowed, but at most one person to win the good. What seems like the obvious thing to do?

[00:06:54]So, the highest bidder, right? Everybody said what they'd be willing to pay. Pick the one who said they'd be willing to pay the most. And we'll see later sometimes there are reasons you actually don't want to do that. But for today, we're only going to focus on auctions that indeed award the good to the highest bidder.

[00:07:28]So all auctions we talk about today will have that property that indeed uh whoever is the highest bidder gets the good.

[00:07:39]Now step three deciding what to charge the winner. Well, again, perhaps one natural thing comes to mind. It's actually there's a bunch of reasonable things you could do in step three. And in fact, the behavior of the biders will be very different depending on the decision on your implementation of step three. Here's a trivial example. What if you want to try to be altruistic? Okay, you say, you know what? I'm not even going to charge the winner anything. You know, I just want to sort of figure out who wants it the most and I'm just going to give it to them. Okay.

[00:08:15]So, who wants to volunteer? So, imagine you were uh actually participating in this auction. So, who wants to volunteer how they might what bid they might submit into this auction?

[00:08:27]Okay. Suppose it had to be a finite number.

[00:08:32]Yeah. So, you'd be tempted to write something like one more than the highest other bit, right?

[00:08:36]Or in general, you'd write down just the highest number you have time to write down in your envelope.

[00:08:41]Okay.

[00:08:43]I'm sorry.

[00:08:45]Something like this. Yeah. Right. So, you want to do your best. So, basically, you name the highest number you can think of. The winner is simply who could name the highest number. Has nothing to do with how much they actually wanted.

[00:08:56]The good has nothing to do with their valuation. So, that choice of step three does nothing to discourage people from over bidding. Okay. So, there's an incentives problem. Okay.

[00:09:07]All right. Right? So that's obviously a bad idea if you want to have the allocation of the good correlate uh with biders valuations.

[00:09:17]So another very natural idea and indeed an idea that uh is reasonably prevalent in practice is the first price auction.

[00:09:30]And the way I sort of told the story so far this is probably the first thing that would come to mind for most of you.

[00:09:35]What do you charge the highest bidder?

[00:09:38]Well, they wrote down what they'd be willing to pay. So, just ask them for it, right? So, just have them pay what they bid.

[00:09:57]And the main thing I want to tell you about, the main thing I want to convince you of today about first price auctions is that they are non-trivial to reason about. Even if you're a single participant in a first-p price auction, it's non-trivial to reason about. And certainly as a designer thinking about a collection of participants in a first-p price auction, it's non-trivial to reason about. So to drive this point home, we're going to do an experiment.

[00:10:20]Okay? And uh this experiment is only for those of you that are officially registered in the class in Axis. And you'll see why in a second. So if you are officially registered, get a slip of paper. If you don't have one, borrow one from a neighbor.

[00:11:00]I'm going to give you an opportunity to earn a little pocket change as you attend 364A.

[00:11:10]So, here's what I want you to write down on your slip of paper. Okay.

[00:11:18]So, first of all, who you are, second of all, your birthday.

[00:11:30]Okay.

[00:11:33]There's going to be five things to write down.

[00:11:36]So, you don't want to lie about your name because then we won't be able to give you your money on Monday. Okay?

[00:11:42]Condition on your name. we can verify your birthday. That's why I want only for the people who are registered for the class. So don't try lying about number two.

[00:11:51]The reason I don't want you to lie about your birthday is because your valuation is going to be a function of your birthday.

[00:11:59]So, I'm going to define your valuation as the twodigit number of your month, your birth month, plus the two-digit number of your day, times 10 cents.

[00:12:17]So for example, the biggest valuation you could have if you were born on the last day of the year, your valuation would be 12 + 31 *.1 or $4.30.

[00:12:31]Okay, if any of you are New Year's Day babies, then your valuation is only 20.

[00:12:36]Okay, now what the fourth and fifth things I want you to write down are bids.

[00:12:44]The way this is going to work is we're going to collect all of your slips and we're going to do two experiments. In the first experiment, we're going to take each registered student and pair them randomly with another registered student. And we're going to run for each of these pairs. Okay? And you'll participate in exactly one pair. For each of these pairs, we'll run a first price auction. Okay? So, there'll be two biders and one thing for sale. The higher of the two bids will win. And the utility, i.e. what you'll get paid next week is your valuation minus what your bid was. Okay, so that's experiment one.

[00:13:17]Experiment two will put you in a group of three randomly and we'll do exactly the same thing. We'll run a first price auction. Only one of the three biders will win and that bidder will again get paid on top of whatever they earned in the first experiment their value minus their bid. If you want, you're welcome to write down the same bid twice. You can bid the same way with two players, with one a competitor as with two competitors. That's fine. Or you could perhaps see a reason to bid differently in the two different experiments. In any case, spend some time thinking about what those two bids should be and write them down on the on the slips. We'll collect them at the end of the class.

[00:13:59]There's only one round to this.

[00:14:03]Excuse me.

[00:14:06]This is 430. So it gets multiplied by 10 cents.

[00:14:10]The biggest your valuation could be is4 $4.30.

[00:14:13]I had to put a budget on this experiment.

[00:14:18]I realize this is only pocket change for a bunch of Stanford engineering students, but you know, I hope that some of the competitive fire nonetheless compels you to think carefully about what to bid.

[00:14:35]Any other questions about uh what the experiment is or what I want from you?

[00:14:59]Yep.

[00:15:00]Question.

[00:15:03]something.

[00:15:04]Can you speak up?

[00:15:06]Can we be nasty and did like some horrible announce?

[00:15:10]How would you do that?

[00:15:13]Does it might not give up?

[00:15:16]Um, do what you will. Other questions?

[00:15:20]Yep.

[00:15:20]Can I register after class?

[00:15:22]I'm sorry.

[00:15:22]Can I register after class? Uh um yeah, if you promise register after class, you can you can do it. Other questions?

[00:15:39]Good question. Good question. Notice notice that if you win an auction at a sale price higher than your valuation, then utility is actually negative. So in the context of this experiment, you owe me money.

[00:15:54]And I do expect you to pay up. And if you don't, you can expect a penalty on the on your point total.

[00:16:00]Really, what I'd encourage you to do strongly is don't bid higher than your valuation.

[00:16:06]But you are free to if you want.

[00:16:08]Yep.

[00:16:12]Would it make more sense to have some sort of invaluation price? would you get some utility from winning at your arguably not arguably there's some price at which you're indifferent between not winning and winning it at that price.

[00:16:29]Y so ties I mean ties will flip a coin.

[00:16:35]So in general in general what we all this stuff we discuss about auctions it won't matter how you break ties for concretess for these experiments we're going to choose randomly amongst those with the highest bid.

[00:16:48]Okay. So, a couple other announcements.

[00:16:52]So, first of all, do keep an eye on the web page. There's been some updates. So, for example, the um you the the video for the first lecture is now up on YouTube. There's a link uh from the website. So, go ahead and check that out. You know, they'll go up whenever they go up, but I'm hoping generally it'll be at most a few days after the lecture. Uh there's also a very rough draft of lecture notes for the first lecture. Those will frankly be a little bit more erratic in the timing that they appear on the web page. So don't count on the lecture notes uh being too prompt. Although the videos I hope will be reasonably prompt. Also posted is the first exercise set. To remind you from Monday, there are two types of homeworks. Exercises and problems.

[00:17:32]Exercises are supposed to be easy.

[00:17:34]They're just supposed to fill in things that I've glossed over in lecture. You might even want to do them quite quickly after the lecture. I think you'll find them straightforward if the lectures themselves uh made sense at the time.

[00:17:45]So, this has already been posted.

[00:17:47]Problem set number one. Problem sets are the ones with open-ended harder problems, which you should do in groups of up to three. One write up per group.

[00:17:54]The problem set is written, but I'm still proofreading it. Uh, so that'll be posted later tonight. That's due in 16 days. So, the exercise set, this is the easy one, do in seven days. The harder one do in 16 days. Question. Um can you repeat the rules for second or first selection for the what?

[00:18:12]Uh the number four.

[00:18:14]So four you are randomly matched with one other student. The one who the one who bids lower has utility zero. The one who bids higher wins and the utility which is what you are paid next week is your value minus the bid that you submitted.

[00:18:28]Yeah.

[00:18:31]So ties will break randomly. Yes. Um, can we collaborate on the exercise sets as well?

[00:18:36]So, see the instructions. I listed specific instructions on the exercise set about collaboration.

[00:18:41]Yep.

[00:18:44]Excuse me.

[00:18:45]When do we have to turn the slips of paper?

[00:18:47]Turns turn in the slips of paper at the end of class to one of the TAs who to remind you are Oka and Kostas in the back.

[00:18:57]Yes. Um, so could we technically all pay zero or the zero pay amount of money?

[00:19:06]Yeah. So, uh, you know. Okay. Would you like to turn them in now? Would that answer the question? We can do that, too.

[00:19:22]Okay. So, the rule is they're due at the end of class. That's all I'm going to say.

[00:19:27]Okay. Other announcements? Yes, there is another announcement. So, because the class is being videotaped, I have to sort of interrupt uh for an announcement from the Stanford legal department.

[00:19:40]Uh, everyone actually has to sign a release.

[00:19:44]What the release says is that either you consent that you your face might show up on a video on YouTube, namely in this class, or if you're not cool with that, then you agree to sit in some part of the room which is off camera. And so there's there's lots of the room which is off camera. Actually, there's almost none of you show up on the on the video.

[00:20:03]And you also agree that you know you'll save questions till uh after class.

[00:20:08]Okay. So those are the those are the two options. So, but I do uh just, you know, they've asked me to have everybody sign one of those release forms um because the class is being videotaped.

[00:20:21]Okay. So, I'm not going to say anything more about first price auctions. There is interesting theory about first price auctions. You will see a glimpse of it on the first problem set. And for those of you that take the sequel course to this in the winter, we'll talk about the theory more about analyzing first price auctions. But the right place to start is with a different auction format also very common in practice called the second price or victory auction.

[00:20:58]How many of you have ever bid in an auction on eBay?

[00:21:03]Good. So let me ask you a question. So, what happens when you win in an auction on eBay? So, for example, maybe I'm bidding on someone else's iPhone 4S and maybe I bid, you know, say $100. Okay?

[00:21:20]And suppose I win.

[00:21:22]Do I necessarily pay $100 for that iPhone?

[00:21:30]No, I don't. Right? So, eBay is not a first price auction. In a first price auction, I would have to pay my bid of $100 every time I won. So why what do I pay instead? If I don't pay what I bid, what do I pay?

[00:21:42]You pay the minimum of your bid and um um one of the minimum price increment over the second, right? So to first order, what you have to pay is you basically pay the minimum amount necessary to beat out all of the competition. Okay? So your closest competition is the second highest bidder. So, if the next highest bidder bid $90 and I bid 100, I'd only have to pay 90. Okay, 91. There's this increment. But the first order, what I pay is not my bid, the highest bid, but just the highest other bid, the second highest bid overall.

[00:22:43]So, what I want to talk about next is exactly this. This second price auction.

[00:22:46]I don't want to talk about exactly the same thing that's run on eBay. I want to talk about a sealed bid auction. There's a problem on the exercise set asking you to compare and contrast the exact eBay auction format with the sealed bid auction format we're going to talk about right now. So to be clear right now we're talking about sealed bid auction.

[00:23:03]Each bidder submits their bid. The winner is the highest bid and the price the winner pays is the second highest bid. That's a second price auction also called the victory auction.

[00:23:14]Now the second price auction in contrast to the first price auction is easy to analyze both in the sense that as a participant it's easy to figure out what you should do and secondly as the designer it is easy to predict what will happen.

[00:23:37]So let's make that precise.

[00:23:46]So, here's the key insight by Victory.

[00:24:02]So, this claim makes precise how each bidder has an obvious optimal strategy in a second price auction.

[00:24:13]By obvious formally we mean a dominant strategy namely to set its bid to be its actual true valuation visa bot. What I mean by this being a dominant strategy, I mean amongst all the bids bidder I could submit, no matter what the other biders are doing, this bid is guaranteed to maximize I's utility.

[00:25:07]The reason this is such a breath of fresh air for the bidder is because this guarantees you do not have to reason about what the other biders are doing.

[00:25:16]You don't care how many other biders there are. You don't care if they're bidding their values or if they're bidding in some complicated way. Doesn't matter. whatever they're doing, you should just bid your true value. It's guaranteed to be optimal. Obviously, that's different than the thought experiment I just made you go through for first price auctions, where of course you don't bid your value. If you bid your value in a first price auction, you are guaranteed zero utility. In a first price auction, you always bid less than your value. The question is by how much. And the answer to by how much depends on what you think other people are bidding. That's the contrast to the second price auction and this guarantee that's independent of how other biders behave.

[00:26:11][Music] So this is one of those great mathematical statements that is both really interesting and really easy to prove.

[00:26:28]So let's talk about why it's true.

[00:26:35]Yep.

[00:26:38]CS 364A.

[00:26:44]Why do you ask?

[00:26:47]messy.

[00:26:57]So proof.

[00:27:00]So pick your favorite player I.

[00:27:03]I don't care which. Their valuation is whatever it is V subi.

[00:27:10]And I also need to fix what the other biders are doing because I'm not supposed to care what the other biders are doing. That can be arbitrary.

[00:27:25]This may be your first exposure to a bit of very common but also rather wonky notation. B minus I refers to the bids of everybody other than I. So this is just a vector with the i component deleted. Okay, so that means what everybody else did. So what do we have to show? We have to show that no matter what I is, no matter what VI is, and no matter what V minus I is, we need to show that I's utility is maximized by bidding V subi.

[00:28:06]Okay, so just to be clear, the valuation of a bidder is not something that it chooses, right? You in some sense are born with your valuation. That's what you that's how badly you want this object. The bid is what you get to choose. So what this is saying is you may as well set your bid to your valuation. That maximizes your utility. Yeah.

[00:28:27]It's the bids of all players except for that of buy.

[00:28:38]So, we're just going to compare to the highest other bid. So, I'm going to call that capital B.

[00:28:46]So, B is the largest bid by one of I's competitors.

[00:28:50]Okay.

[00:28:54]Now, here's what's special about a second price auction.

[00:28:59]What's special is that even though there's a zillion different bids that I could submit, only two different things could happen.

[00:29:22]So utility can only be one of two things.

[00:29:28]In one case it bids less than capital B. What is its utility in that case?

[00:29:37]Zero. It loses.

[00:29:42]Or what if it bids at least the highest other bit? Let's say strictly greater than the highest other bid.

[00:29:52]What's its utility?

[00:29:58]Yeah. So it's it's value for winning. So then it wins, right? Then it's the highest bid.

[00:30:04]So it's its value minus the price that it pays. Because it's a second price auction. The second highest bid, assuming BI is the highest. The second highest bid is capital B.

[00:30:18]Okay.

[00:30:20]And this is just already totally not true for a first price auction. Okay.

[00:30:25]What would I have to write here in a first price auction? I'd have to write something different. What would it be?

[00:30:33]VI minus BI. Okay, because the price would not is not the second highest bid capital B, but rather I's bid itself, B subi. So, it's utility in that case would be VI minus BI. Okay, so that's really nice. There's only two different things that could happen.

[00:30:50]All right, so that's just sort of an observation. Remember what we need to show? We need to show eyes utility is always maximized by bidding truthfully.

[00:30:58]So there's just two cases.

[00:31:02]There's the case where the amount I would be willing to pay V subi is at least capital B is at least the highest of the bid and the case where it's not.

[00:31:14]So first suppose that uh the maximum that I is willing to pay is less than capital B.

[00:31:26]What is the best case utility for I in these two cases then it can't do better than zero. Right? If VI is less than B this is a negative that's a zero. Okay.

[00:31:40]So in this case, max possible utility over all bids it could submit is equal to zero. And in particular, if it does bid its true value, it will lose and it will have utility zero.

[00:32:00]Okay, so it is an optimal thing to do in this case. Let's check the other case when VI is at least capital V.

[00:32:11]So now what's the max possible utility that I could ever get?

[00:32:17]So if VI is at least B then this quantity is the better of the two. Okay.

[00:32:22]So this is the best utility that could achieve and again it does achieve that utility when it bids truthfully when it sets BI to be VI.

[00:32:50]Okay. And so since the bid are I, its valuation V subi and the bids B minus I well are arbitrary. This concludes the proof. Doesn't matter which player you are. Doesn't matter what your valuation is. Doesn't matter what the other players are doing. Bid your value.

[00:33:03]You're guaranteed to maximize your utility.

[00:33:10]And again, clearly not true for say a first price auction.

[00:33:21]So that's the sense in which second price auctions are unusually easy to participate in. Let me just point out another very easy property to see which is you will also never regret participating in a second price auction at least if you do the obvious thing and bid truthfully.

[00:33:43]So I claim that in a second price auction every I'm going to call it a truthtelling bidder. That just means you set your bid equal to your value as in this dominant strategy.

[00:34:03]Every truthtelling bidder gets non- negative utility.

[00:34:11]Obviously, it might be zero. In particular, if you lose, it's going to be zero, but it's never going to be negative if you bid your true value. Do you see why that's true?

[00:34:22]and want to suggest a sort of simple proof of that property.

[00:34:29]So, who's at risk? Who's the only possible bidder that could have negative utility?

[00:34:34]The winner, right? Everybody else is zero. What does the winner pay?

[00:34:40]Second highest bid by definition, right?

[00:34:43]And by because it was the winner, it was the highest bid. And because it's telling the truth, its bid equals its value. So it pays something less than its value or at most its value. So that means its utility is non- negative.

[00:34:55]Okay.

[00:34:57]So proof it's simply because the selling price is no more than the winner's bid.

[00:35:11]Okay.

[00:35:15]All right. So that is the second price or victory auction and probably its most important properties. So in both the exercise set and the problem set that are going out today, I'm going to ask you to sort of explore around the victory auction and this theorem a bit so you can prove something a little bit stronger. So while it's not the case that the uh bidding the true value is always in every situation the unique best bid you can prove it's unique in the following sense. If you submit any bid other than the true value your true value there will be scenarios where it comes back to haunt you. Okay there will be scenarios where utility your utility is not as high as it would have been if you had bid your true value. So in that sense uh bidding your true value is the natural dominant strategy uh in a victory auction. I'll also ask you to consider an extension where you have not one item but multiple items and so on.

[00:36:11]Okay, good.

[00:36:23]So what if we take a step back we've proved the following theorem or sort of a meta theorem which is that the victory auction is awesome.

[00:36:49]by which I mean it achieves simultaneously a number of quite different but all quite desirable properties. The one I've focused on so far are the incentive properties. The fact that bidding truthfully is a dominant strategy.

[00:37:05]It also as we'll see has a performance guarantee. It in some sense solves the optimization problem that we would have wanted to solve a priori in giving the good to the bidder who wants it the most. And thirdly, it is obviously to this audience a computationally efficient auction. There's no obstacle to running this in practice.

[00:37:27]Let me just write that down. So by awesome I mean three properties good incentive properties and there's a more formal term for this dominant strategy incentive compatible.

[00:37:50]or dick.

[00:37:54]What does this mean formally? Formally, this just means what we just proved in claim one and claim two. Okay, that's what that's what dominant strategy and compatible means. It means bidding your true value is a dominant strategy. And if you bid your true value, then you're guaranteed non- negative utility.

[00:38:15]What are the performance guarantees? So, okay, two things. First of all, this is really strong. This is great. All right.

[00:38:21]So, we want to reason about what happens in systems with strategic participants.

[00:38:26]Any such theory has to make behavioral assumptions about how biders behave. The weaker the bidder, the weaker the behavioral assumptions we impose, the more plausible is the prediction. our theoretical prediction for what happens in that system. When you have an auction like this which is dominant strategy incentive compatible the only thing we have to assume and it's still an assumption okay but it's a relatively weak assumption is that when a bidder has sort of a natural obvious dominant strategy then they will play that strategy okay so when you have a dich auction that is the background behavioral model that you're assuming okay and that's about as weak as it gets so we're very happy when we have this kind of incentive properties now of course this isn't enough by its own Right. Right. You could have an auction that simply always held the item and never g gave it to anybody. Okay.

[00:39:17]Strictly speaking, that would satisfy this property. Wouldn't be very interesting. So, the second part of the story about why this is an awesome auction is that it maximizes the social surplus, meaning it awards the good to the bidder who has the highest value.

[00:39:37]So formally if biders bid truthfully and by property one we have a reasonable conviction that they should bid truthfully.

[00:39:58]Then the auction maximizes what I'm going to call the social surplus [Applause] which by definition is just the sum of the values of the winners. Okay. Now in a single item auction there can only be one winner. So it's just the value of the winner.

[00:40:27]Vi or no I mean vi the valuation.

[00:40:34]Okay. So what I mean is the sum over the biders of VIXI where XI is just an indicator of whether I won or lost the auction.

[00:40:47][Applause] Okay.

[00:40:56]So this is the claim. The victory auction maximizes this sum where the meaning of x i is just one as a winner and zero if it's a loser. Now I've written it in sort of a more general notation that I need to just to move forward. But remember by there's only one copy of an item. So xi is one for one person and zero for the rest. So this is just the value of the winner. So what I'm claiming here is that the highest valuation bidder wins in the victory auction assuming that all of the biders report their true valuations.

[00:41:25]Why is that true? Well, by definition, the victory auction selects as the winner the highest bidder. If everyone's bids equals their valuations, then the winner is the bidder with the highest valuation. Okay? So, that's all I'm saying right here. Okay? But this is also really cool, right? Because remember these VI were private what people were willing to pay. We had no idea what they were in the first place.

[00:41:50]That's why we were running the auction because we didn't know what this was worth to people.

[00:41:54]If we had known, maybe our objective, one reasonable objective would be to make sure the item goes to the person who wants it the most. We just didn't know who know who that was up front. And this simple victory auction protocol despite all this information being private or priority. At the end of the day, it solves that optimization problem as well as if the data was public, as if we did know it up front. Okay, so that's a very nice guarantee. Okay, this optimization problem, we might have wanted to solve our priority. We didn't even know the data. We didn't know the VIS and at the end of the day we get the solution the optimal solution surplus maximizing solution.

[00:42:30]Yeah.

[00:42:36]It depends. We will talk about revenue maximization as well.

[00:42:42]The question was in some surely in some context you care about revenue. The answer is yes. Sometimes you do.

[00:42:49]Sometimes you actually do care about surplus if you're in a highly competitive environment or for many government auctions. This is more the first order objective. Uh but we will cover revenue maximization uh in a couple weeks as well.

[00:43:07]So those are the two really key properties. We simultaneously get these super strong incentive properties, dominance strategy, incentive compatibility, and this great performance guarantee that we get optimal social surplus. And we also don't have to work that hard to do it right. All we have to do is identify the highest bid. So it's a linear time auction if you like. Okay.

[00:43:37]And as far as where we're going next, sort of the overarching question will be, you know, can we have analogously awesome auctions for other and more complex situations than just social surplus and single item auctions?

[00:43:58]Sometimes the answer will be yes, sometimes the answer will be no.

[00:44:15]So what is the motivation for trying to generalize this? Well, we already mentioned we'd certainly also like to understand revenue maximization.

[00:44:23]That is certainly sometimes the chief objective for people who are running auctions and we will discuss it. The other thing is sometimes just the goods we're trying to auction off, we don't just have one. is a lot more complicated. Okay, so we'll actually get into such an application next when I start talking about sponsored searchs auctions.

[00:44:47]Another case study we'll do in a couple weeks is when we talk about wireless spectrum. Okay, and it's it's lots of different goods and they're not necessarily all identical. So, it's much more complicated to figure out how to allocate them to a bunch of biders. And the question is as we go to these more complicated but extremely important applications, can we have these three properties simultaneously or not?

[00:45:10]Okay, let me pause for questions. Coming up next is sort of a brief case study of sponsored search options. So there's a natural time to take questions.

[00:45:21]Yeah.

[00:45:24]Why is it closing?

[00:45:26]It's just a def. It's just a name.

[00:45:29]So that's just what it's called.

[00:45:31]Yeah. So quasi linear utility just means you want to maximize the value for what you get minus the price for what you have to pay for it. It's just a definition. Other questions?

[00:45:41]Yeah.

[00:45:52]This is for the experiment.

[00:45:53]Yes.

[00:45:54]Let's save this experiment questions for afterwards. Other questions?

[00:46:03]Yeah.

[00:46:06]Excellent point. So the question was what's up with collusion in the victory auction? So what if biders don't behave unilaterally but rather form groups. So that in fact is one of the questions on problem set number one asking you to explore uh in what ways the victory auction is vulnerable to collusion.

[00:46:24]designing collusion resistant auctions turns out to be a quite tough problem and the the theory I would say is not very advanced and there's a lot of actually impossibility results. So in practice if you look at how people handle collusion it's usually more through legal means. So rather than try to design an auction which is intrinsically robust to collusion because very few such auction formats exist. You actually just kind of go outside the model to make sure that it's very difficult for anything more than very small collusion uh coalitions to form. Yeah, good question.

[00:46:56]Any other questions?

[00:47:01]All right, cool.

[00:47:03]All right, so so you know, so why should you know why isn't this victory auction enough, right? So, so is the rest of this just going to be theory for theory sake? How general can we make it? Well, absolutely not. Okay, so the next application I give you about a more complex auction format I mean has just been a jaw-dropping draw jaw-droppingly large fraction of the internet economy. Okay, so let's talk about sponsored search auctions.

[00:47:48]So, for example, around 2006, these auctions were responsible for roughly 98% of Google's revenue. Okay?

[00:47:57]So, now they have lots of different advertising streams, but we're still talking tens of billions of dollars a year generated through the auctions I'm about to tell you about.

[00:48:09]So, what are these?

[00:48:13]Well, to tell you something, I'm sure you already know.

[00:48:20]When you go search on some query in a search engine, what comes back? Two sets of results.

[00:48:32]Okay, the format can look a little bit more complicated than this sometimes, but uh let's just say there's two lists of links that come back when you search for say camera. So, first there are so-called organic search results.

[00:48:53]So these are uh URLs that the search algorithm has deemed by some algorithm like page rank or variant to be deemed relevant to your query.

[00:49:06]And initially in the early days of the search engines, this is all there was.

[00:49:09]All there was was the organic search results. And then sort of early 21st century people realized it could be a very good idea to also allow people to pay to have links to say their own landing page shown along with the organic search results on the search results page.

[00:49:27]So these are the sponsored links.

[00:49:33]So this is advertisers submitting bids to the search engine for in in effect purchasing this real estate on this search results page. Okay. Every time you search for a query on a search engine in real time, one of these sponsored search auctions is run. Okay.

[00:49:52]So we're talking probably millions if not billions of these being run every single day. in the background, you know, there's some interface by which as an advertiser, really anybody can bid on these keywords. Okay? So, the system just stores which advertisers have bid on which keywords. When a keyword gets searched on, that pool of advertisers get entered into an auction automatically and it is somehow, as I'll describe, uh, decided upon which advertisers get shown on the page and in which order and what they're going to pay. Okay.

[00:50:26]Heat. Heat.

[00:50:33][Music] [Music] This is no longer a single item auction.

[00:51:03]Why not?

[00:51:08]There's not only one slot for sale, right? If I was only going to have one slot, one advertiser shown on this page, it would be a single item auction. Okay?

[00:51:17]But as you recall in general you have many sponsored links. Okay. So it's not immediately a single item auction. We can't immediately use a second price auction. Okay.

[00:51:31]Moreover, not only are there multiple goods, but they're not interchangeable.

[00:51:36]They're not all the same. Why not?

[00:51:43]Feel free to just shout it out.

[00:51:45]First spot is better.

[00:51:48]Different pieces of real estate are more valuable than others. Okay? And in fact, as most people track from top to bottom, the higher the slot that you're awarded, the happier you are, the more likely you are to get what's called the click-through, the person actually clicking on your link. Okay? So, there's multiple goods and they are not all the same. So, those are two senses in which this is more complex than the single item auctions discussed so far.

[00:52:18]So these are often called slots in this context. So the goods are the K slots on the results page.

[00:52:29]You know different keywords vary dramatically as far as how many people care about them. But you know for some concrete numbers you might think about there being eight slots. So K equals to 8 and there could be you know say 100 biders n equals to 100 vying for those eight slots. Yeah.

[00:52:45]And we're just assuming right now that our universe has like one keyword that turns.

[00:52:49]So this is the format. I mean so every time that uh you know so an auction of the format I'm going to describe is run every time something is searched on. So there is a universal auction format no matter what is searched on. Okay. There are parameters get that get tuned that depend on the search word like what's the reserve price etc etc etc but there is this uh searchindependent auction format and that's what I'm describing now okay so those are the goods who are the biders these are the advertisers who have bid on the query on the current query.

[00:53:41]Okay, so the set of biders, who these biders are of course depends on what the query is, right? If I search for uh you know, station wagon, it's going to be one set of biders, the biders that care about that search query. If I search for camera, it'll be a totally different set of biders who have bid on that particular keyword. Okay?

[00:53:59]All right.

[00:54:01]And as we said, these are not identical goods and generally speaking, higher on the page is better.

[00:54:15]Okay.

[00:54:26]So, we're going to have a pretty simplistic model of how this goes on, but this actually been a very influential simplistic model. It really has guided a lot of how these search options have evolved over the past now almost 10 years.

[00:54:41]So, a keynote so okay so we need to explain or quantify the extent the way in which one of these slots is better than another. So that's done using parameters called click-through rates.

[00:54:54]So, alpha J is going to be the notation for the probability that whoever typed in this search the search query, it's the probability that they're going to click on the link in the J slot.

[00:55:24]Okay. So, this is called a click-through rate.

[00:55:29]If you like, it's the fraction of impressions, the fraction of the number of times that your ad is shown that it actually results in a click-through to your landing page or CTR.

[00:55:52]Obviously, a higher alpha means a better slot, a more desirable slot.

[00:55:57]Here are the assumptions I will make about the click-through rates.

[00:56:10]As we've already said, higher is better.

[00:56:12]Okay, so slot one is the topmost. That's also going to be the highest CTR.

[00:56:20]So the alphas only get smaller as you go from top to bottom. Okay? And that's a pretty uncontroversial assumption. It's not perfect, but uh it's really quite reasonable.

[00:56:30]Let me now give you an assumption which is unreasonable, but it's actually very easy to extend everything I'm going to say to a much more reasonable version, and that'll be on uh the second exercise set.

[00:56:42]So, the unreasonable assumption will be that the click-through rate of slot J doesn't depend on which advertiser you put there. Okay.

[00:57:02]So if you had a bunch of companies that were basically interchangeable, this would be a reasonable assumption. If you had, you know, two companies with very different reputations, then you'd expect the click-through rate to also depend on the reputation of the company that you put there. Okay? But it's easy to introduce a second set of parameters that are specific to the advertisers so that the click-through rate is just the product of those two parameters and everything that we'll say will continue to extend. Okay. So this unreasonable assumption is for convenience only.

[00:57:36]The third assumption is that what an advertiser cares on cares about is not one of these slots per se. Okay, really what an advertiser cares about is a clickth through. Okay, we're going to use that as our unit of measurement for what advertisers care about. Okay, it cares about clicks. So have a valuation, a private one like before, V subby, which is what it would be willing to pay for every click to its landing page.

[00:58:21]So as a consequence, so if you have an advertiser I with this perclick valuation V subi and you put it in slot J, what value does it derive from slot J?

[00:58:35]the product. Okay, it's value per click V subi times the fraction the probability it expects to get a click alpha subj. Okay.

[00:58:56]All right. So that's the model. Those are the assumptions.

[00:59:02]Any questions about that?

[00:59:16]So now we're going to ask the same question we did with a single item auction. Single item auction, we had maybe like 10 biders who wanted this one iPhone. We had to figure out who wins and what do they pay. Now we've got maybe a hundred advertisers vying for these eight slots of varying qualities.

[00:59:30]We have to figure out which eight of the 100 do we choose, what order do we put them in the slots, and what price should each of them have to pay. And the question is, can we have an auction as awesome as the victory auction for this more complex setting?

[00:59:54][Applause] So what does that mean?

[01:00:05]So first, if possible, it would be great if it was a dominant strategy instead of compatible auction.

[01:00:12]Again, what does that mean? That means reporting your true value per click is a dominant strategy. And secondly, if you report your true value, you're guaranteed non- negative utility. Why do we want that property if possible? First of all, as a participant, it's easy to play. You have an obvious strategy.

[01:00:29]Secondly, as the manager of this system, you have a much you have a pretty strong prediction about what's going to happen.

[01:00:36]You expect people to bid their do to do their dominant strategies. You expect truthful bids. You can reason about the behavior of your system.

[01:00:44][Music] But the other thing the victory auction did is it solved an allocation problem optimally. It gave the item to the person who wanted it. at the most. So we again like that property a performance guarantee saying that after the fact even though we didn't know valuations up front we have an allocation which is just as good as if we did know the valuations up front.

[01:01:19]So, so for now we're going to again want to maximize social surplus.

[01:01:25]I'm again going to write it as a sum over the bids I equ= 1 to N of the VI * XI. XI semantics are now different. In a victory auction, Xi was just one or zero whether you won or lost. Now Xi is the fraction of a click that you get in your slot. Okay? So if this bidder I winds up in the first slot, it gets alpha 1 of a click. So X I would be equal to alpha 1.

[01:01:48]If it's if it winds up in the second slot, it's X I would be equal to alpha 2 because that's how much stuff it gets.

[01:01:52]It's what fraction of a click it gets in this particular allocation.

[01:01:58]So where XI is the CTR of the slot I gets assigned.

[01:02:12]Now, of course, in this example with 100 biders and eight slots, 92 people get no slot at all and their XI of course is zero.

[01:02:28]Okay.

[01:02:30]And of course, when I say maximize social surplus, maximizes quantity, I mean subject to feasibility. Okay. So, you can't put more than one bidder in the same slot. So subject to at most one person in the top slot, one person in the second slot and so forth. And then the third one you'll recall is you know we want these auctions to run in real time. So you know certainly they should be poly time you know ideally even something like linear time.

[01:02:55]Yeah.

[01:02:59]Uh it doesn't matter. So it's it's going to be scale and variant the option I discuss. So if you like scale them so they sum to one. Okay. But it's not it turns out to not be important.

[01:03:10]Okay.

[01:03:13]So that's the model and the question is is there or is there not an auction with all three of these properties?

[01:03:20]So are we saying that no bidder gets more than one slot?

[01:03:25]Uh good question. We will also disallow a bidder from getting more than one slot. Okay. In principle, you know, you could imagine writing the code to put them in more than one slot, but that's thought to be a a waste of resources.

[01:03:39]So, better to better to give the second slot to somebody else to maximize the chance that somebody gets clicked on.

[01:03:44]Yeah. Other questions?

[01:03:51]Almost. Okay. All right. So, you know, a little truth in advertising. It will not be the case that we can always get all three of these properties. All right?

[01:04:03]There's not going to be some universal mechanism which is always awesome. But for sponsored search auctions, there is an auction with all three properties.

[01:04:12]Okay.

[01:04:14]So, I want to tell you a little bit about that auction today and then we'll uh finish the discussion on Monday.

[01:04:28][Music] So, the reason mechanism design problems are hard or at least seem hard if you don't have the right toolbox is because you really have two coupled decisions you have to make. Right? Even just for these simple sealed bid auctions, you have to decide who wins. You have to decide what the winners are going to pay. And whether or not players have an incentive to game the system depends not on really just either one individually, but rather on are they coupled in the correct way. Okay. So for example in a first price auction or even with sort of no payments at all in some sense we were picking the right winner okay awarding to the highest bidder there is a way using the second price to incentivize players correctly okay so that so that you get a dominant strategy implementation but if you get the payment wrong so even if you get the winner selection correct if you get the prices wrong the incentives can go haywire okay so we really have these two joint design problems who wins and what do they Okay. So, an approach that we're going to be able to get away with for this problem and some others which we'll make precise next week is we're going to be able to do mechanism design by factoring these two design problems apart and solving it one at a time.

[01:06:05]We're going to first figure out who the winners are. And then given that decision, we're going to be able to always successfully define selling prices so that we get the desired incentive property, so that we get a dominant strategy implementation.

[01:06:23]So the approach we're going to use so let me just uh for reference let me remind you what are the three properties we want dominant strategy and center compatible max social surplus and poly All right.

[01:08:35]Step one, how do we set prices so that one holds?

[01:08:51]So we first satisfy these two properties conditioned on somehow later taking on fate satisfying one and then we actually pay the piper we define payments so we get these set properties.

[01:09:05]So all I have time to tell you about today with sponsored search options is step one.

[01:09:11]So I'm going to tell you how if we were so lucky to have truthful bids I'm going to tell you how advertisers should get assigned to the slots. It's not working.

[01:09:20]Monday I'm going to discuss step two quite generally. How you render algorithms dominant strategy set compatible by charging suitable payments. That is Monday we will look at vast generalizations of bicker second price rule including to the slot allocation algorithm we're going to define right now.

[01:09:52]So, who has a guess?

[01:09:56]Number one, suppose we had clairvoyance and actually knew the true private valuation per click of these 100 advertisements.

[01:10:07]And I've got these eight slots of varying quality to assign to them. And I want to maximize the social who should get which in order gets the best.

[01:10:25]Yeah.

[01:10:27]Great. So the person who wants clicks the most should get the most clicks. You should put them in the first slot. Okay.

[01:10:33]The next best person who wants clicks almost as badly gets the second slot and so on.

[01:10:41]So in other words, the obvious reality assign the J minus B to the J slot.

[01:11:03]Okay, obviously polinomial time all you have to do is sort It's easy to prove it's maximizes the surplus. That's the last exercise in exercise set number one.

[01:11:15]It's an easy exchange.

[01:11:31]So that's the first step. If we had clear variance voyance and new people's true valuations, we'd know what to do.

[01:11:40]Just like in the victory auction, if we knew people's private valuations, we just knew we should give it to the highest valuation. The magic in the victory auction is assigning payments so people actually do give you the true valuations. Is there a way to assign payments in a sponsored search option so that people actually are incentivized to give you the true valuations per click?

[01:11:59]We'll find out.