Hi folks. So this is Matt again. And we are now going to talk about Vickrey-Clarke-Groves Mechanisms, or VCG mechanisms. And these have become one of the most well studied set of mechanisms in game theory. And with good reason, they have wonderful properties, some very interesting properties. And let's talk a little bit about the kinds of positive results we'll get now out of these mechanisms before we're going to the detailed definitions and so forth. So, we're going to work in a quasilinear setting, and we're going to work here. Remember now, we'll look at direction mechanisms where you society will have a choice rule and the payment rule based on what preferences people report to the mechanism. And the nice thing about VCG mechanisms, Vickrey-Clarke-Groves mechanisms, is that they will have truth as a dominant strategy. So people won't have to worry about other individuals are doing regardless of what their preferences are, the best thing they can do in terms of maximizing their utility is to tell the truth. And, this mechanism is also going to choose efficient x's. So choices here mean when we choose, when we think about which x in X maximizes the overall total sum of utilities in a society, it's going to pick those. So, it might not be efficient in terms of making all the payments balance. But it's going to make efficient choices, okay. Now, these mechanisms in terms of the history of this, Vickrey was the first to define these in an auction settings. So this is going to have a close relationship to second price auctions and basically, generalizes second price auctions to a more general class of auctions known as Vickrey auctions in the auction setting. Clarke then generalize that to a more general class of settings and define what was known as the pivotal mechanism which is a special class of these mechanisms. And then Groves gave basically the class of all such mechanisms and there are some nice properties of a more general class of these. And so we'll look at these in more detail. The nice thing is we're going to have dominant strategies and efficient choices, and the quasilinearity is going to be critical here in making sure everything works. And so we're looking at private values, so conditional utility independence in general, and we'll be looking at settings where we have quasilinearity is going to make things go for us, okay. Under you know, some particular settings will be able to get additional things like a weak budget balance condition, interim individual rationality, other kinds of nice things coming out but basically, the key ingredients here are going to be dominant strategies and efficiencies. Okay, so let's start with the general class of these mechanisms which are known as Groves mechanisms after Ted Groves. And so we're looking at direct mechanisms so this is going to be making a choice out of whatever our x set is. And then the ps are going to be, the p is going to be in our n again. So it's telling a payment for each of the individuals. And the interesting thing about a Groves mechanism is a Groves mechanism's going to be any mechanism of the following sort. Look at the announced utility functions. Each person is telling us now what's their evaluation function. That's their private information, so we get these announcements. So people are telling us v hat 1 through v hat n which are telling us how do they value the different x alternatives. So, society first of all is going to make a choice which maximizes the total sum of those. If that's unique, then that ties this thing down exactly. Sometimes there could be ties. It's going to always pick something which is best for society in terms of overall maximization. Then the key thing here is going to be the payment rule. And what's the payment rule going to look like? The payment rule for a given individual is going to be something which is going to depend on some function of what the other individuals announced. So minus i meaning the vector of utility functions announced by the other individuals other than i. And, it's also going to have a part here. We'll subtract off the sum of the announced valuation functions evaluated at the chosen alternative by society. Okay, so society makes a choice, we look at how much does everyone else, in terms of utility for that. We can add in some other thing that doesn't depend on a given individual. So sometimes it's going to be useful to add in other things, and we'll talk about that in a moment. Anything which has this structure to it is known as a Groves mechanism. Okay, so this is a particular class of mechanisms. Sometimes these are referred to as VCG mechanisms. That name has more recently been used to look at a situation with a very specific payment rule here, and we'll talk about that in a moment. But this is a general class of Groves mechanisms. Okay, so now let's look at Vickrey-Clerke-Groves mechanisms of the special class which is also this go by different names and different literatures on the economics that are sure this was originally known as a pivotal mechanism. In part of the computer science literature and the game theory literature more generally is becoming known Vickery or VCG mechanism. Sometimes VCG is used to look at the broader class but what's specialized here is, if you remember that h function we had. So we had an h function, hi(v hat-i). That function now takes a very specific form. And that specific form, in particular, is one where what we do is pick something which maximizes the sum of everyone else's utility. So what would society choose if i were ignored? And then look at the total sum of utilities that would come out of that. And compare that to what people get when i is taken into account, right? So this is the choice that's made when i is being accounted for. This is the choice that would be made if we ignored i and this pivotal mechanism. What it does in terms of i's payment is say, how much would everyone get if we ignored you? How much does everyone else get if we take you into account? This is generally going to be a lower number, right? This is going to have to be a lower number. People can't be made better off by including i in terms of the decision. That all they can do is distort things away from the overall maximizer for these individuals. So this number is generally going to be a non-negative number. So this will be a payment that different individuals would be making into the society. Okay, so let's have a look at what we end up with here. And so we've got this structure. Something which maximizes overall utility, and that particular payment scheme. And so what you get paid is, everyone's utility under the allocation is actually chosen, except your own. You get that as the direct utility. And then you get charged everybody's utility so when we take off this minus pi, what you're going to be charged is how much everyone else would've gotten in this world where they didn't have to take you into account. Less what they're getting in a world where they do have to take you into account. And so we can think of this as the social cost of an individual i. Right, so this is social cost, Of i. What does that mean? That means having i present imposes some change in utility for the other individuals. Individuals are paying their social cost. Who pays 0 in this world? Well, people who end up not affecting the outcome at all. So, their presence or non presence, their announcement of their utility function didn't affect things over all. So, who pays more than 0? Pivotal agents who make things worse by existing. So there's situations where the fact that they existed actually changed the outcome in a way that made the individuals worse off. Who winds up getting paid? Well people can, in some circumstances under some of these mechanisms gets paid by making things better off for other individuals. Okay, one nice thing about these mechanisms and the beauty of these mechanisms is that truth telling's going to be a dominant strategy under any Groves mechanism, including the pivotal mechanism or these VCG mechanisms. So, when we have this basic form the theorem tells us that truth is the dominant strategy. And let's go through that. So we'll first go through this theorem, and then we'll talk about a converse theorem that says basically, if you want truth to be a dominant strategy in these settings with quasilinear preferences and private values, it's going to have to be a Grove mechanism. So these mechanisms will be dominant strategy. And basically in this setting they be the only dominant strategy mechanisms. That results in efficient x choices. Okay, so let's have a look at this, so let's look at it to try and see why this theorem is true. Let's think of what i's problem is. So what they're getting is they're getting this is their true utility vi. And they're thinking about what they should announce, right? So, i is choosing, what function should I tell the mechanism that I have in terms of like, my utility function. So, that's going to affects the outcome, and it's going to affect the price. And this is the overall utility, so they want to choose the announcement to maximize the utility function. So let's have a look at the Groves mechanism. Substitute in for this and then see what people's incentives are in the world. So under a Groves mechanism your payment were looks like this. So it looks like an hi minus the v hat and then we take the minus of the over all thing and we end up with this. So, and there should be an i here, subscript i. So when we looked at that payment scheme the individual is choosing this to maximize their overall utility. So first of all, notice that this thing does not depend on v hat i, so maximizing that is equivalent to maximizing this when we ignore it. So now we've boiled this problem down to solving this problem. So maximize vi of the chosen alternative as a function of what you announce plus the other people's announced utilities. Now one thing to notice, is this begins to look like you're just trying to maximize the overall sum of utilities where yours is the truthful and then everyone else is what the announced one is. So I would like to choose a declaration which would lead the mechanism to pick an outcome which is going to maximize this overall thing. So what you'd like to do is choose a v head i that will lead the mechanism to make a choice which solves this problem. So if we go back and look at this problem maximizing overall the v head i is equivalent to saying let's try and get the mechanism to choose an x which will maximize this overall if that declaration gets an x that maximizes this. Then it's certainly doing it as well as possible. Now remember under a Groves mechanism, the x of the v hat i is something which maximizes exactly the sum where what you've done is put in your announced utility. If you want to get them to do it with respect to your true utility then the way in which to do this is to have your announced utility be equal to your true utility and then they'll be maximizing exactly the function that you want them to be maximizing and so that means that truth is a dominant strategy. So the Groves mechanism will choose x in a way that solves this maximization problem precisely when v hat is equal to vi. Therefore, truth is a dominant strategy. So this is a deceivingly simple proof, so it takes a while to go back through this, convince yourself it's true, but the basic idea here is that the payment that a given individual has is essentially what everyone else's announced utility function is. And whether those are truthful or not, from their perspective, what they're getting in terms of an outcome is something which then maximizes the overall total sum of utilities. Because what they're doing is maximizing their true utility, plus what other people have told the mechanism their utility functions look like, and by being truthful they get an outcome which maximizes that overall total sum. Which indeed is the best they can do, in terms of maximizing their utility given this payment rule. So the nice thing about these VCG mechanisms, or in general, the Groves mechanism, is they align the individuals' incentives with the society's incentives, by making sure that the payment rule accounts for what their decision choice is what the impact of their announcement is on everyone elses utility. Okay, now the uniqueness of these things in terms of being the converse theorem. There's a theorem by Green and Laffont from the late 1970s or early 80s which then says there's a converse here. So suppose that for any utility function, it's so each individual could have any possible utility function over the public decision or the non monetary decision. So domain is going to be rich in a very particular sense that people could have any possible utility ordering, or utility function over this set of alternatives. Then we'll say that a mechanism that's efficient, so it's choosing a decision as a function of the announced preferences, which maximizes the overall utility. That's going to have truthful recording as a dominant strategy for all agents and preferences only if it's a Groves mechanism. So the payment rule has to look like what we said in terms of Groves mechanism. That's the only way that you can be truthful for all possible announcements of preferences. So, not only are the Groves mechanisms dominant strategy incentive compatible, but if we require efficient outcomes, these are the only ones that work. Okay, so I won't prove this explicitly. The proof is actually fairly straightforward. You can find the version in a survey I wrote on mechanism design on my website. But in terms of summary here so far, what have we got? Groves mechanisms and a special class of those, the pivotal mechanisms or VCG mechanisms, have really nice properties in terms of incentives. Truth is always a dominant strategy. The agent's payment rules, they basically align their incentives with this society in terms of making sure that they're taking into account their impact on other individuals' preferences and utilities and therefore we end up with efficient outcome choices. So that leads people to internalize the externalities and leads to efficient choices over the x's. Now one thing that is also important to emphasize is that it might be that these mechanisms are not overall efficient in the sense that we might have to charge the agents money in order to get this to work. So it could be that the sum of the payments that pi's is greater than 0. So that means that people are making a bunch of payments into the society and we're not giving them all back to the society. So either we have to funnel them off to somebody who's not involved in any of the decision process, or we're going to have to burn that. If we try and give it back, that could change the incentives that we've just aligned so nicely. So the part of the issue about this is we've put these payment rules in, which align incentives very nicely. But in order to do that, we might have to be charging agents a lot in terms of what their impact on the society is. And in order to get things to balance, we might have to give up some nice conditions that we'd want. So nice thing about these mechanisms, dominant strategies and that's why they've been studied so extensively. There's a number of settings where they form nice benchmarks and have really a long list of nice properties. There are other settings where they've serve as a benchmark, and don't satisfy all the conditions we'd want, and that generally has to do with the balance kind of conditions with the payments. And the idea that sometimes people will be charged even if they would rather not participate in the mechanisms, so we might want to think about individual rationality conditions, balance conditions, and other kinds of things. So we'll take a look at these in more detail and context, and that'll be our next thing up.
